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.

$\endgroup$
  • $\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 '15 at 12:20
  • $\begingroup$ That's exactly what I meant. I'll edit my question accordingly. Thanks! $\endgroup$ – Haden Hooyeon Lee Jun 18 '15 at 16:47
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}$?
$\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.