The Parameter Report
An Orientation Guide for Data-Driven Parameterization
Exact parameter values for the neighborhood-based parameters
Image: pyplotTo provide a guideline for the choice of practically meaningful structural parameterizations for graph problems, we computed parameter values for a representative set of small to mid-sized real-world instances.
We present some diagrams showing the distribution of the parameter values in the benchmark data set. Solid black lines show the median, green dashed lines the average, red dotted lines are 90th and 10th percentiles.
A comprehensive description of our findings is presented in
Christian Komusiewicz, Nils Morawietz, Frank Sommer, and Luca Staus. The Parameter Report: An Orientation Guide for Data-Driven ParameterizationExternal link. Journal of Graph Algorithms and ApplicationsExternal link, 30(1), 385–419.
Findings
Exact parameter values for degree-based parameters
Image: pyplotIn the degree-based parameter family, all parameters with exception of the maximum degree are reasonably small. As exepected, degeneracy is typically very small but already the h-index takes on reasonably small parameter values.
In contrast, the neighborhood-based parameters (shown above) are all rather large.
For the vertex deletion- and tree-based parameters (shown below), we can see that the vertex cover number is typically quite large. Vertex deletion parameters towards bounded maximum degree or cluster graphs or cographs are somewhat smaller. The overall smallest vertex-deletion based parameter is vertex integrity; the tree-based parameters treedepth and treewidth are much smaller.
Further Links
Exact parameter values for modulator- and tree-based parameters
Image: pyplotThe experimental data and the computed parameter values is available at https://git.uni-jena.de/algo-engineering/data/graph-repoExternal link. Since the study is currently limited to undirected graphs, all results can be found in the unweighted-undirected folder.
The source code for computing the parameters is available at https://git.uni-jena.de/algo-engineering/param-reportExternal link.
If you are aware of small to medium-size graphs that could be added to the repository or would like to propose the addition of a further parameter to the analysis, please contact us.