3 citations · 8 across the 9 of their papers we have counts for
17 papers
A Note on Approximability of Densest At-Least-k-Subgraph
Bundit Laekhanukit, Pasin Manurangsi, Ohad Trabelsi
We study the Densest At-Least--Subgraph (DALS) problem, in which we are given an undirected graph and an integer , and the goal is to find a subgraph of with at le…
Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
Julia Chuzhoy, Ron Mosenzon, Ohad Trabelsi
We study the directed global minimum vertex-cut problem: given a directed vertex-weighted graph , compute a vertex-cut in of minimum value, which is defined to be…
Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
Julia Chuzhoy, Ohad Trabelsi
We consider the Global Minimum Vertex-Cut problem: given an undirected vertex-weighted graph , compute a minimum-weight subset of its vertices whose removal disconnects . The…
(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
Ohad Trabelsi
The All-Pairs Max-Flow problem has gained significant popularity in the last two decades, and many results are known regarding its fine-grained complexity. Despite this, wide gaps…
Bridge Girth: A Unifying Notion in Network Design
Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi
A classic 1993 paper by Althőfer et al. proved a tight reduction from spanners, emulators, and distance oracles to the extremal function of high-girth graphs. This paper initia…
Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
Amir Abboud, Robert Krauthgamer, Jason Li +3
In 1961, Gomory and Hu showed that the All-Pairs Max-Flow problem of computing the max-flow between all pairs of vertices in an undirected graph can be solved using on…
Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
We devise new cut sparsifiers that are related to the classical sparsification of Nagamochi and Ibaraki [Algorithmica, 1992], which is an algorithm that, given an unweighted graph…
APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
We design an -time algorithm that constructs a cut-equivalent (Gomory-Hu) tree of a simple graph on nodes. This bound is almost-optimal in terms of , and it impr…
Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Every undirected graph has a (weighted) cut-equivalent tree , commonly named after Gomory and Hu who discovered it in 1961. Both and have the same node set, and for…
Cut-Equivalent Trees are Optimal for Min-Cut Queries
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
Min-Cut queries are fundamental: Preprocess an undirected edge-weighted graph, to quickly report a minimum-weight cut that separates a query pair of nodes . The best data stru…
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
Amir Abboud, Robert Krauthgamer, Ohad Trabelsi
We investigate the time-complexity of the All-Pairs Max-Flow problem: Given a graph with nodes and edges, compute for all pairs of nodes the maximum-flow value between them…
Relaxed Voronoi: a Simple Framework for Terminal-Clustering Problems
Arnold Filtser, Robert Krauthgamer, Ohad Trabelsi
We reprove three known algorithmic bounds for terminal-clustering problems, using a single framework that leads to simpler proofs. In this genre of problems, the input is a metric…
Faster Algorithms for All-Pairs Bounded Min-Cuts
Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano +5
The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum - cut (or just its value) for all pairs of vertices . We study this problem in directed…
Nearly Optimal Time Bounds for kPath in Hypergraphs
Lior Kamma, Ohad Trabelsi
We give almost tight conditional lower bounds on the running time of the kHyperPath problem. Given an -uniform hypergraph for some integer , kHyperPath seeks a tight path of…
The Set Cover Conjecture and Subgraph Isomorphism with a Tree Pattern
Robert Krauthgamer, Ohad Trabelsi
In the Set Cover problem, the input is a ground set of elements and a collection of sets, and the goal is to find the smallest sub-collection of sets whose union is the ent…
Conditional Lower Bound for Subgraph Isomorphism with a Tree Pattern
Robert Krauthgamer, Ohad Trabelsi
The kTree problem is a special case of Subgraph Isomorphism where the pattern graph is a tree, that is, the input is an -node graph and a -node tree , and the goal is…
Conditional Lower Bounds for All-Pairs Max-Flow
Robert Krauthgamer, Ohad Trabelsi
We provide evidence that computing the maximum flow value between every pair of nodes in a directed graph on nodes, edges,and capacities in the range , which we cal…