Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees
  in Near-Linear Time   In this paper, we introduce a robust notion of $(1+\epsilon)$-approximate
$(s, t)$-mincuts in undirected graphs where every cut edge can be
simultaneously saturated (in the same direction) to a $\frac{1}{1+\epsilon}$
fraction by an $(s, t)$-flow. We call these $(1+\epsilon)$-fair cuts. Unlike
arbitrary approximate $(s, t)$-mincuts, fair cuts can be uncrossed, which is a
key property of $(s, t)$-mincuts used in many algorithms. We also give a
near-linear $\tilde O(m/\epsilon^3)$-time algorithm for computing an $(s,
t)$-fair cut. This offers a general tool for trading off a
$(1+\epsilon)$-approximation for near-linear running time in mincut based
algorithms.
  As an application of this new concept, we obtain a near-linear time algorithm
for constructing a $(1+\epsilon)$-approximate Gomory-Hu tree, thereby giving a
nearly optimal algorithm for the $(1+\epsilon)$-approximate all-pairs max-flows
(APMF) problem in undirected graphs. Our result is obtained via another
intermediate tool of independent interest. We obtain a near-linear time
algorithm for finding $(1+\epsilon)$-approximate isolating cuts in undirected
graphs, a concept that has gained wide traction over the past year.

2
The categories of this paper are: math
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
7
The categories of this paper are: hep-th
27
The categories of this paper are: comp-gas
3
The categories of this paper are: physics
14
The categories of this paper are: math-ph
12
The categories of this paper are: nucl-th
37
The categories of this paper are: supr-con
6
The categories of this paper are: astro-ph
17
The categories of this paper are: q-fin
19
The categories of this paper are: eess
16
The categories of this paper are: stat
5
The categories of this paper are: gr-qc
29
The categories of this paper are: funct-an
36
The categories of this paper are: cmp-lg