DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.14

Approximating Maximum-Size Properly Colored Forests

Authors: Yuhang Bai, Kristóf Bérczi, Gergely Csáji, and Tamás Schwarcz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree. The problem is interesting not only from a graph coloring point of view, but is also closely related to the Degree Bounded Spanning Tree and (1,2)-Traveling Salesman problems. We propose an optimization version called Maximum-size Properly Colored Forest problem, which aims to find a properly colored forest with as many edges as possible. We consider the problem in different graph classes and for different numbers of colors, and present polynomial-time approximation algorithms as well as inapproximability results for these settings. We also consider the Maximum-size Properly Colored Tree problem asking for the maximum size of a properly colored tree not necessarily spanning all the vertices. We show that the optimum is significantly more difficult to approximate than in the forest case, and provide an approximation algorithm for complete multigraphs.

Cite as

Yuhang Bai, Kristóf Bérczi, Gergely Csáji, and Tamás Schwarcz. Approximating Maximum-Size Properly Colored Forests. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bai_et_al:LIPIcs.ESA.2024.14,
  author =	{Bai, Yuhang and B\'{e}rczi, Krist\'{o}f and Cs\'{a}ji, Gergely and Schwarcz, Tam\'{a}s},
  title =	{{Approximating Maximum-Size Properly Colored Forests}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.14},
  URN =		{urn:nbn:de:0030-drops-210858},
  doi =		{10.4230/LIPIcs.ESA.2024.14},
  annote =	{Keywords: Approximation algorithm, (1,2)-traveling salesman problem, Degree bounded spanning tree, Properly colored forest}
}

Search Results

Documents authored by Bai, Yuhang

Approximating Maximum-Size Properly Colored Forests

Abstract

Cite as

Thanks for your feedback!

Could not send message