# Tag Info

6

This is an interesting (and surprising) example for a P $\to$ NP-hard $\to$ P $\to$ NP-hard $\to \cdots$ phase transition: Deciding if a complete graph on $n$ vertices, in which each vertex has a strict ranking of all other vertices, admits a popular matching is in P for odd $n$ and NP-hard for even $n$. (The parameter is the vertex number $n$.) The ...

0

This problem is in NP. (easy to verify a given solution) Subset sum is NP-Complete, so this problem can be reduced to subset sum.

0

Especially when looking at the Knapsack problem later on, this NP-complete problem might be a good fit: Number guessing, where you can only guess single numbers till you've got it right.

3

The problem seems to be NP-complete. My reduction is from Planar 1-in-3-SAT, just like in their paper. For each variable, take $2k$ vertices. Each of these is covered by two 4-sets and each 4-set covers two consecutive vertices. Thus, we need to take every second of the 4-sets for each variable, this corresponds to TRUE/FALSE. The other two vertices of the 4-...

Top 50 recent answers are included