Charles Explorer logo
🇬🇧

On the Hardness of Switching to a Small Number of Edges

Publication at Faculty of Mathematics and Physics |
2016

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.

Jelinkova et al. [DMTCS 13, no. 2, 2011] presented a proof that it is NP-complete to decide if the input graph can be switched to contain 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. sek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014].