1
$\begingroup$

Is there a natural (and hopefully well-known) maximization problem that is known to be in FPT? For instance, Vertex Cover is in FPT, but it's a minimization problem. I'm looking for natural maximization problems that are in FPT.

Edit (clarification): "I assume you mean a maximization problem that is in FPT when parameterized by the solution size." This is exactly what I meant to ask, as the first comment (by Jan Johannsen) points out.

Improve this question
$\endgroup$
2
  • $\begingroup$ I assume you mean a maximization problem that is in FPT when parameterized by the solution size. You should make that explicit. Otherwise there are many examples like Independent Set parameterized by tree-width. $\endgroup$
    – Jan Johannsen
    Jun 18, 2015 at 12:20
  • $\begingroup$ That's exactly what I meant. I'll edit my question accordingly. Thanks! $\endgroup$
    – Haden Hooyeon Lee
    Jun 18, 2015 at 16:47

1 Answer 1

Reset to default
5
$\begingroup$

Here are a few:

  • Max Cut: Can one color the vertices of an input graph $G$ black and white so that at least $k$ edges go from black to white?
  • Max Sat: Is there an assignment that satisfies at least $k$ clauses?
  • Max Leaf: Does $G$ have a spanning tree with at least $k$ leaves?
  • Longest Path / Cycle: Does $G$ contain a simple path / cycle on at least $k$ vertices?
  • 3-Set Packing: Given a set family ${\cal F}$ of sets of size $3$, are there $k$ pairwise disjoint sets in ${\cal F}$?
Improve this answer
$\endgroup$

Your Answer

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

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