On the Hardness of Switching to a Small Number of Edges
Vít Jelínek, Eva Jelínková, Jan Kratochvı́l · Journal of Graph Theory · 2026
ABSTRACT Seidel's switching is a graph operation which makes a given vertex adjacent to precisely those vertices to which it was non‐adjacent before, while keeping the rest of the graph unchanged. Two graphs are called switching‐equivalent if one can be made isomorphic to the other one by a sequence of switches. Jelínková et al. [DMTCS 13, no. 2, 2011] presented a proof that it is NP‐complete to decide whether the input graph is switching‐equivalent to a graph that contains at most a given number of edges. There turns out to be a flaw in their proof. We present a correct proof. Furthermore, we prove that the problem remains NP‐complete even when restricted to graphs whose density is bounded from above by an arbitrary fixed constant. This partially answers a question of Matoušek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014].