Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-013 | 15th February 2012 19:10

Packing Edge-Disjoint Triangles in Given Graphs


Authors: Tomas Feder, Carlos Subi
Publication: 16th February 2012 10:36
Downloads: 6617


Given a graph $G$, we consider the problem of finding the largest set
of edge-disjoint triangles contained in $G$. We show that even the
simpler case of decomposing the edges of
a sparse split graph $G$ into edge-disjoint triangles
is NP-complete. We show next that the case of a general $G$ can be approximated
within a factor of $\frac{3}{5}$ in polynomial time, and is NP-hard to
approximate within some constant $1-\epsilon$, $0<\epsilon<1$.
We generalize this to the question of finding the largest set of edge-disjoint
copies of a fixed graph $H$ in $G$, which we approximate within
$\frac{2}{|E(H)|+1}$ in polynomial time, and show hard to approximate when
$H=K_r$ or $H=C_r$ is a fixed clique or cycle on at least three vertices.
This relates to a problem solved by Kirkpatrick and Hell.

We finally determine optimal solutions for
the case where $G$ is a clique of any size by examining a
family of dense split graphs. The motivation for the case of cliques is
the theory of block designs, in particular the case of Steiner triple
systems, and
a conjecture of Erd\"{o}s, Faber, and Lovasz which states that the union
of $n$ edge-disjoint cliques of size $n$ has vertex chromatic number $n$.
The connection to this conjecture is obtained through a dualization argument.

ISSN 1433-8092 | Imprint