A recent breakthrough by [LNPSY STOC'21] showed that solving s-t vertex connectivity is sufficient (up to polylogarithmic factors) to solve (global) vertex connectivity in the sequential model. This raises a natural question: What is the relationship between s-t and global vertex connectivity in other computational models? In this paper, we demonstrate that the connection between global and s-t variants behaves very differently across computational models. In parallel and distributed models, we obtain almost tight reductions from global to s-t vertex connectivity. In PRAM, this leads to a n^ω+o(1)-work and n^o(1)-depth algorithm for vertex connectivity, improving over the 35-year-old Õ(n^ω+1-work O(log²n)-depth algorithm by [LLW FOCS'86], where ω is the matrix multiplication exponent and n is the number of vertices. In CONGEST, the reduction implies the first sublinear-round vertex connectivity algorithm when the diameter is moderately small. This answers an open question in [JM STOC'23]. In contrast, we show that global vertex connectivity is strictly harder than s-t vertex connectivity in the two-party communication setting, requiring n^1.5 bits of communication. The s-t variant was known to be solvable in Õ(n) communication [BvdBEMN FOCS'22]. Our results resolve open problems raised by [MN STOC'20, BvdBEMN FOCS'22, AS SOSA'23]. At the heart of our results is a new graph decomposition framework we call common-neighborhood clustering, which can be applied in multiple models. Finally, we observe that global vertex connectivity cannot be solved without using s-t vertex connectivity by proving an s-t to global reduction in dense graphs in the PRAM and communication models.

Matchings, Maximum Flow, and Matroid Intersections are fundamental combinatorial optimization problems that have been studied extensively since the inception of computer science. A series of breakthroughs in graph algorithms and continuous optimization in the past decade has led to exciting almost-optimal algorithms for maximum flow and bipartite matching. However, we are still far from fully understanding these problems. First, it remains open how to solve these problems in modern models of computation, such as parallel, dynamic, online, and communication models. Second, as algorithms become more sophisticated in pursuit of efficiency, they often sacrifice simplicity, potentially obscuring valuable combinatorial insights. This raises a fundamental question: can we develop efficient algorithms that maintain the combinatorial nature of these problems, rather than relying on linear algebra and continuous methods?

This thesis returns to the classic augmenting paths framework---the original approach to matchings, maximum flow, and matroid intersection---with the goal of developing new efficient combinatorial algorithms. Our key contributions include the first combinatorial algorithm achieving almost-linear time for maximum flow on dense graphs, and the first subquadratic independence-query algorithm for matroid intersection. For modern computational models, our contributions include an improved online rounding scheme for fractional matching (leading to an optimal online edge coloring algorithm), a resolution of the query and communication complexity for bipartite matching, and the first sublinear-round parallel algorithms for matroid intersection.

Matchningar, Maximala Flöden och Matroidsnitt är grundläggande kombinatoriska optimeringsproblem som har studerats ingående sedan datorvetenskapens början.  En serie genombrott inom grafalgoritmik och kontinuerlig optimering under det senaste årentiondet har lett till imponerande nästan optimala algoritmer för maximalt flöde och bipartit matchning. Vi är dock fortfarande långt ifrån att fullt förstå dessa problem. För det första återstår frågan om hur man kan lösa dessa problem i andra beräkningsmodeller, såsom parallell-, dynamisk-, online- och kommunikationsmodeller. För det andra, när algoritmer blir allt mer sofistikerade i deras effektivitetsträvan, offrar de ofta enkelhet, vilket potentiellt kan dölja värdefulla kombinatoriska insikter. Detta motiverar en grundläggande fråga: kan vi utveckla effektiva algoritmer som bevarar den kombinatoriska karaktären hos dessa problem, istället för att förlita sig på linjär algebra och kontinuerliga metoder?

Denna avhandling återgår till de klassiska augmenting-pathsalgoritmerna---det ursprungliga angreppssättet för matchningar, maximalt flöde och matroid-snitt---med målet att utveckla nya effektiva kombinatoriska algoritmer. Våra viktigaste bidrag inkluderar den första kombinatoriska algoritmen som uppnår nästan linjär tid för maximalt flöde på täta grafer, och den första subkvadratiska independence-query-algoritmen för matroidsnitt. För moderna beräkningsmodeller inkluderar våra bidrag förbättrade  onlineavrundningsalgorithmer för fraktionell matchning (vilket leder till en optimal onlinealgoritm för kantfärgning), en lösning av query- och kommunikationskomplexiteten för bipartit matchning, och de första sublinjära parallella algoritmerna för matroidsnitt.

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with n vertices and edge capacities from {1,…,U} in n^2+o(1)logU time, which is almost optimal in dense graphs. Our algorithm is a novel implementation of the classical augmenting-path framework; we list augmenting paths more efficiently using a new variant of the push-relabel algorithm that uses additional edge weights to guide the algorithm, and we derive the edge weights by constructing a directed expander hierarchy.

Even in unit-capacity graphs, this breaks the long-standing O(m⋅min{√m,n^2/3}) time bound of the previous combinatorial algorithms by Karzanov (1973) and Even and Tarjan (1975) when the graph has m=ω(n^4/3) edges. Notably, our approach does not rely on continuous optimization nor heavy dynamic graph data structures, both of which are crucial in the recent developments that led to the almost-linear time algorithm by Chen et al. (FOCS 2022). Our running time also matches the n^2+o(1) time bound of the independent combinatorial algorithm by Chuzhoy and Khanna (STOC 2024) for computing the maximum bipartite matching, a special case of maximum flow.

We present a combinatorial algorithm for computing exact maximum flows in directed graphs with n vertices and edge capacities from 1, ·, U in n2+o(1) log U time, which is almost optimal in dense graphs. Our algorithm is a novel implementation of the classical augmenting-path framework; we list augmenting paths more efficiently using a new variant of the push-relabel algorithm that uses additional edge weights to guide the algorithm, and we derive the edge weights by constructing a directed expander hierarchy. Even in unit-capacity graphs, this breaks the long-standing O(m · √m,n2/3) time bound of the previous combinatorial algorithms by Karzanov (1973) and Even and Tarjan (1975) when the graph has m=Ω(n4/3) edges. Notably, our approach does not rely on continuous optimization nor heavy dynamic graph data structures, both of which are crucial in the recent developments that led to the almost-linear time algorithm by Chen et al. (FOCS 2022). Our running time also matches the n2+o(1) time bound of the independent combinatorial algorithm by Chuzhoy and Khanna (STOC 2024) for computing the maximum bipartite matching, a special case of maximum flow.

We devise a polynomial-time algorithm for partitioning a simple polygon P into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades [Avis and Toussaint, Pattern Recognit., 1981] and it has been repeated frequently, for example in O'Rourke's famous book [Art Gallery Theorems and Algorithms, 1987]. In addition to its strong theoretical motivation, the problem is also motivated by practical domains such as CNC pocket milling, motion planning, and shape parameterization. The only previously known algorithm for a non-trivial special case is for P being both monotone and rectilinear [Liu and Ntafos, Algorithmica, 1991]. For general polygons, an algorithm was only known for the restricted version in which Steiner points are disallowed [Keil, SIAM J. Comput., 1985], meaning that each corner of a piece in the partition must also be a corner of P. Interestingly, the solution size for the restricted version may be linear for instances where the unrestricted solution has constant size. The covering variant in which the pieces are star-shaped but allowed to overlap - known as the Art Gallery Problem - was recently shown to be ∃ℝ-complete and is thus likely not in NP [Abrahamsen, Adamaszek and Miltzow, STOC 2018 & J. ACM 2022]; this is in stark contrast to our result. Arguably the most related work to ours is the polynomial-time algorithm to partition a simple polygon into a minimum number of convex pieces by Chazelle and Dobkin [STOC, 1979 & Comp. Geom., 1985].

The classic theorem of Vizing (Diskret. Analiz.'64) asserts that any graph of maximum degree Δcan be edge colored (offline) using no more than Γ+1 colors (with Δbeing a trivial lower bound). In the online setting, Bar-Noy, Motwani and Naor (IPL'92) conjectured that a (1+o(1))Γ-edge-coloring can be computed online in n-vertex graphs of maximum degree Γ=ω(logn). Numerous algorithms made progress on this question, using a higher number of colors or assuming restricted arrival models, such as random-order edge arrivals or vertex arrivals (e.g., AGKM FOCS'03, BMM SODA'10, CPW FOCS'19, BGW SODA'21, KLSST STOC'22). In this work, we resolve this longstanding conjecture in the affirmative in the most general setting of adversarial edge arrivals. We further generalize this result to obtain online counterparts of the list edge coloring result of Kahn (J. Comb. Theory. A'96) and of the recent "local"edge coloring result of Christiansen (STOC'23).

We provide a simple online ∆(1 + o(1))-edge-coloring algorithm for bipartite graphs of maximum degree ∆ = ω(log n) under adversarial vertex arrivals on one side of the graph. Our algorithm slightly improves the result of (Cohen, Peng and Wajc, FOCS19), which was the first, and currently only, to obtain an asymptotically optimal ∆(1 + o(1)) guarantee for an adversarial arrival model. More importantly, our algorithm provides a new, simpler approach for tackling online edge coloring.

We initiate the study of matroid problems in a new oracle model called dynamic oracle. Our algorithms in this model lead to new bounds for some classic problems, and a "unified"algorithm whose performance matches previous results developed in various papers for various problems. We also show a lower bound that answers some open problems from a few decades ago. Concretely, our results are as follows. Improved algorithms for matroid union and disjoint spanning trees. We show an algorithm with Õk(n+rr) dynamic-rank-query and time complexities for the matroid union problem over k matroids, where n is the input size, r is the output size, and Õk hides poly(k, log(n)). This implies the following consequences. (i) An improvement over the Õk(nr) bound implied by [Chakrabarty-Lee-Sidford-Singla-Wong FOCS'19] for matroid union in the traditional rank-query model. (ii) An Õk(|E|+|V||V|)-time algorithm for the k-disjoint spanning tree problem. This is nearly linear for moderately dense input graphs and improves the Õk(|V||E|) bounds of Gabow-Westermann [STOC'88] and Gabow [STOC'91]. Consequently, this gives improved bounds for, e.g., Shannon Switching Game and Graph Irreducibility. Matroid intersection. We show a matroid intersection algorithm with Õ(nr) dynamic-rank-query and time complexities. This implies new bounds for some problems (e.g. maximum forest with deadlines) and bounds that match the classic ones obtained in various papers for various problems, e.g. colorful spanning tree [Gabow-Stallmann ICALP'85], graphic matroid intersection [Gabow-Xu FOCS'89], simple job scheduling matroid intersection [Xu-Gabow ISAAC'94], and Hopcroft-Karp combinatorial bipartite matching. More importantly, this is done via a "unified"algorithm in the sense that an improvement over our dynamic-rank-query algorithm would imply improved bounds for all the above problems simultaneously. Lower bounds. We show simple super-linear (ω(nlogn)) query lower bounds for matroid intersection and union problems in our dynamic-rank-oracle and the traditional independence-query models; the latter improves the previous log2(3)n-o(n) bound by Harvey [SODA'08] and answers an open problem raised by, e.g., Welsh [1976] and CLSSW [FOCS'19].

In the dynamic approximate maximum bipartite matching problem we are given bipartite graph G undergoing updates and our goal is to maintain a matching of G which is large compared the maximum matching size µ(G). We define a dynamic matching algorithm to be α (respectively (α, β))-approximate if it maintains matching M such that at all times |M| ≥ µ(G) · α (respectively |M| ≥ µ(G) · α − β). We present the first deterministic (1 − ε)-approximate dynamic matching algorithm with O(poly(ε−1)) amortized update time for graphs undergoing edge insertions. Previous solutions either required super-constant [Gupta FSTTCS’14, Bhattacharya-Kiss-Saranurak SODA’23] or exponential in 1/ε [Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA’19] update time. Our implementation is arguably simpler than the mentioned algorithms and its description is self contained. Moreover, we show that if we allow for additive (1, ε · n)-approximation our algorithm seamlessly extends to also handle vertex deletions, on top of edge insertions. This makes our algorithm one of the few small update time algorithms for (1 − ε)-approximate dynamic matching allowing for updates both increasing and decreasing the maximum matching size of G in a fully dynamic manner. Our algorithm relies on the weighted variant of the celebrated Edge-Degree-Constrained-Subgraph (EDCS) datastructure introduced by [Bernstein-Stein ICALP’15]. As far as we are aware we introduce the first application of the weighted-EDCS for arbitrarily dense graphs. We also present a significantly simplified proof for the approximation ratio of weighed-EDCS as a matching sparsifier compared to [Bernstein-Stein], as well as simple descriptions of a fractional matching and fractional vertex cover defined on top of the EDCS. Considering the wide range of applications EDCS has found in settings such as streaming, sub-linear, stochastic and more we hope our techniques will be of independent research interest outside of the dynamic setting.

We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models. Our results answer open problems that have been raised repeatedly since at least three decades ago [Hajnal, Maass, and Turan STOC'88; Ivanyos, Klauck, Lee, Santha, and de Wolf FSTTCS'12; Dobzinski, Nisan, and Oren STOC'14; Nisan SODA'21] and tighten the lower bounds shown by Beniamini and Nisan [STOC'21] and Zhang [ICALP'04]. We also settle the communication complexity of the generalizations of BMM, such as maximum-cost bipartite b-matching and trans-shipment; and the query complexity of unique bipartite perfect matching (answering an open question by Beniamini [2022]). Our algorithms and lower bounds follow from simple applications of known techniques such as cutting planes methods and set disjointness.