The Parameter Report: An Orientation Guide for Data-Driven Parameterization
Christian Komusiewicz, Nils Morawietz, Frank Sommer, Luca Pascal Staus · 2025
Read The Parameter Report: An Orientation Guide for Data-Driven Parameterization by Christian Komusiewicz, Nils Morawietz, Frank Sommer, Luca Pascal Staus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-06880.txt.
Introduction
Which algorithm parameters actually take small values on real graphs? Christian Komusiewicz and three co-authors answer with data in a 2025 algorithms paper. Parameterized algorithmics designs methods whose cost depends on a chosen parameter, and smaller parameters usually mean slower-growing guarantees. Theory alone cannot say whether real instances reward that trade.
The authors measured many parameters across benchmark graphs from real applications: degree-based ones like maximum degree and degeneracy, neighborhood-based ones like modular-width, modulator-based ones like vertex cover number, and treewidth. Some parameters disappoint: vertex cover numbers often sit just below half the graph size, so gains are slim. Treewidth, by contrast, is usually far below the graph size, making treewidth-based running times genuinely practical. Code and full experimental data are openly available, including first implementations of several parameters.
Catalog record
| CREATOR | Christian Komusiewicz, Nils Morawietz, Frank Sommer, Luca Pascal Staus |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 89 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06880
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Parameter Report: An Orientation Guide for Data-Driven Parameterization Christian Komusiewicz, Nils Morawietz, Frank Sommer, Luca Pascal Staus 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 𝗏𝖼 \mathsf{vc} of n n -vertex graphs is often only slightly below n / 2 n/2 . Thus, a running time bound of 𝒪 ( 2 𝗏𝖼 ) \mathcal{O}(2^{\mathsf{vc}}) is only slightly better than a running time bound of 𝒪 ( 1.4 n ) \mathcal{O}(1.4^{n}) . In contrast, the treewidth 𝗍𝗐 \mathsf{tw} is almost always below n / 3 n/3 and often close to n / 9 n/9 , making a running time of 𝒪 ( 2 𝗍𝗐 ) \mathcal{O}(2^{\mathsf{tw}}) much more practical on real-world instances. We make our implementation and full experimental data openly available 1 1 1 The source code of all solvers, all graph data and our experimental results are all publicly available at https://www.fmi.uni-jena.de/en/19723/parameter-report . . In particular, this provides the first implementations for several graph parameters such as 4-path vertex cover number and vertex integrity. 1 Introduction In the quest to cope with computational intractability, parameterized algorithmics offers an approach for designing exact algorithms with practically useful running time guarantees. The aim is to design FPT-algorithms, that is, algorithms with running time f(k)\cdot\operatorname{poly}(n) where k is a problem-specific parameter and n denotes the overall input size. Now, if k is small on real-world instances and if f does not grow too quickly then these algorithms have a practically feasible running time. The classic example for this approach is the NP-hard Vertex Cover problem where the input is a graph G and a number k and the task is to decide whether G contains a set of at most k vertices that cover all edges. Vertex Cover can be easily seen to be solvable in 2^{k}\cdot\operatorname{poly}(n) time by a simple branching algorithm. After achieving such a first FPT-algorithm for a problem at hand, the daily trade of researchers in parameterized algorithms is now to chip away from the rock of intractability by providing better and better FPT-algorithms [ 15 ] . There are two pathways to achieve this: The first is to improve FPT-algorithms for the parameter k at hand which means first and foremost to improve the superpolynomial running time part f(k) . For Vertex Cover this pathway has been thoroughly explored, with the current best FPT-algorithm having a running time of \mathcal{O}(1.26^{k}+n) [ 31 ] . The second pathway is to consider smaller and smaller parameters: After developing an FPT-algorithm for some parameter k , one may try to find an FPT-algorithm for some parameter k^{\prime} which is never larger than k . For Vertex Cover , such a parameter is for example the treewidth \mathsf{tw} of G for which an algorithm with running time \mathcal{O}(2^{\mathsf{tw}}\cdot n) is known. 2 2 2 Here, one assumes that one is given a tree decomposition of width \mathsf{tw} . From a purely theoretical standpoint, the latter algorithm is usually deemed preferable: For Vertex Cover , the parameterization by the solution size bound k is essentially a parameterization by the vertex cover number of G , denoted \mathsf{vc} . This number is the size of a smallest vertex cover of G . Due to the known parameter relation \mathsf{vc}\geq\mathsf{tw} , any FPT-algorithm for the treewidth trivially implies an FPT-algorithm for the vertex cover number \mathsf{vc} . This line of research in parameterized algorithms is commonly referred to as multivariate algorithmics [ 7 , 18 , 19 , 39 , 43 ] or structural parameterization [ 6 , 24 , 32 , 38 ] . There are at least two potential pitfalls with this approach: First, at least for graph problems, the space of known parameterizations is huge and ever-growing. Hence, it is infeasible to thoroughly study all parameterizations and essentially every choice of a parameter subset in an algorithmic study is in some sense arbitrary. Second, the improvement in the parameter dimension often comes at the cost of an increased running time. In the Vertex Cover example, the running time bound for treewidth is larger than for the vertex cover number. Hence, it is not clear whether the theoretical improvement in the parameter dimension carries over to better algorithms in practice or whether the running times actually get worse. To avoid both pitfalls, we propose a data-driven approach, where the actual values of parameters in real-world instances guide the navigation through parameter space: When going from a parametrization k to a parameterization k^{\prime} , we may then choose the parameterization which has smaller values in practice so any obtained FPT-algorithms will be more relevant in practice. Moreover, when knowing the typical relation between the values of two parameters in real-world instances, we may better compare known running time bounds. Our Contribution. To facilitate this data-driven approach, we present a study on the values of 19 popular graph parameters on a benchmark set of 87 graphs from real-world applications. The 19 parameters are as follows: • Degree-related: maximum degree ( \Delta ), h -index, degeneracy ( d ), {2}\textnormal{-}\mathsf{core} , and {3}\textnormal{-}\mathsf{core} , c -closure ( c ), and weak- c -closure ( \gamma ). • Neighborhood-based: neighborhood diversity ( \mathsf{nd} ), dilworth-number ( \nabla ), modular-width ( \mathsf{mw} ), and split-width ( \mathsf{sw} ). • Modulator-based: vertex cover number ( \mathsf{vc} ), 1 -bounded-degree deletion number ( {1}\textnormal{-}\mathsf{bdd} ), 2 -bounded-degree deletion number ( {2}\textnormal{-}\mathsf{bdd} ), 4 -path vertex cover number ( {4}\textnormal{-}\mathsf{pvc} ), cluster vertex deletion number ( \mathsf{cvd} ), distance to cograph ( \mathsf{dco} ), and feedback vertex set number ( \mathsf{fvs} ). • Treewidth ( \mathsf{tw} ). We present various ways to compare the parameter values in an algorithmic setting and describe some scenarios how the parameter values may be used to guide the exploration of parameter space. Our results indicate, for example, that the running time bound of \mathcal{O}(2^{\mathsf{tw}}\cdot n) for the Vertex Cover problem is better than the \mathcal{O}(1.26^{\mathsf{vc}}+n) -time bound. We make the source code of the implementation of the algorithms for computing the considered graph parameters and all the experimental data fully available 3 3 3 For several parameters, for