Frontiers of Graph Algorithms

Schedule

Titles and Abstracts

• Anupam Gupta

  Title: Good, Better, Best: Combinatorial Optimization via Comparisons

  Abstract: In classical combinatorial optimization problems, we are given a feasible set and an objective function (either explicitly, or via a value/demand oracle), and we want to find an optimal solution. Motivated by applications where users provide very sparse feedback, we ask: what if we are only allowed comparisons between feasible solutions? For instance, suppose we can compare any two edge-cuts in a graph and find out which is smaller, or if they are equal. Can we find the minimum cut using few comparisons? Can we do this efficiently? In this work, we pose and answer some of these questions, and suggest other exciting directions for research.

  This is joint work with Vincent Cohen-Addad, Tommaso d'Orsi, Guru Guruganesh, Euiwoong Lee, Renato Paes Leme, Debmalya Panigrahi, Madhusudhan Pittu, Jon Schneider, and David Woodruff.

• Manoj Gupta

  Title: Improved 2-Approximate Shortest Paths for close vertex pairs

  Abstract: An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in $\tilde{O}(n^{2+O(1/k)})$ time, ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at least $k$ apart, where $k \geq 2$. We present the first improvement on this result in over 25 years. Our algorithm achieves roughly same $\tilde{O}(n^{2+1/k})$ runtime but applies to vertex pairs merely $O(\log k)$ apart, where $\log k \geq 1$. When $k = \log n$, the running time of our algorithm is $\tilde{O}(n^2)$ and it works for all pairs at least $O(\log \log n)$ apart. Our algorithm is combinatorial, randomized, and returns correct results for all pairs with a high probability.

• Sanjeev Khanna

  Title: Fully Dynamic Matching, Matching Sparsifiers, and Ruzsa-Szemerédi Graphs

  Abstract: The fully dynamic matching problem involves efficiently maintaining a near-optimal matching in a graph undergoing edge insertions and deletions. Despite significant effort, the goal of designing highly efficient fully dynamic matching algorithms has remained elusive. A promising natural approach toward faster algorithms is to maintain a matching sparsifier — a sparse subgraph that approximately preserves large matchings in every vertex-induced subgraph of the original graph. The success of this approach hinges on resolving two key challenges: proving the existence of sparse matching sparsifiers and designing efficient algorithms to construct them. As it turns out, both challenges are intimately connected to the question of determining the density of Ruzsa–Szemerédi (RS) graphs, namely graphs whose edges can be partitioned into induced matchings of linear size. This talk will explore the fascinating interplay between these ideas and show how this connection has led to a conditional "dream result" for fully dynamic matching.

• Danupon Nanongkai

  Title: Daydreaming About Cross-Paradigm Graph Algorithms

  Abstract: A goal in the theory of graph algorithms is to develop techniques that allow computing devices to process graph data with minimal resources—time, space, communication, and so on. This pursuit has led to rich and often separate bodies of work in different computational models, including sequential, distributed, and streaming algorithms. The cross-paradigm perspective seeks to tackle the same fundamental graph problems across multiple models, aiming for techniques that perform near-optimally in each and may spark new insights beyond any single paradigm. In this talk, I will discuss some of the ideas and open problems in this research direction, focusing on foundational problems such as minimum cut, shortest path, and maximum flow.

• Kavitha Telikepalli

  Title: Assignments, Arborescences, and Popularity

  Abstract: Matching problems with one-sided preferences are seen in applications such as campus housing allocation in universities. Popularity is a well-studied notion of optimality in this model. There is a simple algorithm to solve the popular assignment problem. A related problem asks for a popular arborescence in a directed graph where vertices have preferences over their in-neighbors. Such arborescences are relevant in liquid democracy. We will see that the popular arborescence problem can be solved by a generalization of the popular assignment algorithm.

• Surender Baswana

  Title: Compact structures for various mincuts

  Abstract: Mincuts are one of the most well-researched topics in algorithms. In recent years, there has been phenomenal research on algorithms for computing $(s, t)$-mincuts and global mincuts. On the other hand, the data structural and graph theoretical aspects of mincuts have also been well-researched in the last 50 years, though they are not as widely known despite being very fundamental and seminal.

  We shall begin with a light discussion of the following two classical results: (1) there is a directed acyclic graph that stores all $(s,t)$-mincuts of a graph, and (2) there is a tree-like graph that stores all global mincuts of a graph. We shall then discuss a structure that stores Steiner mincuts—a generalization of $(s,t)$-mincuts and global mincuts. This structure, designed by Dinitz and Vainshtein, is elegant and beautiful. We shall discuss this structure along with new and much simpler proofs of its properties.

  Note: Anyone with basic knowledge of algorithms and elementary graph theory should be able to follow most of the talk.

• Jaikumar Radhakrishnan

  Title: Graph problems through the lens of communication complexity: I

  Abstract: In the first two sessions of the workshop, we will introduce the audience to the area of communication complexity with the focus on graph problems. In the first half, we review the classical models of deterministic and randomised communication, and show, by means of reductions, how lower bounds are derived by appealing to well-studied problems such as index function, pointer chasing and set-disjointness. In the second half, we show a few communication protocols for solving fundamental graph problems such as minimum cut, vertex connectivity and bipartite maximum matching. We also mention how these communication protocols help us come up with efficient algorithms for these problems in various other models of computation.

  These sessions are designed as boot-camp sessions and no prior familiarity with the area of communication complexity will be expected of the audience.

• Sagnik Mukhopadhyay

  Title: Graph problems through the lens of communication complexity: II

  Abstract: In the first two sessions of the workshop, we will introduce the audience to the area of communication complexity with the focus on graph problems. In the first half, we review the classical models of deterministic and randomised communication, and show, by means of reductions, how lower bounds are derived by appealing to well-studied problems such as index function, pointer chasing and set-disjointness. In the second half, we show a few communication protocols for solving fundamental graph problems such as minimum cut, vertex connectivity and bipartite maximum matching. We also mention how these communication protocols help us come up with efficient algorithms for these problems in various other models of computation.

  These sessions are designed as boot-camp sessions and no prior familiarity with the area of communication complexity will be expected of the audience.

• Amit Kumar

  Title: Efficient Algorithms for the Disjoint Shortest Paths Problem and its Extensions

  Abstract: In this talk, we shall consdier the 2-Disjoint Shortest Paths problem: given a directed weighted graph and two terminal pairs $(s_1,t_1)$ and $(s_2,t_2)$, decide whether there exist vertex-disjoint shortest paths between each pair.

  Building on recent advances in disjoint shortest paths for DAGs and undirected graphs (Akmal et al. 2024), we present an $O(mn \log n)$-time algorithm for this problem in weighted directed graphs that do not contain negative or zero weight cycles. This algorithm presents a significant improvement over the previously known $O(m^5n)$-time bound (Berczi et al. 2017). Our approach exploits the algebraic structure of polynomials that enumerate shortest paths between terminal pairs. A key insight is that these polynomials admit a recursive decomposition, enabling efficient evaluation via dynamic programming over fields of characteristic two.

  In addition, we extend our techniques to a more general setting: given two terminal pairs $(s_1, t_1)$ and $(s_2, t_2)$ in a directed graph, find the minimum possible number of vertex intersections between any shortest path from $s_1$ to $t_1$ and $s_2$ to $t_2$. We call this the Minimum 2-Disjoint Shortest Paths problem. We provide the first efficient algorithm for this problem, including an $O(m^2 n^3)$-time algorithm for directed graphs with positive edge weights, and an $O(m+n)$-time algorithm for DAGs and undirected graphs.

  This is joint work with Keerti Choudhary and Lakshay Saggi.

• Thatchaphol Saranurak

  Title: Design templates of Dynamic Graph Algorithms

  Abstract: I will explain three simple yet powerful templates behind many dynamic graph algorithms in the literature, including (1) rebuilding in the background, (2) batching, and (3) vertex sparsifiers. As examples, we will see algorithms for dynamic approximate matching, dynamic connectivity, and dynamic minmax paths.

• Deeparnab Chakrabarty

  Title: Graph (and hypergraph) Connectivity using CUT queries

  Abstract: In this talk, we consider the problem of designing algorithms for graphs when we can access the latter only via certain kinds of queries. In particular, we will focus on CUT queries (we input a subset of vertices and obtain the size of the edge cut induced by the subset) and the problem of determining the connectivity of the graph. The plan is to give a sampling of techniques with some time spent on the “coin weighing paradigm” leading to an $O(n)$ query (in expectation) for the connectivity problem. Time permitting I will discuss the generalization of this problem to hypergraphs.

• Barna Saha

  Title: Fine-Grained Optimality of Partially Dynamic Shortest Paths

  Abstract: Single Source Shortest Paths (SSSP) is arguably the most basic problem in graph algorithms. This talk explores its complexity in the dynamic regime and explains why, despite decades of progress, designing an exact dynamic SSSP algorithm that improves upon the naïve strategy of re-running a static algorithm after each update remains out of reach.

• Amit Chakrabarti

  Title: Graph Coloring Vignettes: Streaming, Communication, Robustness

  Abstract: Graph coloring is a deeply studied algorithmic problem, besides being a fundamental topic in combinatorics. It is trivial to color a graph with maximum degree $\Delta$ using at most $\Delta+1$ colors... or is it? In the many models of "sublinear algorithms" in vogue today, producing a $(\Delta+1)$-coloring efficiently is a challenging algorithmic problem. A landmark result of Assadi, Chen, and Khanna [ACK 2019] gave a randomized streaming algorithm for this problem with essentially optimal space usage. That work inspired a number of subsequent works, some of which I shall survey in this talk. Among the questions we shall address are: (1) Can the [ACK 2019] algorithm be derandomized? (2) Can we improve upon its chromatic parameter? (3) Does this space of algorithmic ideas lead to interesting communication protocols?

• Naveen Garg

  Title: Seymour instances, half-integral flows and uncrossable cut-cover

  Abstract: The cut condition is necessary and sufficient for routing of multicommodity flow when the union of the supply and demand graph is planar; such instances are called Seymour instances. We consider the problem of maximizing ½-integral flow and provide a tight relation with integer multicut in such instances. To do so we prove that the primal-dual algorithm of Williamson et.al. for finding a minimum cover of uncrossable set functions can be modified to obtain a half-integral dual.

• Saket Saurabh

  Title: The Curious Case of Hedge Cut

  Abstract: In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and we ask: what is the minimum number of hedges we need to delete to disconnect the graph? Ghaffari, Karger, and Panigrahi (SODA 2017) showed that Hedge Cut can be solved in quasipolynomial time, which raised the hope that there might even be a polynomial-time algorithm. Jaffke, Lima, Masarík, Pilipczuk, and Souza (SODA 2023) complemented this by showing that, assuming the Exponential Time Hypothesis (ETH), no polynomial-time algorithm exists.

  In this talk, we show that Hedge Cut is fixed-parameter tractable when parameterized by the solution size $\ell$. In particular, we give an algorithm with running time \[ \binom{O(\log n) + \ell}{\ell} \cdot m^{O(1)}, \] which can be upper bounded by \[ c^{\ell} \cdot (n+m)^{O(1)} \] for any constant $c>1$. This running time simultaneously reflects that the problem is quasipolynomial-time solvable and that it is fixed-parameter tractable in $\ell$.

  We further generalize this to an algorithm for Hedge $k$-Cut, with running time \[ \binom{O(k \log n) + \ell}{\ell} \cdot n^{O(k)} \cdot m^{O(1)}. \]

• Debmalya Panigrahi

  Title: Network Unreliability in Graphs and Hypergraphs

  Abstract: The (all-terminal) network unreliability problem asks for an estimation of the probability that a given network disconnects when every edge (or hyperedge) fails independently with a given probability. This is one of the original #P-hard problems from Valiant's seminal 1979 paper introducing this complexity class for counting problems. In this talk, I will describe recent progress in this problem on graphs and hypergraphs.

• Greg Bodwin

  Title: The Forbidden Structure Method in Graph Metric Sparsification

  Abstract: We will survey the "forbidden structure method," a recently-popular technique for building graph metric sparsifiers. In this method, one uses a simple greedy algorithm to construct a sparsifier, and then shows that the sparsifier may not have a certain structure as a subgraph (or similar). Then, one applies bounds from extremal combinatorics to control the maximum possible size of a graph avoiding this structure. We will demonstrate this method on spanners and preservers as our main sparsifiers of interest.

  The first part of this talk will focus on algorithms that reduce to forbidden structure problems. The second part will overview methods from extremal combinatorics for proving bounds on these problems.