HOPS Documentation
This website uses several things that deserve to be explained in detail.
Structure of HOPS
This website contains a collection of parameters, some relevant graph classes, their relations, and sources which established the results.
As one may view parameters in several different ways let us introduce our viewpoint.
Parameters
Parameterized problem is a decision problem along with a natural number parameter.
In our case, the input is a graph and parameter which tells us something about the graph – e.g. size of its vertex cover.
Note that the input instance is not guaranteed to have the correct parameter value, e.g. the vertex cover parameter is way smaller than the actual vertex cover size.
However, for inputs with an incorrect parameter value we may return an incorrect answer; so we assume correct value and answer arbitrarily if along the way we reach a contradiction.
For the sake of simplicity, let us fix the parameter to be the vertex cover in the following discussion.
Any fixed graph has a fixed value of its minimum vertex cover.
We can extend this notion also to graph classes, saying that has bounded vertex cover if there is a number such that all graphs have bounded vertex cover .
This relation can also be viewed from the other side – fix value of a parameter , and let be all graphs with vertex cover at most .
Naturally, this creates a sequence of graphs where is maximal reasonable value (could be ).
For vertex cover, we observe that as bigger vertex cover is “stronger”.
This relation is typical for parameters, however, is not necessarily required and it is feasible to have parameters that do not satisfy it, e.g. girth satisfies the inverse inclusion.
Parameter relations
We say that a parameter is “smaller” than on a graph class if for every for some computable function .
This is same as saying that if is bounded on , then is bounded on .
Usually, we consider to be the graph class of bounded , so the assumption is trivially true.
However, some parameters are defined well just for a fixed graph class and one cannot define a graph class that contains all elements with a bounded parameter value (e.g. shrub-depth).
Observe that if is “smaller” than it does not mean that its value is smaller arithmetically.
The point is that bounded implies bounded , so cannot grow arbitrarily big when is not changing.
On this page, we depict smaller parameters as being (generally) the ones on the bottom.
Relations among parameters and graphs
As a degenerate case of parameter relations, we may consider to be a fixed graph class .
If has bounded value of parameter then indeed .
On the other hand, we can show that a graph class contains a sequence of graphs where the parameter value grows arbitrarily high so the graph class has unbounded .
This website contains diagrams that convey the graph-parameter relations, read the legend for notation.
Inference of relations
Upper bound relation is reflexive and transitive, hence, we can serially compose the known upper bound relations.
The resulting function is the result of function composition, i.e., if and , then .
In the other direction, we may know that does NOT upper bounds .
Because of transitivity this implies that if and while , then we can infer , , and .
Both of these inferences are shown in the following picture.
Showing the inferred relations in Hasse diagrams makes them harder to read, so we hide the transitive relations.
We also hide the incomparabilities as there is just too many of them.
Instead, all the pairwise relations are shown in separate relation tables.
Some parameters are defined as a combination of two other parameters, i.e., parameter means that both and are bounded.
We can easily infer that and .
In this case, there is an inference that if and then which makes the former relations transitive of the latter and can be hidden in the Hasse view, simplifying it.
Refining complexity results and how does the hierarchy help
While having a problem in mind we can show it is either tractable or hard.
Diagrams in HOPS show how those results propagate.
Tractabilities propagate up while hardnesses propagate down.
For example, we observe that maximum clique is upper bounded by chromatic number.
This means that all graphs with chromatic number have maximum clique at most (in this specific case is known to be a linear function).
Notice that when we substitute a parameter for a computable function of the other parameter (substitute for ) an algorithm that was FPT remains FPT, and an XP algorithm remains XP.
Hence, our tractability results automatically also work for any parameter that upper bounds maximum clique.
So to improve our results, we can now show that maximum clique problem remains W[1]-hard even when parameterized by chromatic number – this result is indeed also known to be true.
A natural question now is: how far up can we push the hardness and how far down can we push tractability?
The following picture shows an example work-in-progress state for some problem.