On the Hardness of Switching to a Small Number of Edges
Journal of Graph Theory · 2026-10 · 113 (2) · 237-251
DOI: 10.1002/jgt.70063 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 14.05.2026. Verfasst von Vít Jelínek und 2 weiteren Autor:innen. Die Arbeit nennt 29 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Grantová Agentura České Republiky.
Abstract (Originalsprache)
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].
Förderung
- Grantová Agentura České Republiky
Zitieren
APA
Jelínek, V., Jelínková, E., & Kratochvíl, J. (2026). On the Hardness of Switching to a Small Number of Edges. Journal of Graph Theory, 113(2), 237-251. https://doi.org/10.1002/jgt.70063
Vancouver
Jelínek V, Jelínková E, Kratochvíl J. On the Hardness of Switching to a Small Number of Edges. Journal of Graph Theory. 2026;113(2):237-251. doi:10.1002/jgt.70063
BibTeX
@article{Jelnek2026,
author = {Jelínek, Vít and Jelínková, Eva and Kratochvíl, Jan},
title = {On the Hardness of Switching to a Small Number of Edges},
journal = {Journal of Graph Theory},
year = {2026},
volume = {113},
number = {2},
pages = {237--251},
doi = {10.1002/jgt.70063}
}
EUVIMED