4 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…