9

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


5

Intuitively, the intermediate cases should be neither in P, nor NP-hard. Perhaps it depends exactly on what we mean by "intermediate case". Here is one interpretation for which we can prove something. Note: The Exponential-Time Hypothesis, or ETH, is that it is not the case that, for every constant $\epsilon>0$, SAT has an algorithm running in time $2^{...


2

The answer to your question is already contained in Fekete's paper. In Section 3, Fekete shows that the following problem GRID-EMPTY is NP-complete: Problem: GRID-EMPTY Instance: a set $S$ of $n$ grid points in the plane Question: Is there a simple polygon on this vertex set $S$ that does not contain any other grid points on its boundary or in its ...


Only top voted, non community-wiki answers of a minimum length are eligible