skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Thursday, June 13 until 2:00 AM ET on Friday, June 14 due to maintenance. We apologize for the inconvenience.


Search for: All records

Creators/Authors contains: "Li, Jason"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. In the k -cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into k connected components. Algorithms of Karger and Stein can solve this in roughly O ( n 2k ) time. However, lower bounds from conjectures about the k -clique problem imply that 惟 ( n (1- o (1)) k ) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for general k -cut in n 1.98k + O(1) time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights). In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixed k -cut of weight 伪 位 k with probability 惟 k ( n - 伪 k ), where 位 k denotes the minimum k -cut weight. This also gives an extremal bound of O k ( n k ) on the number of minimum k -cuts and an algorithm to compute 位 k with roughly n k polylog( n ) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight k -clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 位 k / k , using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks鈥攁nd how the average degree evolves鈥攊n the Karger process. 
    more » « less
  2. We give an algorithm to find a minimum cut in an edge-weighted directed graph with n vertices and m edges in O 虄(n 路 max{m^{2/3}, n}) time. This improves on the 30 year old bound of O 虄(nm) obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain O 虄 (n^2 /蔚^2 )-time (1+蔚)-approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed 蔚. Before our work, no (1+蔚)-approximation algorithm better than the exact runtime of O 虄(nm) is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to O 虄 (min{n/m^{1/3} , 鈭歯}) calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph. 
    more » « less