Fabian Kuhn

SODA Conference 2024 Conference Paper

A (3 + ɛ)-Approximate Correlation Clustering Algorithm in Dynamic Streams

• Mélanie Cambus
• Fabian Kuhn
• Etna Lindy
• Shreyas Pai
• Jara Uitto

Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming and parallel algorithms for correlation clustering, where each pair of elements is labeled either similar or dissimilar. The task is to partition the elements and the objective is to minimize disagreements, that is, the number of dissimilar elements grouped together and similar elements that get separated. Our main contribution is a semi-streaming algorithm that achieves a (3 + ɛ)-approximation to the minimum number of disagreements using a single pass over the stream. In addition, the algorithm also works for dynamic streams. Our approach builds on the analysis of the PIVOT algorithm by Ailon, Charikar, and Newman [JACM’08] that obtains a 3-approximation in the centralized setting. Our design allows us to sparsify the input graph by ignoring a large portion of the nodes and edges without a large extra cost as compared to the analysis of PIVOT. This sparsification makes our technique applicable in several models of massive graph processing, such as semi-streaming and Massively Parallel Computing (MPC), where sparse graphs can typically be handled much more efficiently. Our work improves on the approximation ratio of the recent single-pass 5-approximation algorithm and on the number of passes of the recent O (1/ɛ)-pass (3 + ɛ)-approximation algorithm [Behnezhad, Charikar, Ma, Tan FOCS’22, SODA’23]. Our algorithm is also more robust and can be applied in dynamic streams. Furthermore, it is the first single pass (3 + ɛ)-approximation algorithm that uses polynomial post-processing time.

SODA Conference 2024 Conference Paper

A Distributed Palette Sparsification Theorem

• Maxime Flin
• Mohsen Ghaffari 0001
• Magnús M. Halldórsson
• Fabian Kuhn
• Alexandre Nolin

STOC Conference 2024 Conference Paper

No Distributed Quantum Advantage for Approximate Graph Coloring

• Xavier Coiteux-Roy
• Francesco d'Amore 0001
• Rishikesh Gajjala
• Fabian Kuhn
• François Le Gall
• Henrik Lievonen
• Augusto Modanese
• Marc-Olivier Renou

SODA Conference 2023 Conference Paper

Distributed Maximal Matching and Maximal Independent Set on Hypergraphs

• Alkida Balliu
• Sebastian Brandt 0002
• Fabian Kuhn
• Dennis Olivetti

We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph H = ( V H, E H ) is a maximal disjoint set M ⊆ E h of hyperedges and an MIS S ⊆ V H is a maximal set of nodes such that no hyperedge is fully contained in S. Both problems can be solved by a simple sequential greedy algorithm, which can be implemented naïvely in O (Δ r + log * n ) rounds, where Δ is the maximum degree, r is the rank, and n is the number of nodes of the hypergraph. We show that for maximal matching, this naive algorithm is optimal in the following sense. Any deterministic algorithm for solving the problem requires Ω(min {Δ r, log Δr n }) rounds, and any randomized one requires Ω(min {Δ r, log Δ r log n }) rounds. Hence, for any algorithm with a complexity of the form O ( f (Δ, r ) + g ( n )), we have f (Δ, r ) ∈ Ω(Δ r ) if g(n) is not too large, and in particular if g(n) = log * n (which is the optimal asymptotic dependency on n due to Linial's lower bound [FOCS'87]). Our lower bound proof is based on the round elimination framework, and its structure is inspired by a new round elimination fixed point that we give for the Δ-vertex coloring problem in hypergraphs, where nodes need to be colored such that there are no monochromatic hyperedges. For the MIS problem on hypergraphs, we show that for Δ ≪ r, there are significant improvements over the naive O (Δ r + log * n )-round algorithm. We give two deterministic algorithms for the problem. We show that a hypergraph MIS can be computed in O (Δ 2 · log r + Δ · log r · log * r + log * n ) rounds. We further show that at the cost of a much worse dependency on Δ, the dependency on r can be removed almost entirely, by giving an algorithm with round complexity Δ O (Δ) · log * r + 0(log * n ).

SODA Conference 2023 Conference Paper

Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond

• Salwa Faour
• Mohsen Ghaffari 0001
• Christoph Grunau
• Fabian Kuhn
• Václav Rozhon

We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of vertices. Roughly speaking, the method can transform fractional/probabilistic label assignments of the vertices into integral/deterministic label assignments for the vertices, while approximately preserving a potential function that is a linear combination of functions, each of which depends on at most two vertices (subject to some conditions usually satisfied in pairwise analyses). The method unifies and significantly generalizes prior work on deterministic local rounding techniques [Ghaffari, Kuhn FOCS'21; Harris FOCS'19; Fischer, Ghaffari, Kuhn FOCS'17; Fischer DISC'17] to obtain polylogarithmic-time deterministic distributed solutions for combinatorial graph problems. Our general rounding result enables us to locally and efficiently derandomize a range of distributed algorithms for local graph problems, including maximal independent set (MIS), maximum-weight independent set approximation, and minimum-cost set cover approximation. As highlights, we in particular obtain the following results. • We obtain a deterministic O (log 2 Δ · log n )-round algorithm for computing an MIS in the LOCAL model and an almost as efficient O (log 2 Δ · log log Δ · log n )-round deterministic MIS algorithm in the CONGEST model. As a result, the best known deterministic distributed time complexity of the four most widely studied distributed symmetry breaking problems (MIS, maximal matching, (Δ + 1)-vertex coloring, and (2Δ − 1)-edge coloring) is now O (log 2 Δ · log n ). Our new MIS algorithm is also the first direct polylogarithmic-time deterministic distributed MIS algorithm, which is not based on network decomposition. • We obtain efficient deterministic distributed algorithms for rounding fractional solutions for maximum (weighted) independent set and minimum (weighted) set cover. We in particular give a deterministic O (log 2 Δ + log * n )-round algorithms for computing an independent set of size (1/2 — ε) · n / deg avg and we give deterministic O (log 2 (Δ W ) + log * n )-round algorithms for computing a (1 — ε)/Δ-approximation of maximum weight independent set, and for computing a (1 — ε)/ r -approximation of maximum weight matching in hypergraphs of rank r. For minimum set cover instances with sets of size at most s and where each element is contained in at most t sets, we show that an O (log s )-approximation can be computed in time O (log s · log 2 t + log * n ). * The full version of the paper can be accessed at https: //arxiv. org/abs/2209. 11651

STOC Conference 2022 Conference Paper

Distributed ∆-coloring plays hide-and-seek

• Alkida Balliu
• Sebastian Brandt 0002
• Fabian Kuhn
• Dennis Olivetti

We prove several new tight or near-tight distributed lower bounds for classic symmetry breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a Δ-coloring on Δ-regular trees requires Ω(log Δ n ) rounds and any randomized such algorithm requires Ω(log Δ log n ) rounds. We prove this by showing that a natural relaxation of the Δ-coloring problem is a fixed point in the round elimination framework.

STOC Conference 2022 Conference Paper

Near-optimal distributed degree+1 coloring

• Magnús M. Halldórsson
• Fabian Kuhn
• Alexandre Nolin
• Tigran Tonoyan

We present a new approach to randomized distributed graph coloring that is simpler and more efficient than previous ones. In particular, it allows us to tackle the (deg+1)-list-coloring (D1LC) problem, where each node v of degree d v is assigned a palette of d v +1 colors, and the objective is to find a proper coloring using these palettes. While for (Δ+1)-coloring (where Δ is the maximum degree), there is a fast randomized distributed O (log 3 log n )-round algorithm due to Chang, Li, and Pettie, no o (log n )-round algorithms are known for the D1LC problem.

FOCS Conference 2021 Conference Paper

Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition

• Mohsen Ghaffari 0001
• Fabian Kuhn

We present a simple deterministic distributed algorithm that computes a ( $\Delta+1$ )-vertex coloring in $O(\text{log}^{2}\Delta. \text{log}\ n)$ rounds. The algorithm can be implemented with $O(\text{log}\ n)$ -bit messages. The algorithm can also be extended to the more general ( $degree+1$ )-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for ( $\Delta +1$ )-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozhoň and Ghaffari [STOC'20]. The current state of the art is based on an improved variant of their decomposition, which leads to an $O(\text{log}^{5}n)$ -round algorithm for ( $\Delta+1$ )-vertex coloring. Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignments. Moreover, via the approach of Chang, Li, and Pettie [STOC'18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for ( $\Delta +1$ )-coloring, now reaching the bound of $O(\text{log}^{3}\text{log}\ n)$ rounds. As a further application, we provide faster deterministic distributed algorithms for the following vertex coloring variants. In graphs of arboricity $a$, we show that a $(2+\varepsilon)a$ -vertex coloring can be computed in $O(\text{log}^{3}a\cdot \text{log} n)$ rounds. We also show that for $\Delta\geq 3$, a $\Delta$ -coloring of a $\Delta$ -colorable graph $G$ can be computed in $O(\text{log}^{2}\Delta\cdot \text{log}^{2}n)$ rounds.

STOC Conference 2021 Conference Paper

Efficient randomized distributed coloring in CONGEST

• Magnús M. Halldórsson
• Fabian Kuhn
• Yannic Maus
• Tigran Tonoyan

Distributed vertex coloring is one of the classic problems and probably also the most widely studied problems in the area of distributed graph algorithms. We present a new randomized distributed vertex coloring algorithm for the standard CONGEST model, where the network is modeled as an n -node graph G , and where the nodes of G operate in synchronous communication rounds in which they can exchange O (log n )-bit messages over all the edges of G . For graphs with maximum degree Δ, we show that the (Δ+1)-list coloring problem (and therefore also the standard (Δ+1)-coloring problem) can be solved in O (log 5 log n ) rounds. Previously such a result was only known for the significantly more powerful LOCAL model, where in each round, neighboring nodes can exchange messages of arbitrary size. The best previous (Δ+1)-coloring algorithm in the CONGEST model had a running time of O (logΔ + log 6 log n ) rounds. As a function of n alone, the best previous algorithm therefore had a round complexity of O (log n ), which is a bound that can also be achieved by a na'ive folklore algorithm. For large maximum degree Δ, our algorithm hence is an exponential improvement over the previous state of the art.

SODA Conference 2020 Conference Paper

Faster Deterministic Distributed Coloring Through Recursive List Coloring

• Fabian Kuhn

We provide novel deterministic distributed vertex coloring algorithms. As our main result, we give a deterministic distributed algorithm to compute a (Δ + 1)-coloring of an n -node graph with maximum degree rounds. For graphs with arboricity a, we obtain a deterministic distributed algorithm to compute a (2 + o (1)) a -coloring in time. Further, for graphs with bounded neighborhood independence, we show that a (Δ + 1)-coloring can be computed more efficiently in time. This in particular implies that also a (2Δ – 1)-edge coloring can be computed deterministically in rounds, which improves the best known time bound for small values of Δ. All results even hold for the list coloring variants of the problems. As a consequence, we also obtain an improved deterministic n -round algorithm for Δ-coloring non-complete graphs with maximum degree Δ ≥ 3. Most of our algorithms only require messages of O (log n ) bits (including the (Δ + 1)-vertex coloring algorithms). Our main technical contribution is a recursive deterministic distributed list coloring algorithm to solve list coloring problems with lists of size Δ 1+ o (1). Given some list coloring problem and an orientation of the edges, we show how to recursively divide the global color space into smaller subspaces, assign one of the subspaces to each node of the graph, and compute a new edge orientation such that for each node, the list size to out-degree ratio degrades at most by a constant factor on each recursion level.

TCS Journal 2020 Journal Article

Rumor spreading with bounded in-degree

• Sebastian Daum
• Fabian Kuhn
• Yannic Maus

In the gossip-based model of communication for disseminating information in a network, in each time unit, every node u can contact a single random neighbor v but can possibly be contacted by many nodes. In the present paper, we consider a restricted model where at each node only one incoming call can be answered in one time unit. We study the implied weaker version of the well-studied pull protocol, which we call restricted pull. We prove an exponential separation of the rumor spreading time between two variants of the protocol (the answered call among a set of calls is chosen adversarially or uniformly at random). Further, we show that if the answered call is chosen randomly, the slowdown of restricted pull versus the classic pull protocol can w. h. p. be upper bounded by O ( ψ ( G ) ⋅ log ⁡ n ), where ψ ( G ) = max { u, v } ∈ E ⁡ d ( u ) / d ( v ) ≤ Δ δ with Δ and δ being the largest and smallest degree of the network G = ( V, E ) and d ( u ) being the degree of u.

SODA Conference 2020 Conference Paper

Shortest Paths in a Hybrid Network Model

• John Augustine 0001
• Kristian Hinnenthal
• Fabian Kuhn
• Christian Scheideler
• Philipp Schneider

We introduce a communication model for hybrid networks, where nodes have access to two different communication modes: a local mode where (like in traditional networks) communication is only possible between specific pairs of nodes, and a global mode where (like in overlay networks) communication between any pair of nodes is possible. Typically, communication over short-range connections is cheaper and can be done at a much higher rate than communication via the overlay network. Therefore, we are focusing on the LOCAL model for the local connections where nodes can exchange an unbounded amount of information per round. For the global communication we assume the so-called nodecapacitated clique model, where in each round every node can exchange O (log n )-bit messages with O (log n ) arbitrary nodes. We explore the impact of hybrid communication on the complexity of distributed algorithms by studying the problem of computing shortest paths in the graph given by the local connections. We present the following results. For the all-pairs shortest paths problem, we show that an exact solution can be computed in time Õ ( n 2/3 ), and that approximate solutions can be computed in time but not faster. For the single-source shortest paths problem an exact solution can be computed in time, where SPD denotes the shortest path diameter. Furthermore, a (l + o (1))-approximate solution can be computed in time. Finally, we show that for every constant ε > 0, it is possible to compute an O (1)-approximate solution in time.

TCS Journal 2020 Journal Article

The cost of global broadcast in dynamic radio networks

• Mohamad Ahmadi
• Abdolhamid Ghodselahi
• Fabian Kuhn
• Anisur Rahaman Molla

We study the time complexity of single and multi token broadcast in adversarial dynamic radio networks. Initially, k tokens (which are k pieces of information) are distributed among the n nodes of a network and all the tokens need to be disseminated to all the nodes in the network. We first consider the single-token broadcast problem (i. e. , the case k = 1 ). By presenting upper and lower bounds, we show that the time complexity of single-token broadcast depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. Then, we give two generic algorithms which allow to transform generalized forms of single-token broadcast algorithms into multi-token broadcast (k-token broadcast) algorithms. Based on these generic algorithms, we obtain k-token broadcast algorithms for a number of different dynamic network settings. For one of the modeling assumptions, our algorithm is complemented by a lower bound which shows that the upper bound is close to optimal.

FOCS Conference 2019 Conference Paper

Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds

• Mohsen Ghaffari 0001
• Fabian Kuhn
• Jara Uitto

We present the first conditional hardness results for massively parallel algorithms for some central graph problems including (approximating) maximum matching, vertex cover, maximal independent set, and coloring. In some cases, these hardness results match or get close to the state of the art algorithms. Our hardness results are conditioned on a widely believed conjecture in massively parallel computation about the complexity of the connectivity problem. We also note that it is known that an unconditional variant of such hardness results might be somewhat out of reach for now, as it would lead to considerably improved circuit complexity lower bounds and would concretely imply that NC 1 is a proper subset of P. We obtain our conditional hardness result via a general method that lifts unconditional lower bounds from the well-studied LOCAL model of distributed computing to the massively parallel computation setting.

STOC Conference 2018 Conference Paper

Deterministic distributed edge-coloring with fewer colors

• Mohsen Ghaffari 0001
• Fabian Kuhn
• Yannic Maus
• Jara Uitto

We present a deterministic distributed algorithm, in the LOCAL model, that computes a (1+ o (1))Δ-edge-coloring in polylogarithmic-time, so long as the maximum degree Δ=Ω(log n ). For smaller Δ, we give a polylogarithmic-time 3Δ/2-edge-coloring. These are the first deterministic algorithms to go below the natural barrier of 2Δ−1 colors, and they improve significantly on the recent polylogarithmic-time (2Δ−1)(1+ o (1))-edge-coloring of Ghaffari and Su [SODA’17] and the (2Δ−1)-edge-coloring of Fischer, Ghaffari, and Kuhn [FOCS’17], positively answering the main open question of the latter. The key technical ingredient of our algorithm is a simple and novel gradual packing of judiciously chosen near-maximum matchings, each of which becomes one of the color classes.

SODA Conference 2018 Conference Paper

Labeling Schemes for Nearest Common Ancestors through Minor-Universal Trees

• Pawel Gawrychowski
• Fabian Kuhn
• Jakub Lopuszanski
• Konstantinos Panagiotou
• Pascal Su

Preprocessing a tree for finding the nearest common ancestor of two nodes is a basic tool with multiple applications. Quite a few linear-space constant-time solutions are known and the problem seems to be well-understood. This is however not so clear if we want to design a labeling scheme. In this model, the structure should be distributed: every node receives a distinct binary string, called its label, so that given the labels of two nodes (and no further information about the topology of the tree) we can compute the label of their nearest common ancestor. The goal is to make the labels as short as possible. Alstrup, Gavoille, Kaplan, and Rauhe [Theor. Comput. Syst. 37(3): 441–456 2004] showed that O (log n )-bit labels are enough, with a somewhat large constant. More recently, Alstrup, Halvorsen, and Larsen [SODA 2014] refined this to only 2. 772 log n, and provided a lower bound of 1. 008 log n. We connect the question of designing a labeling scheme for nearest common ancestors to the existence of a tree, called a minor-universal tree, that contains every tree on n nodes as a topological minor. Even though it is not clear if a labeling scheme must be based on such a notion, we argue that all already existing schemes can be reformulated as such. Further, we show that this notion allows us to easily obtain clean and good bounds on the length of the labels. As the main upper bound, we show that 2. 318 log n -bit labels are enough. Surprisingly, the notion of a minor-universal tree for binary trees on n nodes has been already used in a different context by Hrubes et al. [CCC 2010], and Young, Chu, and Wong [J. ACM 46(3): 416–435, 1999] introduced a very closely related (but not equivalent) notion of a universal tree. On the lower bound side, we show that any minor-universal tree for trees on n nodes must contain at least Ω( n 2. 174 ) nodes. This highlights a natural limitation for all approaches based on defining a minor-universal tree. We complement the existential results with a generic transformation that allows us, for any labeling scheme for nearest common ancestors based on a minor-universal tree, to decrease the query time to constant, while increasing the length of the labels only by lower order terms.

FOCS Conference 2018 Conference Paper

On Derandomizing Local Distributed Algorithms

• Mohsen Ghaffari 0001
• David G. Harris 0001
• Fabian Kuhn

The gap between the known randomized and deterministic local distributed algorithms underlies arguably the most fundamental and central open question in distributed graph algorithms. In this paper, we combine the method of conditional expectation with network decompositions to obtain a generic and clean recipe for derandomizing LOCAL algorithms. This leads to significant improvements on a number of problems, in cases resolving known open problems. Two main results are: - An improved deterministic distributed algorithm for hypergraph maximal matching, improving on Fischer, Ghaffari, and Kuhn [FOCS '17]. This yields improved algorithms for edge-coloring, maximum matching approximation, and low out-degree edge orientation. The last result gives the first positive resolution in the Open Problem 11. 10 in the book of Barenboim and Elkin. - Improved randomized and deterministic distributed algorithms for the Lovász Local Lemma, which get closer to a conjecture of Chang and Pettie [FOCS '17].

MFCS Conference 2018 Conference Paper

Shape Recognition by a Finite Automaton Robot

• Robert Gmyr
• Kristian Hinnenthal
• Irina Kostitsyna
• Fabian Kuhn
• Dorian Rudolph
• Christian Scheideler

Motivated by the problem of shape recognition by nanoscale computing agents, we investigate the problem of detecting the geometric shape of a structure composed of hexagonal tiles by a finite-state automaton robot. In particular, in this paper we consider the question of recognizing whether the tiles are assembled into a parallelogram whose longer side has length l = f(h), for a given function f(*), where h is the length of the shorter side. To determine the computational power of the finite-state automaton robot, we identify functions that can or cannot be decided when the robot is given a certain number of pebbles. We show that the robot can decide whether l = ah+b for constant integers a and b without any pebbles, but cannot detect whether l = f(h) for any function f(x) = omega(x). For a robot with a single pebble, we present an algorithm to decide whether l = p(h) for a given polynomial p(*) of constant degree. We contrast this result by showing that, for any constant k, any function f(x) = omega(x^(6k + 2)) cannot be decided by a robot with k states and a single pebble. We further present exponential functions that can be decided using two pebbles. Finally, we present a family of functions f_n(*) such that the robot needs more than n pebbles to decide whether l = f_n(h).

FOCS Conference 2017 Conference Paper

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching

• Manuela Fischer
• Mohsen Ghaffari 0001
• Fabian Kuhn

We present a deterministic distributed algorithm that computes a (2Δ-1)-edge-coloring, or even list-edge-coloring, in any n-node graph with maximum degree Δ, in O(log 8 Δ·log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms} from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e. g. , Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2 O(√(log n) by Panconesi and Srinivasan [STOC'92] and Õ(√(Δ)) + O(log* n) by Fraigniaud, Heinrich, and Kosowski [FOCS'16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2Δ-1)-edge-coloring to poly(log log n) rounds. The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r - where each hyperedge has at most r vertices - with n nodes and maximum degree Δ, this algorithm computes a maximal matching in O(r 5 log 6+log r Δ·log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkins book, a ((log Δ/ε) O(log 1/ε) )-round deterministic algorithm for (1+ε)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting λ-arboricity graphs with out-degree at most ⌈(1+ε)λ⌉, for any constant ε>0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.

STOC Conference 2017 Conference Paper

On the complexity of local distributed graph problems

• Mohsen Ghaffari 0001
• Fabian Kuhn
• Yannic Maus

This paper is centered on the complexity of graph problems in the well-studied LOCAL model of distributed computing, introduced by Linial [FOCS '87]. It is widely known that for many of the classic distributed graph problems (including maximal independent set (MIS) and (Δ+1)-vertex coloring), the randomized complexity is at most polylogarithmic in the size n of the network, while the best deterministic complexity is typically 2 O (√log n ) . Understanding and potentially narrowing down this exponential gap is considered to be one of the central long-standing open questions in the area of distributed graph algorithms. We investigate the problem by introducing a complexity-theoretic framework that allows us to shed some light on the role of randomness in the LOCAL model. We define the SLOCAL model as a sequential version of the LOCAL model. Our framework allows us to prove completeness results with respect to the class of problems which can be solved efficiently in the SLOCAL model, implying that if any of the complete problems can be solved deterministically in log n rounds in the LOCAL model, we can deterministically solve all efficient SLOCAL-problems (including MIS and (Δ+1)-coloring) in log n rounds in the LOCAL model. Perhaps most surprisingly, we show that a rather rudimentary looking graph coloring problem is complete in the above sense: Color the nodes of a graph with colors red and blue such that each node of sufficiently large polylogarithmic degree has at least one neighbor of each color. The problem admits a trivial zero-round randomized solution. The result can be viewed as showing that the only obstacle to getting efficient determinstic algorithms in the LOCAL model is an efficient algorithm to approximately round fractional values into integer values. In addition, our formal framework also allows us to develop polylogarithmic-time randomized distributed algorithms in a simpler way. As a result, we provide a polylog-time distributed approximation scheme for arbitrary distributed covering and packing integer linear programs.

SODA Conference 2015 Conference Paper

Tight Bounds on Vertex Connectivity Under Vertex Sampling

• Keren Censor-Hillel
• Mohsen Ghaffari 0001
• George Giakkoupis
• Bernhard Haeupler
• Fabian Kuhn

SODA Conference 2014 Conference Paper

A New Perspective on Vertex Connectivity

• Keren Censor-Hillel
• Mohsen Ghaffari 0001
• Fabian Kuhn

Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge connectivity our knowledge in the case of vertex connectivity is much more limited. An essential tool in capturing edge connectivity are the classical results of Tutte and Nash-Williams from 1961 which show that a λ -edge-connected graph contains ⌊( λ − 1)/2⌋ edge-disjoint spanning trees. We argue that connected dominating set partitions and packings are the natural analogues of edge-disjoint spanning trees in the context of vertex connectivity and we use them to obtain structural results about vertex connectivity in the spirit of those for edge connectivity. More specifically connected dominating set (CDS) partitions and packings are counterparts of edge-disjoint spanning trees, focusing on vertex-disjointness rather than edge-disjointness, and their sizes are always upper bounded by the vertex connectivity k. We constructively show that every k -vertex-connected graph with n nodes has CDS packings and partitions with sizes, respectively, Ω( k /log n ) and Ω( k /log 5 n ), and we prove that the former bound is existentially optimal. Beautiful results by Karger show that when edges of a λedge-connected graph are independently sampled with probability p, the sampled graph has edge connectivity ( λp ). Obtaining such a result for vertex sampling remained open. We illustrate the strength of our approach by proving that when vertices of a k -vertex-connected graph are independently sampled with probability p, the graph induced by the sampled vertices has vertex connectivity ( kp 2 ). This bound is optimal up to poly-log factors and is proven by building an ( kp 2 ) size CDS packing on the sampled vertices while sampling happens. As an additional important application, we show CDS packings to be tightly related to the throughput of routing-based algorithms and use our new toolbox to yield a routing-based broadcast algorithm with optimal throughput Ω( k /log n + 1), improving the (previously best-known) trivial throughput of Θ(1).

I&C Journal 2013 Journal Article

Vertex cover in graphs with locally few colors

• Fabian Kuhn
• Monaldo Mastrolilli

Erdős et al. defined the local chromatic number of a graph as the minimum number of colors that must appear within distance 1 of a vertex. For any Δ ⩾ 2, there are graphs with arbitrarily large chromatic number that can be colored so that (i) no vertex neighborhood contains more than Δ different colors (bounded local colorability), and (ii) adjacent vertices from two color classes induce a complete bipartite graph (biclique coloring). We investigate the weighted vertex cover problem in graphs when a locally bounded coloring is given. This generalizes the vertex cover problem in bounded degree graphs to a class of graphs with arbitrarily large chromatic number. Assuming the Unique Game Conjecture (UGC), we provide a tight characterization. We prove that it is UGC-hard to improve the approximation ratio of 2 − 2 / ( Δ + 1 ) on ( Δ + 1 ) -locally (but not necessarily biclique) colorable graphs. A matching upper bound is also provided. Vice versa, when properties (i) and (ii) hold, we present a randomized algorithm with approximation ratio of 2 − Ω ( 1 ) ln ln Δ ln Δ. This matches known inapproximability results for the special case of bounded degree graphs. Moreover, we show that when both the above two properties (i) and (ii) hold, the obtained result finds a natural application in a classical scheduling problem, namely the precedence constrained single machine scheduling problem to minimize the total weighted completion time, denoted as 1 | prec | ∑ w j C j in standard scheduling notation. In a series of recent papers it was established that this scheduling problem is a special case of the minimum weighted vertex cover in graphs G P of incomparable pairs defined in the dimension theory of partial orders. We show that G P satisfies properties (i) and (ii) where Δ − 1 is the maximum number of predecessors (or successors) of each job.

STOC Conference 2010 Conference Paper

Distributed computation in dynamic networks

• Fabian Kuhn
• Nancy A. Lynch
• Rotem Oshman

SODA Conference 2010 Conference Paper

Synchrony and Asynchrony in Neural Networks

• Fabian Kuhn
• Konstantinos Panagiotou
• Joel Spencer
• Angelika Steger

SODA Conference 2006 Conference Paper

The price of being near-sighted

• Fabian Kuhn
• Thomas Moscibroda
• Roger Wattenhofer