HOPS web view
This page lists:
Parameters
The hierarchy of parameters is still under construction – contributions to its refinement are greatly appreciated. The following diagram shows parameter inclusions. Arrow styles: normal for linear, thin for polynomial, dotted for exponential, gray for “under construction”. Arrows that can be implied by other arrows are hidden for clarity.
We follow with a complete comparison of all pairs of parameters. Row-to-column meaning is: green for inclusion (bounded), red for exclusion (unbounded), blue for “under construction” The above diagram shows only a meaningful subset of the green relations below.
- acyclic chromatic number
- arboricity
- average degree
- average distance
- bandwidth
- bisection bandwidth
- book thickness
- boolean width
- boxicity
- branch width
- carving-width
- chordality
- chromatic number
- clique cover number
- clique width
- cutwidth
- degeneracy
- diameter
- distance to bipartite
- distance to block
- distance to bounded components
- distance to chordal
- distance to cluster
- distance to co-cluster
- distance to cograph
- distance to complete
- distance to constant components
- distance to edgeless
- distance to forest
- distance to interval
- distance to linear forest
- distance to maximum degree
- distance to outerplanar
- distance to perfect
- distance to planar
- distance to stars
- domatic number
- domination number
- edge clique cover number
- edge connectivity
- feedback edge set
- feedback vertex set
- genus
- girth
- h-index
- inf-flip-width
- linear clique-width
- linear rank width
- maximum clique
- maximum degree
- maximum independent set
- maximum induced matching
- maximum leaf number
- maximum matching
- minimum degree
- modular-width
- neighborhood diversity
- odd cycle transversal
- pathwidth
- pathwidth+maxdegree
- radius-r flip-width
- rank width
- shrub-depth
- topological bandwidth
- treedepth
- treewidth
- twin width
- twin-cover number
- vertex cover
- vertex integrity
Graph classes
Some parameters are derived from associated graph classes. Graph classes can be also used as witnesses of proper inclusions. For these purposes, we use the following graph class hierarchy. We assume that all of the graph class inclusions are proper.
We aim to have here only the graph classes that influence parameter inclusions. Please, see Information System on Graph Classes and their Inclusions (ISGCI) for an exhaustive list of graph classes and their inclusions.
- bipartite
- block
- bounded components
- bounded degree
- chordal
- cluster
- co-cluster
- cograph
- complete
- connected
- constant components
- cycle
- cycles
- disjoint cycles
- edgeless
- forest
- grid
- interval
- linear forest
- outerplanar
- parameter degree
- path
- perfect
- planar
- stars
- tree
Sources
- Torunczyk2023
- Tran2022
- SchroderThesis
- Sorge2019
- Ganian2019
- Froemmrich2018
- Diestel2017
- ParameterizedAlgorithms2015
- Jansen2013
- Belmonte2013
- GanianTwinCover2012
- BuiXuan2011
- Sasak2010
- spanningTreesManyLeaves2008
- Oum2006
- courcelle2000
- Bodlaender1998
- BodlaenderMohring1993
- RobertsonSymour1991
- RobertsonSymour1986V
- RobertsonSymour1986
- Chung1985