pith. sign in

arxiv: 2604.25841 · v1 · submitted 2026-04-28 · 💻 cs.DS

Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width

Benjamin Bergougnoux , Vera Chekan , Stefan Kratsch This is my paper

Pith reviewed 2026-05-07 15:03 UTC · model grok-4.3

classification 💻 cs.DS
keywords multi-clique-widthfine-grained complexityExponential Time HypothesisMax CutHamiltonian CycleEdge Dominating Setparameterized algorithmsgraph width parameters
0
0 comments X

The pith

Under ETH, Max Cut has no algorithm running in n^{2^{o(k)}} f(k) time on multi-clique-width k graphs.

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

The paper proves that Max Cut cannot be solved in time n^{2^{o(k)}} times any computable function of k when the input graph has multi-clique-width k, assuming the Exponential Time Hypothesis. It contrasts this with the known n to the O(k) algorithm that is tight for the related clique-width parameter. The authors also give n to the O(k) algorithms for Hamiltonian Cycle and Edge Dominating Set that match the clique-width bounds. These results highlight that multi-clique-width, which generalizes both clique-width and treewidth without exponential blow-up in one direction, can produce different fine-grained complexity for some problems.

Core claim

Under the ETH the Max Cut problem cannot be solved in time n^{2^{o(k)}} · f(k) on graphs of multi-clique-width k for any computable function f. For clique-width k an n^{O(k)} algorithm is known and tight under ETH. Hamiltonian Cycle and Edge Dominating Set admit n^{O(k)} algorithms on multi-clique-width k graphs, matching their clique-width running times.

What carries the argument

Multi-clique-width, the graph parameter in which every vertex may carry multiple labels at once, used both for the ETH lower-bound reduction on Max Cut and for the dynamic-programming upper bounds on the other two problems.

If this is right

  • Max Cut exhibits a qualitatively worse tight running time under multi-clique-width than under clique-width.
  • Hamiltonian Cycle and Edge Dominating Set have the same n^{O(k)} upper bound for both parameters.
  • Some W[1]-hard problems admit different fine-grained bounds when parameterized by multi-clique-width versus clique-width.
  • The list of problems known to require n^{2^{o(k)}} f(k) time under ETH grows by at least one entry.

Where Pith is reading between the lines

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

  • The same reduction technique might separate the complexity of additional problems that currently share the same bounds for the two width parameters.
  • Because multi-clique-width is at most linear in treewidth plus a constant, the lower bound for Max Cut immediately transfers to a treewidth parameterization up to a constant factor in the exponent.
  • Dynamic-programming routines for Hamiltonian Cycle and Edge Dominating Set on multi-clique-width may be reusable on other intermediate width measures between treewidth and clique-width.

Load-bearing premise

The ETH reduction for Max Cut produces output graphs whose multi-clique-width is bounded by a linear function of the source parameter.

What would settle it

An explicit algorithm that solves Max Cut in n^{2^{o(k)}} f(k) time for some computable f on a sequence of graphs whose multi-clique-width grows as k would contradict the claimed lower bound if the reduction is parameter-preserving.

read the original abstract

In this work we contribute to the study of the fine-grained complexity of problems parameterized by multi-clique-width, which was initiated by F\"urer [ITCS 2017] and pursued further by Chekan and Kratsch [MFCS 2023]. Multi-clique-width is a parameter defined analogously to clique-width but every vertex is allowed to hold multiple labels simultaneously. This parameter is upper-bounded by both clique-width and treewidth (plus a constant), hence it generalizes both of them without an exponential blow-up. Conversely, graphs of multi-clique-width $k$ have clique-width at most $2^k$, and there exist graphs with clique-width at least $2^{\Omega(k)}$. Thus, while the two parameters are functionally equivalent, the fine-grained complexity of problems may differ relative to them. As our first and main result we show that under ETH the Max Cut problem cannot be solved in time $n^{2^{o(k)}} \cdot f(k)$ on graphs of multi-clique-width $k$ for any computable function $f$. For clique-width $k$ an $n^{\mathcal{O}(k)}$ algorithm by Fomin et al. [SIAM J. Comput. 2014] is tight under ETH. This makes Max Cut the first known problem for which the tight running times differ for parameterization by clique-width and multi-clique-width and it contributes to the short list of known lower bounds of form $n^{2^{o(k)}} \cdot f(k)$. As our second contribution we show that Hamiltonian Cycle and Edge Dominating Set can be solved in time $n^{\mathcal{O}(k)}$ on graphs of multi-clique-width $k$ matching the tight running time for clique-width. These results answer three questions left open by Chekan and Kratsch [MFCS 2023].

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

1 major / 1 minor

Summary. The manuscript establishes tight fine-grained complexity bounds for problems parameterized by multi-clique-width. Under the Exponential Time Hypothesis, it shows that Max Cut cannot be solved in time n^{2^{o(k)}} · f(k) for graphs of multi-clique-width k. It also provides n^{O(k)} algorithms for Hamiltonian Cycle and Edge Dominating Set on multi-clique-width k graphs, matching the bounds known for clique-width parameterization. These results highlight differences between clique-width and multi-clique-width and answer open questions from Chekan and Kratsch.

Significance. If the results are correct, this paper makes a significant contribution by identifying Max Cut as the first problem with differing tight running times under clique-width versus multi-clique-width. The lower bound of the form n^{2^{o(k)}} f(k) under ETH is notable and adds to the limited known examples of such bounds. The upper bounds for the other problems are solid and resolve prior open questions, advancing the study of multi-clique-width as a parameter that generalizes both clique-width and treewidth.

major comments (1)
  1. [Reduction establishing the Max Cut ETH lower bound] The ETH lower bound for Max Cut (the main result) rests on a reduction from an ETH-hard problem whose output graph must have multi-clique-width bounded by some computable g(k) with no exponential dependence on k. The abstract asserts the n^{2^{o(k)}} f(k) bound but supplies no explicit multi-clique-width calculation or bound for the constructed instance; this verification is load-bearing because an exponential blow-up would only yield the weaker statement n^{2^{o(g(k))}} f(k).
minor comments (1)
  1. [Abstract] The abstract and introduction use both n^{2^{o(k)}} and n^{O(k)}; adopt a uniform notation (e.g., always with mathcal) for asymptotic expressions throughout.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and constructive feedback. The comment highlights an important point about the clarity of our ETH lower bound proof. We address it below and will revise the manuscript to improve explicitness.

read point-by-point responses

  1. Referee: [Reduction establishing the Max Cut ETH lower bound] The ETH lower bound for Max Cut (the main result) rests on a reduction from an ETH-hard problem whose output graph must have multi-clique-width bounded by some computable g(k) with no exponential dependence on k. The abstract asserts the n^{2^{o(k)}} f(k) bound but supplies no explicit multi-clique-width calculation or bound for the constructed instance; this verification is load-bearing because an exponential blow-up would only yield the weaker statement n^{2^{o(g(k))}} f(k).

    Authors: We agree that an explicit verification of the multi-clique-width bound is essential for the result to hold in the stated form. The reduction in Section 3 is from a parameterized ETH-hard problem (specifically, a variant of 3-SAT or k-Clique with parameter k) and constructs the target graph such that each vertex receives a constant number of additional labels beyond those needed for the original structure. We will add a dedicated lemma immediately following the reduction description that proves the output graph has multi-clique-width at most 3k + 2 (linear in the source parameter, with no exponential dependence). This lemma will include the full multi-labeling construction and the join/relabel operations used. The revised manuscript will also cross-reference this bound in the statement of the main theorem and the abstract discussion. We believe this fully resolves the concern while preserving the correctness of the existing proof. revision: yes

Circularity Check

0 steps flagged

No circularity detected in ETH lower bound or algorithmic results

full rationale

The paper's central claims consist of a new ETH-based reduction establishing the n^{2^{o(k)}} lower bound for Max Cut on multi-clique-width-k graphs and new n^{O(k)} algorithms for Hamiltonian Cycle and Edge Dominating Set. These are presented as original contributions that answer open questions from prior work, without any reduction of the target bounds to fitted parameters, self-definitions, or load-bearing self-citations. The abstract explicitly states the results as shown in this work, and the parameter preservation in the reduction is part of the claimed proof rather than an unverified assumption imported from self-citation. No equations or steps in the provided text equate outputs to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central lower bound rests on the standard Exponential Time Hypothesis and on the functional relationship between multi-clique-width and clique-width established in prior work; no new free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked to obtain the conditional lower bound for Max Cut.

pith-pipeline@v0.9.0 · 5650 in / 1295 out tokens · 194987 ms · 2026-05-07T15:03:30.266046+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

38 extracted references · 38 canonical work pages

  1. [1]

    Tight lower bounds for problems parameterized by rank-width

    2 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 Science, STACS 2023, Hamburg, Germany, March 7-9, 2023, volume 254 of LIPIcs, pages...

    work page 2023

  2. [2]

    Tight double exponential lower bounds

    3 Ivan Bliznets and Markus Hecher. Tight double exponential lower bounds. In Xujin Chen and Bo Li, editors,Theory and Applications of Models of Computation - 18th Annual Conference, TAMC 2024, Hong Kong, China, May 13-15, 2024, Proceedings, volume 14637 ofLecture Notes in Computer Science, pages 124–136. Springer,

    work page 2024

  3. [3]

    Bodlaender, Erik Jan van Leeuwen, Johan M

    5 Hans L. Bodlaender, Erik Jan van Leeuwen, Johan M. M. van Rooij, and Martin Vatshelle. Faster algorithms on branch and clique decompositions. In Petr Hlinený and Antonín Kucera, editors,Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27,

    work page 2010

  4. [4]

    Bergougnoux, V

    B. Bergougnoux, V. Chekan, S. Kratsch 47 6 Narek Bojikian, Vera Chekan, Falko Hegerfeld, and Stefan Kratsch. Tight bounds for connectivity problems parameterized by cutwidth. In Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté, editors,40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, Hamburg, G...

    work page 2023

  5. [5]

    Tight bounds for some classical problems parameterized by cutwidth

    7 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-17, 2025, volume 351 ofLIPIcs, pages 13:1–13:17. Schloss Dagstuhl - Leibniz-Zen...

    work page 2025

  6. [6]

    Atightmonte-carloalgorithmforsteinertreeparameterized by clique-width

    8 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, Tallinn, Estonia, July 8-12, 2024, volume 297 ofLIPIcs, pages 29:1–29:18. Schloss Dagstuhl - L...

    work page 2024

  7. [7]

    Tight bounds for connected odd cycle transversal parameterized by clique-width

    9 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, September 17-19, 2025, volume 358 ofLIPIcs, pages 19:1–19:15. Schloss Dagstuhl - Leibniz-Z...

    work page 2025

  8. [8]

    Treewidth inapproximability and tight ETH lower bound

    10 Édouard Bonnet. Treewidth inapproximability and tight ETH lower bound. In Michal Koucký and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 2130–2135. ACM,

    work page 2025

  9. [9]

    Tight Algorithmic Applications of Clique-Width Generalizations

    11 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, August 28 to September 1, 2023, Bordeaux, France, volume 272 ofLIPIcs, pages 35:1–35:15. Schloss Dagstuhl - ...

    work page 2023

  10. [10]

    Tight algorithmic applications of clique-width generalizations

    12 Vera Chekan and Stefan Kratsch. Tight algorithmic applications of clique-width generalizations. CoRR, abs/2307.04628,

    work page arXiv

  11. [11]

    Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus

    14 Radu Curticapean and Dániel Marx. Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus. In Robert Krauthgamer, editor,Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, V A, USA, January 10-12, 2016, pages 1650–1669. SIAM,

    work page 2016

  12. [12]

    On maximum 2-clubs

    18 Joanne Dumont, Michael Lampis, Mathieu Liedloff, Anthony Perez, and Ioan Todinca. On maximum 2-clubs. In Akanksha Agrawal and Erik Jan van Leeuwen, editors,20th International Symposium on Parameterized and Exact Computation, IPEC 2025, Warsaw, Poland, September 17-19, 2025, volume 358 ofLIPIcs, pages 13:1–13:14. Schloss Dagstuhl - Leibniz-Zentrum für I...

    work page 2025

  13. [13]

    Fundamental problems on bounded-treewidth graphs: The real source of hardness

    48 Tight Bounds for some W[1]-hard Problems Parameterized by Multi-clique-width 19 Baris Can Esmer, Jacob Focke, Dániel Marx, and Pawel Rzazewski. Fundamental problems on bounded-treewidth graphs: The real source of hardness. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st International Colloquium on Automata, Languages, a...

    work page 2024

  14. [14]

    List homomorphisms by deleting edges and vertices: Tight complexity bounds for bounded-treewidth graphs

    20 Baris Can Esmer, Jacob Focke, Dániel Marx, and Pawel Rzazewski. List homomorphisms by deleting edges and vertices: Tight complexity bounds for bounded-treewidth graphs. In Timothy M. Chan, Johannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Symposium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September...

    work page 2024

  15. [15]

    Generalized graph packing problems parameterized by treewidth

    21 Baris Can Esmer and Dániel Marx. Generalized graph packing problems parameterized by treewidth. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors, 33rd Annual European Symposium on Algorithms, ESA 2025, Warsaw, Poland, September 15-17, 2025, volume 351 ofLIPIcs, pages 3:1–3:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2025

  16. [16]

    Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover

    29 Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Problems in NP can admit double-exponential lower bounds when parameterized by treewidth or vertex cover. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st International Colloquium on Automata, Languages, a...

    work page 2024

  17. [17]

    A natural generalization of bounded tree-width and bounded clique-width

    30 Martin Fürer. A natural generalization of bounded tree-width and bounded clique-width. In Alberto Pardo and Alfredo Viola, editors,LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4,

    work page 2014

  18. [18]

    Multi-clique-width

    31 Martin Fürer. Multi-clique-width. In Christos H. Papadimitriou, editor,8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 ofLIPIcs, pages 14:1–14:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2017

  19. [19]

    Thepriceofbeingpartial: Complexityofpartialgeneralized dominating set on bounded-treewidth graphs.CoRR, abs/2506.01645,

    33 JakobGreilhuberandDánielMarx. Thepriceofbeingpartial: Complexityofpartialgeneralized dominating set on bounded-treewidth graphs.CoRR, abs/2506.01645,

    work page arXiv

  20. [20]

    Residue domination in bounded- treewidth graphs

    34 Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz. Residue domination in bounded- treewidth graphs. In Olaf Beyersdorff, Michal Pilipczuk, Elaine Pimentel, and Kim Thang Nguyen, editors,42nd International Symposium on Theoretical Aspects of Computer Science, STACS 2025, March 4-7, 2025, Jena, Germany, volume 327 ofLIPIcs, pages 41:1–41:20. Schlos...

    work page 2025

  21. [21]

    Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters

    35 Carla Groenland, Isja Mannens, Jesper Nederlof, Marta Piecyk, and Pawel Rzazewski. Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors,51st International Colloquium on Automata, Languages, and Programming, ICALP 20...

    work page 2024

  22. [22]

    Tight bounds for counting colorings and connected edge sets parameterized by cutwidth

    36 Carla Groenland, Isja Mannens, Jesper Nederlof, and Krisztina Szilágyi. Tight bounds for counting colorings and connected edge sets parameterized by cutwidth. In Petra Berenbrink and Benjamin Monmege, editors,39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, Marseille, France (Virtual Conference), March 15-18, 2022, v...

    work page 2022

  23. [23]

    Hedonic games and treewidth revisited

    38 Tesshu Hanaka and Michael Lampis. Hedonic games and treewidth revisited. In Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman, editors,30th Annual European Symposium on Algorithms, ESA 2022, Berlin/Potsdam, Germany, September 5-9, 2022, volume 244 ofLIPIcs, pages 64:1–64:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2022

  24. [24]

    Structural parameters for steiner orientation

    39 Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, and Manolis Vasilakis. Structural parameters for steiner orientation. In Ho-Lin Chen, Wing- Kai Hon, and Meng-Tsung Tsai, editors,36th International Symposium on Algorithms and Computation, ISAAC 2025, Tainan, Taiwan, December 7-10, 2025, volume 359 ofLIPIcs, pages 38:1–3...

    work page 2025

  25. [25]

    Towards exact structural thresholds for parameterized complexity

    40 Falko Hegerfeld and Stefan Kratsch. Towards exact structural thresholds for parameterized complexity. In Holger Dell and Jesper Nederlof, editors,17th International Symposium on Parameterized and Exact Computation, IPEC 2022, Potsdam, Germany, September 7-9, 2022, volume 249 ofLIPIcs, pages 17:1–17:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2022

  26. [26]

    Tight algorithms for connectivity problems parameterized by clique-width

    41 Falko Hegerfeld and Stefan Kratsch. Tight algorithms for connectivity problems parameterized by clique-width. In Inge Li Gørtz, Martin Farach-Colton, Simon J. Puglisi, and Grzegorz Herman, editors,31st Annual European Symposium on Algorithms, ESA 2023, Amsterdam, The Netherlands, September 4-6, 2023, volume 274 ofLIPIcs, pages 59:1–59:19. Schloss Dagst...

    work page 2023

  27. [27]

    Tight algorithms for connectivity problems parameterized by modular-treewidth

    42 Falko Hegerfeld and Stefan Kratsch. Tight algorithms for connectivity problems parameterized by modular-treewidth. In Daniël Paulusma and Bernard Ries, editors,Graph-Theoretic Concepts in Computer Science - 49th International Workshop, WG 2023, Fribourg, Switzerland, June 28-30, 2023, Revised Selected Papers, volume 14093 ofLecture Notes in Computer Sc...

    work page 2023

  28. [28]

    The primal pathwidth SETH

    47 Michael Lampis. The primal pathwidth SETH. In Yossi Azar and Debmalya Panigrahi, editors, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 1494–1564. SIAM,

    work page 2025

  29. [29]

    Circuits and Backdoors: Five Shades of the SETH

    48 Michael Lampis. Circuits and Backdoors: Five Shades of the SETH. In Kasper Green Larsen and Barna Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 1945–2001. SIAM,

    work page 2026

  30. [30]

    k-SUM Hardness Implies Treewidth-SETH

    49 Michael Lampis. k-SUM Hardness Implies Treewidth-SETH. In Kasper Green Larsen and Barna Saha, editors,Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, pages 1916–1944. SIAM,

    work page 2026

  31. [31]

    Treewidth with a quantifier alternation revisited

    51 Michael Lampis and Valia Mitsou. Treewidth with a quantifier alternation revisited. In Daniel Lokshtanov and Naomi Nishimura, editors,12th International Symposium on Parameterized and Exact Computation, IPEC 2017, Vienna, Austria, September 6-8, 2017, volume 89 of LIPIcs, pages 26:1–26:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2017

  32. [32]

    Parameterized maximum node-disjoint paths

    54 Michael Lampis and Manolis Vasilakis. Parameterized maximum node-disjoint paths. In Akanksha Agrawal and Erik Jan van Leeuwen, editors,20th International Symposium on Parameterized and Exact Computation, IPEC 2025, Warsaw, Poland, September 17-19, 2025, volume 358 ofLIPIcs, pages 3:1–3:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,

    work page 2025

  33. [33]

    Structural parameterizations for induced and acyclic matching

    55 Michael Lampis and Manolis Vasilakis. Structural parameterizations for induced and acyclic matching. In Henning Fernau and Philipp Kindermann, editors,Graph-Theoretic Concepts in Computer Science - 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11-13, 2025, Revised Selected Papers, volume 16124 ofLecture Notes in Computer Science, pag...

    work page 2025

  34. [34]

    Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth

    59 Dániel Marx and Valia Mitsou. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors,43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 11-15, 2016, volume 55 ofL...

    work page 2016

  35. [35]

    Sankar, and Philipp Schepper

    60 Dániel Marx, Govind S. Sankar, and Philipp Schepper. Degrees and gaps: Tight complexity results of general factor problems parameterized by treewidth and cutwidth. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors,48th International Colloquium on Automata, B. Bergougnoux, V. Chekan, S. Kratsch 51 Languages, and Programming, ICALP 2021, Gla...

    work page 2021

  36. [36]

    Fine-grained complexity of the list homomorphism problem: Feedback vertex set and cutwidth

    61 Marta Piecyk and Pawel Rzazewski. Fine-grained complexity of the list homomorphism problem: Feedback vertex set and cutwidth. In Markus Bläser and Benjamin Monmege, editors,38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021, Saarbrücken, Germany (Virtual Conference), March 16-19, 2021, volume 187 ofLIPIcs, pages 56:1–56...

    work page 2021

  37. [37]

    64 Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith. Dynamic programming on tree decompositions using generalised fast subset convolution. In Amos Fiat and Peter Sanders, editors,Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9,

    work page 2009

  38. [38]

    Springer, 2009

    Proceedings, volume 5757 ofLecture Notes in Computer Science, pages 566–577. Springer, 2009

    work page 2009