{"ID":5443836,"CreatedAt":"2026-07-01T02:07:11.383974684Z","UpdatedAt":"2026-07-03T15:47:14.94733546Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31873","arxiv_id":"2606.31873","title":"Tight bounds for clique-packing parameterized by clique-width","abstract":"In the $d$-Clique Packing problem, given a graph $G$ and an integer $t$, we need to decide whether $G$ contains a set of $t$ pairwise vertex-disjoint cliques of size $d$ each. This generalizes Triangle Packing and it is NP-complete for all $d\\geq 3$. For each such $d$, we show how to solve the problem in $n^{O(k^{d-1})}$ time where $k$ is the clique-width of the graph (with a $k$-expression of $G$ given in the input). We complement this by showing that, assuming the Exponential-Time Hypothesis (ETH), there is no algorithm that solves the problem in $n^{o(k^{d-1})}$ time for any fixed $d\\geq 3$, already for the special case of seeking a partition into cliques of size $d$. Our proof also entails W[1]-hardness of $d$-Clique Packing (and $d$-Clique Partition) parameterized by clique-width for each $d\\geq 3$. Our work continues a series of results on ETH-tight bounds for fundamental graph problems started by Fomin et al.\\ (SICOMP 2010+2014) who obtained tight bounds for Max-Cut and Edge Dominating Set.","short_abstract":"In the $d$-Clique Packing problem, given a graph $G$ and an integer $t$, we need to decide whether $G$ contains a set of $t$ pairwise vertex-disjoint cliques of size $d$ each. This generalizes Triangle Packing and it is NP-complete for all $d\\geq 3$. For each such $d$, we show how to solve the problem in $n^{O(k^{d-1})...","url_abs":"https://arxiv.org/abs/2606.31873","url_pdf":"https://arxiv.org/pdf/2606.31873v1","authors":"[\"Narek Bojikian\",\"Stefan Kratsch\"]","published":"2026-06-30T15:57:21Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}