Fast algorithms for identifying maximal common connected sets of interval graphs

Given a family of interval graphs F={G₁=(V,E₁),…,G_k=(V,E_k)} on the same vertices V, a set S⊂V is a maximal common connected set of F if the subgraphs of G_i,1?i?k, induced by S are connected in all G_i and S is maximal for the inclusion order. The maximal general common connected set for interval graphs problem (gen-CCPI) consists in efficiently computing the partition of V in maximal common connected sets of F. This problem has many practical applications, notably in computational biology. Let n=|V| and . For k?2, an algorithm in O((kn+m)logn) time is presented in Habib et al. [Maximal common connected sets of interval graphs, in: Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 3109, Springer, Berlin, 2004, pp. 359-372]. In this paper, we improve this bound to O(knlogn+m). Moreover, if the interval graphs are given as k sets of n intervals, which is often the case in bioinformatics, we present a simple time algorithm.     

Polar graphs and maximal independent sets

We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1,2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1,1)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (α,β)-polar graphs and study the computational complexity of the problems on polar graphs of special types.     

Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

We give two new linear-time algorithms, one for recognizing proper circular-arc graphs and the other for recognizing unit circular-arc graphs. Both algorithms provide either a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time. No other previous algorithm for each of these two graph classes provides a certificate for its result.     

Counting the number of independent sets in chordal graphs

We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.     

Obstructions to chordal circular-arc graphs of small independence number

A blocking quadruple (BQ) is a quadruple of vertices of a graph such that any two vertices of the quadruple either miss (have no neighbours on) some path connecting the remaining two vertices of the quadruple, or are connected by some path missed by the remaining two vertices. This is akin to the notion of asteroidal triple used in the classical characterization of interval graphs by Lekkerkerker and Boland [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.].In this note, we first observe that blocking quadruples are obstructions for circular-arc graphs. We then focus on chordal graphs, and study the relationship between the structure of chordal graphs and the presence/absence of blocking quadruples.Our contribution is two-fold. Firstly, we provide a forbidden induced subgraph characterization of chordal graphs without blocking quadruples. In particular, we observe that all the forbidden subgraphs are variants of the subgraphs forbidden for interval graphs [Klee, V., What are the intersection graphs of arcs in a circle?, American Mathematical Monthly 76 (1976), pp. 810–813.]. Secondly, we show that the absence of blocking quadruples is sufficient to guarantee that a chordal graph with no independent set of size five is a circular-arc graph. In our proof we use a novel geometric approach, constructing a circular-arc representation by traversing around a carefully chosen clique tree.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

A relationship between triangulated graphs,comparability graphs,proper interval graphs,proper circular-arc graphs,and nested interval graphs

Given a set F of digraphs, we say a graph G is a F-graph (resp., F*-graph) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in F. It is proved that all the classes of graphs mentioned in the title are F-graphs or F*-graphs for subsets F of a set of three digraphs.     

The number of maximal independent sets in connected graphs

Generalizing a theorem of Moon and Moser, we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50.     

On maximal independent sets of vertices in claw-free graphs

A graph is claw-free if: whenever three (distinct) vertices are joined to a single vertex, those three vertices are a nonindependent (nonstable) set. Given a finite claw-free graph with real numbers (weights) assigned to the vertices, we exhibit an algorithm for producing an independent set of vertices of maximum total weight. This algorithm is “efficient” in the sense of J. Edmonds, that is to say, the number of computational steps required is of polynomial (not exponential or factorial) order in n, the number of vertices of the graph. This problem was solved earlier by Edmonds for the special case of “edge-graphs”; our solution is by reducing the more general problem to the earlier-solved special case. Separate attention is given to the case in which all weights are (+1) and thus an independent set is sought which is maximal in the sense of its cardinality.     

Paired domination on interval and circular-arc graphs

We study the paired-domination problem on interval graphs and circular-arc graphs. Given an interval model with endpoints sorted, we give an O(m+n) time algorithm to solve the paired-domination problem on interval graphs. The result is extended to solve the paired-domination problem on circular-arc graphs in O(m(m+n)) time.     

Constraints on the number of maximal independent sets in graphs

A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. Let i(G) denote the number of maximal independent sets of G. Here, we prove two conjectures, suggested by P. Erdös, that the maximum number of maximal independent sets among all graphs of order n in a family Φ is o(3^n/3) if Φ is either a family of connected graphs such that the largest value of maximum degrees among all graphs of order n in Φ is o(n) or a family of graphs such that the approaches infinity as n → ∞.     

Disjoint cliques and disjoint maximal independent sets of vertices in graphs

In this paper, we find lower bounds for the maximum and minimum numbers of cliques in maximal sets of pairwise disjoint cliques in a graph. By complementation, these yield lower bounds for the maximum and minimum numbers of independent sets in maximal sets of pairwise disjoint maximal independent sets of vertices in a graph. In the latter context, we show by examples that one of our bounds is best possible.     

Algorithms for clique-independent sets on subclasses of circular-arc graphs

A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a -free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n²). These algorithms suppose that an HCA model of the graph is given.     

Brambles and independent packings in chordal graphs

An independent packing of triangles is a set of pairwise disjoint triangles, no two of which are joined by an edge. A triangle bramble is a set of triangles, every pair of which intersect or are joined by an edge. More generally, I consider independent packings and brambles of any specified connected graphs, not just triangles. I give a min-max theorem for the maximum number of graphs in an independent packing of any family of connected graphs in a chordal graph, and a dual min-max theorem for the maximum number of graphs in a bramble in a chordal graph.     

On the interval completion of chordal graphs

For a given graph G=(V,E), the interval completion problem of G is to find an edge set F such that the supergraph H=(V,E∪F) of G is an interval graph and |F| is minimum. It has been shown that it is equivalent to the minimum sum cut problem, the profile minimization problem and a kind of graph searching problems. Furthermore, it has applications in computational biology, archaeology, and clone fingerprinting. In this paper, we show that it is NP-complete on split graphs and propose an efficient algorithm on primitive starlike graphs.     

The maximum number of maximal independent sets in unicyclic connected graphs

In this paper, we determine the maximum number of maximal independent sets in a unicyclic connected graph. We also find a class of graphs achieving this maximum value.     

Domination,independent domination,and duality in strongly chordal graphs

We present polynomial algorithms to locate minimum weight dominating sets and independent dominating sets in strongly chordal graphs. We utilize an intimate relationship between strongly chordal graphs and totally balanced matrices to show that the domatic number achieves its theoretical lower bound in strongly chordal graphs and to efficiently solve certain optimization problems for totally balanced matrices.     

Graphs whose powers are chordal and graphs whose powers are interval graphs

The main theorem of this paper gives a forbidden induced subgraph condition on G that is sufficient for chordality of G^m. This theorem is a generalization of a theorem of Balakrishnan and Paulraja who had provided this only for m = 2. We also give a forbidden subgraph condition on G that is sufficient for chordality of G^2m. Similar conditions on G that are sufficient for G^m being an interval graph are also obtained. In addition it is easy to see, that no family of forbidden (induced) subgraphs of G is necessary for G^m being chordal or interval graph. © 1997 John Wiley & Sons, Inc.     

Randomized on-line algorithms and lower bounds for computing large independent sets in disk graphs

We study the on-line version of the maximum independent set problem, for the case of disk graphs which are graphs resulting from intersections of disks on the plane. In particular, we investigate whether randomization can be used to break known lower bounds for deterministic on-line independent set algorithms and present new upper and lower bounds.     

A finiteness theorem for maximal independent sets

Denote bymi(G) the number of maximal independent sets ofG. This paper studies the setS(k) of all graphsG withmi(G) = k and without isolated vertices (exceptG K ₁) or duplicated vertices. We determineS(1), S(2), andS(3) and prove that |V(G)| 2 ^k–1 +k – 2 for anyG inS(k) andk 2; consequently,S(k) is finite for anyk. Supported in part by the National Science Council under grant NSC 83-0208-M009-050