<p>Here are a few:</p>

<ul>
<li>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?</li>
<li>Max Sat: Is there an assignment that satisfies at least $k$
clauses?</li>
<li>Max Leaf: Does $G$ have a spanning tree with at least $k$
leaves?</li>
<li>Longest Path / Cycle: Does $G$ contain a simple path / cycle on at least $k$
vertices? </li>
<li>3-Set Packing: Given a set family ${\cal F}$ of sets of
size $3$, are there $k$ pairwise disjoint sets in ${\cal F}$?</li>
</ul>

CC BY-SA 3.0
2015-06-17T21:00:28.017Z
2015-06-17T21:52:14.187Z
2015-06-17T21:52:14.187Z
daniello
<p>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. </p>

<p>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. </p>

CC BY-SA 3.0
2015-06-18T12:20:23.547Z
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.
Jan Johannsen
CC BY-SA 3.0
2015-06-18T16:47:33.767Z
That's exactly what I meant. I'll edit my question accordingly. Thanks!
Haden Hooyeon Lee
<parameterized-complexity><fixed-parameter-tractable>
Natural maximization problems in FPT
Haden Hooyeon Lee
# Natural maximization problems in FPT

(Asked by: username_0 on 2015-06-17)

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.

**Tags:** parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: 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.  
> **username_0**: That's exactly what I meant. I'll edit my question accordingly. Thanks!  

---

## 1 answers

### Answer by username_2 on 2015-06-17. Score: 5 | Accepted answer

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}$?


---

