<p><a href="http://www.graphclasses.org/index.html" rel="nofollow">ISGCI</a> just recently added parameters. They are still in beta at the time of writing, but one might look at <a href="http://www.graphclasses.org/classes/par_6.html" rel="nofollow">diameter</a>: minimum dominating set is a minimal upper bound, and by following the trail upwards, we find maximum independent set, and so forth.</p>

<p>They reference e.g. the 2013 manuscript of Sorge and Weller, available <a href="http://fpt.akt.tu-berlin.de/msorge/parameter-hierarchy.pdf" rel="nofollow">here</a> (see Figure 1).</p>

CC BY-SA 3.0
2015-03-29T18:15:31.250Z
2015-03-29T18:15:31.250Z
Juho
<p>I think Figure 1 (page 4) of the paper "<a href="http://fpt.akt.tu-berlin.de/publications/fpt-races.pdf">New Races in Parameterized Algorithmics</a>" of Komusiewicz and Niedermeier is what you are looking for.</p>

<p>In particular, being in XP for the parameter diameter implies being in XP for parameters: min dominating set, max independent set, minimum clique cover, distance to cograph, distance to co-cluster, distance to clique, distance to cluster, vertex cover, and cluster editing.</p>

CC BY-SA 3.0
2015-03-22T20:21:27.383Z
Great, thanks! I had a feeling I had seen a figure like this before, but couldn't locate it. One might want to notice that "average degree" can be added to the figure, and connected with a line to "degenerency".
Juho
CC BY-SA 3.0
2015-03-22T20:03:33.870Z
2015-03-22T20:03:33.870Z
user
<p>Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if it can be solved in $n^{f(k)}$ time). Does this imply solvability in XP time for other interesting parameters?</p>

<p>If so, is there maybe even some more or less "standard" list or web of parameters and how they relate documented somewhere?</p>

<graph-theory><parameterized-complexity><fixed-parameter-tractable>
Implications of a problem being in XP when parameterized by diameter
Juho
# Implications of a problem being in XP when parameterized by diameter

(Asked by: username_0 on 2015-03-22)

Let $X$ be an NP-complete graph problem. Suppose $X$ is solvable in polynomial time on graphs of bounded diameter. In other words, $X$ parameterized by diameter is in XP. (Recall a problem is in XP if it can be solved in $n^{f(k)}$ time). Does this imply solvability in XP time for other interesting parameters?

If so, is there maybe even some more or less "standard" list or web of parameters and how they relate documented somewhere?

**Tags:** graph-theory, parameterized-complexity, fixed-parameter-tractable

---

## 2 answers

### Answer by username_1 on 2015-03-22. Score: 10 | Accepted answer

I think Figure 1 (page 4) of the paper "[New Races in Parameterized Algorithmics](http://fpt.akt.tu-berlin.de/publications/fpt-races.pdf)" of Komusiewicz and Niedermeier is what you are looking for.

In particular, being in XP for the parameter diameter implies being in XP for parameters: min dominating set, max independent set, minimum clique cover, distance to cograph, distance to co-cluster, distance to clique, distance to cluster, vertex cover, and cluster editing.

> **Comments:**
> **username_0**: Great, thanks! I had a feeling I had seen a figure like this before, but couldn't locate it. One might want to notice that "average degree" can be added to the figure, and connected with a line to "degenerency".  

---

### Answer by username_0 on 2015-03-29. Score: 1

[ISGCI](http://www.graphclasses.org/index.html) just recently added parameters. They are still in beta at the time of writing, but one might look at [diameter](http://www.graphclasses.org/classes/par_6.html): minimum dominating set is a minimal upper bound, and by following the trail upwards, we find maximum independent set, and so forth.

They reference e.g. the 2013 manuscript of Sorge and Weller, available [here](http://fpt.akt.tu-berlin.de/msorge/parameter-hierarchy.pdf) (see Figure 1).


---

