pith. sign in

arxiv: 2509.06880 · v2 · submitted 2025-09-08 · 💻 cs.CC

The Parameter Report: An Orientation Guide for Data-Driven Parameterization

Christian Komusiewicz , Nils Morawietz , Frank Sommer , Luca Pascal Staus This is my paper

Pith reviewed 2026-05-18 17:50 UTC · model grok-4.3

classification 💻 cs.CC
keywords parameterized algorithmsgraph parameterstreewidthvertex coverbenchmark graphsreal-world instancesFPTempirical analysis
0
0 comments X

The pith

On real-world graphs, treewidth is usually near n/10 while vertex cover is near n/2, making certain FPT algorithms much more practical than others.

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

The paper compares values of many graph parameters on a collection of benchmark graphs from real applications. It finds that some parameters like treewidth tend to be small relative to the number of vertices, while others like the vertex cover number are larger. This data helps decide which parameterization to use when designing algorithms for practical problems, since smaller parameters can make exponential-time algorithms feasible even if the base is larger. A reader cares because pure theory cannot predict which parameters will be small enough on actual data to matter for solving instances.

Core claim

We measure degree-related, neighborhood-based, modulator-based parameters and treewidth on real-world graphs and observe that the treewidth tw is almost always below n/3 and often close to n/10, while the vertex cover number vc is often only slightly below n/2. This suggests that O(2^tw) algorithms are practical on real instances whereas O(2^vc) is only marginally better than brute force exponential in n.

What carries the argument

Empirical measurement of parameter values such as treewidth and vertex cover number on a set of real-world benchmark graphs to assess their typical size relative to n.

Load-bearing premise

The selected benchmark graphs from real-world applications represent the kinds of graphs that typically appear in parameterized complexity applications.

What would settle it

Finding a substantial collection of real-world graphs where the treewidth is not below n/3 on average or where vertex cover is much smaller than n/2 would challenge the observed distributions.

Figures

Figures reproduced from arXiv: 2509.06880 by Christian Komusiewicz, Frank Sommer, Luca Pascal Staus, Nils Morawietz.

Figure 1
Figure 1. Figure 1: An annotated parameter hierarchy. For an edge from parameter [PITH_FULL_IMAGE:figures/full_fig_p011_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: An annotated parameter hierarchy for the pairwise minimum of [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Running time comparison between the parameters [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
read the original abstract

A strength of parameterized algorithmics is that each problem can be parameterized by an essentially inexhaustible set of parameters. Usually, the choice of the considered parameter is informed by the theoretical relations between parameters with the general goal of achieving FPT-algorithms for smaller and smaller parameters. However, the FPT-algorithms for smaller parameters usually have higher running times and it is unclear whether the decrease in the parameter value or the increase in the running time bound dominates in real-world data. This question cannot be answered from purely theoretical considerations and any answer requires knowledge on typical parameter values. To provide a data-driven guideline for parameterized complexity studies of graph problems, we present the first comprehensive comparison of parameter values for a set of benchmark graphs originating from real-world applications. Our study covers degree-related parameters, such as maximum degree or degeneracy, neighborhood-based parameters such as neighborhood diversity and modular-width, modulator-based parameters such as vertex cover number and feedback vertex set number, and the treewidth of the graphs. Our results may help assess the significance of FPT-running time bounds on the solvability of real-world instances. For example, the vertex cover number $vc$ of $n$-vertex graphs is often only slightly below $n/2$. Thus, a running time bound of $O(2^{vc})$ is only slightly better than a running time bound of $O(1.4^{n})$. In contrast, the treewidth $tw$ is almost always below $n/3$ and often close to $n/10$, making a running time of $O(2^{tw})$ much more practical on real-world instances. We make our implementation and full experimental data openly available. In particular, this provides the first implementations for several graph parameters such as 4-path vertex cover number and vertex integrity.

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

2 major / 1 minor

Summary. The manuscript presents the first comprehensive empirical comparison of multiple graph parameters—including degree-related (max degree, degeneracy), neighborhood-based (neighborhood diversity, modular-width), modulator-based (vertex cover, feedback vertex set), and treewidth—on a collection of benchmark graphs drawn from real-world applications. It concludes that, on these instances, the vertex cover number vc is typically only slightly below n/2 (so that O(2^vc) is only marginally better than O(1.4^n)), while treewidth tw is almost always below n/3 and often near n/10 (making O(2^tw) far more practical). The authors release implementations and full data, including first implementations for 4-path vertex cover and vertex integrity.

Significance. If the chosen benchmarks are representative of graphs arising in parameterized-complexity applications, the study supplies concrete, data-driven orientation that purely theoretical parameter comparisons cannot provide. The open release of code and experimental data for several parameters is a clear strength that supports reproducibility and enables follow-up work.

major comments (2)
  1. [Experimental design / benchmark collection] Benchmark selection and experimental setup: The paper states that the graphs 'originat[e] from real-world applications' and reports distributions such as 'tw is almost always below n/3' and 'often close to n/10', yet provides no explicit sampling frame, domain coverage analysis, instance counts, size distribution, or comparison against graphs on which FPT results are typically evaluated. This directly affects the load-bearing claim that the observed ratios supply general practical guidance.
  2. [Results / abstract claims] Quantitative claims and statistical presentation: The abstract and results assert specific thresholds ('almost always below n/3', 'only slightly below n/2', 'often close to n/10') without reference to the underlying tables or figures that would show medians, quartiles, number of instances, or any robustness checks against graph-size variation. This makes it impossible to assess whether the headline comparisons are robust or sensitive to the particular benchmark collection.
minor comments (1)
  1. [Notation] Clarify notation for parameters (e.g., consistent use of vc, tw, n) across text, tables, and figures.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. The comments highlight opportunities to strengthen the description of our experimental design and the presentation of quantitative results. We address each major comment below and will incorporate the suggested improvements in a revised version.

read point-by-point responses

  1. Referee: [Experimental design / benchmark collection] Benchmark selection and experimental setup: The paper states that the graphs 'originat[e] from real-world applications' and reports distributions such as 'tw is almost always below n/3' and 'often close to n/10', yet provides no explicit sampling frame, domain coverage analysis, instance counts, size distribution, or comparison against graphs on which FPT results are typically evaluated. This directly affects the load-bearing claim that the observed ratios supply general practical guidance.

    Authors: We acknowledge that a more explicit description of the benchmark collection would improve transparency. In the revised manuscript we will add a dedicated subsection on the experimental setup. This will specify the data sources and repositories used, report the total number of instances together with their size distribution (via summary statistics and a supplementary table or figure), and include a short discussion of how the chosen graphs relate to those commonly appearing in FPT evaluation studies. The full dataset is already publicly released, enabling readers to inspect the collection directly. These additions will support the claim that the observed parameter ratios provide practical guidance for real-world instances. revision: yes

  2. Referee: [Results / abstract claims] Quantitative claims and statistical presentation: The abstract and results assert specific thresholds ('almost always below n/3', 'only slightly below n/2', 'often close to n/10') without reference to the underlying tables or figures that would show medians, quartiles, number of instances, or any robustness checks against graph-size variation. This makes it impossible to assess whether the headline comparisons are robust or sensitive to the particular benchmark collection.

    Authors: We agree that the quantitative statements should be more explicitly tied to the supporting data. In the revision we will insert direct references to the relevant tables and figures (including those reporting medians, quartiles, and instance counts) immediately after each headline claim in the abstract and results sections. We will also add a short robustness analysis that stratifies the parameter ratios by graph size. Because the complete experimental data are already available online, independent verification of these statistics is possible. These changes will make the presentation more verifiable without altering the reported findings. revision: yes

Circularity Check

0 steps flagged

Purely empirical measurements of graph parameters on external benchmarks

full rationale

The paper reports observed distributions of parameters (treewidth, vertex cover, etc.) computed directly on a fixed collection of real-world benchmark graphs. No derivation, prediction, or uniqueness claim reduces to a fitted quantity, self-defined input, or self-citation chain inside the paper. The representativeness assumption is an external modeling choice, not an internal loop that forces the reported ratios by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The study rests on the assumption that the selected benchmark graphs are sufficiently representative of real-world instances to support general guidance about typical parameter sizes.

axioms (1)
  • domain assumption The selected benchmark graphs originating from real-world applications are representative of the graphs encountered in typical parameterized algorithm use cases.
    All comparative claims about 'often' and 'almost always' depend on this representativeness.

pith-pipeline@v0.9.0 · 5872 in / 1316 out tokens · 41521 ms · 2026-05-18T17:50:27.652705+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial

    cs.DS 2026-05 conditional novelty 7.0

    Algorithms for LS Vertex Cover achieve ℓ^{f(k)} n^{O(1)} time for ℓ equal to h-index, treewidth, modular-width, or a new modular-decomposition degree parameter, and extend to weighted d-improving swaps.

Reference graph

Works this paper leans on

60 extracted references · 60 canonical work pages · cited by 1 Pith paper

  1. [1]

    A 2-approximation algorithm for the undirected feedback vertex set problem.SIAM Journal on Discrete Mathematics, 12(3):289–297, 1999

    Vineet Bafna, Piotr Berman, and Toshihiro Fujito. A 2-approximation algorithm for the undirected feedback vertex set problem.SIAM Journal on Discrete Mathematics, 12(3):289–297, 1999

    work page 1999

  2. [2]

    Barefoot, Roger Entringer, and Henda Swart

    Curtis A. Barefoot, Roger Entringer, and Henda Swart. Vulnerability in graphs–a comparative survey.Journal of Combinatorial Mathematics and Combinatorial Computing, 1(38):13–22, 1987

    work page 1987

  3. [3]

    On bounded-degree vertex deletion parameterized by treewidth.Discrete Applied Mathematics, 160(1-2):53–60, 2012

    Nadja Betzler, Robert Bredereck, Rolf Niedermeier, and Johannes Uhlmann. On bounded-degree vertex deletion parameterized by treewidth.Discrete Applied Mathematics, 160(1-2):53–60, 2012

    work page 2012

  4. [4]

    Boisvert, Roldan Pozo, Karin Remington, Richard F

    Ronald F. Boisvert, Roldan Pozo, Karin Remington, Richard F. Barrett, and Jack J. Dongarra.Matrix Market: a web resource for test matrix collections, pages 125–137. Springer US, Boston, MA, 1997

    work page 1997

  5. [5]

    Minimum k-path vertex cover.Discrete Applied Mathematics, 159(12):1189–1195, 2011

    Bostjan Bresar, Frantisek Kardos, J´ an Katrenic, and Gabriel Semanisin. Minimum k-path vertex cover.Discrete Applied Mathematics, 159(12):1189–1195, 2011

    work page 2011

  6. [6]

    Structural parameterizations for boxicity.Algorithmica, 74(4):1453–1472, 2016

    Henning Bruhn, Morgan Chopin, Felix Joos, and Oliver Schaudt. Structural parameterizations for boxicity.Algorithmica, 74(4):1453–1472, 2016

    work page 2016

  7. [7]

    Multivariate algorithmics for NP-hard string problems.Bulletin of the EATCS, 114, 2014

    Laurent Bulteau, Falk H¨ uffner, Christian Komusiewicz, and Rolf Niedermeier. Multivariate algorithmics for NP-hard string problems.Bulletin of the EATCS, 114, 2014

    work page 2014

  8. [8]

    Parameterized complexity of vertex colouring.Discrete Applied Mathematics, 127(3):415–429, 2003

    Leizhen Cai. Parameterized complexity of vertex colouring.Discrete Applied Mathematics, 127(3):415–429, 2003

    work page 2003

  9. [9]

    Linear time split decomposition revisited.SIAM Journal on Discrete Mathematics, 26(2):499–514, 2012

    Pierre Charbit, Fabien de Montgolfier, and Mathieu Raffinot. Linear time split decomposition revisited.SIAM Journal on Discrete Mathematics, 26(2):499–514, 2012

    work page 2012

  10. [10]

    Decomposition of directed graphs.SIAM Journal on Algebraic Discrete Methods, 3(2):214–228, 1982

    William H Cunningham. Decomposition of directed graphs.SIAM Journal on Algebraic Discrete Methods, 3(2):214–228, 1982

    work page 1982

  11. [11]

    Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Ko- musiewicz, and Frances A. Rosamond. The first parameterized algorithms and computational experiments challenge. InProceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC ’16), volume 63 of LIPIcs, pages 30:1–30:9. Schloss Dagstuhl - Leibniz-Ze...

    work page 2016

  12. [12]

    Springer, 2016

    Reinhard Diestel.Graph Theory, 5th Edition, volume 173 ofGraduate Texts in Mathematics. Springer, 2016

    work page 2016

  13. [13]

    R. P. Dilworth. A decomposition theorem for partially ordered sets.Annals of Mathematics, 51(1):161–166, 1950

    work page 1950

  14. [14]

    Cluster vertex deletion: A parameterization between vertex cover and clique-width

    Martin Doucha and Jan Kratochv´ ıl. Cluster vertex deletion: A parameterization between vertex cover and clique-width. InProceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS ’12), volume 7464 ofLecture Notes in Computer Science, pages 348–359. Springer, 2012

    work page 2012

  15. [15]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows.Parameterized Complexity. Monographs in Computer Science. Springer, 1999. 24

    work page 1999

  16. [16]

    Dregi, and Pim van ’t Hof

    P˚ al Grøn˚ as Drange, Markus S. Dregi, and Pim van ’t Hof. On the computational complexity of vertex integrity and component order connectivity.Algorithmica, 76(4):1181–1202, 2016

    work page 2016

  17. [17]

    David Eppstein and Emma S. Spiro. The h-index of a graph and its application to dynamic subgraph statistics.Journal of Graph Algorithms and Applications, 16(2):543–567, 2012

    work page 2012

  18. [18]

    Fellows, Bart M

    Michael R. Fellows, Bart M. P. Jansen, and Frances A. Rosamond. Towards fully mul- tivariate algorithmics: Parameter ecology and the deconstruction of computational complexity.European Journal of Combinatorics, 34(3):541–566, 2013

    work page 2013

  19. [19]

    Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A

    Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, and Saket Saurabh. The complexity ecology of parameters: An illustra- tion using bounded max leaf number.Theory of Computing Systems, 45(4):822–848, 2009

    work page 2009

  20. [20]

    Stefan Felsner, Vijay Raghavan, and Jeremy P. Spinrad. Recognition algorithms for orders of small width and graphs of small dilworth number.Order, 20(4):351–364, 2003

    work page 2003

  21. [21]

    Seshadhri, Fan Wei, and Nicole Wein

    Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein. Finding cliques in social networks: A new distribution-free model.SIAM Journal on Computing, 49(2):448–464, 2020

    work page 2020

  22. [22]

    Note on dilworth’s decomposition theorem for partially ordered sets.Proceedings of the American Mathematical Society, 7(4):701–702, 1956

    Delbert R Fulkerson. Note on dilworth’s decomposition theorem for partially ordered sets.Proceedings of the American Mathematical Society, 7(4):701–702, 1956

    work page 1956

  23. [23]

    Parameterized algo- rithms for modular-width

    Jakub Gajarsk´ y, Michael Lampis, and Sebastian Ordyniak. Parameterized algo- rithms for modular-width. InProceedings of the 8th International Symposium on Parameterized and Exact Computation (IPEC ’13), volume 8246 ofLecture Notes in Computer Science, pages 163–176. Springer, 2013

    work page 2013

  24. [24]

    On structural parameteriza- tions of the bounded-degree vertex deletion problem.Algorithmica, 83(1):297–336, 2021

    Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On structural parameteriza- tions of the bounded-degree vertex deletion problem.Algorithmica, 83(1):297–336, 2021

    work page 2021

  25. [25]

    Structural parameterizations of vertex integrity

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, and Yota Otachi. Structural parameterizations of vertex integrity. InProceedings of the 18th International Conference and Workshops on Algorithms and Computation (WALCOM ’24), volume 14549 ofLecture Notes in Computer Science, pages 406–420. Springer, 2024

    work page 2024

  26. [26]

    Integrity in graphs: bounds and basics

    Wayne Goddard and Henda C Swart. Integrity in graphs: bounds and basics. Journal of Combinatorial Mathematics and Combinatorial Computing, 7:139–151, 1990

    work page 1990

  27. [27]

    Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le

    Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined notions of parameterized enumeration kernels with applications to matching cut enumeration.Journal of Computer and System Sciences, 123:76–102, 2022

    work page 2022

  28. [28]

    Gurobi Optimizer Reference Manual, 2023

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2023

    work page 2023

  29. [29]

    Swart, and Daniel Schult

    Aric Hagberg, Pieter J. Swart, and Daniel Schult. Exploring network structure, dynamics, and function using networkx. InProceedings of the 7th Python in Science Conference, 2008. 25

    work page 2008

  30. [30]

    Rudolf Halin.S-functions for graphs.Journal of Geometry, 8:171–186, 1976

    work page 1976

  31. [31]

    Harris and N

    David G. Harris and N. S. Narayanaswamy. A faster algorithm for vertex cover parameterized by solution size. InProceedings of the 41st International Symposium on Theoretical Aspects of Computer Science (STACS ’24), volume 289 ofLIPIcs, pages 40:1–40:18. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2024

    work page 2024

  32. [32]

    On structural parameterizations for the 2-club problem.Discrete Applied Mathematics, 185:79–92, 2015

    Sepp Hartung, Christian Komusiewicz, Andr´ e Nichterlein, and Ondrej Such´ y. On structural parameterizations for the 2-club problem.Discrete Applied Mathematics, 185:79–92, 2015

    work page 2015

  33. [33]

    Fixed- parameter algorithms for cluster vertex deletion.Theory of Computing Systems, 47(1):196–217, 2010

    Falk H¨ uffner, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier. Fixed- parameter algorithms for cluster vertex deletion.Theory of Computing Systems, 47(1):196–217, 2010

    work page 2010

  34. [34]

    Linear-time kernelization for feedback vertex set

    Yoichi Iwata. Linear-time kernelization for feedback vertex set. InProceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP ’17), volume 80 ofLIPIcs, pages 68:1–68:14. Schloss Dagstuhl - Leibniz- Zentrum f¨ ur Informatik, 2017

    work page 2017

  35. [35]

    Improved analysis of highest-degree branching for feedback vertex set.Algorithmica, 83(8):2503–2520, 2021

    Yoichi Iwata and Yusuke Kobayashi. Improved analysis of highest-degree branching for feedback vertex set.Algorithmica, 83(8):2503–2520, 2021

    work page 2021

  36. [36]

    Half-integrality, LP- branching, and FPT algorithms.SIAM Journal on Computing, 45(4):1377–1411, 2016

    Yoichi Iwata, Magnus Wahlstr¨ om, and Yuichi Yoshida. Half-integrality, LP- branching, and FPT algorithms.SIAM Journal on Computing, 45(4):1377–1411, 2016

    work page 2016

  37. [37]

    Bart M. P. Jansen.The power of data reduction: Kernels for fundamental graph problems. PhD thesis, Utrecht University, 2013

    work page 2013

  38. [38]

    Bart M. P. Jansen and Stefan Kratsch. On polynomial kernels for structural parameterizations of odd cycle transversal. InProceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC ’11), volume 7112 of Lecture Notes in Computer Science, pages 132–144. Springer, 2011

    work page 2011

  39. [39]

    Multivariate algorithmics for finding cohesive subnetworks

    Christian Komusiewicz. Multivariate algorithmics for finding cohesive subnetworks. Algorithms, 9(1):21, 2016

    work page 2016

  40. [40]

    Isolation concepts for efficiently enumerating dense subgraphs.Theoretical Computer Science, 410(38-40):3640–3654, 2009

    Christian Komusiewicz, Falk H¨ uffner, Hannes Moser, and Rolf Niedermeier. Isolation concepts for efficiently enumerating dense subgraphs.Theoretical Computer Science, 410(38-40):3640–3654, 2009

    work page 2009

  41. [41]

    Parameterized local search for vertex cover: When only the search radius is crucial

    Christian Komusiewicz and Nils Morawietz. Parameterized local search for vertex cover: When only the search radius is crucial. InProceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC ’22), volume 249 of LIPIcs, pages 20:1–20:18. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2022

    work page 2022

  42. [42]

    Code, data and experimental results for ”The parameter report: An orientation guide for data-driven parameterization”, 2025

    Christian Komusiewicz, Nils Morawietz, Frank Sommer, and Luca Pascal Staus. Code, data and experimental results for ”The parameter report: An orientation guide for data-driven parameterization”, 2025. Zenodo, https://doi.org/10.5281/ zenodo.17053998

    work page 2025

  43. [43]

    New races in parameterized algo- rithmics

    Christian Komusiewicz and Rolf Niedermeier. New races in parameterized algo- rithmics. InProceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS ’12), volume 7464 ofLecture Notes in Computer Science, pages 19–30. Springer, 2012. 26

    work page 2012

  44. [44]

    The PACE 2020 parameterized algorithms and computational experiments challenge: Treedepth

    Lukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, and Piotr Wygocki. The PACE 2020 parameterized algorithms and computational experiments challenge: Treedepth. InProceedings of the 15th International Sympo- sium on Parameterized and Exact Computation (IPEC ’20), volume 180 ofLIPIcs, pages 37:1–37:18. Schloss Dagstuhl - Leibniz...

    work page 2020

  45. [45]

    KONECT: the Koblenz network collection

    J´ erˆ ome Kunegis. KONECT: the Koblenz network collection. InProceedings of the 22nd International World Wide Web Conference (WWW ’13), pages 1343–1350. International World Wide Web Conferences Steering Committee / ACM, 2013

    work page 2013

  46. [46]

    Algorithmic meta-theorems for restrictions of treewidth.Algorith- mica, 64(1):19–37, 2012

    Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth.Algorith- mica, 64(1):19–37, 2012

    work page 2012

  47. [47]

    SNAP Datasets: Stanford large network dataset collection.http://snap.stanford.edu/data, June 2014

    Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection.http://snap.stanford.edu/data, June 2014

    work page 2014

  48. [48]

    Detecting feedback vertex sets of sizekinO ⋆(2.7k) time.ACM Transactions on Algorithms, 18(4):34:1–34:26, 2022

    Jason Li and Jesper Nederlof. Detecting feedback vertex sets of sizekinO ⋆(2.7k) time.ACM Transactions on Algorithms, 18(4):34:1–34:26, 2022

    work page 2022

  49. [49]

    Lick and Arthur T

    Don R. Lick and Arthur T. White. k-Degenerate graphs.Canadian Journal of Mathematics, 22(5):1082–1096, 1970

    work page 1970

  50. [50]

    James Nastos and Yong Gao. Bounded search tree algorithms for parametrized cograph deletion: Efficient branching rules by exploiting structures of special graph classes.Discrete Mathematics, Algorithms and Applications, 4(01):1250008, 2012

    work page 2012

  51. [51]

    Tree-depth, subgraph coloring and homomorphism bounds.European Journal of Combinatorics, 27(6):1022–1041, 2006

    Jaroslav Nesetril and Patrice Ossona de Mendez. Tree-depth, subgraph coloring and homomorphism bounds.European Journal of Combinatorics, 27(6):1022–1041, 2006

    work page 2006

  52. [52]

    Neil Robertson and Paul D. Seymour. Graph minors. II. algorithmic aspects of tree-width.Journal of Algorithms, 7(3):309–322, 1986

    work page 1986

  53. [53]

    Rossi and Nesreen K

    Ryan A. Rossi and Nesreen K. Ahmed. The network data repository with interactive graph analytics and visualization. InProceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI ’15), pages 4292–4293. AAAI Press, 2015

    work page 2015

  54. [54]

    Stephen B. Seidman. Network structure and minimum degree.Social networks, 5(3):269–287, 1983

    work page 1983

  55. [55]

    The graph parameter hierarchy, 2019

    Manuel Sorge and Mathias Weller. The graph parameter hierarchy, 2019. https: //manyu.pro/assets/parameter-hierarchy.pdf

    work page 2019

  56. [56]

    A contraction-recursive algorithm for treewidth

    Hisao Tamaki. A contraction-recursive algorithm for treewidth. InProceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC ’23), volume 285 ofLIPIcs, pages 34:1–34:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2023

    work page 2023

  57. [57]

    Corneil, Michel Habib, and Christophe Paul

    Marc Tedder, Derek G. Corneil, Michel Habib, and Christophe Paul. Simpler linear- time modular decomposition via recursive factorizing permutations. InProceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP ’08), volume 5125 ofLecture Notes in Computer Science, pages 634–645. Springer, 2008

    work page 2008

  58. [58]

    Bachelor’s thesis, TU Berlin, 2022

    Duc Long Tran.Expanding the Graph Parameter Hierarchy. Bachelor’s thesis, TU Berlin, 2022. 27

    work page 2022

  59. [59]

    PACE solver description: Bute-plus: A bottom-up exact solver for treedepth

    James Trimble. PACE solver description: Bute-plus: A bottom-up exact solver for treedepth. InProceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC ’20), volume 180 ofLIPIcs, pages 34:1–34:4. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2020

    work page 2020

  60. [60]

    Kirilin, Daniel A

    Ren´ e van Bevern, Artem M. Kirilin, Daniel A. Skachkov, Pavel V. Smirnov, and Oxana Yu. Tsidulko. Serial and parallel kernelization of multiple hitting set param- eterized by the dilworth number, implemented on the GPU.Journal of Computer and System Sciences, 139:103479, 2024. 28 A Instance Properties Table 7: Sizes and some additional parameter values f...

    work page 2024