An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917012434845696 |
|---|---|
| author | Mkrtchyan, Vahan |
| author_facet | Mkrtchyan, Vahan |
| contents | In this paper, we consider the maximum $k$-edge-colorable subgraph problem. In this problem we are given a graph $G$ and a positive integer $k$, the goal is to take $k$ matchings of $G$ such that their union contains maximum number of edges. This problem is NP-hard in cubic graphs, and polynomial-time solvable in bipartite graphs as we observe in our paper. We present an NP-hardness result for a version of this problem where we have color constraints on vertices. In fact, we show that this version is NP-hard already in bipartite graphs of maximum degree three. In order to achieve the result, we establish a connection between our problem and the problem of construction of special maximum matchings considered in the Master thesis of the author and defended back in 2003. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15388 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs Mkrtchyan, Vahan Combinatorics Discrete Mathematics 05C85, 68R10, 05C15, 05C70 In this paper, we consider the maximum $k$-edge-colorable subgraph problem. In this problem we are given a graph $G$ and a positive integer $k$, the goal is to take $k$ matchings of $G$ such that their union contains maximum number of edges. This problem is NP-hard in cubic graphs, and polynomial-time solvable in bipartite graphs as we observe in our paper. We present an NP-hardness result for a version of this problem where we have color constraints on vertices. In fact, we show that this version is NP-hard already in bipartite graphs of maximum degree three. In order to achieve the result, we establish a connection between our problem and the problem of construction of special maximum matchings considered in the Master thesis of the author and defended back in 2003. |
| title | An NP-hardness result for the colored constrained maximum 2-edge-colorable subgraph problem in bipartite graphs |
| topic | Combinatorics Discrete Mathematics 05C85, 68R10, 05C15, 05C70 |
| url | https://arxiv.org/abs/2409.15388 |