期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 53 in polynomial time, and is NP-hard to
approximate within some constant 1−, 01.
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
2E(H)+1 in polynomial time, and show hard to approximate when
H=Kr or H=Cr is a fixed clique or cycle on at least three vertices.
This relates to a problem solved by Kirkpatrick and Hell.
