BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Julia Chuzhoy

Julia Chuzhoy appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsDiscrete MathematicsComputational GeometryComputational Complexitymath.CO

Catalog footprint

What is connected

20works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

20 published item(s)

preprint2025arXiv

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs

We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph $G$, compute a vertex-cut $(L,S,R)$ in $G$ of minimum value, which is defined to be the total weight of all vertices in $S$. The problem, together with its edge-based variant, is one of the most basic in graph theory and algorithms, and has been studied extensively. The fastest currently known algorithm for directed global minimum vertex-cut (Henzinger, Rao and Gabow, FOCS 1996 and J. Algorithms 2000) has running time $\tilde{O}(mn)$, where $m$ and $n$ denote the number of edges and vertices in the input graph, respectively. A long line of work over the past decades led to faster algorithms for other main versions of the problem, including the undirected edge-based setting (Karger, STOC 1996 and J. ACM 2000), directed edge-based setting (Cen et al., FOCS 2021), and undirected vertex-based setting (Chuzhoy and Trabelsi, STOC 2025). However, for the vertex-based version in directed graphs, the 29 year-old $\tilde{O}(mn)$-time algorithm of Henzinger, Rao and Gabow remains the state of the art to this day, in all edge-density regimes. In this paper we break the $Θ(mn)$ running time barrier for the first time, by providing a randomized algorithm for directed global minimum vertex-cut, with running time $O\left(mn^{0.976}\cdot\operatorname{polylog} W\right)$ where $W$ is the ratio of largest to smallest vertex weight. Additionally, we provide a randomized $O\left(\min\left\{m^{1+o(1)}\cdot k,n^{2+o(1)}\right\}\right)$-time algorithm for the unweighted version of directed global minimum vertex-cut, where $k$ is the value of the optimal solution. The best previous algorithm for the problem achieved running time $\tilde O\left(\min\left\{k^2 \cdot m, mn^{11/12+o(1)}, n^{2+o(1)}\right\}\right)$ (Forster et al., SODA 2020, Li et al., STOC 2021).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs

We consider the classical Minimum Crossing Number problem: given an $n$-vertex graph $G$, compute a drawing of $G$ in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on $Δ$ -- the maximum vertex degree in $G$. The best current approximation algorithm achieves an $O(n^{1/2-\varepsilon}\cdot \text{poly}(Δ\cdot\log n))$-approximation, for a small fixed constant $ε$, while the best negative result is APX-hardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomized $O\left(2^{O((\log n)^{7/8}\log\log n)}\cdot\text{poly}(Δ)\right )$-approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial in $n$ approximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial in $n$). In order to achieve this approximation factor, we design a new algorithm for a closely related problem called Crossing Number with Rotation System, in which, for every vertex $v\in V(G)$, the circular ordering, in which the images of the edges incident to $v$ must enter the image of $v$ in the drawing is fixed as part of the input. Combining this result with the recent reduction of [Chuzhoy, Mahabadi, Tan '20] immediately yields the improved approximation algorithm for Minimum Crossing Number. We introduce several new technical tools, that we hope will be helpful in obtaining better algorithms for the problem in the future.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Towards Better Approximation of Graph Crossing Number

Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. Despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a $\tilde O(\sqrt n)$-approximation, while the best current negative result is APX-hardness. All current approximation algorithms for the problem build on the same paradigm: compute a set $E'$ of edges (called a \emph{planarizing set}) such that $G\setminus E'$ is planar; compute a planar drawing of $G\setminus E'$; then add the drawings of the edges of $E'$ to the resulting drawing. Unfortunately, there are examples of graphs, in which any implementation of this method must incur $Ω(\text{OPT}^2)$ crossings, where $\text{OPT}$ is the value of the optimal solution. This barrier seems to doom the only known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than $O(\sqrt n)$-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm that, given a bounded-degree graph $G$ and a planarizing set $E'$ of its edges, computes another set $E''$ with $E'\subseteq E''$, such that $|E''|$ is relatively small, and there exists a near-optimal drawing of $G$ in which only edges of $E''$ participate in crossings. This allows us to reduce the Crossing Number problem to \emph{Crossing Number with Rotation System} -- a variant in which the ordering of the edges incident to every vertex is fixed as part of input. We show a randomized algorithm for this new problem, that allows us to obtain an $O(n^{1/2-ε})$-approximation for Crossing Number on bounded-degree graphs, for some constant $ε>0$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

We consider the classical Minimum Balanced Cut problem: given a graph $G$, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first {\em deterministic, almost-linear time} approximation algorithm for this problem. Specifically, our algorithm, given an $n$-vertex $m$-edge graph $G$ and any parameter $1\leq r\leq O(\log n)$, computes a $(\log m)^{r^2}$-approximation for Minimum Balanced Cut on $G$, in time $O\left ( m^{1+O(1/r)+o(1)}\cdot (\log m)^{O(r^2)}\right )$. In particular, we obtain a $(\log m)^{1/ε}$-approximation in time $m^{1+O(1/\sqrtε)}$ for any constant $ε$, and a $(\log m)^{f(m)}$-approximation in time $m^{1+o(1)}$, for any slowly growing function $m$. We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of $G$ that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an $n$-vertex graph is $n^{o(1)}$, thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in $n$ factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition

In the decremental single-source shortest paths (SSSP) problem, the input is an undirected graph $G=(V,E)$ with $n$ vertices and $m$ edges undergoing edge deletions, together with a fixed source vertex $s\in V$. The goal is to maintain a data structure that supports shortest-path queries: given a vertex $v\in V$, quickly return an (approximate) shortest path from $s$ to $v$. The decremental all-pairs shortest paths (APSP) problem is defined similarly, but now the shortest-path queries are allowed between any pair of vertices of $V$. Both problems have been studied extensively since the 80's, and algorithms with near-optimal total update time and query time have been discovered for them. Unfortunately, all these algorithms are randomized and, more importantly, they need to assume an oblivious adversary. Our first result is a deterministic algorithm for the decremental SSSP problem on weighted graphs with $O(n^{2+o(1)})$ total update time, that supports $(1+ε)$-approximate shortest-path queries, with query time $O(|P|\cdot n^{o(1)})$, where $P$ is the returned path. This is the first $(1+ε)$-approximation algorithm against an adaptive adversary that supports shortest-path queries in time below $O(n)$, that breaks the $O(mn)$ total update time bound of the classical algorithm of Even and Shiloah from 1981. Our second result is a deterministic algorithm for the decremental APSP problem on unweighted graphs that achieves total update time $O(n^{2.5+δ})$, for any constant $δ>0$, supports approximate distance queries in $O(\log\log n)$ time; the algorithm achieves an $O(1)$-multiplicative and $n^{o(1)}$-additive approximation on the path length. All previous algorithms for APSP either assume an oblivious adversary or have an $Ω(n^{3})$ total update time when $m=Ω(n^{2})$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Packing Low-Diameter Spanning Trees

Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every $k$-edge connected graph $G$ contains a collection $\cal{T}$ of $\lfloor k/2 \rfloor$ edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing $\cal{T}$ is the largest diameter of any tree in $\cal{T}$. A desirable property of a tree packing, that is both sufficient and necessary for leveraging the high connectivity of a graph in distributed communication, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing, whose diameter is sublinear in $|V(G)|$, in a low-diameter graph $G$, or alternatively how to show that such a packing does not exist. In this paper we provide first non-trivial upper and lower bounds on the diameter of tree packing. First, we show that, for every $k$-edge connected $n$-vertex graph $G$ of diameter $D$, there is a tree packing $\cal{T}$ of size $Ω(k)$, diameter $O((101k\log n)^D)$, that causes edge-congestion at most $2$. Second, we show that for every $k$-edge connected $n$-vertex graph $G$ of diameter $D$, the diameter of $G[p]$ is $O(k^{D(D+1)/2})$ with high probability, where $G[p]$ is obtained by sampling each edge of $G$ independently with probability $p=Θ(\log n/k)$. This provides a packing of $Ω(k/\log n)$ edge-disjoint trees of diameter at most $O(k^{(D(D+1)/2)})$ each. We then prove that these two results are nearly tight. Lastly, we show that if every pair of vertices in a graph has $k$ edge-disjoint paths of length at most $D$ connecting them, then there is a tree packing of size $k$, diameter $O(D\log n)$, causing edge-congestion $O(\log n)$. We also provide several applications of low-diameter tree packing in distributed computation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Improved Approximation for Node-Disjoint Paths in Planar Graphs

We study the classical Node-Disjoint Paths (NDP) problem: given an $n$-vertex graph $G$ and a collection $M=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of vertices of $G$ called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of $O(\sqrt n)$ on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than $Ω(\log^{1/2-δ}n)$-approximation for any constant $δ$, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is $Ω(\sqrt n)$ for NDP, even in planar graphs. In this paper, we break the barrier of $O(\sqrt n)$ on the approximability of the NDP problem in planar graphs and obtain an $\tilde O(n^{9/19})$-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Improved Bounds for the Excluded Grid Theorem

We study the Excluded Grid Theorem of Robertson and Seymour. This is a fundamental result in graph theory, that states that there is some function $f: Z^+\rightarrow Z^+$, such that for all integers $g>0$, every graph of treewidth at least $f(g)$ contains the $(g\times g)$-grid as a minor. Until recently, the best known upper bounds on $f$ were super-exponential in $g$. A recent work of Chekuri and Chuzhoy provided the first polynomial bound, by showing that treewidth $f(g)=O(g^{98}\operatorname{poly}\log g)$ is sufficient to ensure the existence of the $(g\times g)$-grid minor in any graph. In this paper we improve this bound to $f(g)=O(g^{19}\operatorname{poly}\log g)$. We introduce a number of new techniques, including a conceptually simple and almost entirely self-contained proof of the theorem that achieves a polynomial bound on $f(g)$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

New Hardness Results for Routing on Disjoint Paths

In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection $\mathcal{M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand, pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(\sqrt n)$, while the best current negative result is an $Ω(\log^{1/2-δ}n)$-hardness of approximation for any constant $δ$, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $\tilde O(n^{1/4})$-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $\tilde O(n^{9/19})$. The best currently known lower bound on the approximability of both these versions of the problem is APX-hardness. In this paper we prove that NDP is $2^{Ω(\sqrt{\log n})}$-hard to approximate, unless all problems in NP have algorithms with running time $n^{O(\log n)}$. Our result holds even when the underlying graph is a planar graph with maximum vertex degree $3$, and all source vertices lie on the boundary of a single face (but the destination vertices may lie anywhere in the graph). We extend this result to the closely related Edge-Disjoint Paths problem, showing the same hardness of approximation ratio even for sub-cubic planar graphs with all sources lying on the boundary of a single face.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Approximating Maximum Independent Set of Rectangles

We study the Maximum Independent Set of Rectangles (MISR) problem: given a set of $n$ axis-parallel rectangles, find a largest-cardinality subset of the rectangles, such that no two of them overlap. MISR is a basic geometric optimization problem with many applications, that has been studied extensively. Until recently, the best approximation algorithm for it achieved an $O(\log \log n)$-approximation factor. In a recent breakthrough, Adamaszek and Wiese provided a quasi-polynomial time approximation scheme: a $(1-ε)$-approximation algorithm with running time $n^{O(\operatorname{poly}(\log n)/ε)}$. Despite this result, obtaining a PTAS or even a polynomial-time constant-factor approximation remains a challenging open problem. In this paper we make progress towards this goal by providing an algorithm for MISR that achieves a $(1 - ε)$-approximation in time $n^{O(\operatorname{poly}(\log\log{n} / ε))}$. We introduce several new technical ideas, that we hope will lead to further progress on this and related problems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Polynomial Bounds for the Grid-Minor Theorem

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The theorem states that for every grid $H$, every graph whose treewidth is large enough relative to $|V(H)|$ contains $H$ as a minor. This theorem has found many applications in graph theory and algorithms. Let $f(k)$ denote the largest value such that every graph of treewidth $k$ contains a grid minor of size $(f(k)\times f(k))$. The best previous quantitative bound, due to recent work of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that $f(k)=Ω(\sqrt{\log k/\log \log k})$. In contrast, the best known upper bound implies that $f(k) = O(\sqrt{k/\log k})$. In this paper we obtain the first polynomial relationship between treewidth and grid minor size by showing that $f(k)=Ω(k^δ)$ for some fixed constant $δ> 0$, and describe a randomized algorithm, whose running time is polynomial in $|V(G)|$ and $k$, that with high probability finds a model of such a grid minor in $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Degree-3 Treewidth Sparsifiers

We study treewidth sparsifiers. Informally, given a graph $G$ of treewidth $k$, a treewidth sparsifier $H$ is a minor of $G$, whose treewidth is close to $k$, $|V(H)|$ is small, and the maximum vertex degree in $H$ is bounded. Treewidth sparsifiers of degree $3$ are of particular interest, as routing on node-disjoint paths, and computing minors seems easier in sub-cubic graphs than in general graphs. In this paper we describe an algorithm that, given a graph $G$ of treewidth $k$, computes a topological minor $H$ of $G$ such that (i) the treewidth of $H$ is $Ω(k/\text{polylog}(k))$; (ii) $|V(H)| = O(k^4)$; and (iii) the maximum vertex degree in $H$ is $3$. The running time of the algorithm is polynomial in $|V(G)|$ and $k$. Our result is in contrast to the known fact that unless $NP \subseteq coNP/{\sf poly}$, treewidth does not admit polynomial-size kernels. One of our key technical tools, which is of independent interest, is a construction of a small minor that preserves node-disjoint routability between two pairs of vertex subsets. This is closely related to the open question of computing small good-quality vertex-cut sparsifiers that are also minors of the original graph.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improved Bounds for the Flat Wall Theorem

The Flat Wall Theorem of Robertson and Seymour states that there is some function $f$, such that for all integers $w,t>1$, every graph $G$ containing a wall of size $f(w,t)$, must contain either (i) a $K_t$-minor; or (ii) a small subset $A\subset V(G)$ of vertices, and a flat wall of size $w$ in $G\setminus A$. Kawarabayashi, Thomas and Wollan recently showed a self-contained proof of this theorem with the following two sets of parameters: (1) $f(w,t)=Θ(t^{24}(t^2+w))$ with $|A|=O(t^{24})$, and (2) $f(w,t)=w^{2^{Θ(t^{24})}}$ with $|A|\leq t-5$. The latter result gives the best possible bound on $|A|$. In this paper we improve their bounds to $f(w,t)=Θ(t(t+w))$ with $|A|\leq t-5$. For the special case where the maximum vertex degree in $G$ is bounded by $D$, we show that, if $G$ contains a wall of size $Ω(Dt(t+w))$, then either $G$ contains a $K_t$-minor, or there is a flat wall of size $w$ in $G$. This setting naturally arises in algorithms for the Edge-Disjoint Paths problem, with $D\leq 4$. Like the proof of Kawarabayashi et al., our proof is self-contained, except for using a well-known theorem on routing pairs of disjoint paths. We also provide efficient algorithms that return either a model of the $K_t$-minor, or a vertex set $A$ and a flat wall of size $w$ in $G\setminus A$. We complement our result for the low-degree scenario by proving an almost matching lower bound: namely, for all integers $w,t>1$, there is a graph $G$, containing a wall of size $Ω(wt)$, such that the maximum vertex degree in $G$ is 5, and $G$ contains no flat wall of size $w$, and no $K_t$-minor.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Large-Treewidth Graph Decompositions and Applications

Treewidth is a graph parameter that plays a fundamental role in several structural and algorithmic results. We study the problem of decomposing a given graph $G$ into node-disjoint subgraphs, where each subgraph has sufficiently large treewidth. We prove two theorems on the tradeoff between the number of the desired subgraphs $h$, and the desired lower bound $r$ on the treewidth of each subgraph. The theorems assert that, given a graph $G$ with treewidth $k$, a decomposition with parameters $h,r$ is feasible whenever $hr^2 \le k/\polylog(k)$, or $h^3r \le k/\polylog(k)$ holds. We then show a framework for using these theorems to bypass the well-known Grid-Minor Theorem of Robertson and Seymour in some applications. In particular, this leads to substantially improved parameters in some Erdos-Posa-type results, and faster algorithms for a class of fixed-parameter tractable problems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2

In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an undirected n-vertex graph G, a collection M={(s_1,t_1),...,(s_k,t_k)} of demand pairs and an integer c. The goal is to connect the maximum possible number of the demand pairs by paths, so that the maximum edge congestion - the number of paths sharing any edge - is bounded by c. When the maximum allowed congestion is c=1, this is the classical Edge-Disjoint Paths problem (EDP). The best current approximation algorithm for EDP achieves an $O(\sqrt n)$-approximation, by rounding the standard multi-commodity flow relaxation of the problem. This matches the $Ω(\sqrt n)$ lower bound on the integrality gap of this relaxation. We show an $O(poly log k)$-approximation algorithm for EDPwC with congestion c=2, by rounding the same multi-commodity flow relaxation. This gives the best possible congestion for a sub-polynomial approximation of EDPwC via this relaxation. Our results are also close to optimal in terms of the number of pairs routed, since EDPwC is known to be hard to approximate to within a factor of $\tildeΩ((\log n)^{1/(c+1)})$ for any constant congestion c. Prior to our work, the best approximation factor for EDPwC with congestion 2 was $\tilde O(n^{3/7})$, and the best algorithm achieving a polylogarithmic approximation required congestion 14.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Vertex Sparsifiers with Steiner Nodes

Given an undirected graph $G=(V,E)$ with edge capacities $c_e\geq 1$ for $e\in E$ and a subset $T$ of $k$ vertices called terminals, we say that a graph $H$ is a quality-$q$ cut sparsifier for $G$ iff $T\subseteq V(H)$, and for any partition $(A,B)$ of $T$, the values of the minimum cuts separating $A$ and $B$ in graphs $G$ and $H$ are within a factor $q$ from each other. We say that $H$ is a quality-$q$ flow sparsifier for $G$ iff $T\subseteq V(H)$, and for any set $D$ of demands over the terminals, the values of the minimum edge congestion incurred by fractionally routing the demands in $D$ in graphs $G$ and $H$ are within a factor $q$ from each other. So far vertex sparsifiers have been studied in a restricted setting where the sparsifier $H$ is not allowed to contain any non-terminal vertices, that is $V(H)=T$. For this setting, efficient algorithms are known for constructing quality-$O(\log k/\log\log k)$ cut and flow vertex sparsifiers, as well as a lower bound of $\tildeΩ(\sqrt{\log k})$ on the quality of any flow or cut sparsifier. We study flow and cut sparsifiers in the more general setting where Steiner vertices are allowed, that is, we no longer require that $V(H)=T$. We show algorithms to construct constant-quality cut sparsifiers of size $O(C^3)$ in time $\poly(n)\cdot 2^C$, and constant-quality flow sparsifiers of size $C^{O(\log\log C)}$ in time $n^{O(\log C)}\cdot 2^C$, where $C$ is the total capacity of the edges incident on the terminals.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Approximation Algorithms and Hardness of the k-Route Cut Problem

We study the k-route cut problem: given an undirected edge-weighted graph G=(V,E), a collection {(s_1,t_1),(s_2,t_2),...,(s_r,t_r)} of source-sink pairs, and an integer connectivity requirement k, the goal is to find a minimum-weight subset E' of edges to remove, such that the connectivity of every pair (s_i, t_i) falls below k. Specifically, in the edge-connectivity version, EC-kRC, the requirement is that there are at most (k-1) edge-disjoint paths connecting s_i to t_i in G \ E', while in the vertex-connectivity version, NC-kRC, the same requirement is for vertex-disjoint paths. Prior to our work, poly-logarithmic approximation algorithms have been known for the special case where k >= 3, but no non-trivial approximation algorithms were known for any value k>3, except in the single-source setting. We show an O(k log^{3/2}r)-approximation algorithm for EC-kRC with uniform edge weights, and several polylogarithmic bi-criteria approximation algorithms for EC-kRC and NC-kRC, where the connectivity requirement k is violated by a constant factor. We complement these upper bounds by proving that NC-kRC is hard to approximate to within a factor of k^{eps} for some fixed eps>0. We then turn to study a simpler version of NC-kRC, where only one source-sink pair is present. We give a simple bi-criteria approximation algorithm for this case, and show evidence that even this restricted version of the problem may be hard to approximate. For example, we prove that the single source-sink pair version of NC-kRC has no constant-factor approximation, assuming Feige's Random k-AND assumption.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Routing in Undirected Graphs with Constant Congestion

Given an undirected graph G=(V,E), a collection (s_1,t_1),...,(s_k,t_k) of k source-sink pairs, and an integer c, the goal in the Edge Disjoint Paths with Congestion problem is to connect maximum possible number of the source-sink pairs by paths, so that the maximum load on any edge (called edge congestion) does not exceed c. We show an efficient randomized algorithm to route $Ω(OPT/\poly\log k)$ source-sink pairs with congestion at most 14, where OPT is the maximum number of pairs that can be simultaneously routed on edge-disjoint paths. The best previous algorithm that routed $Ω(OPT/\poly\log n)$ pairs required congestion $\poly(\log \log n)$, and for the setting where the maximum allowed congestion is bounded by a constant c, the best previous algorithms could only guarantee the routing of $OPT/n^{O(1/c)}$ pairs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

An Algorithm for the Graph Crossing Number Problem

We study the Minimum Crossing Number problem: given an $n$-vertex graph $G$, the goal is to find a drawing of $G$ in the plane with minimum number of edge crossings. This is one of the central problems in topological graph theory, that has been studied extensively over the past three decades. The first non-trivial efficient algorithm for the problem, due to Leighton and Rao, achieved an $O(n\log^4n)$-approximation for bounded degree graphs. This algorithm has since been improved by poly-logarithmic factors, with the best current approximation ratio standing on $O(n \poly(d) \log^{3/2}n)$ for graphs with maximum degree $d$. In contrast, only APX-hardness is known on the negative side. In this paper we present an efficient randomized algorithm to find a drawing of any $n$-vertex graph $G$ in the plane with $O(OPT^{10}\cdot \poly(d \log n))$ crossings, where $OPT$ is the number of crossings in the optimal solution, and $d$ is the maximum vertex degree in $G$. This result implies an $\tilde{O}(n^{9/10} \poly(d))$-approximation for Minimum Crossing Number, thus breaking the long-standing $\tilde{O}(n)$-approximation barrier for bounded-degree graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On Graph Crossing Number and Edge Planarization

Given an n-vertex graph G, a drawing of G in the plane is a mapping of its vertices into points of the plane, and its edges into continuous curves, connecting the images of their endpoints. A crossing in such a drawing is a point where two such curves intersect. In the Minimum Crossing Number problem, the goal is to find a drawing of G with minimum number of crossings. The value of the optimal solution, denoted by OPT, is called the graph's crossing number. This is a very basic problem in topological graph theory, that has received a significant amount of attention, but is still poorly understood algorithmically. The best currently known efficient algorithm produces drawings with $O(\log^2 n)(n + OPT)$ crossings on bounded-degree graphs, while only a constant factor hardness of approximation is known. A closely related problem is Minimum Edge Planarization, in which the goal is to remove a minimum-cardinality subset of edges from G, such that the remaining graph is planar. Our main technical result establishes the following connection between the two problems: if we are given a solution of cost k to the Minimum Edge Planarization problem on graph G, then we can efficiently find a drawing of G with at most $\poly(d)\cdot k\cdot (k+OPT)$ crossings, where $d$ is the maximum degree in G. This result implies an $O(n\cdot \poly(d)\cdot \log^{3/2}n)$-approximation for Minimum Crossing Number, as well as improved algorithms for special cases of the problem, such as, for example, k-apex and bounded-genus graphs.

0 citations0 reviewsNo code linkedOpen access