Solving Partition Problems Almost Always Requires Pushing Many Vertices Around

Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1

A fundamental graph problem is to recognize whether the vertex set of a graph $G$ can be bipartitioned into sets $A$ and $B$ such that $G[A]$ and $G[B]$ satisfy properties ${\Pi }_A$ an…