8
$\begingroup$

The class $XP$ is the class of problems parameterized by $k$ that can be solved in time $n^{f(k)}$ for some function $f$ (each $k$ may require a different algorithm).

In their book on parameterized complexity, Downey and Fellows give an example of an XP-complete problem, which is called the $(2k + 1)$-pebbling game. The XP-hardness reduction is generic and reduces Turing machinery to this game.

The literature on other XP-hard problem is very sparse. I'd like to know if there are other known XP-hard problems, perhaps that use a more natural type of reduction.

Improve this question
$\endgroup$
17
  • 1
    $\begingroup$ If you happened to find the tree automata problem interesting, please let me know. I actively pursue research problems in this area and can provide some relevant references if interested. Also, for some info and references on pebbling problems with known time complexity lower bounds, see this past stack exchange post: cstheory.stackexchange.com/questions/33063/… $\endgroup$
    – Michael Wehar
    Commented Apr 15, 2017 at 5:50
  • 1
    $\begingroup$ In addition, for a couple years now, I've been seeking natural problems that are W[P]-complete. However, I've only found a few. I would be very interested in trying to build a list of W[P]-complete problems as well. :) $\endgroup$
    – Michael Wehar
    Commented Apr 15, 2017 at 5:50
  • 1
    $\begingroup$ @Michael Wehar : thanks for the insightful comments. I might indeed be interested in the tree automata problem, so if you have a reference I'd gladly take it. In fact, I'd be interested in any reference you have for other XP-completeness results, so if you have some you can provide that as an answer if you want. $\endgroup$
    – Manuel Lafond
    Commented Apr 16, 2017 at 2:21
  • 1
    $\begingroup$ For the tree automata problem, it was shown to be EXPTIME-complete in a paper called "On Computational Complexity of Basic Decision Problems of Finite Tree Automata". Then, I wrote a paper with a friend showing that when parameterized by the number of automata, this problem cannot be solved in less than $n^{\Omega(k)}$ time. This paper is titled "On the Complexity of Intersecting Regular, Context-free, and Tree Languages". Finally, in my dissertation titled "On the Complexity of Intersection Non-Emptiness Problems", I included that this problem is $XP$-complete. $\endgroup$
    – Michael Wehar
    Commented Apr 16, 2017 at 5:52
  • 1
    $\begingroup$ @user124864 Thank you very much!! :) $\endgroup$
    – Michael Wehar
    Commented Jun 6, 2018 at 20:02

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.