Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) running time bound due to Even and Tarjan [16]. By well-known reductions, this also establishes an O(m^10/7)-time algorithm for the maximum-cardinality bipartite matching problem. That, in turn, gives an improvement over the celebrated O(mn^1/2) running time bound of Hopcroft and Karp [25] whenever the input graph is sufficiently sparse. At a very high level, our results stem from acquiring a deeper understanding of interior-point methods - a powerful tool in convex optimization - in the context of flow problems, as well as, utilizing certain interplay between maximum flows and bipartite matchings.

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emerged in recent decades, such as processing the data in a stream, parallel processing, and data compression. The aim of this thesis is to apply these techniques to various important graph theoretical problems. Our contributions can be broadly classified into two categories: spectral graph theory, and maximum matching.Spectral Graph Theory. Spectral sparsification is a technique of rendering an arbitrary graph sparse, while approximately preserving the quadratic form of the Laplacian matrix. In this thesis, we extend the result of (Kapralov et al.), and propose a sketch and corresponding decoding algorithm for constructing a spectral sparsifier from a dynamic stream of edge insertions and deletions. The size of the resulting sparsifier, the size of the sketch, and the decoding time are all nearly linear in the number of vertices, and consequently nearly optimal.The concept of spectral sparsification has recently been generalized to hypergraphs (Soma and Yoshida) -- an analogue of graphs for modeling higher order relationships. As one of the main contributions of the thesis, we prove for the first time the existence of nearly-linear sized spectral sparsifiers for arbitrary hypergraphs, and provide a corresponding nearly-linear time algorithm for constructing them. Through a lower bound construction, we show that our sparsifiers achieve nearly-optimal compression of the hypergraph spectral structure.On the more applied side of spectral graph theory, we present a fully scalable MPC (massively parallel computation) algorithm which is capable of simulating a large number of independent random walks of length L from an arbitrary starting distribution in O(log(L)) rounds.Maximum Matching. We propose a novel randomized composable coreset for the problem of maximum matching, called the matching skeleton. The coreset achieves a 1/2 approximation, while having fewer than n edges.We also propose a new, highly space-efficient variant of a peeling algorithm for maximum matching. With this, we are able to approximate the maximum matching size of a graph to within a constant factor, using a stream of m uniformly random edges (where m is the total number of edges), in as little as O(log^2(n)) space. Conversely, we show that significantly fewer (that is m^(1-Omega(1))) samples do not suffice, even with unlimited space. Finally, we design a Local Computation Algorithm, which implicitly construct a constant-approximate maximum matching in time and space that is nearly linear in the maximum degree.

EPFL2022

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. Somewhat surprisingly, similar polyhedral techniques can be harnessed in the two seemingly disparate settings. In the first part of the thesis we address a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given directed graph with weights on edges. Due to its NP-hardness, the theoretical study of algorithms for ATSP has focused on approximation algorithms: ones that are provably both efficient and give solutions competitive with the optimum. Specifically, a rho-approximation algorithm for ATSP is one that runs in polynomial time and always outputs a tour that is at most rho times longer than the shortest tour. Finding such an approximation algorithm with rho bounded (i.e., a constant factor) had been a long-standing open problem. In this thesis, we give such an algorithm. Our approximation guarantee is analyzed with respect to the standard linear programming relaxation, and thus our result also confirms the conjectured constant integrality gap of that relaxation. Our techniques build upon the constant-factor approximation algorithm for the special case of node-weighted metrics due to Svensson. In particular, we give a generic reduction to structured instances that resemble but are more general than those arising from node-weighted metrics. This reduction takes advantage of a laminar family of vertex sets that arises from the linear programming relaxation. In the second part of the thesis we address the perfect matching problem. The first polynomial-time algorithm for it, given by Edmonds in 1965, is historically associated with the introduction of the class P and our notion that polynomial-time'' means efficient''. That algorithm is sequential and deterministic. We have also known since the 1980s that the matching problem has efficient parallel algorithms if the use of randomness is allowed. Formally, it is in the class RNC, i.e., it has randomized algorithms that use polynomially many processors and run in polylogarithmic time. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. In this thesis we show that the matching problem is in quasi-NC. That is, we give a deterministic parallel algorithm that runs in O(log^3 n) time on n^{O(log^2 n)} processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain an RNC algorithm. Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

EPFL2019

Generalized vertex coloring problems using split graphs

Tinaz Ekim

Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. For mathematicians, it is interesting for an additional reason: it is extremely hard to solve it in an efficient way. In this thesis, we introduce several problems generalizing the usual vertex coloring problem, and hence, extending its application domain. We say that a graph is (p, k)-colorable if its vertex set can be partitioned into p cliques and k stable sets. Then, for a given p (respectively k), one may ask the following questions: how to choose p cliques (respectively k stable sets) to be removed from the graph such that the number of stable sets (respectively cliques) partitioning the remaining vertices is minimized? These are called (p, k)-coloring problems. We also introduce Min Split-coloring which is, given a graph G, the problem of minimizing k such that G is (k, k)-colorable. Along the saine line, given a graph G, the objective of the problem Min Cocoloring is to minimize p + k such that G is (p, k)-colorable. All these problems, called together generalized coloring problems, are obviously at least as difficult as Min Coloring. The purpose of this dissertation is to study generalized coloring problems in nome restricted classes of graphs in order to bring a new insight on the relative difficulties of these problems. To this end, we detect in a more precise way the limits between NP-hard and polynomially solvable problems. Chapter 1 introduces generalized coloring problems by emphasizing nome preliminary results which will guide the questions to handle in the following chapters. Chapter 2 exposes the first clans of graphs, namely cacti, where Min Split-coloring is shown to be polynomially solvable. We also observe that generalized coloring problems can be polynomially solved in triangulated graphs. The main result of Chapter 3 is a new characterization of cographs: it is equivalent to say that G is a cograph, and to state that, for every subgraph G' ⊆ G, G' is (p, k)-colorable if and only if G' [V \ K] is (p – 1, k)-colorable, where K induces a maximum clique of G'. This result implies simple combinatorial algorithme to solve all generalized coloring problems; the one for Min Cocoloring improves the best time complexity known so far. In Chapter 4, we handle the recognition of polar graphs which can be seen as a particular (p, k)-coloring, where p cliques are independent (i.e., not linked at all) and k stable sets form a complete k-partite graph. It is known that the recognition of polar graphs is NP-complete. Here, we determine the first clans of graphs, namely cographs, where the polar graphs can be recognized in polynomial time, more precisely in time O(n log n). We also give a characterization by forbidden subgraphs. In the came manner, we characterize monopolar cographs, i.e., cographs admitting a polar partition with at most one clique or at most one stable set. Chapter 5 is devoted to generalized coloring problems in line graphs. Here, we detect the first classes of graphs, namely line graphs of trees, line graphs of bipartite graphs and line graphs of line-perfect graphs, where generalized coloring problems diverge in terms of NP-hardness. In Chapter 6 we study the approximability of generalized coloring problems in line graphs, in comparability graphs and in general graphs. We derive approximation algorithms with a performance guarantee using both the standard approximation ratio and the differential approximation ratio. We show that both Min Split-coloring and Min Cocoloring are at least as hard as Min Coloring to approximate from the standard approximation ratio point of view, whereas, they admit a polynomial time differential approximation scheme and Min Coloring only a constant differential approximation ratio. We also show that Min Cocoloring reduces to Min Split-coloring in all classes of graphs closed under addition of disjoint cliques and under join of a complete k-partite graph. In Chapter 7, we handle two different applications of Min Split-coloring in permutation graphs. They give birth to a new problem, called Min Threshold-coloring, that we study in the came spirit as the other generalized coloring problems. In the last chapter, we present several open questions arising from this thesis.

EPFL2006