The problem of deciding whether the edge-set of a
given graph can be partitioned into at most k cliques
is well known to be NP-complete. In this paper we
investigate this problem from the point of view of parameterized
complexity. We show that this problem
is fixed parameter tractable if we choose the number
of cliques as parameter. In particular, we show that
in polynomial time, a kernel bounded by k^2 can be
obtained, where k is the number of cliques. We also
give an O(2^{((k+3) log k)/2}n) algorithm for this problem
in K_4-free graphs. |
Cite as: Mujuni, E. and Rosamond, F. (2008). Parameterized Complexity of the Clique Partition Problem. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds. ACS. 75-78. |
(from crpit.com)
(local if available)
|