The complexity of the vertex-minor problem

Dahlberg, E.A.; Helsen, J.; Wehner, S.D.C.

doi:10.1016/j.ipl.2021.106222

The complexity of the vertex-minor problem

Title

The complexity of the vertex-minor problem

Author

Dahlberg, E.A. (TU Delft QID/Wehner Group; TU Delft QuTech Advanced Research Centre)
Helsen, J. (TU Delft Quantum Information and Software; TU Delft QuTech Advanced Research Centre)
Wehner, S.D.C. (TU Delft Quantum Information and Software; TU Delft Quantum Internet Division; TU Delft QuTech Advanced Research Centre)

Department

Quantum Internet Division

Date

2022

Abstract

A graph H is a vertex-minor of a graph G if it can be reached from G by the successive application of local complementations and vertex deletions. Vertex-minors have been the subject of intense study in graph theory over the last decades and have found applications in other fields such as quantum information theory. Therefore it is natural to consider the computational complexity of deciding whether a given graph G has a vertex-minor isomorphic to another graph H. Here we prove that this decision problem is NP-complete, even when restricting H and G to be circle graphs, a class of graphs that has a natural relation to vertex-minors.

Subject

Circle graphs
Computational complexity
NP-complete
Vertex-minor

To reference this document use:

http://resolver.tudelft.nl/uuid:c8fc9546-a1ea-4a66-a822-ec7a3ee69cfa

DOI

https://doi.org/10.1016/j.ipl.2021.106222

ISSN

0020-0190

Source

Information Processing Letters, 175

Part of collection

Institutional Repository