Threshold-based preprocessing for approximating the weighted dense k-subgraph problem

Based on an application in forestry, we study the dense k  -subgraph problem: Given a parameter k∈N$k\in \mathbb{N}$ and an undirected weighted graph G, the task is to find a subgraph of G with k vertices such that the sum of the weights of the induced edges is maximized. The problem is well-known to be NP-hard and difficult to approximate if the underlying graph does not satisfy the triangle inequality.     

Approximation of RNA multiple structural alignment

In the context of non-coding RNA (ncRNA) multiple structural alignment, Davydov and Batzoglou (2006) introduced in [7] the problem of finding the largest nested linear graph that occurs in a set G of linear graphs, the so-called Max-NLS problem. This problem generalizes both the longest common subsequence problem and the maximum common homeomorphic subtree problem for rooted ordered trees.In the present paper, we give a fast algorithm for finding the largest nested linear subgraph of a linear graph and a polynomial-time algorithm for a fixed number (k) of linear graphs. Also, we strongly strengthen the result of Davydov and Batzoglou (2006) [7] by proving that the problem is NP-complete even if G is composed of nested linear graphs of height at most 2, thereby precisely defining the borderline between tractable and intractable instances of the problem. Of particular importance, we improve the result of Davydov and Batzoglou (2006) [7] by showing that the Max-NLS problem is approximable within ratio in O(kn²) running time, where mopt is the size of an optimal solution. We also present O(1)-approximation of Max-NLS problem running in O(kn) time for restricted linear graphs. In particular, for ncRNA derived linear graphs, a -approximation is presented.     

Computing the bipartite edge frustration of fullerene graphs

Bipartite edge frustration of a graph is defined as the smallest number of edges that have to be deleted from the graph to obtain a bipartite spanning subgraph. We show that for fullerene graphs this quantity can be computed in polynomial time and obtain explicit formulas for the icosahedral fullerenes. We also report some computational results and discuss a potential application of this invariant in the context of fullerene stability.     

关于图Kn-H2n+i(i=1,2)的升分解

Ｙｏｕｓｅｆ．Ａｌａｖｉ等人在文献［１］中定义了一种新分解（Ａｓｃｅｎｄｉｎｇ Ｓｕｂｇｒａｐｈ Ｄｅｃｏｍｐｏｓｉ－ ｔｉｏｎ），即“升分解”，并且猜想：任意有正整数条边的图都可以升分解．本文证明了下面两个结 论： １．Ｋ_n-H_2n+1可以升分解，其中Ｈ_2n+1为含有２ｎ＋１条边的Ｋ_n的子图； ２．Ｋ_n-H_2n+2可以升分解，其中Ｈ_2n+2为含有２ｎ＋     

QSAR models based on isomorphic and nonisomorphic data fusion for predicting the blood brain barrier permeability

A QSAR model for predicting the blood brain barrier permeability (BBBP) in a large and heterogeneous variety of compounds (136 compounds) has been developed using approximate similarity (AS) matrices as predictors and PLS as multivariate regression technique. AS values fuse information of both the isomorphic similarity and nonisomorphic dissimilarity with the purpose of achieving an accurate predictive space. In addition to the fact of applying AS values to heterogeneous data sets, a new concept on graph isomorphism based on the extended maximum common subgraph (EMCS) is defined for the building of AS spaces considering the atoms and bonds, which are bridges between the isomorphic and nonisomorphic substructures. This new isomorphism detection has as objective to take into account the position and nature of the nucleus substituents, thus allowing the development of accurate models for large and diverse sets of compounds. After an outliers study, the training and test stages were made and the results obtained using several AS approaches were compared. Several validation processes were carried out by means of employing several test sets, and high predictive ability was obtained for all the cases (Q(2) = 0.81 and standard error in prediction, SEP = 0.29).     

Degree conditions restricted to induced paths for hamiltonicity of claw-heavy graphs

Broersma and Veldman proved that every 2-connected claw-free and P ₆-free graph is hamiltonian. Chen et al. extended this result by proving every 2-connected claw-heavy and P ₆-free graph is hamiltonian. On the other hand, Li et al. constructed a class of 2-connected graphs which are claw-heavy and P ₆-o-heavy but not hamiltonian. In this paper, we further give some Ore-type degree conditions restricting to induced copies of P ₆ of a 2-connected claw-heavy graph that can guarantee the graph to be hamiltonian. This improves some previous related results.     

All good (bad) words consisting of 5 blocks

Generalized Fibonacci cube Q_d(f), introduced by Ilic, Klavzar and Rho, is the graph obtained from the hypercube Q_d by removing all vertices that contain f as factor. A word f is good if Q_d(f) is an isometric subgraph of Q_d for all d ≥ 1, and bad otherwise. A non-extendable sequence of contiguous equal digits in a word μ is called a block of μ. Ilic, Klavzar and Rho shown that all the words consisting of one block are good, and all the words consisting of three blocks are bad. So a natural problem is to study the words consisting of other odd number of blocks. In the present paper,a necessary condition for a word consisting of odd number of blocks being good is given, and all the good(bad) words consisting of 5 blocks is determined.     

Small subgraphs in random graphs and the power of multiple choices

The standard paradigm for online power of two choices problems in random graphs is the Achlioptas process. Here we consider the following natural generalization: Starting with G₀ as the empty graph on n vertices, in every step a set of r edges is drawn uniformly at random from all edges that have not been drawn in previous steps. From these, one edge has to be selected, and the remaining r−1 edges are discarded. Thus after N steps, we have seen rN edges, and selected exactly N out of these to create a graph GN.In a recent paper by Krivelevich, Loh, and Sudakov (2009) [11], the problem of avoiding a copy of some fixed graph F in GN for as long as possible is considered, and a threshold result is derived for some special cases. Moreover, the authors conjecture a general threshold formula for arbitrary graphs F. In this work we disprove this conjecture and give the complete solution of the problem by deriving explicit threshold functions N₀(F,r,n) for arbitrary graphs F and any fixed integer r. That is, we propose an edge selection strategy that a.a.s. (asymptotically almost surely, i.e. with probability 1−o(1) as n→∞) avoids creating a copy of F for as long as N=o(N₀), and prove that any online strategy will a.a.s. create such a copy once N=ω(N₀).     

The complexity of dissociation set problems in graphs

A subset of vertices in a graph is called a dissociation set if it induces a subgraph with a vertex degree of at most 1. The maximum dissociation set problem, i.e., the problem of finding a dissociation set of maximum size in a given graph is known to be NP-hard for bipartite graphs. We show that the maximum dissociation set problem is NP-hard for planar line graphs of planar bipartite graphs. In addition, we describe several polynomially solvable cases for the problem under consideration. One of them deals with the subclass of the so-called chair-free graphs. Furthermore, the related problem of finding a maximal (by inclusion) dissociation set of minimum size in a given graph is studied, and NP-hardness results for this problem, namely for weakly chordal and bipartite graphs, are derived. Finally, we provide inapproximability results for the dissociation set problems mentioned above.