pith. sign in

arxiv: 2606.31873 · v1 · pith:2BIHSWU6new · submitted 2026-06-30 · 💻 cs.DS

Tight bounds for clique-packing parameterized by clique-width

Narek Bojikian , Stefan Kratsch This is my paper

Pith reviewed 2026-07-01 02:28 UTC · model grok-4.3

classification 💻 cs.DS
keywords clique packingclique-widthparameterized complexityexponential time hypothesisdynamic programmingW[1]-hardnessgraph algorithmspartition problems
0
0 comments X

The pith

d-Clique Packing can be solved in n^{O(k^{d-1})} time parameterized by clique-width k, with a matching ETH lower bound for d >= 3.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves an algorithm for finding t disjoint d-sized cliques in a graph that runs in time n to the power of O(k to the d minus 1), where k is the clique-width and the expression is given. It shows that this is the best possible under the exponential time hypothesis, as no algorithm with a smaller exponent in the power of k exists for d at least 3. This holds even when the task is to cover all vertices with such cliques. The result also establishes that the problem is hard for the W[1] class when parameterized by clique-width. Readers care because these bounds tell exactly how the graph's construction complexity affects the packing task.

Core claim

For each fixed d >= 3, the d-Clique Packing problem admits an algorithm running in n^{O(k^{d-1})} time on graphs of clique-width k when a k-expression is given. Assuming the Exponential Time Hypothesis, no algorithm exists with runtime n^{o(k^{d-1})} even for the d-Clique Partition problem. The proof also shows W[1]-hardness of both problems parameterized by clique-width.

What carries the argument

Dynamic programming on the parse tree of the given k-expression, with states sized to produce the O(k^{d-1}) exponent in the runtime.

If this is right

  • The problem is solvable in polynomial time for any constant clique-width.
  • The same upper and lower bounds apply to d-Clique Partition.
  • The problems are W[1]-hard parameterized by clique-width for d >= 3.
  • The exponent in the runtime depends on d but not on the number of cliques t.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar exponent patterns might appear in other packing or covering problems parameterized by clique-width.
  • The results highlight that providing the k-expression is key to achieving the upper bound.
  • One could test whether the bounds extend to related problems like packing other subgraphs of size d.

Load-bearing premise

The exponential time hypothesis holds.

What would settle it

An algorithm solving d-clique packing in time n^{o(k^{d-1})} for some fixed d at least 3 on graphs with given k-expression would falsify the lower bound.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper studies the d-Clique Packing problem (decide if a graph contains t vertex-disjoint d-cliques) and its special case d-Clique Partition. For each fixed d≥3 it gives an algorithm running in n^{O(k^{d-1})} time when a k-expression is provided, and proves that, under ETH, no n^{o(k^{d-1})} algorithm exists even for d-Clique Partition. The lower bound also implies W[1]-hardness parameterized by clique-width.

Significance. If correct, the results supply the first ETH-tight bounds for a natural packing problem on clique-width, extending the Fomin et al. program. The algorithmic side follows the standard clique-width DP template with state size governed by fixed d; the matching lower bound is obtained via an explicit reduction from a known ETH-hard problem. These are concrete strengths.

minor comments (3)
  1. [§3] §3, the DP recurrence for the general packing case: the transition when introducing a new label is described only at a high level; an explicit enumeration of the O(k^{d-1}) states would help verify the exponent.
  2. [§5] The W[1]-hardness claim is derived from the ETH lower bound but is stated without a separate parameterized reduction; a short paragraph clarifying the parameter dependence would avoid any ambiguity.
  3. [Figure 1] Figure 1 (the reduction gadget) uses a non-standard notation for the clique-width labels; adding a small legend would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the paper, the accurate summary of its contributions, and the recommendation of minor revision. The results are correctly described as providing the first ETH-tight bounds for a natural packing problem parameterized by clique-width.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's upper bound is an explicit dynamic-programming algorithm on a provided k-expression whose state size is governed by the fixed parameter d; this is a standard construction for clique-width and does not reduce to any fitted quantity or self-definition. The matching lower bound (including W[1]-hardness) is derived from the external Exponential-Time Hypothesis, which is stated as an independent assumption and is not obtained from any equation or prior result internal to the paper. No self-citation is load-bearing, no ansatz is smuggled, and no renaming of a known result occurs. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the ETH for the lower bound and on standard definitions of clique-width expressions and dynamic programming over them; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked in the abstract to derive the no n^{o(k^{d-1})} lower bound.

pith-pipeline@v0.9.1-grok · 5762 in / 1439 out tokens · 59069 ms · 2026-07-01T02:28:29.287831+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    2 Benjamin Bergougnoux, Mamadou Moustapha Kanté, and O-joung Kwon

    doi:10.1016/j.tcs.2019.02.030. 2 Benjamin Bergougnoux, Mamadou Moustapha Kanté, and O-joung Kwon. An optimal XP algorithm for hamiltonian cycle on graphs of bounded clique-width.Algorithmica, 82(6):1654–1674,

    work page doi:10.1016/j.tcs.2019.02.030 2019

  2. [2]

    1007/S00453-019-00663-9

    URL: https://doi.org/10.1007/s00453-019-00663-9, doi:10. 1007/S00453-019-00663-9. 3 Benjamin Bergougnoux, Tuukka Korhonen, and Jesper Nederlof. Tight lower bounds for problems parameterized by rank-width. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors,40th International Symposium on Theoretical Aspects of Computer S...

    work page doi:10.1007/s00453-019-00663-9 2023

  3. [3]

    4 Hans L

    doi:10.4230/LIPIcs.STACS.2023.11. 4 Hans L. Bodlaender and Jurriaan Hage. On switching classes, nlc-width, cliquewidth and treewidth.Theor. Comput. Sci., 429:30–35,

    work page doi:10.4230/lipics.stacs.2023.11 2023

  4. [4]

    Theo- retical Computer Science1066, 115746 (2026).https://doi.org/10.1016/j.tcs

    URL: https://doi.org/10.1016/j.tcs. 2011.12.021,doi:10.1016/J.TCS.2011.12.021. 5 Narek Bojikian, Vera Chekan, and Stefan Kratsch. Tight bounds for some classical problems parameterized by cutwidth. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors,33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15-...

    work page doi:10.1016/j.tcs 2011

  5. [5]

    6 NarekBojikianandStefanKratsch

    URL:https://doi.org/10.4230/LIPIcs.ESA.2025.13, doi:10.4230/ LIPICS.ESA.2025.13. 6 NarekBojikianandStefanKratsch. Atightmonte-carloalgorithmforsteinertreeparameterized by clique-width. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2...

    work page doi:10.4230/lipics.esa.2025.13 2025

  6. [6]

    7 Narek Bojikian and Stefan Kratsch

    URL: https://doi.org/10.4230/LIPIcs.ICALP.2024.29, doi:10.4230/LIPICS.ICALP.2024.29. 7 Narek Bojikian and Stefan Kratsch. Tight bounds for connected odd cycle transversal parameterized by clique-width. In Akanksha Agrawal and Erik Jan van Leeuwen, editors,20th International Symposium on Parameterized and Exact Computation, IPEC 2025, Warsaw, Poland, Septe...

    work page doi:10.4230/lipics.icalp.2024.29 2024

  7. [7]

    8 Narek Bojikian and Stefan Kratsch

    URL:https://doi.org/10.4230/LIPIcs.IPEC.2025.19, doi:10.4230/ LIPICS.IPEC.2025.19. 8 Narek Bojikian and Stefan Kratsch. Tight bounds for feedback vertex set parameterized by clique-width.CoRR, abs/2512.01900,

    work page doi:10.4230/lipics.ipec.2025.19 2025

  8. [8]

    Quantifying the dynamics of consciousness using hierarchical integration, organ- ised complexity and metastability,

    URL: https://doi.org/10.48550/arXiv.2512. 01900,arXiv:2512.01900,doi:10.48550/ARXIV.2512.01900. 9 Vera Chekan and Stefan Kratsch. Tight algorithmic applications of clique-width generalizations. In Jérôme Leroux, Sylvain Lombardy, and David Peleg, editors,48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, Bordeaux, Fra...

    work page doi:10.48550/arxiv.2512 2023

  9. [9]

    10 Bruno Courcelle, Johann A

    URL: https://doi.org/10.4230/LIPIcs.MFCS.2023.35, doi:10.4230/ LIPICS.MFCS.2023.35. 10 Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width.Theory Comput. Syst., 33(2):125–150,

    work page doi:10.4230/lipics.mfcs.2023.35 2023

  10. [10]

    11 Marek Cygan, Fedor V

    doi:10.1007/s002249910009. 11 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer,

    work page doi:10.1007/s002249910009

  11. [11]

    7 Andrea D’Ascenzo, Giuseppe F

    doi:10.1007/978-3-319-21275-3. 12 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Intractability of clique-width parameterizations.SIAM J. Comput., 39(5):1941–1956, 2010.doi:10.1137/ 080742270. 13 Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost optimal lower bounds for problems parameterized by clique...

    work page doi:10.1007/978-3-319-21275-3 1941

  12. [12]

    Springer, 2014.doi:10.1007/978-3-642-54423-1\ _7

    Proceedings, Lecture Notes in Computer Science, pages 72–83. Springer, 2014.doi:10.1007/978-3-642-54423-1\ _7. 16 Martin Fürer. Multi-clique-width. In Christos H. Papadimitriou, editor,8th Innovations in Theoretical Computer Science Conference, ITCS 2017, Berkeley, CA, USA, January 9-11, 2017, LIPIcs, pages 14:1–14:13. Schloss Dagstuhl - Leibniz-Zentrum f...

    work page doi:10.1007/978-3-642-54423-1 2014

  13. [13]

    17 Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and Kirill Simonov

    URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.14,doi:10.4230/LIPICS.ITCS.2017.14. 17 Robert Ganian, Thekla Hamm, Viktoriia Korchemna, Karolina Okrasa, and Kirill Simonov. The fine-grained complexity of graph homomorphism parameterized by clique-width.ACM Trans. Algorithms, 20(3):19, 2024.doi:10.1145/3652514. 18 Falko Hegerfeld and Stefan Kratsch. Tight al...

    work page doi:10.4230/lipics.itcs.2017.14 2017

  14. [14]

    21 Ojvind Johansson

    URL: https://doi.org/10.1007/ s00224-023-10132-0,doi:10.1007/S00224-023-10132-0. 21 Ojvind Johansson. Clique-decomposition, nlc-decomposition, and modular decomposition- relationships and results for random graphs.Congressus Numerantium, pages 39–60,

    work page doi:10.1007/s00224-023-10132-0

  15. [15]

    23 Michael Lampis

    doi:10.1016/S0166-218X(02)00198-1. 23 Michael Lampis. Finer tight bounds for coloring on clique-width.SIAM J. Discret. Math., 34(3):1538–1558, 2020.doi:10.1137/19M1280326. 24 Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the exponential time hypothesis.Bull. EATCS, 105:41–72,

    work page doi:10.1016/s0166-218x(02)00198-1 2020