8
$\begingroup$

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?

$\endgroup$
10
$\begingroup$

I think Figure 1 (page 4) of the paper "New Races in Parameterized Algorithmics" 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.

$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Juho Mar 22 '15 at 20:21
1
$\begingroup$

ISGCI just recently added parameters. They are still in beta at the time of writing, but one might look at diameter: 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 (see Figure 1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.