Back to Search Start Over

The complexity of the perfect matching‐cut problem.

The complexity of the perfect matching‐cut problem.

Authors :
Bouquet, Valentin
Picouleau, Christophe
Source :
Journal of Graph Theory. Oct2024, p1. 31p. 15 Illustrations.
Publication Year :
2024

Abstract

PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five‐regular graphs, for graphs of diameter three, and for bipartite graphs of diameter four. We show that there exist polynomial‐time algorithms for the following classes of graphs: claw‐free, P5 ${P}_{5}$‐free, diameter two, bipartite with diameter three, and graphs with bounded treewidth. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
03649024
Database :
Academic Search Index
Journal :
Journal of Graph Theory
Publication Type :
Academic Journal
Accession number :
180186648
Full Text :
https://doi.org/10.1002/jgt.23167