Optimization problems in multiple subtree graphs

We study various optimization problems in t-subtree graphs, the intersection graphs of t-subtrees, where a t-subtree is the union of t disjoint subtrees of some tree. This graph class generalizes both the class of chordal graphs and the class of t-interval graphs, a generalization of interval graphs that has recently been studied from a combinatorial optimization point of view. We present approximation algorithms for the Maximum Independent Set, Minimum Coloring, Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique problems.     

The clique operator on matching and chessboard graphs

Given positive integers m,n, we consider the graphs G_n and G_m,n whose simplicial complexes of complete subgraphs are the well-known matching complex M_n and chessboard complex M_m,n. Those are the matching and chessboard graphs. We determine which matching and chessboard graphs are clique-Helly. If the parameters are small enough, we show that these graphs (even if not clique-Helly) are homotopy equivalent to their clique graphs. We determine the clique behavior of the chessboard graph G_m,n in terms of m and n, and show that G_m,n is clique-divergent if and only if it is not clique-Helly. We give partial results for the clique behavior of the matching graph G_n.     

On the kernel size of clique cover reductions for random intersection graphs

Covering all edges of a graph by a minimum number of cliques is a well known $\mathsf{NP}$-hard problem. For the parameter k being the maximal number of cliques to be used, the problem becomes fixed parameter tractable. However, assuming the Exponential Time Hypothesis, there is no kernel of subexponential size in the worst-case.We study the average kernel size for random intersection graphs with n vertices, edge probability p, and clique covers of size k. We consider the well-known set of reduction rules of Gramm, Guo, Hüffner, and Niedermeier (2009) [17] and show that with high probability they reduce the graph completely if p is bounded away from 1 and $k<c\log n$ for some constant $c>0$. This shows that for large probabilistic graph classes like random intersection graphs the expected kernel size can be substantially smaller than the known exponential worst-case bounds.     

On maximizing clique, clique-Helly and hereditary clique-Helly induced subgraphs

Clique-Helly and hereditary clique-Helly graphs are polynomial-time recognizable. Recently, we presented a proof that the clique graph recognition problem is NP-complete [L. Alcón, L. Faria, C.M.H. de Figueiredo, M. Gutierrez, Clique graph recognition is NP-complete, in: Proc. WG 2006, in: Lecture Notes in Comput. Sci., vol. 4271, Springer, 2006, pp. 269-277]. In this work, we consider the decision problems: given a graph G=(V,E) and an integer k≥0, we ask whether there exists a subset V^′⊆V with |V^′|≥k such that the induced subgraph G[V^′] of G is, variously, a clique, clique-Helly or hereditary clique-Helly graph. The first problem is clearly NP-complete, from the above reference; we prove that the other two decision problems mentioned are NP-complete, even for maximum degree 6 planar graphs. We consider the corresponding maximization problems of finding a maximum induced subgraph that is, respectively, clique, clique-Helly or hereditary clique-Helly. We show that these problems are Max SNP-hard, even for maximum degree 6 graphs. We show a general polynomial-time -approximation algorithm for these problems when restricted to graphs with fixed maximum degree Δ. We generalize these results to other graph classes. We exhibit a polynomial 6-approximation algorithm to minimize the number of vertices to be removed in order to obtain a hereditary clique-Helly subgraph.     

Circle graphs and the cycle double cover conjecture

The long standing Cycle Double Cover Conjecture states that every bridgeless graph can be covered by a family of cycles such that every edge is covered exactly twice. Intimately related is the problem of finding, in an eulerian graph, a circuit decomposition compatible with a given transition system (transition systems are also known as decompositions into closed paths). One approach that seems promising consists in finding a black anticlique in the corresponding Sabidussi orbit of bicolored circle graphs.     

Approximating the balanced minimum evolution problem

We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instances. Furthermore, we give a MST-based 2-approximation algorithm for the problem for such instances.     

Sphericity, cubicity, and edge clique covers of graphs

The sphericity sph(G) of a graph G is the minimum dimension d for which G is the intersection graph of a family of congruent spheres in R^d. The edge clique cover number θ(G) is the minimum cardinality of a set of cliques (complete subgraphs) that covers all edges of G. We prove that if G has at least one edge, then sph(G)?θ(G). Our upper bound remains valid for intersection graphs defined by balls in the L_p-norm for 1?p?∞.     

Packing triangles in low degree graphs and indifference graphs

We consider the problems of finding the maximum number of vertex-disjoint triangles (VTP) and edge-disjoint triangles (ETP) in a simple graph. Both problems are NP-hard. The algorithm with the best approximation ratio known so far for these problems has ratio 3/2+?, a result that follows from a more general algorithm for set packing obtained by Hurkens and Schrijver [On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2(1) (1989) 68-72]. We present improvements on the approximation ratio for restricted cases of VTP and ETP that are known to be APX-hard: we give an approximation algorithm for VTP on graphs with maximum degree 4 with ratio slightly less than 1.2, and for ETP on graphs with maximum degree 5 with ratio 4/3. We also present an exact linear-time algorithm for VTP on the class of indifference graphs.     

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.     

Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems

We consider an -hard variant (Δ-Max-ATSP) and an -hard relaxation (Max-3-DCC) of the classical traveling salesman problem. We present a -approximation algorithm for Δ-Max-ATSP and a -approximation algorithm for Max-3-DCC with polynomial running time. The results are obtained via a new way of applying techniques for computing undirected cycle covers to directed problems.     

Extremal problems on the Hamiltonicity of claw-free graphs

In 1962, Erd?s proved that if a graph $G$ with $n$ vertices satisfies

$e\left(G\right)>max\left\{\left(\genfrac{}{}{0ex}{}{n?k}{2}\right)+k^2,\left(\genfrac{}{}{0ex}{}{?(n+1)∕2?}{2}\right)+{?\frac{n?1}{2}?}^2\right\},$

where the minimum degree $\delta \left(G\right)\ge k$ and $1\le k\le (n?1)∕2$, then it is Hamiltonian. For $n\ge 2k+1$, let $E_n^k=K_k\vee (k{K}_1+K_{n?2k})$, where “$\vee$” is the “join” operation. One can observe $e\left(E_n^k\right)=\left(\genfrac{}{}{0ex}{}{n?k}{2}\right)+k^2$ and $E_n^k$ is not Hamiltonian. As $E_n^k$ contains induced claws for $k\ge 2$, a natural question is to characterize all 2-connected claw-free non-Hamiltonian graphs with the largest possible number of edges. We answer this question completely by proving a claw-free analog of Erd?s’ theorem. Moreover, as byproducts, we establish several tight spectral conditions for a 2-connected claw-free graph to be Hamiltonian. Similar results for the traceability of connected claw-free graphs are also obtained. Our tools include Ryjá?ek’s claw-free closure theory and Brousek’s characterization of minimal 2-connected claw-free non-Hamiltonian graphs.     

An edge-reduction algorithm for the vertex cover problem

An approximation algorithm for the vertex cover problem is proposed with performance ratio on special graphs. On an arbitrary graph, the algorithm guarantees a vertex cover S₁ such that where S^∗ is an optimal cover and ξ is an error bound identified.     

Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree

Let T = (V, A) be a directed tree. Given a collection P{\mathcal{P}} of dipaths on T, we can look at the arc-intersection graph I(P,T){I(\mathcal{P},T)} whose vertex set is P{\mathcal{P}} and where two vertices are connected by an edge if the corresponding dipaths share a common arc. Monma and Wei, who started their study in a seminal paper on intersection graphs of paths on a tree, called them DE graphs (for directed edge path graphs) and proved that they are perfect. DE graphs find one of their applications in the context of optical networks. For instance, assigning wavelengths to set of dipaths in a directed tree network consists in finding a proper coloring of the arc-intersection graph. In the present paper, we give

Approximating the maximum 3-edge-colorable subgraph problem

We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least of its edges, where γ_o(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/15 of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least 6/7 of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound.For a fixed value of a parameter k≥1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be APX-hard for all k≥2. However, approximation algorithms with approximation ratios tending to 1 as k goes to infinity are also known. At present, the best known performance ratios for the cases k=2 and k=3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k=3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C₅’s are also banned).