QP-2013-01

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

Dömötör Pálvölgyi



Abstract

We show that the problem of deciding whether the edge set of a bipartite graph can be partitioned into three matchings, of size $k_1$, $k_2$ and $k_3$ 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$.


Bibtex entry:

@techreport{egresqp-13-01,
AUTHOR = {P{\'a}lvölgyi, Dömötör},
TITLE = {Partitioning to three matchings of given size is NP-complete for bipartite graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2013},
NUMBER = {QP-2013-01}
}


Last modification: 19.5.2019. Please email your comments to Tamás Király!