Hsin-Hao Su

SODA Conference 2024 Conference Paper

Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds

• Nairen Cao
• Shang-En Huang
• Hsin-Hao Su

STOC Conference 2019 Conference Paper

Towards the locality of Vizing's theorem

• Hsin-Hao Su
• Hoa T. Vu

Vizing showed that it suffices to color the edges of a simple graph using Δ + 1 colors, where Δ is the maximum degree of the graph. However, up to this date, no efficient distributed edge-coloring algorithm is known for obtaining such coloring, even for constant degree graphs. The current algorithms that get closest to this number of colors are the randomized (Δ + Θ(√Δ))-edge-coloring algorithm that runs in ( n ) rounds by Chang et al. [SODA 2018] and the deterministic (Δ + ( n ))-edge-coloring algorithm that runs in (Δ, log n ) rounds by Ghaffari et al. [STOC 2018]. We present two distributed edge-coloring algorithms that run in (Δ,log n ) rounds. The first algorithm, with randomization, uses only Δ+2 colors. The second algorithm is a deterministic algorithm that uses Δ+ O (log n / loglog n ) colors. Our approach is to reduce the distributed edge-coloring problem into an online and restricted version of balls-into-bins problem. If ℓ is the maximum load of the bins, our algorithm uses Δ + 2ℓ − 1 colors. We show how to achieve ℓ = 1 with randomization and ℓ = O (log n / loglog n ) without randomization.

SODA Conference 2017 Conference Paper

Distributed Degree Splitting, Edge Coloring, and Orientations

• Mohsen Ghaffari 0001
• Hsin-Hao Su

We study a family of closely-related distributed graph problems, which we call degree splitting, where roughly speaking the objective is to partition (or orient) the edges such that each node's degree is split almost uniformly. Our findings lead to answers for a number of problems, a sampling of which includes: We present a poly log n round deterministic algorithm for (2Δ – 1) •(1+o(1))-edge-coloring, where Δ denotes the maximum degree. Modulo the 1 + o(1) factor, this settles one of the long-standing open problems of the area from the 1990's (see e. g. Panconesi and Srinivasan [PODC'92]). Indeed, a weaker requirement of (2Δ – 1) · poly log Δ-edge- coloring in poly log n rounds was asked for in the 4th open question in the Distributed Graph Coloring book by Barenboim and Elkin. We show that sinkless orientation —i. e. , orienting edges such that each node has at least one outgoing edge—on Δ-regular graphs can be solved in O (log A log n ) rounds randomized and in O (log A n ) rounds deterministically. These prove the corresponding lower bounds by Brandt et al. [STOC'16] and Chang, Kopelowitz, and Pettie [FOCS'16] to be tight. Moreover, these show that sinkless orientation exhibits an exponential separation between its randomized and deterministic complexities, akin to the results of Chang et al. for Δ-coloring Δ- regular trees. We present a randomized O (log 4 n ) round algorithm for orienting a -arboricity graphs with maximum out-degree a(1 + ∊). This can be also turned into a decomposition into a(1 + ∊) forests when a = 0(log n ) and into a(1 + ∊) pseduo-forests when a = o(log n ). Obtaining an efficient distributed decomposition into less than 2a forests was stated as the 10th open problem in the book by Barenboim and Elkin.

SODA Conference 2017 Conference Paper

Scaling Algorithms for Weighted Matching in General Graphs

• Ran Duan
• Seth Pettie
• Hsin-Hao Su

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in time, per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs [29, 18]. Here m, n, and n bound the number of edges, vertices, and magnitude of any integer edge weight. Our result improves on a 25-year old algorithm of Gabow and Tarjan, which runs in time.

STOC Conference 2016 Conference Paper

Distributed (∆+1)-coloring in sublogarithmic rounds

• David G. Harris 0001
• Johannes Schneider 0002
• Hsin-Hao Su

The (∆+1)-coloring problem is a fundamental symmetry breaking problem in distributed computing. We give a new randomized coloring algorithm for (∆+1)-coloring running in O(√log ∆)+ 2^O(√log log n) rounds with probability 1-1/n^Ω(1) in a graph with n nodes and maximum degree ∆. This implies that the (∆+1)-coloring problem is easier than the maximal independent set problem and the maximal matching problem, due to their lower bounds by Kuhn, Moscibroda, and Wattenhofer [PODC'04]. Our algorithm also extends to the list-coloring problem where the palette of each node contains ∆+1 colors.

SODA Conference 2015 Conference Paper

(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting

• Michael Elkin
• Seth Pettie
• Hsin-Hao Su

Graph coloring is a central problem in distributed computing. Both vertex- and edge-coloring problems have been extensively studied in this context. In this paper we show that a (2Δ — l)-edge-coloring can be computed in time smaller than log ε n for any ε > 0, specifically, in rounds. This establishes a separation between the (2Δ — 1)-edge-coloring and Maximal Matching problems, as the latter is known to require time [15]. No such separation is currently known between the (Δ + l)-vertex-coloring and Maximal Independent Set problems. We devise a (1 + ε)Δ-edge-coloring algorithm for an arbitrarily small constant ε > 0. This result applies whenever Δ ≥ Δε, for some constant Δ ε which depends on e. The running time of this algorithm is. A much earlier logarithmic-time algorithm by Dubhashi, Grable and Panconesi [11] assumed Δ ≥ (log n ) 1+Ω(1). For Δ = (log n ) 1+Ω(1) the running time of our algorithm is only O (log* n ). This constitutes a drastic improvement of the previous logarithmic bound [11, 9]. Our results for (2Δ — 1)-edge-coloring also follows from our more general results concerning (1 — ε) -locally sparse graphs. Specifically, we devise a (Δ + l)-vertex coloring algorithm for (1 — ε)-locally sparse graphs that runs in O (log* Δ + log(l/ε)) rounds for any ε > 0, provided that ε Δ = (log n ) 1+Ω(1). We conclude that the (Δ + l)-vertex coloring problem for (1 — ε)-locally sparse graphs can be solved in time. This imply our result about (2Δ — 1)-edge-coloring, because (2Δ — 1)-edge-coloring reduces to (Δ + l)-vertex-coloring of the line graph of the original graph, and because line graphs are (1/2 + o (1))-locally sparse.

I&C Journal 2015 Journal Article

Distributed coloring algorithms for triangle-free graphs

• Seth Pettie
• Hsin-Hao Su

Vertex coloring is a central concept in graph theory and an important symmetry-breaking primitive in distributed computing. Whereas degree-Δ graphs may require palettes of Δ + 1 colors in the worst case, it is well known that the chromatic number of many natural graph classes can be much smaller. In this paper we give new distributed algorithms to find ( Δ / k ) -coloring in graphs of girth 4 (triangle-free graphs), girth 5, and trees. The parameter k can be at most ( 1 4 − o ( 1 ) ) ln ⁡ Δ in triangle-free graphs and at most ( 1 − o ( 1 ) ) ln ⁡ Δ in girth-5 graphs and trees, where o ( 1 ) is a function of Δ. Specifically, for Δ sufficiently large we can find such a coloring in O ( k + log ⁎ ⁡ n ) time. Moreover, for any Δ we can compute such colorings in roughly logarithmic time for triangle-free and girth-5 graphs, and in O ( log ⁡ Δ + log Δ ⁡ log ⁡ n ) time on trees. As a byproduct, our algorithm shows that the chromatic number of triangle-free graphs is at most ( 4 + o ( 1 ) ) Δ ln ⁡ Δ, which improves on Jamall's recent bound of ( 67 + o ( 1 ) ) Δ ln ⁡ Δ. Finally, we show that ( Δ + 1 ) -coloring for triangle-free graphs can be obtained in sublogarithmic time for any Δ.

SODA Conference 2012 Conference Paper

A scaling algorithm for maximum weight matching in bipartite graphs

• Ran Duan
• Hsin-Hao Su