On maximum planar induced subgraphs

The nonplanar vertex deletion or vertex deletion vd(G) of a graph G is the smallest nonnegative integer k, such that the removal of k vertices from G produces a planar graph G^′. In this case G^′ is said to be a maximum planar induced subgraph of G. We solve a problem proposed by Yannakakis: find the threshold for the maximum degree of a graph G such that, given a graph G and a nonnegative integer k, to decide whether vd(G)?k is NP-complete. We prove that it is NP-complete to decide whether a maximum degree 3 graph G and a nonnegative integer k satisfy vd(G)?k. We prove that unless P=NP there is no polynomial-time approximation algorithm with fixed ratio to compute the size of a maximum planar induced subgraph for graphs in general. We prove that it is Max SNP-hard to compute vd(G) when restricted to a cubic input G. Finally, we exhibit a polynomial-time -approximation algorithm for finding a maximum planar induced subgraph of a maximum degree 3 graph.     

On hereditary clique-Helly self-clique graphs

A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.     

Partition into cliques for cubic graphs: Planar case, complexity and approximation

Given a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V₁,V₂,…,V_k such that the subgraph induced by each part V_i is a complete subgraph (clique) of G. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time -approximation algorithm for finding clique partitions in maximum degree three graphs.     

Characterization and recognition of generalized clique-Helly graphs

Let p?1 and q?0 be integers. A family of sets F is (p,q)-intersecting when every subfamily F^′⊆F formed by p or less members has total intersection of cardinality at least q. A family of sets F is (p,q)-Helly when every (p,q)-intersecting subfamily F^′⊆F has total intersection of cardinality at least q. A graph G is a (p,q)-clique-Helly graph when its family of (maximal) cliques is (p,q)-Helly. According to this terminology, the usual Helly property and the clique-Helly graphs correspond to the case p=2,q=1. In this work we present a characterization for (p,q)-clique-Helly graphs. For fixed p,q, this characterization leads to a polynomial-time recognition algorithm. When p or q is not fixed, it is shown that the recognition of (p,q)-clique-Helly graphs is NP-hard.     

Clique-critical graphs: Maximum size and recognition

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K^-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.     

Equivariant collapses and the homotopy type of iterated clique graphs

The clique graph K(G) of a simple graph G is the intersection graph of its maximal complete subgraphs, and we define iterated clique graphs by K⁰(G)=G, Kⁿ⁺¹(G)=K(Kⁿ(G)). We say that two graphs are homotopy equivalent if their simplicial complexes of complete subgraphs are so. From known results, it can be easily inferred that Kⁿ(G) is homotopy equivalent to G for every n if G belongs to the class of clique-Helly graphs or to the class of dismantlable graphs. However, in both of these cases the collection of iterated clique graphs is finite up to isomorphism. In this paper, we show two infinite classes of clique-divergent graphs that satisfy G?Kⁿ(G) for all n, moreover Kⁿ(G) and G are simple-homotopy equivalent. We provide some results on simple-homotopy type that are of independent interest.     

On retracts,absolute retracts,and foldings in cographs

A retract of a graph G is an induced subgraph H of G such that there exists a homomorphism \(\rho :G \rightarrow H\). When both G and H are cographs, we show that the problem to determine whether H is a retract of G is NP-complete; moreover, we show that this problem on cographs is fixed-parameter tractable when parameterized by the size of H. When restricted to the class of threshold graphs or to the class of trivially perfect graphs, the retract problem becomes tractable in polynomial time. The retract problem is also solvable in linear time when one cograph is given as an induced subgraph of the other. We characterize absolute retracts for the class of cographs. Foldings generalize retractions. We show that the problem to fold a trivially perfect graph onto a largest possible clique is NP-complete.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

Efficient algorithms for Roman domination on some classes of graphs

A Roman dominating function of a graph G=(V,E) is a function f:V→{0,1,2} such that every vertex x with f(x)=0 is adjacent to at least one vertex y with f(y)=2. The weight of a Roman dominating function is defined to be f(V)=∑_x∈Vf(x), and the minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. In this paper we first answer an open question mentioned in [E.J. Cockayne, P.A. Dreyer Jr., S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004) 11-22] by showing that the Roman domination number of an interval graph can be computed in linear time. We then show that the Roman domination number of a cograph (and a graph with bounded cliquewidth) can be computed in linear time. As a by-product, we give a characterization of Roman cographs. It leads to a linear-time algorithm for recognizing Roman cographs. Finally, we show that there are polynomial-time algorithms for computing the Roman domination numbers of -free graphs and graphs with a d-octopus.     

Vertex- and edge-minimal and locally minimal graphs

Given a family of graphs , a graph is called edge-minimal (vertex-minimal) if for every subgraph (induced subgraph) G^′ of G; furthermore, G is called locally edge-minimal (locally vertex-minimal) if whenever G^′ is obtained from G by deleting an edge (a vertex). Similarly, the concepts of minimality and local minimality are introduced for directed graphs (digraphs) and, more generally, for partially ordered sets.For example, by the Strong Perfect Graph Theorem, the only vertex-minimal graphs with χ>ω are odd holes and anti-holes. In contrast, the only locally vertex-minimal graphs with χ>ω are partitionable graphs. Somewhat surprisingly, there are infinitely many non-trivial perfect graphs that are locally edge-minimal and -maximal simultaneously. In other words, such a graph is perfect but it becomes imperfect after any edge is deleted from or added to it.In this paper we consider vertex- and edge-minimal and locally minimal graphs in the following families: (i) perfect and imperfect graphs, (ii) graphs with χ=ω and with χ>ω, (iii) digraphs that have a kernel and kernel-free digraphs, and finally, (iv) vertex-minimal complementary connected d-graphs.     

Approximating the minimum clique cover and other hard problems in subtree filament graphs

Subtree filament graphs are the intersection graphs of subtree filaments in a tree. This class of graphs contains subtree overlap graphs, interval filament graphs, chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs. In this paper we show that, for circle graphs, the clique cover problem is NP-complete and the h-clique cover problem for fixed h is solvable in polynomial time. We then present a general scheme for developing approximation algorithms for subtree filament graphs, and give approximation algorithms developed from the scheme for the following problems which are NP-complete on circle graphs and therefore on subtree filament graphs: clique cover, vertex colouring, maximum k-colourable subgraph, and maximum h-coverable subgraph.     

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.     

A (2 + )-Approximation Scheme for Minimum Domination on Circle Graphs

The main result of this paper is a (2 + )-approximation scheme for the minimum dominating set problem on circle graphs. We first present an O(n²) time 8-approximation algorithm for this problem and then extend it to an time (2 + )-approximation scheme for this problem. Here n and m are the number of vertices and the number of edges of the circle graph. We then present simple modifications to this algorithm that yield (3 + )-approximation schemes for the minimum connected and the minimum total dominating set problems on circle graphs. Keil (1993, Discrete Appl. Math.42, 51–63) shows that these problems are NP-complete for circle graphs and leaves open the problem of devising approximation algorithms for them. These are the first O(1)-approximation algorithms for domination problems on circle graphs.     

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.     

Partial characterizations of clique-perfect graphs II: Diamond-free and Helly circular-arc graphs

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. The list of minimal forbidden induced subgraphs for the class of clique-perfect graphs is not known. Another open question concerning clique-perfect graphs is the complexity of the recognition problem. Recently we were able to characterize clique-perfect graphs by a restricted list of forbidden induced subgraphs when the graph belongs to two different subclasses of claw-free graphs. These characterizations lead to polynomial time recognition of clique-perfect graphs in these classes of graphs. In this paper we solve the characterization problem in two new classes of graphs: diamond-free and Helly circular-arc () graphs. This last characterization leads to a polynomial time recognition algorithm for clique-perfect graphs.     

Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

On the strong p-Helly property

The notion of strong p-Helly hypergraphs was introduced by Golumbic and Jamison in 1985 [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B 38 (1985) 8-22]. Independently, other authors [A. Bretto, S. Ubéda, J. ?erovnik, A polynomial algorithm for the strong Helly property. Inform. Process. Lett. 81 (2002) 55-57, E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220, W.D. Wallis, Guo-Hui Zhang, On maximal clique irreducible graphs. J. Combin. Math. Combin. Comput. 8 (1990) 187-193.] have also considered the strong Helly property in other contexts. In this paper, we characterize strong p-Helly hypergraphs. This characterization leads to an algorithm for recognizing such hypergraphs, which terminates within polynomial time whenever p is fixed. In contrast, we show that the recognition problem is co-NP-complete, for arbitrary p. Further, we apply the concept of strong p-Helly hypergraphs to the cliques of a graph, leading to the class of strong p-clique-Helly graphs. For p=2, this class is equivalent to that of hereditary clique-Helly graphs [E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220]. We describe a characterization for this class and obtain an algorithm for recognizing such graphs. Again, the algorithm has polynomial-time complexity for p fixed, and we show the corresponding recognition problem to be NP-hard, for arbitrary p.     

Bipartite graphs are not universal fixers

For any permutation π of the vertex set of a graph G, the graph πG is obtained from two copies G^′ and G^″ of G by joining u∈V(G^′) and v∈V(G^″) if and only if v=π(u). Denote the domination number of G by γ(G). For all permutations π of V(G), γ(G)≤γ(πG)≤2γ(G). If γ(πG)=γ(G) for all π, then G is called a universal fixer. We prove that graphs without 5-cycles are not universal fixers, from which it follows that bipartite graphs are not universal fixers.