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 ≥ 2, yet can be solved in polynomial time for k ∈ {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)^√k ⋅ n^𝒪(1).