8

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.

Manuel Lafond
  • 312
  • 1
  • 6
  • Intersection Non-emptiness for tree automata (parameterized by the number of auatomata) is an example of an XP-complete problem. There are some parameterized pebbling problems that are known to be XP-complete as well. I'll try to share a few references later tonight. Thanks for asking this question. Creating such a list would be very helpful!! :) – Michael Wehar Apr 14 '17 at 23:48
  • Showing that a parameterized decision problem $X$ is XP-hard is similar to proving that $X$ has a time complexity lower bound. In general, the way that you show $X$ is XP-hard is by reducing the computation of an $n^k$ time bounded Turing machine on an input of length $n$ to an instance of $f(k)$-$X$. Using the time hierarchy theorem, this is essentially the same approach for proving that $X$ has an $n^{g(k)}$ time complexity lower bound where $f(g(k)) \leq k$. – Michael Wehar Apr 15 '17 at 05:48
  • 1
    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: https://cstheory.stackexchange.com/questions/33063/are-there-more-polynomial-time-problems-with-complexity-lower-bounds – Michael Wehar Apr 15 '17 at 05:50
  • 1
    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. :) – Michael Wehar Apr 15 '17 at 05:50
  • 1
    @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. – Manuel Lafond Apr 16 '17 at 02:21
  • 1
    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. – Michael Wehar Apr 16 '17 at 05:52
  • I wish I had some more references to other people's work, but I'm in the same boat as you. I'm trying to find other problems that are known to be $XP$-complete. :) – Michael Wehar Apr 16 '17 at 05:55
  • @user124864 This is great!! I didn't know about the $W[P]$ complete problem that you mentioned. Could you possibly provide a reference. I would very much like to learn more about it. :) – Michael Wehar Jun 06 '18 at 18:11
  • @user124864 For XP complete problems, I wish I had some other references, but the only XP complete problems that I can think of are emptiness problems for automata, pebbling problems, and machine simulations problems. – Michael Wehar Jun 06 '18 at 18:25
  • 1
    @user124864 Thank you very much!! :) – Michael Wehar Jun 06 '18 at 20:02
  • 1
    @user124864 I will look into this. Thanks for sharing!! :) – Michael Wehar Jun 06 '18 at 21:40
  • @user124864 Haven't yet had a chance to look into your queries, but I hope to this weekend. :) – Michael Wehar Jun 08 '18 at 18:59
  • I recently found a paper that lists P-complete problems. Maybe some of them can be generalized to XP-complete parameterized problems. See here: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.2644 – Michael Wehar Apr 08 '20 at 16:51
  • Recently the following paper was shared with me that suggests a new W[P]-complete problem. I thought that this might be relevant. :) – Michael Wehar Sep 29 '22 at 15:44
  • 1
    See here: https://link.springer.com/article/10.1007/s10458-022-09578-2 – Michael Wehar Sep 29 '22 at 15:45
  • 1
    @Michael Wehar : while searching for W[P]-complete problems, I ended up here and I just saw that you added comments to this. Thanks for sharing, again! Also, in case you have the answer, a question here asks for the W classification problem for partial set cover, where the difficulty is making a circuit is that one must count the number of covered elements: https://cstheory.stackexchange.com/questions/52821/wt-containment-of-partial-covering-problems – Manuel Lafond May 12 '23 at 20:59
  • Thank you very much for sharing this!! :) – Michael Wehar May 13 '23 at 15:21

0 Answers0