<abstract xmlns="http://www.w3.org/1999/xhtml">We show that the problem of deciding whether the edge set of a bipartite graph can be partitioned into three matchings, of size k1, k2 and k3 is NP-complete, even if one of the matchings is required to be perfect. We also show that the problem of deciding whether the edge set of a simple graph contains a perfect matching and a disjoint matching of size k or not is NP-complete, already for bipartite graphs with maximum degree 3. It also follows from our construction that it is NP-complete to decide whether in a bipartite graph there is a perfect matching and a disjoint matching that covers all vertices whose degree is at least 2.</abstract>

We show that the problem of deciding whether the edge set of a bipartite graph can be partitioned into three matchings, of size k1, k2 and k3 is NP-complete, even if one of the matchings is required to be perfect. We also show that the problem of deciding whether the edge set of a simple graph contains a perfect matching and a disjoint matching of size k or not is NP-complete, already for bipartite graphs with maximum degree 3. It also follows from our construction that it is NP-complete to decide whether in a bipartite graph there is a perfect matching and a disjoint matching that covers all vertices whose degree is at least 2.

Partitioning to three matchings of given size is NP-complete for bipartite graphs

Eötvös Loránd University, Institute of Mathematics

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

We show that the problem of deciding whether the edge set of a bipartite graph can be partitioned into three matchings, of size k1, k2 and k3 is NP-complete,...

Partitioning to three matchings of given size is NP-complete for bipartite graphs

Publié en ligne: 27 janv. 2015

Pages: 206 - 209

Reçu: 11 juil. 2014

DOI: https://doi.org/10.1515/ausi-2015-0004

© 2015

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.