Pith. sign in

REVIEW 3 major objections 4 minor 35 references

Elimination Distance to Dominated Clusters

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves uniform fixed-parameter algorithms for Dominated Cluster Deletion and Elimination Distance to Dominated Clusters, with the second running in $f(k,d,\ell)\cdot n^{O(1)}$ where $\ell$ is the semi-ladder index.

desk verdict Uniform f(k,d)n^{O(d)} algorithm is solid and answers the open question; the stronger semi-ladder-index FPT result has a repairable proof gap in Lemma 48 and depends on an unreviewed preprint. read the letter →

arxiv 2504.21675 v2 pith:UYI4C3JI submitted 2025-04-30 cs.DM

Nicole Schirrmacher , Sebastian Siebertz , Alexandre Vigny This is my paper · ORCID
classification cs.DM MSC 68Q2705C6905C85
keywords dominatedclusterdeletioneliminationdistancesemi-ladderindexfixed-parametertractabilityparameterizedcomplexitytreedecompositionsunbreakablegraphsdomination
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper claims that two related graph-deletion problems are easier than previously known. Dominated Cluster Deletion and Elimination Distance to Dominated Clusters each admit a uniform algorithm with running time $f(k,d)\cdot n^{O(d)}$ on all graphs, and each admits an FPT algorithm with running time $f(k,d,\ell)\cdot n^{O(1)}$ when the input graph has semi-ladder index $\ell$. Because every class of bounded degeneracy also has bounded semi-ladder index, this settles the open question of whether the problems are FPT for the parameter $k+d+c$. The paper also completes nearly all of the complexity and kernelization classification for the recursive version, leaving only the treedepth case on bounded-degree graphs open.

What carries the argument

The argument runs through three linked devices. First, an unbreakable tree-decomposition theorem produces bags that cannot be split in a balanced way by separators of order at most $k$, so after deleting $k$ vertices each instance has one large connected component and only small ones. Second, the dynamic program works on bag graphs: the small components are compressed into $d$-gadgets, and the decision problems on each bag reduce to an instance of Annotated Partial Domination. Third, the semi-ladder index governs the runtime: the semi-ladder is the largest $n$ for which two sequences of distinct vertices satisfy $a_i b_j\in E(G)$ for $i>j$ and $a_i b_i\notin E(G)$, and on classes with bounded semi-ladder index the cited meta-theorem evaluates the needed domination-type formula in linear time. This combination is what turns the tree decomposition into an $f(k,d,\ell)\cdot n^{O(1)}$ algorithm, and the same skeleton-and-bag-graph machinery produces the uniform $f(k,d)\cdot n^{O(d)}$ algorithm on general graphs.

What would settle it

Exhibit a graph class with bounded semi-ladder index on which Annotated Partial Domination, specifically the formula $\delta_{k,d}$ used in the proof, cannot be solved in $f(d,k,\ell)\cdot n^{O(1)}$ time, or produce a distance formula $\delta$ whose associated bipartite graph has bounded semi-ladder index but whose decision problem is not fixed-parameter tractable; either would falsify Theorem 4 and with it Theorems 1 and 2.

Watch

Extended reading notes

Core claim

The central claim is that both deletion problems become uniformly tractable. For any computable function $f$, Dominated Cluster Deletion can be solved in time $f(k,d)\cdot n^{O(d)}$ and in time $f(k,d,\ell)\cdot n^{O(1)}$, and the same two running-time bounds hold for Elimination Distance to Dominated Clusters, where $\ell$ is the semi-ladder index of the input graph. The first bound upgrades a previously non-uniform algorithm to a uniform one. The second covers every semi-ladder-free graph class, which includes all degenerate and biclique-free classes, and therefore implies fixed-parameter tractability with respect to $k+d+c$, answering the open question from the earlier classification. Alongside the algorithms, the paper shows Elimination Distance to Dominated Clusters is para-NP-hard for parameter $k+\Delta$ and for parameter $d$, $W[2]$-hard for $k+d$, and admits no polynomial kernel for parameter $k$ even when $d=0$ and $c=2$, unless $\mathrm{NP}\subseteq \mathrm{coNP}/\mathrm{poly}$.

Load-bearing premise

Everything rests on a theorem the paper cites but does not prove: on graphs where the semi-ladder index is bounded, the class of domination-type formulas used in the proof can be evaluated in linear time; if that cited theorem fails or does not apply to the bag graphs constructed here, both main algorithms collapse.

Editorial extensions

If this is right

  • The earlier non-uniform $f(k,d)\cdot n^{O(d)}$ algorithm for Dominated Cluster Deletion is replaced by one uniform algorithm, with the same dependence on $n$.
  • Open question answered: both problems are FPT for $k+d+c$, since the semi-ladder index is no larger than the degeneracy $c$ and is often much smaller.
  • The FPT result transfers to every graph class on which Annotated Partial Domination is FPT and the parameter transfers to bag graphs, not only to semi-ladder-free classes.
  • Recursive deletion to dominated clusters is tractable on the same broad classes as one-shot deletion, so measuring distance by elimination depth does not add hardness there.
  • The classification of Elimination Distance to Dominated Clusters is almost complete: only the $d=0$ treedepth case on bounded maximum degree remains open, and no polynomial kernel exists for parameter $k$ with $d=0$ and $c=2$ unless $\mathrm{NP}\subseteq \mathrm{coNP}/\mathrm{poly}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the cited semi-ladder meta-theorem is correct, the same machinery should give uniform FPT algorithms for other deletion problems whose target class is defined by small dominating sets, such as Red-Blue domination variants, on all semi-ladder-free classes.
  • The collapse of elimination distance to deletion distance on unbreakable graphs suggests a general principle: once a graph is unbreakable, recursive deletion adds no extra hardness for hereditary-style target classes; this could simplify other elimination-distance algorithms.
  • The bound in Lemma 48 that every bag graph inherits semi-ladder index at most $q+\ell+4$ is directly checkable on synthetic semi-ladder-free instances and would provide an empirical sanity check independent of the preprint's meta-theorem.
  • The real remaining barrier is treedepth on bounded-degree graphs; if that case is NP-hard, the $d+\Delta$ parameter becomes para-NP-hard and the classification is complete.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies two graph modification problems: Dominated Cluster Deletion, where one deletes at most k vertices so that every remaining connected component has a dominating set of size at most d, and its recursive analogue Elimination Distance to Dominated Clusters. The main results are a uniform algorithm running in time f(k,d)·n^{O(d)} for both problems and an FPT algorithm with running time f(k,d,ℓ)·n^{O(1)}, where ℓ is the semi-ladder index of the input graph. The latter result is claimed to answer positively the open question of Bentert et al. on fixed-parameter tractability with respect to k+d+c, since bounded degeneracy implies bounded semi-ladder index. The paper also supplies a classification of hardness and kernelization for the elimination-distance variant: para-NP-hardness for k+Δ and for d, W[2]-hardness for k+d, and the absence of a polynomial kernel for parameter k even when d=0 and c=2.

Significance. If the main theorems are correct, the paper is a genuine advance: it replaces a non-uniform algorithm of Bentert et al. by a uniform f(k,d)·n^{O(d)} algorithm and introduces a new structural parameter (semi-ladder index) under which both problems become FPT, thereby resolving the open question about degeneracy. The hardness and kernelization classification for the elimination-distance variant is also valuable. The paper is well structured and the appendix contains substantial technical material. However, the FPT-by-semi-ladder-index claim currently rests on two load-bearing steps that are not fully supported: an external meta-theorem cited from an unreviewed preprint with overlapping authorship, and a transfer lemma (Lemma 48) whose proof contains a shifted-index gap. These issues do not affect the f(k,d)·n^{O(d)} uniform algorithms, but they must be resolved before the main FPT claim can be accepted.

major comments (3)
  1. [Section 3, Theorem 4 and Corollary 6] The proof of Lemma 48 asserts that a_{q+5},...,a_t and b_1,...,b_{t-q-4} form a semi-ladder of G. Pairing these sequences termwise gives pairs (a_{q+4+i}, b_i) for i=1,...,t-q-4. For such a pair, the original semi-ladder condition implies that {a_{q+4+i}, b_i} is an edge, because q+4+i > i; the semi-ladder definition instead requires a non-edge on the diagonal. Hence the constructed pair of sequences is not a semi-ladder, and the claimed bound t ≤ q+ℓ+4 does not follow. This lemma is the only step establishing that the semi-ladder index has Property 2, so the f(k,d,ℓ)·n^{O(1)} running times in Theorems 1 and 2 are currently unsupported. The gap appears repairable: one can take a same-index middle subsequence and absorb all gadget vertices into an additive O(q+d) term, which still suffices for Property 2, but the proof must be rewritten.
  2. [Appendix B.2, Claim 50 and Lemma 53] The semi-ladder-index results depend entirely on Theorem 4 of [20] and on Lemmas 4–5 of that same arXiv preprint, which is coauthored by one of the present authors and is not proved in this manuscript. The proof of Lemma 5 is only a citation to those lemmas, and Corollary 6 inherits the full weight of the external result. If [20] is not yet available in a peer-reviewed venue, the authors should provide a self-contained proof of the specific evaluation and closure facts needed for the formula δ_{k,d}; alternatively, they should cite a published version with a DOI. As written, a referee cannot verify the main FPT claim without relying on an external unreviewed source.
  3. [Appendix B.2] The correctness argument for the dynamic programming step (Proposition 49) is highly compressed. Claim 50 is proved in two paragraphs that do not state a formal invariant connecting the selected marks of the children, the counter c, the partition P, and the constructed bag graph H; for example, it is not shown precisely how the pi-gadgets encode the requirement that each component's Blue dominating set has size at most p and how the count |D|+c is maintained across the branching. Lemma 53 also needs a precise argument that every branching step increases |S|+s or |D|+c, since the branch that selects a mark with ky=0 and all pi=0 is supposed to make no progress. These gaps make the proof of the central DP difficult to verify and should be expanded.
minor comments (4)
  1. [Appendix A] In the proof of Lemma 37, the text bounds the number of Red exterior vertices in G−C0 by qd, but this does not follow from the assumption |E∩B|≤qd and appears inconsistent with the later bound '3qd+q' used in the same appendix. The constants should be reconciled.
  2. [Section 2] In the definition of N[Y], the displayed formula '⋃_{v∈Y} N[y]' mixes the variables y and v; it should be '⋃_{v∈Y} N[v]'.
  3. [Section 4] The statement that for |G|≥2q+1 every deletion of at most k vertices leaves a unique connected component with more than q vertices is not justified by size alone; a graph could in principle break into several components all of size at most q. The subsequent lemmas that invoke C0 (Lemma 8, Lemma 13) should either prove this claim from (q,k)-unbreakability or explicitly handle the case where no large component exists.
  4. [Section 6] There is a typo in 'sudivision vertex' and the proof would benefit from a figure or a more detailed exchange argument, since the claim that a subdivision vertex can always be swapped with an endpoint without increasing depth is stated rather than shown.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the FPT results reduce cluster deletion to an independent domination-type evaluation problem and to a DP over unbreakable tree decompositions; self-citations to [20] and [31] are load-bearing but not definitionally circular, and the Lemma 48 index issue is a correctness concern, not a reduction-to-inputs.

full rationale

The derivation chain is: (1) rewrite Dominated Cluster Deletion and Elimination Distance to Dominated Clusters as Annotated Partial Domination on bag graphs; (2) solve Annotated Partial Domination either by brute-force n^{O(d)} guessing or by the semi-ladder meta-theorem of [20]; (3) combine these with the Cygan et al. unbreakable-tree-decomposition DP. None of these steps sets the target statement equal to its own input by construction. The uniform f(k,d)n^{O(d)} algorithm is not a renaming of Bentert et al.'s non-uniform result: it uses an explicit DP over bag graphs with a direct n^{O(d)} domination oracle. The f(k,d,\ell)n^{O(1)} result does rely on Theorem 4 of [20], a preprint coauthored by one of the present authors, and on Lemma 48 to transfer bounded semi-ladder index from G to bag graphs. This is a load-bearing self-citation, but [20] is about general distance formulas and does not assume the cluster-deletion conclusion, so the reduction has independent mathematical content and is not circular. Lemma 48's proof does appear to have an index-pairing gap: it pairs a_{q+5},...,a_t with b_1,...,b_{t-q-4}, and the required non-edges {a_{q+4+i},b_i} are not implied by the original semi-ladder non-edge condition; this is a correctness risk, not a circularity. The hardness and kernel lower bounds reduce from Dominating Set and Treedepth, which are external problems. No fitted parameter is renamed as a prediction, and no uniqueness theorem is imported from the authors' prior work to forbid alternatives. Accordingly, no circular step is exhibited.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no fitted parameters or new physical entities. It relies on several external theorems, most notably the existence of unbreakable tree decompositions (Cygan et al.) and the semi-ladder meta-theorem of Fabiański et al. The latter is the most fragile dependency because it is cited from an unreviewed preprint with overlapping authorship.

assumptions (5)
  • domain assumption Existence and computability of (q,k)-unbreakable tree decompositions with adhesion size at most q (Theorem 3, from Cygan et al. [13])
    Used in Sections 2 and 5 to reduce the graph to bag graphs; the entire DP framework depends on this decomposition.
  • domain assumption Any (q,k)-unbreakable tree decomposition can be made regular (Lemma 2.8 of [8] and discussion in [31])
    Regularity is required for the bag graph construction and for the size bounds in Lemma 47.
  • domain assumption Meta-theorem that domination-type formulas with bounded semi-ladder index are solvable in linear time (Theorem 4 of [20])
    Central engine for the f(k,d,ℓ)·n^{O(1)} algorithms; not proved in this paper and cited from an unreviewed preprint.
  • standard math The AND-cross-composition framework for kernel lower bounds (Drucker [19])
    Used in Section 6 to prove the non-existence of polynomial kernels.
  • domain assumption FO model checking is FPT on nowhere dense and monadically stable graph classes (cited in Section 1, not used in main proof)
    Mentioned to contextualize the results; not load-bearing.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Elimination Distance to Dominated Clusters." pith.science (2026). https://pith.science/paper/UYI4C3JI

@misc{pith2026250421675,
  author       = {Pith},
  title        = {Pith review of: Elimination Distance to Dominated Clusters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UYI4C3JI}},
  note         = {Machine review of arXiv:2504.21675}
}
abstract

In the Dominated Cluster Deletion problem, we are given an undirected graph $G$ and integers $k$ and $d$ and the question is to decide whether there exists a set of at most $k$ vertices whose removal results in a graph in which each connected component has a dominating set of size at most $d$. In the Elimination Distance to Dominated Clusters problem, we are again given an undirected graph $G$ and integers $k$ and $d$ and the question is to decide whether we can recursively delete vertices up to depth $k$ such that each remaining connected component has a dominating set of size at most $d$. Bentert et al.~[Bentert et al., MFCS 2024] recently provided an almost complete classification of the parameterized complexity of Dominated Cluster Deletion with respect to the parameters $k$, $d$, $c$, and $\Delta$, where $c$ and $\Delta$ are the degeneracy, and the maximum degree of the input graph, respectively. In particular, they provided a non-uniform algorithm with running time $f(k,d)\cdot n^{O(d)}$. They left as an open problem whether the problem is fixed-parameter tractable with respect to the parameter $k+d+c$. We provide a uniform algorithm running in time $f(k,d)\cdot n^{O(d)}$ for both Dominated Cluster Deletion and Elimination Distance to Dominated Clusters. We furthermore show that both problems are FPT when parameterized by $k+d+\ell$, where $\ell$ is the semi-ladder index of the input graph, a parameter that is upper bounded and may be much smaller than the degeneracy $c$, positively answering the open question of Bentert et al. We further complete the picture by providing an almost full classification for the parameterized complexity and kernelization complexity of Elimination Distance to Dominated Clusters. The one difficult base case that remains open is whether treedepth (the case $d=0$) is NP-hard on graphs of bounded maximum degree.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

35 extracted references · 15 canonical work pages

  1. [20]

    Progressive algorithms for domination and independence

    Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. Progressive algorithms for domination and independence. CoRR , abs/1811.06799, 2018. URL: http://arxiv.org/abs/1811.06799, https://arxiv.org/abs/1811.06799 arXiv:1811.06799 , https://doi.org/10.48550/arXiv.1811.06799 doi:10.48550/arXiv.1811.06799

    arXiv doi:10.48550/arxiv.1811.06799 2018

  2. [2]

    A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs

    Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, MS Ramanujan, and Saket Saurabh. A fixed-parameter tractable algorithm for elimination distance to bounded degree graphs. SIAM Journal on Discrete Mathematics , 36(2):911--921, 2022. https://doi.org/10.1137/21m1396824 doi:10.1137/21m1396824

    work page doi:10.1137/21m1396824 2022

  3. [1]

    Akanksha Agrawal, Lawqueen Kanesh, Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Deleting, eliminating and decomposing to hereditary classes are all fpt-equivalent. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Al...

    doi:10.1137/1.9781611977073.79 2022

  4. [3]

    On the parameterized complexity of clique elimination distance

    Akanksha Agrawal and MS Ramanujan. On the parameterized complexity of clique elimination distance. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2020. https://doi.org/10.4230/LIPIcs.IPEC.2020.1 doi:10.4230/LIPIcs.IPEC.2020.1

    work page doi:10.4230/lipics.ipec.2020.1 2020

  5. [4]

    u r Informatik, Schloss Dagstuhl - Leibniz-Zentrum f \

    Matthias Bentert, Michael R. Fellows, Petr A. Golovach, Frances A. Rosamond, and Saket Saurabh. Breaking a graph into connected components with small dominating sets. In Rastislav Kr \' a lovic and Anton \' n Kucera, editors, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia ,...

    work page 2024

  6. [5]

    Kernelization for graph packing problems via rainbow matching

    St \'e phane Bessy, Marin Bougeret, Dimitrios M Thilikos, and Sebastian Wiederrecht. Kernelization for graph packing problems via rainbow matching. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 3654--3663. SIAM, 2023. https://doi.org/10.1137/1.9781611977554.ch139 doi:10.1137/1.9781611977554.ch139

    doi:10.1137/1.9781611977554.ch139 2023

  7. [6]

    Bodlaender, \' E douard Bonnet, Lars Jaffke, Dusan Knop, Paloma T

    Hans L. Bodlaender, \' E douard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, and Ondrej Such \' y . Treewidth is NP -complete on cubic graphs. In 18th International Symposium on Parameterized and Exact Computation, (IPEC 2023) . Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2023. https://do...

    work page doi:10.4230/lipics.ipec.2023.7 2023

  8. [7]

    Treewidth for graphs with small chordality

    Hans L Bodlaender and Dimitrios M Thilikos. Treewidth for graphs with small chordality. Discrete Applied Mathematics , 79(1-3):45--61, 1997. https://doi.org/10.1016/S0166-218X(97)00031-0 doi:10.1016/S0166-218X(97)00031-0

    doi:10.1016/s0166-218x(97)00031-0 1997

Show all 35 references
  1. [8]

    Definability equals recognizability for graphs of bounded treewidth

    Mikolaj Bojanczyk and Michal Pilipczuk. Definability equals recognizability for graphs of bounded treewidth. In Martin Grohe, Eric Koskinen, and Natarajan Shankar, editors, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, ...

    2016

  2. [9]

    Twin-width I : tractable FO model checking

    \'E douard Bonnet, Eun Jung Kim, St \'e phan Thomass \'e , and R \'e mi Watrigant. Twin-width I : tractable FO model checking. ACM Journal of the ACM (JACM) , 69(1):1--46, 2021. https://doi.org/10.1145/3486655 doi:10.1145/3486655

    2021 doi

  3. [10]

    Graph isomorphism parameterized by elimination distance to bounded degree

    Jannis Bulian and Anuj Dawar. Graph isomorphism parameterized by elimination distance to bounded degree. Algorithmica , 75(2):363--382, 2016. https://doi.org/10.1007/s00453-015-0045-3 doi:10.1007/s00453-015-0045-3

    2016 doi

  4. [11]

    Linear time solvable optimization problems on graphs of bounded clique-width

    Bruno Courcelle, Johann A Makowsky, and Udi Rotics. Linear time solvable optimization problems on graphs of bounded clique-width. Theory of Computing Systems , 33(2):125--150, 2000. https://doi.org/10.1007/s002249910009 doi:10.1007/s002249910009

    doi

  5. [12]

    Randomized contractions meet lean decompositions

    Marek Cygan, Pawe Komosa, Daniel Lokshtanov, Marcin Pilipczuk, Micha Pilipczuk, Saket Saurabh, and Magnus Wahlstr \"o m. Randomized contractions meet lean decompositions. ACM Transactions on Algorithms (TALG) , 17(1):1--30, 2020. https://doi.org/10.1145/3426738 doi:10.1145/3426738

    2020 doi

  6. [13]

    Minimum bisection is fixed-parameter tractable

    Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Minimum bisection is fixed-parameter tractable. SIAM J. Comput. , 48(2):417--450, 2019. https://doi.org/10.1137/140988553 doi:10.1137/140988553

    2019 doi

  7. [14]

    Graph Theory, 4th Edition , volume 173 of Graduate texts in mathematics

    Reinhard Diestel. Graph Theory, 4th Edition , volume 173 of Graduate texts in mathematics . Springer, 2012

    2012

  8. [15]

    Fixed-parameter tractability and completeness II : On completeness for W [1]

    Rod G Downey and Michael R Fellows. Fixed-parameter tractability and completeness II : On completeness for W [1]. Theoretical Computer Science , 141(1-2):109--131, 1995. https://doi.org/10.1016/0304-3975(94)00097-3 doi:10.1016/0304-3975(94)00097-3

    1995 doi

  9. [16]

    First-order model checking on monadically stable graph classes

    Jan Dreier, Ioannis Eleftheriadis, Nikolas M \" a hlmann, Rose McCarty, Michal Pilipczuk, and Szymon Torunczyk. First-order model checking on monadically stable graph classes. CoRR , abs/2311.18740, 2023. https://doi.org/10.48550/arXiv.2311.18740 doi:10.48550/arXiv.2311.18740

    2023 doi arXiv

  10. [17]

    First-order model checking on structurally sparse graph classes

    Jan Dreier, Nikolas M \"a hlmann, and Sebastian Siebertz. First-order model checking on structurally sparse graph classes. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023) , pages 567--580, 2023. https://doi.org/10.1145/3564246.3585186 doi:10....

    2023

  11. [18]

    Sat backdoors: Depth beats size

    Jan Dreier, Sebastian Ordyniak, and Stefan Szeider. Sat backdoors: Depth beats size. Journal of Computer and System Sciences , 142:103520, 2024. https://doi.org/10.1016/j.jcss.2024.103520 doi:10.1016/j.jcss.2024.103520

    2024

  12. [19]

    New limits to classical and quantum instance compression

    Andrew Drucker. New limits to classical and quantum instance compression. SIAM Journal on Computing , 44(5):1443--1479, 2015. https://doi.org/10.1137/130927115 doi:10.1137/130927115

    2015 doi

  13. [21]

    On 2-clubs in graph-based data clustering: theory and algorithm engineering

    Aleksander Figiel, Anne - Sophie Himmel, Andr \' e Nichterlein, and Rolf Niedermeier. On 2-clubs in graph-based data clustering: theory and algorithm engineering. In Tiziana Calamoneri and Federico Cor \` o , editors, Algorithms and Complexity - 12th International Conference, ...

    2021 doi

  14. [22]

    Parameterized complexity of elimination distance to first-order logic properties

    Fedor V Fomin, Petr A Golovach, and Dimitrios M Thilikos. Parameterized complexity of elimination distance to first-order logic properties. ACM Transactions on Computational Logic (TOCL) , 23(3):1--35, 2022. https://doi.org/10.1145/3517129 doi:10.1145/3517129

    2022 doi

  15. [23]

    M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness , volume 174. W. H. Freeman, 1979

    1979

  16. [24]

    Deciding first-order properties of nowhere dense graphs

    Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. Journal of the ACM (JACM) , 64(3):1--32, 2017. https://doi.org/10.1145/3051095 doi:10.1145/3051095

    2017 doi

  17. [25]

    A structural view on parameterizing problems: Distance from triviality

    Jiong Guo, Falk H \" u ffner, and Rolf Niedermeier. A structural view on parameterizing problems: Distance from triviality. In Rodney G. Downey, Michael R. Fellows, and Frank K. H. A. Dehne, editors, Parameterized and Exact Computation, First International Workshop, IWPEC 2004...

    2004 doi

  18. [26]

    A more relaxed model for graph-based data clustering: s-plex cluster editing

    Jiong Guo, Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann. A more relaxed model for graph-based data clustering: s-plex cluster editing. SIAM Journal on Discrete Mathematics , 24(4):1662--1683, 2010. https://doi.org/10.1137/090767285 doi:10.1137/090767285

    2010 doi

  19. [27]

    Elimination distances, blocking sets, and kernels for vertex cover

    Eva-Maria C Hols, Stefan Kratsch, and Astrid Pieterse. Elimination distances, blocking sets, and kernels for vertex cover. SIAM Journal on Discrete Mathematics , 36(3):1955--1990, 2022. https://doi.org/10.1137/20m1335285 doi:10.1137/20m1335285

    1955 doi

  20. [28]

    On editing graphs into 2-club clusters

    Hong Liu, Peng Zhang, and Daming Zhu. On editing graphs into 2-club clusters. In Jack Snoeyink, Pinyan Lu, Kaile Su, and Lusheng Wang, editors, Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference, FAW-AAIM 2012, Beij...

    2012 doi

  21. [29]

    Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Meirav Zehavi. Reducing CMSO model checking to highly connected graphs. In Ioannis Chatzigiannakis, Christos Kaklamanis, D \' a niel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages,...

    2018 doi

  22. [30]

    Recursive backdoors for SAT

    Nikolas M \" a hlmann, Sebastian Siebertz, and Alexandre Vigny. Recursive backdoors for SAT . In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) . Schloss Dagstuhl - Leibniz-Zentrum f \" u r...

    2021 doi

  23. [31]

    Algorithms and data structures for first-order logic with connectivity under vertex failures

    Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, and Alexandre Vigny. Algorithms and data structures for first-order logic with connectivity under vertex failures. In 49th International Colloquium on Automata, Languages, and Programming ( ICALP 2022...

    2022 doi

  24. [32]

    The complexity of optimal elimination trees

    Alex Pothen. The complexity of optimal elimination trees. Technical Report , 1988

    1988

  25. [33]

    First-order logic with connectivity operators

    Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny. First-order logic with connectivity operators. ACM Transactions on Computational Logic , 24(4):1--23, 2023. https://doi.org/10.1145/3595922 doi:10.1145/3595922

    2023 doi

  26. [34]

    Faster parameterized algorithm for cluster vertex deletion

    Dekel Tsur. Faster parameterized algorithm for cluster vertex deletion. Theory of Computing Systems , 65(2):323--343, 2021. https://doi.org/10.1007/s00224-020-10005-w doi:10.1007/s00224-020-10005-w

    2021 doi

  27. [35]

    Approximation and tidying—a problem kernel for s-plex cluster vertex deletion

    Ren \'e Van Bevern, Hannes Moser, and Rolf Niedermeier. Approximation and tidying—a problem kernel for s-plex cluster vertex deletion. Algorithmica , 62:930--950, 2012. https://doi.org/10.1007/s00453-011-9492-7 doi:10.1007/s00453-011-9492-7

    2012 doi

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.