54. On the Complexity of Finding Maximum Size Properly Colored Trees and Forests in Edge-Colored Graphs
Invited abstract in session TC-3: Approximation algorithms for graph problems, stream Approximation algorithms.
Thursday, 12:00 - 13:30Room: C 104
Authors (first author is the speaker)
| 1. | Gergely Csáji
|
| HUN-REN KRTK KTI | |
| 2. | Yuhang Bai
|
| School of Mathematics and Statistics, Northwestern Polytechnical University and Xi’an-Budapest Joint Research Center for Combinatorics, Xi’an 710129, Shaanxi, People’s Republic of China | |
| 3. | Kristof Berczi
|
| Eötvös Loránd University | |
| 4. | Tamás Schwarcz
|
| Department of Operations Research, Eötvös Loránd University |
Abstract
We consider problems related to Properly Colored Spanning Trees.
Previous work on properly colored spanning trees has mainly focused on determining the existence of such a tree and therefore the corresponding natural maximization problems were left mostly unexplored. In this paper, we propose an optimization version called Maximum-size Properly Colored Forest problem, where the goal is to find a subset of edges that is both properly colored and forms a forest of the underlying undirected graph. We study the complexity and approximability of the problem based on several different graph classes and different numbers of colors.
On the negative side, we provide several inapproximability results which shows that apart from some very special cases, the problem cannot admit a polynomial-time approximation scheme, unless P=NP. On the positive side, we present polynomial-time approximation algorithms as well, for all of our studied settings. Our proof technique relies on the sum of matching matroids defined by the color classes, a connection that might be of independent combinatorial interest.
The other maximization problem we consider is the Maximum-size Properly Colored Tree problem, which asks for the maximum size of a properly colored tree. We show that approximating the optimum is significantly more difficult than in the forest case.
On the positive side, we show that in the case of complete multigraphs, the problem can be approximated in polynomial-time.
Keywords
- Complexity and efficiency of optimization algorithms
Status: accepted
Back to the list of papers