Nearly Perfect Bipartition is NP-complete
Carl Feghali · arXiv (Cornell University) · 2021
A graph $G = (V, E)$ has a nearly perfect bipartition $(S, V - S)$ iff every vertex in $V - S$ is adjacent to at most one vertex in $S$ and every vertex in $S$ is adjacent to at most one vertex in $V - S$. We show that the problem of deciding if a graph has a nearly perfect bipartition is NP-complete. This answers a question of Dunbar, Harris, Hedetniemi, Hedetniemi, McRae and Laskar from 1995.