Edge Clique Partition and Cover Beyond Independence
Preprint
Abstract
Covering and partitioning the edges of a graph into cliques are classical problems at the intersection of combinatorial optimization and graph theory, having been studied through a range of algorithmic and complexity-theoretic lenses. Despite the well-known fixed-parameter tractability of these problems when parameterized by the total number of cliques, such a parameterization often fails to be meaningful for sparse graphs. In many real-world instances, on the other hand, the minimum number of cliques in an edge cover or partition can be very close to the size of a maximum independent set α(G). Motivated by this observation, we investigate above αparameterizations of the edge clique cover and partition problems. Concretely, we introduce and study Edge Clique Cover Above Independent Set (ECC/α) and Edge Clique Partition Above Independent Set (ECP/α), where the goal is to cover or partition all edges of a graph using at most α(G) + k cliques, and k is the parameter. Our main results reveal a distinct complexity landscape for the two variants. We show that ECP/αis fixed-parameter tractable, whereas ECC/αis NP-complete for all k \geq 2, yet can be solved in polynomial time for k \in {0,1}. These findings highlight intriguing differences between the two problems when viewed through the lens of parameterization above a natural lower bound. Finally, we demonstrate that ECC/αbecomes fixed-parameter tractable when parameterized by k + ω(G), where ω(G) is the size of a maximum clique of the graph G. This result is particularly relevant for sparse graphs, in which ωis typically small. For H-minor free graphs, we design a subexponential algorithm of running time f(H)^{\sqrt{k}}n^{O(1)}.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Large-scale clique cover of real-world networksInformation and Computation, 2020
- Partition into cliques for cubic graphs: Planar case, complexity and approximationDiscrete Applied Mathematics, 2008
- Algorithms for compact letter displays: Comparison and evaluationComputational Statistics & Data Analysis, 2007
- Efficiently covering complex networks with cliques of similar verticesTheoretical Computer Science, 2006
- Local Tree-Width, Excluded Minors, and Approximation AlgorithmsCombinatorica, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Can visibility graphs Be represented compactly?Discrete & Computational Geometry, 1994
- Linear time algorithms on circular-arc graphsInformation Processing Letters, 1991
- Lower bound of the hadwiger number of graphs by their average degreeCombinatorica, 1984
- Contentment in graph theory: Covering graphs with cliquesIndagationes Mathematicae, 1977