Above-Guarantee Algorithm for Properly Colored Spanning Trees
Yuhang Bai, Kristóf Bérczi · 2026
Read Above-Guarantee Algorithm for Properly Colored Spanning Trees by Yuhang Bai, Kristóf Bérczi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-11326.txt.
Introduction
Bai and Bérczi study properly colored spanning trees, where adjacent edges must carry distinct colors. It is known that every connected edge-colored graph holds a properly colored tree of order at least the minimum of its vertex count and twice its minimum color degree. The authors give a polynomial-time algorithm pushing one step above that guarantee. It builds a properly colored tree of order at least the minimum of vertex count and twice the minimum color degree plus one, whenever such a tree exists.
Catalog record
| CREATOR | Yuhang Bai, Kristóf Bérczi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75873 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.11326
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Above-Guarantee Algorithm for Properly Colored Spanning Trees Yuhang Bai, Kristóf Bérczi Abstract In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a spanning tree in which any two adjacent edges have distinct colors. Since finding such a tree is NP-hard in general, previous work often relied on minimum color degree conditions to guarantee the existence of properly colored spanning trees. While it is known that every connected edge-colored graph G G contains a properly colored tree of order at least min { | V ( G ) | , 2 δ c ( G ) } \min\{|V(G)|,2\delta^{c}(G)\} , where δ c ( G ) \delta^{c}(G) denotes the minimum number of colors incident to a vertex, we study the algorithmic above-guarantee problem for properly colored trees. We provide a polynomial-time algorithm that constructs a properly colored tree of order at least min { | V ( G ) | , 2 δ c ( G ) + 1 } \min\{|V(G)|,2\delta^{c}(G)+1\} in a connected edge-colored graph G G , whenever such a tree exists. Keywords: Properly colored tree, Above-guarantee problem, Polynomial-time algorithm 1 Introduction All graphs considered in this paper are finite and simple. A k -edge-colored graph is a graph G=(V,E) with a coloring c\colon E\to[k] of its edges by k colors. For a vertex v\in V , we use N_{G}(v) to denote the set of all neighbors of v in G . The color degree of v , denoted by d_{G}^{c}(v)=\bigl|\{c(vu)\colon u\in N_{G}(v)\}\bigr| . The minimum color degree of G is \delta^{c}(G)=\min_{v\in V}d_{G}^{c}(v) . We refer to a graph that is k -edge-colored for some k\in\mathbb{Z}_{+} as edge-colored . A subgraph H of G is called rainbow if no two edges of H have the same color, and properly colored if any two adjacent edges of H have distinct colors. Degree conditions for spanning structures are a central topic in extremal graph theory. A classical example is Dirac’s theorem [ 5 ] on Hamiltonian cycles. Recently, Fomin, Golovach, Sagunov, and Simonov [ 7 ] studied an algorithmic extension of Dirac’s theorem. Specifically, they showed that deciding whether a 2-connected graph G contains a cycle of length at least \min\{|V(G)|,2\delta(G)+k\} is fixed-parameter tractable when parameterized by k . This framework is referred to as an above-guarantee problem in parameterized complexity. The general idea of this paradigm is that the natural parameterization of a maximization problem by its solution size is often unsatisfactory if a sufficiently large lower bound on that size is already guaranteed. Building on this success, it is natural to ask whether similar guarantees exist in edge-colored graphs. Since a rainbow forest is a common independent set of two matroids, i.e., the partition matroid defined by the color classes and the graphic matroid of the graph, a rainbow forest of maximum size can be found in polynomial time using Edmonds’ celebrated matroid intersection algorithm [ 6 ] . However, much less is known about the properly colored case. In [ 3 ] , Borozan, de La Vega, Manoussakis, Martinhon, Muthu, Pham, and Saad initiated the study of properly colored spanning trees of edge-colored graphs and introduced the Properly Colored Spanning Tree problem ( PST ). This problem generalizes the well-known bounded-degree spanning tree problem for uncolored graphs, since the number of colors effectively limits the degree of each vertex. It also generalizes the properly colored Hamiltonian path problem when the number of colors is restricted to two. Since both of these problems are NP-complete, finding a properly colored spanning tree is computationally hard in general. To overcome this computational hardness, we use the minimum color degree to guarantee the existence of large properly colored structures. Hu, Li, and Maezawa [ 13 ] proved that every connected edge-colored graph G contains a properly colored tree of order at least \min\{|V(G)|,2\delta^{c}(G)\} . This bound is tight, since some connected edge-colored graphs do not contain a properly colored tree of order \min\{|V(G)|,2\delta^{c}(G)+1\} . They also characterized the corresponding families of extremal graphs. However, their proof does not yield a constructive algorithm. Motivated by the work of Fomin et al. [ 7 ] , we study the algorithmic above-guarantee problem: given a connected edge-colored graph G , can we decide in polynomial time whether it contains a properly colored tree of order at least \min\{|V(G)|,2\delta^{c}(G)+1\} , and output one if it exists. 1.1 Related work and motivation Finding properly colored spanning trees in graphs is closely related to constrained spanning tree problems, or in a more general context, to the problem of finding a basis of a matroid subject to further matroid constraints. In what follows, we give an overview of questions that motivated our investigations. Properly colored trees Properly colored spanning trees were first considered in [ 3 ] where their existence was studied from both a graph-theoretic and an algorithmic perspective. They showed that the problem of finding a properly colored spanning tree remains NP-complete even for complete graphs. Deciding the existence of a properly colored spanning tree is hard in general, hence, a considerable amount of work has focused on finding sufficient conditions [ 4 , 14 , 15 ] . Since a properly colored spanning tree may not exist, it is natural to ask for the maximum size of a properly colored tree not necessarily spanning all the vertices, called the Maximum-size Properly Colored Tree problem ( Max-PT ). Borozan et al. [ 3 ] proved that Max-PT is hard to approximate within a factor of 55/56+\varepsilon for any \varepsilon>0 , although they provided polynomial-time algorithms for graphs not containing properly colored cycles. Recently, Bai, Bérczi, Csáji, and Schwarcz [ 1 ] showed that Max-PT is NP-hard to approximate within a factor of 1/n^{1-\varepsilon} for any \varepsilon>0 , even for instances containing a properly colored spanning tree. Furthermore, for any fixed constant \varepsilon>0 , they provided a polynomial-time algorithm that achieves a 1/\sqrt{(2+\varepsilon)(n-1)} -approximation for Max-PT on complete multigraphs on n vertices. Hu et al. [ 13 ] proved that the maximum order of a properly colored tree in an edge-colored connected graph G is at least \min\{|V(G)|,2\delta^{c}(G)\} . Above-guarantee problems The study of parameterized problems above or below guarantees is a well-established paradigm in parameterized complexity; see the survey by Gutin and Mnich [ 12 ] . Following this line of research, Fomin et al. [ 7 ] gave an FPT algorithm, parameterized by k , to decide whether a 2-connected graph G contains a cycle of length at least \min\{|V(G)|,2\delta(G)+k\} . Later, Fomin, Golovach, Sagunov, and Simonov [ 9 ] provided an FPT algorithm, parameterized by k , to decide whether a 2-connected graph G contains a cycle of length at least \mathrm{mad}(G)+k , where \mathrm{mad}(G) denotes the maximum average degree of G . In addition, the same authors [ 8 ] showed that given any polynomial-time algorithm finding a cycle of length f(L) for a subadditive function f , one can construct a cycle of length at least 2\delta(G)+\Omega(f(L-2\delta(G))) in a 2-connected graph G . For trees, they [ 10 ] gave a randomized FPT algorithm parameterized by k to decide whether a graph contains a