2026-07-21T20:02:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24511 2025-12-16T14:00:11Z ddc:004 open_access

Edge Clique Partition and Cover Beyond Independence Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill edge clique partition edge clique cover independence number parameterized complexity above guarantee 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor V. Fomin and Petr A. Golovach and Danil Sagunov and Kirill Simonov 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.43 urn:nbn:de:0030-drops-245113 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.43 eng https://creativecommons.org/licenses/by/4.0/legalcode