MIT EECS and CSAIL, Cambridge MA, USA and
https://www.shyanakmal.comnaysh@mit.eduhttps://orcid.org/0000-0002-7266-2041Supported
in part by NSF grants CCF-2129139 and CCF-2127597. MIT EECS and CSAIL,
Cambridge MA, USA and<EMAIL_ADDRESS>supported by NSF Grant CCF-2129139 and a Siebel Scholarship. Shyan Akmal and
Ce Jin <ccs2012> <concept>
<concept_id>10002950.10003624.10003633.10010917</concept_id>
<concept_desc>Mathematics of computing Graph algorithms</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Mathematics of computing Graph algorithms

###### Acknowledgements.

The first author thanks Virginia Vassilevska Williams for insightful
discussions on algorithms for computing matrix rank.

# An Efficient Algorithm for All-Pairs Bounded Edge Connectivity

Shyan Akmal  Ce Jin

###### Abstract

Our work concerns algorithms for a variant of Maximum Flow in unweighted
graphs. In the All-Pairs Connectivity (APC) problem, we are given a graph $G$
on $n$ vertices and $m$ edges, and are tasked with computing the maximum
number of edge-disjoint paths from $s$ to $t$ (equivalently, the size of a
minimum $(s,t)$-cut) in $G$, for all pairs of vertices $(s,t)$. Significant
algorithmic breakthroughs have recently shown that over undirected graphs, APC
can be solved in $n^{2+o(1)}$ time, which is essentially optimal. In contrast,
the true time complexity of APC over directed graphs remains open: this
problem can be solved in $\tilde{O}(m^{\omega})$ time, where
$\omega\in[2,2.373)$ is the exponent of matrix multiplication, but no matching
conditional lower bound is known.

Following [Abboud et al., ICALP 2019], we study a bounded version of APC
called the $k$-Bounded All Pairs Connectivity ($k$-APC) problem. In this
variant of APC, we are given an integer $k$ in addition to the graph $G$, and
are now tasked with reporting the size of a minimum $(s,t)$-cut only for pairs
$(s,t)$ of vertices with min-cut value less than $k$ (if the minimum
$(s,t)$-cut has size at least $k$, we can just report it is “large” instead of
computing the exact value).

Our main result is an $\tilde{O}((kn)^{\omega})$ time algorithm solving
$k$-APC in directed graphs. This is the first algorithm which solves $k$-APC
faster than simply solving the more general APC problem exactly, for all
$k\geq 3$. This runtime is $\tilde{O}(n^{\omega})$ for all
$k\leq\operatorname{poly}(\log n)$, which essentially matches the optimal
runtime for the $k=1$ case of $k$-APC, under popular conjectures from fine-
grained complexity. Previously, this runtime was only achieved for $k\leq 2$
in general directed graphs [Georgiadis et al., ICALP 2017], and for $k\leq
o(\sqrt{\log n})$ in the special case of directed acyclic graphs [Abboud et
al., ICALP 2019]. Our result employs the same algebraic framework used in
previous work, introduced by [Cheung, Lau, and Leung, FOCS 2011]. A direct
implementation of this framework involves inverting a large random matrix. Our
new algorithm is based off the insight that for solving $k$-APC, it suffices
to invert a low-rank random matrix instead of a generic random matrix.

We also obtain a new algorithm for a variant of $k$-APC, the $k$-Bounded All-
Pairs Vertex Connectivity ($k$-APVC) problem, where we are now tasked with
reporting, for every pair of vertices $(s,t)$, the maximum number of
internally vertex-disjoint (rather than edge-disjoint) paths from $s$ to $t$
if this number is less than $k$, and otherwise reporting that there are at
least $k$ internally vertex-disjoint paths from $s$ to $t$.

Our second result is an $\tilde{O}(k^{2}n^{\omega})$ time algorithm solving
$k$-APVC in directed graphs. Previous work showed how to solve an easier
version of the $k$-APVC problem (where answers only need to be returned for
pairs of vertices $(s,t)$ which are not edges in the graph) in
$\tilde{O}((kn)^{\omega})$ time [Abboud et al, ICALP 2019]. In comparison, our
algorithm solves the full $k$-APVC problem, and is faster if $\omega>2$.

###### keywords:

maximum flow, all-pairs, connectivity, matrix rank

###### category:

##  1 Introduction

Computing maximum flows is a classic problem which has been extensively
studied in graph theory and computer science. In unweighted graphs, this task
specializes to computing connectivities, an interesting computational problem
in its own right. Given a graph $G$ on $n$ vertices and $m$ edges, for any
vertices $s$ and $t$ in $G$, the _connectivity_ $\lambda(s,t)$ from $s$ to $t$
is defined to be the maximum number of edge-disjoint paths111By Menger’s
theorem, $\lambda(s,t)$ is also equal to the minimum number of edges that must
be deleted from the graph $G$ to produce a graph with no $s$ to $t$ path. from
$s$ to $t$. Since maximum flow can be computed in almost-linear time, we can
compute $\lambda(s,t)$ for any given vertices $s$ and $t$ in $m^{1+o(1)}$ time
[4].

What if instead of merely returning the value of a single connectivity, our
goal is to compute all connectivities in the graph? This brings us to the All-
Pairs Connectivity (APC) problem: in this problem, we are given a graph $G$ as
above, and are tasked with computing $\lambda(s,t)$ for all pairs of vertices
$(s,t)$ in $G$. In undirected graphs, APC can be solved in $n^{2+o(1)}$ time
[2], so that this “all-pairs” problem is essentially no harder than outputting
a single connectivity in dense graphs.

In directed graphs, APC appears to be much harder, with various conditional
lower bounds (discussed in Section 1.2) suggesting it is unlikely this problem
can be solved in quadratic time. Naively computing the connectivity separately
for each pair yields an $n^{2}m^{1+o(1)}$ time algorithm for this problem.
Using the flow vector framework (discussed in Section 3), it is possible to
solve APC in directed graphs in $\tilde{O}(m^{\omega})$ time222Given a
function $f$, we write $\tilde{O}(f)$ to denote
$f\cdot\operatorname{poly}(\log f).$ [6], where $\omega$ is the exponent of
matrix multiplication. Known algorithms imply that $\omega<2.37286$ [3], so
the $\tilde{O}(m^{\omega})$ time algorithm is faster than the naive algorithm
whenever the input graph is not too dense.

Our work focuses on a bounded version of the APC problem, which we formally
state as the $k$-Bounded All-Pairs Connectivity ($k$-APC) problem: in this
problem, we are given a _directed_ graph $G$ as above, and are tasked with
computing $\min(k,\lambda(s,t))$ for all pairs of vertices $(s,t)$ in $G$.
Intuitively, this is a relaxation of the APC problem, where our goal is to
compute the exact values of $\lambda(s,t)$ only for pairs $(s,t)$ with small
connectivity. For all other pairs, it suffices to report that the connectivity
is large, where $k$ is our threshold for distinguishing between small and
large connectivity values.

When $k=1$, the $k$-APC problem is equivalent to computing the transitive
closure of the input graph (in this problem, for each pair of vertices
$(s,t)$, we are tasked with determining if $G$ contains a path from $s$ to
$t$), which can be done in $\tilde{O}(n^{\omega})$ time [7]. Similarly, for
the special case of $k=2$, it is known that $k$-APC can be solved in
$\tilde{O}(n^{\omega})$ time, by a divide-and-conquer algorithm employing a
cleverly tailored matrix product [9]. As we discuss in Section 1.2, there is
evidence that these runtimes for $k$-APC when $k\leq 2$ are essentially
optimal.

Already for $k=3$ however, it is open whether $k$-APC can be solved faster
than computing the _exact values_ of $\lambda(s,t)$ for all pairs $(s,t)$ of
vertices! Roughly speaking, this is because the known $\tilde{O}(m^{\omega})$
time algorithm for APC involves encoding the connectivity information in the
inverse of an $m\times m$ matrix, and inverting an $m\times m$ matrix takes
$O(m^{\omega})$ time in general. This encoding step appears to be necessary
for $k$-APC as well. For $k=2$, clever combinatorial observations about the
structure of strongly connected graphs allow one to skip this computation, but
for $k\geq 3$ it is not clear at all from previous work how to avoid this
bottleneck. Moreover, it is consistent with existing hardness results that
$k$-APC could be solved in $O(n^{\omega})$ time for any constant $k$.

######  Open Problem .

Can $k$-APC be solved in faster than $\tilde{O}(m^{\omega})$ time for $k=3$?

Due to this lack of knowledge about the complexity of $k$-APC, researchers
have also studied easier versions of this problem. Given vertices $s$ and $t$
in the graph $G$, we define the _vertex connectivity_ $\nu(s,t)$ from $s$ to
$t$ to be the maximum number of internally vertex-disjoint paths from $s$ to
$t$. We can consider vertex connectivity analogues of the APC and $k$-APC
problems. In the All-Pairs Vertex Connectivity (APVC) problem, we are given a
graph $G$ on $n$ vertices and $m$ edges, and are tasked with computing the
value of $\nu(s,t)$ for all pairs of vertices $(s,t)$ in $G$. In the
$k$-Bounded All-Pairs Vertex Connectivity ($k$-APVC) problem, we are given the
same input $G$ as above, but are now tasked with only computing
$\min(k,\nu(s,t))$ for all pairs of vertices $(s,t)$ in $G$.

The $k$-APVC problem does not face the $O(m^{\omega})$ barrier which existing
algorithmic techniques for $k$-APC seem to encounter, intuitively because it
is possible to encode all the vertex-connectivity information of a graph in
the inverse of an $n\times n$ matrix instead of an $m\times m$ matrix. As a
consequence, [1] was able to present an $\tilde{O}((kn)^{\omega})$ time
algorithm which computes $\min(k,\nu(s,t))$ for all pairs of vertices $(s,t)$
such that $(s,t)$ is not an edge. Given this result, it is natural to ask
whether the more general $k$-APVC and $k$-APC problems can also be solved in
this same running time.

######  Open Problem .

Can $k$-APVC be solved in $\tilde{O}((kn)^{\omega})$ time?

######  Open Problem .

Can $k$-APC be solved in $\tilde{O}((kn)^{\omega})$ time?

###  1.1 Our Contribution

We resolve all three open problems raised in the previous section.

First, we present a faster algorithm for $k$-APC, whose time complexity
matches the runtime given by previous work for solving an easier version of
$k$-APVC.

######  Theorem 1.1.

For any positive integer $k$, $k$-APC can be solved in
$\tilde{O}((kn)^{\omega})$ time.

This is the first algorithm which solves $k$-APC faster than simply solving
APC exactly using the $\tilde{O}(m^{\omega})$ time algorithm of [6], for all
constant $k\geq 3$.

Second, we present an algorithm for $k$-APVC, which is faster than the
$\tilde{O}((kn)^{\omega})$ time algorithm from [1] (which only solves a
restricted version of $k$-APVC) if $\omega>2$.

######  Theorem 1.2.

For any positive integer $k$, $k$-APVC can be solved in
$\tilde{O}(k^{2}n^{\omega})$ time.

###  1.2 Comparison to Previous Results

#### Conditional Lower Bounds

The field of fine-grained complexity contains many popular conjectures (which
hypothesize lower bounds on the complexity of certain computational tasks)
which are used as the basis of conditional hardness results for problems in
computer science. In this section, we review known hardness results for APC
and its variants. The definitions of the problems and conjectures used in this
section are stated in Appendix A.

Assuming that Boolean Matrix Multiplication (BMM) requires $n^{\omega-o(1)}$
time, it is known that $k$-APC and $k$-APVC require $n^{\omega-o(1)}$ time to
solve, even for $k=1$ [7]. In particular, this hypothesis implies our
algorithms for $k$-APC and $k$-APVC are optimal for constant $k$.

Assuming the Strong Exponential Time Hypothesis (SETH), previous work shows
that APC requires $(mn)^{1-o(1)}$ time [11, Theorem 1.8], APVC requires
$m^{3/2-o(1)}$ time [13, Theorem 1.7], and $k$-APC requires
$\left(kn^{2}\right)^{1-o(1)}$ time [11, Theorem 4.3].

Let $\omega(1,2,1)$ be the smallest real number333Known fast matrix
multiplication algorithms imply that $\omega(1,2,1)<3.25669$ [8, Table 2].
such that we can compute the product of an $n\times n^{2}$ matrix and
$n^{2}\times n$ matrix in $n^{\omega(1,2,1)+o(1)}$ time. Assuming the
$4$-Clique Conjecture, the $k$-APVC problem over directed graphs (and thus the
$k$-APC problem as well) requires
$\left(k^{2}n^{\omega(1,2,1)-2}\right)^{1-o(1)}$ time [1]. The 4-Clique
Conjecture also implies that solving APVC in undirected graphs requires
$n^{\omega(1,2,1)-o(1)}$ time [10].

#### Algorithms for Restricted Graph Classes

As mentioned previously, no nontrivial algorithms for $k$-APC over general
directed graphs were known for $k\geq 3$, prior to our work. However, faster
algorithms were already known for $k$-APC over directed acyclic graphs (DAGs).
In particular, [1] presented two algorithms to solve $k$-APC in DAGs, running
in $2^{O(k^{2})}mn$ time and $(k\log n)^{4^{k}+o(k)}n^{\omega}$ time
respectively.

In comparison, our algorithm from Theorem 1.1 solves $k$-APC in _general_
directed graphs, is faster than the former algorithm whenever $m\geq
n^{\omega-1}$ or $k\geq\omega(\sqrt{\log n})$ (for example), is always faster
than the latter algorithm, and is significantly simpler from a technical
perspective than these earlier arguments. However, these algorithms for
$k$-APC on DAGs also return cuts witnessing the connectivity values, while our
algorithm does not.

In the special case of undirected graphs, APVC can be solved in $m^{2+o(1)}$
time [13, Theorem 1.8], which is faster than the aforementioned
$\tilde{O}(m^{\omega})$ time algorithm if $\omega>2$. Over undirected graphs,
$k$-APVC can be solved in $k^{3}m^{1+o(1)}+n^{2}\operatorname{poly}(\log n)$
time. In comparison, our algorithm from Theorem 1.2 can handle $k$-APVC in
both undirected _and_ directed graphs, and is faster for large enough values
of $k$ in dense graphs.

In directed planar graphs with maximum degree $d$, [6, Theorem 1.5] proves
that APC can be solved in $O\left(d^{\omega-2}n^{\omega/2+1}\right)$ time.

#### Additional Related Work

In [14], the authors consider a symmetric variant of $k$-APC. Here, the input
is a directed graph $G$ on $n$ vertices and $m$ edges, and the goal is to
compute for all pairs of vertices $(s,t)$, the value of
$\min(k,\lambda(s,t),\lambda(t,s))$. This easier problem can be solved in
$O(kmn)$ time [14].

###  1.3 Organization

The rest of this paper is devoted to proving Theorems 1.1 and 1.2. In Section
2 we introduce notation, some useful definitions, and results on matrix
computation which will be useful in proving correctness of our algorithms. In
Section 3 we provide an intuitive overview of our algorithms for $k$-APC and
$k$-APVC. In Section 4 we describe a framework of “flow vectors” for capturing
connectivity values, and in Section 5 use this framework to prove Theorem 1.1.
In Section 6 we present helpful results about vertex-connectivity, and in
Section 7 use these results to prove Theorem 1.2. We conclude in Section 8,
highlighting some interesting open problems suggested by our work.

In Appendix A, we include definitions of problems and conjectures mentioned in
Section 1.2. In Appendix B, we discuss how the treatment of $k$-APVC in [1]
differs from our own, and present the proof details for one of the results
stated in Section 6.

##  2 Preliminaries

##### Graph Assumptions

Throughout, we let $G$ denote a directed graph on $n$ vertices and $m$ edges.
Without loss of generality, we assume that the underlying undirected graph of
$G$ is connected, i.e., $G$ is weakly connected (since, if not, we could
simply run our algorithms separately on each weakly connected component of
$G$), so we have $m\geq n-1$. We assume $G$ has no self-loops, since these do
not affect the connectivity or vertex-connectivity values between distinct
vertices.

In Sections 4 and 5 we focus on the $k$-APC problem, and so allow $G$ to have
parallel edges between vertices (i.e., $G$ can be a multigraph). We assume
however, without loss of generality, that for any distinct vertices $s$ and
$t$, there are at most $k$ edges from $s$ to $t$ (since if there were more
than $k$ parallel edges from $s$ to $t$, we could delete some and bring the
count of parallel edges down to $k$ without changing the value of
$\min(k,\lambda(s,t))$). In Sections 6 and 7 we focus on the $k$-APVC problem,
and so assume that $G$ is a simple graph with no parallel edges, since
parallel edges from $u$ to $v$ cannot affect the value of a vertex
connectivity $\nu(s,t)$, unless $u=s$ and $v=t$, in which case the value of
$\nu(s,t)$ is simply increased by the number of additional parallel edges from
$s$ to $t$.

##### Graph Terminology and Notation

Given an edge $e$ from $u$ to $v$ in $G$, we write $e=(u,v)$. We call $u$ the
tail of $e$ and $v$ the head of $e$. Vertices which are tails of edges
entering a vertex $v$ are called _in-neighbors_ of $v$. Similarly, vertices
which are heads of edges exiting $v$ are called _out-neighbors_ of $v$. Given
a vertex $u$ in $G$, we let $E_{\textup{in}}(u)$ denote the set of edges
entering $u$, and $E_{\textup{out}}(u)$ denote the set of edges exiting $u$.
Similarly, $V_{\textup{in}}(u)$ denotes the set of in-neighbors of $u$, and
$V_{\textup{out}}(u)$ denotes the set of out-neighbors of $u$. Furthermore, we
define $V_{\textup{in}}[u]=V_{\textup{in}}(u)\cup\left\\{u\right\\}$ and
$V_{\textup{out}}[u]=V_{\textup{out}}(u)\cup\left\\{u\right\\}$. Finally, let
$\deg_{\text{in}}(u)=|E_{\textup{in}}(u)|$ and
$\deg_{\text{out}}(u)=|E_{\textup{out}}(u)|$ denote the indegree and outdegree
of $u$ respectively.

Given vertices $s$ and $t$, an $(s,t)$-cut is a set $C$ of edges, such that
deleting the edges in $C$ produces a graph with no $s$ to $t$ path. By
Menger’s theorem, the size of a minimum $(s,t)$-cut is equal to the
connectivity $\lambda(s,t)$ from $s$ to $t$. Similarly, an $(s,t)$-vertex cut
is a set of $C^{\prime}$ of vertices with $s,t\not\in C^{\prime}$, such that
deleting $C^{\prime}$ produces a graph with no $s$ to $t$ path. Clearly, a
vertex cut exists if and only if $(s,t)$ is not an edge. When $(s,t)$ is not
an edge, Menger’s theorem implies that the size of a minimum $(s,t)$-vertex
cut is equal to the vertex connectivity $\nu(s,t)$ from $s$ to $t$.

##### Matrix Notation

Let $A$ be a matrix. For indices $i$ and $j$, we let $A[i,j]$ denote the
$(i,j)$ entry of $A$. More generally, if $S$ is a set of row indices and $T$ a
set of column indices, we let $A[S,T]$ denote the submatrix of $A$ restricted
to rows from $S$ and columns from $T$. Similarly, $A[S,\ast]$ denotes $A$
restricted to rows from $S$, and $A[\ast,T]$ denotes $A$ restricted to columns
from $T$. We let $A^{\top}$ denote the transpose of $A$. If $A$ is a square
matrix, then we let $\operatorname{adj}(A)$ denote the adjugate of $A$. If $A$
is invertible, we let $A^{-1}$ denote its inverse. If a theorem, lemma, or
proposition statement refers to $A^{-1}$, it is generally asserting that
$A^{-1}$ exists (or if $A$ is a random matrix, asserting that $A^{-1}$ exists
with some probability) as part of the statement. We let $I$ denote the
identity matrix (the dimensions of this matrix will always be clear from
context). Given a vector $\vec{v}$, for any index $i$ we let $\vec{v}[i]$
denote the $i^{\text{th}}$ entry in $\vec{v}$. We let $\vec{0}$ denote the
zero vector (the dimensions of this vector will always be clear from context).
Given a positive integer $k$, we let $[k]=\left\\{1,\dots,k\right\\}$ denote
the set of the first $k$ positive integers.

##### Matrix and Polynomial Computation

Given a prime $p$, we let $\mathbb{F}_{p}$ denote the finite field on $p$
elements. Arithmetic operations over elements of $\mathbb{F}_{p}$ can be
performed in $\tilde{O}(\log p)$ time.

We now recall some well-known results about computation with matrices and
polynomials, which will be useful for our algorithms.

######  Proposition 2.1.

Let $A$ be an $a\times b$ matrix, and $B$ be a $b\times a$ matrix. If $(I-BA)$
is invertible, then the matrix $(I-AB)$ is also invertible, with inverse

$(I-AB)^{-1}=I+A(I-BA)^{-1}B.$

######  Proof 2.2.

It suffices to verify that the product of $(I-AB)$ with the right hand side of
the above equation yields the identity matrix. Indeed, we have

$\displaystyle(I-AB)\left(I+A(I-BA)^{-1}B\right)$ $\displaystyle=\ $
$\displaystyle I+A(I-BA)^{-1}B-AB-ABA(I-BA)^{-1}B$ $\displaystyle=\ $
$\displaystyle I+A(I-BA)^{-1}B-AB-A\big{(}I-(I-BA)\big{)}(I-BA)^{-1}B$
$\displaystyle=\ $ $\displaystyle I+A(I-BA)^{-1}B-AB-A(I-BA)^{-1}B+AB,$

which simplifies to $I$, as desired.

######  Proposition 2.3.

Let $A$ be an $a\times a$ matrix over $\mathbb{F}_{p}$. We can compute the
inverse $A^{-1}$ (if it exists) in $O(a^{\omega})$ field operations.

######  Proposition 2.4 ([5, Theorem 1.1]).

Let $A$ be an $a\times b$ matrix over $\mathbb{F}_{p}$. Then for any positive
integer $k$, we can compute $\min(k,\operatorname{rank}A)$ in
$O(ab+k^{\omega})$ field operations.

######  Proposition 2.5 (Schwartz-Zippel Lemma [12, Theorem 7.2]).

Let $f\in\mathbb{F}_{p}[x_{1},\dots,x_{r}]$ be a degree $d$, nonzero
polynomial. Let $\vec{a}$ be a uniform random point in $\mathbb{F}_{p}^{r}$.
Then $f(\vec{a})$ is nonzero with probability at least $1-d/p$.

##  3 Proof Overview

###  3.1 Flow Vector Encodings

Previous algorithms for APC [6] and its variants work in two steps:

Step 1: Encode

In this step, we prepare a matrix $M$ which implicitly encodes the
connectivity information of the input graph.

Step 2: Decode

In this step, we iterate over all pairs $(s,t)$ of vertices in the graph, and
for each pair run a small computation on a submatrix of $M$ to compute the
desired connectivity value.

The construction in the encode step is based off the framework of _flow
vectors_ , introduced in [6] as a generalization of classical techniques from
network-coding. We give a high-level overview of how this method has been
previously applied in the APC problem.444For the APVC problem we employ a
different, but analogous, framework described in Section 3.3.

Given the input graph $G$, we fix a source vertex $s$. Let
$d=\deg_{\text{out}}(s)$, and let $\mathbb{F}$ be some ground field.555In our
applications, we will pick $\mathbb{F}$ to be a finite field of size
$\operatorname{poly}(m)$. Our end goal is to assign to each edge $e$ in the
graph a special vector $\vec{e}\in\mathbb{F}^{d}$ which we call a _flow
vector_.

First, for each edge $e\in E_{\textup{out}}(s)$, we introduce a
$d$-dimensional vector $\vec{v_{e}}$. These vectors intuitively correspond to
some starting flow that is pumping out of $s$. It is important that these
vectors are linearly independent (and previous applications have always picked
these vectors to be distinct $d$-dimensional unit vectors). We then push this
flow through the rest of the graph, by having each edge get assigned a vector
which is a random linear combination of the flow vectors assigned to the edges
entering its tail. That is, given an edge $e=(u,v)$ with $u\neq s$, the final
flow vector $\vec{e}$ will be a random linear combination of the flow vectors
for the edges entering $u$. If instead the edge $e=(s,v)$ is in
$E_{\textup{out}}(s)$, the final flow vector $\vec{e}$ will be a random linear
combination of the flow vectors for the edges entering $s$, added to the
initial flow $\vec{v}_{e}$.

The point of this random linear combination is to (with high probability)
preserve linear independence. In this setup, for any vertex $v$ and integer
$\ell$, if some subset of $\ell$ flow vectors assigned to edges in
$E_{\textup{in}}(v)$ is independent, then we expect that every subset of at
most $\ell$ flow vectors assigned to edges in $E_{\textup{out}}(v)$ is also
independent. This sort of behavior turns out to generalize to preserving
linear independence of flow vectors across cuts, which implies that (with high
probability) for any vertex $t$, the rank of the flow vectors assigned to
edges in $E_{\textup{in}}(t)$ equals $\lambda(s,t)$.

Intuitively, this is because the flow vectors assigned to edges in
$E_{\textup{in}}(t)$ will be a linear combination of the $\lambda(s,t)$ flow
vectors assigned to edges in a minimum $(s,t)$-cut, and the flow vectors
assigned to edges in this cut should be independent.

Collecting all the flow vectors as column vectors in a matrix allows us to
produce a single matrix $M_{s}$, such that computing the rank of
$M_{s}[\ast,E_{\textup{in}}(t)]$ yields the desired connectivity value
$\lambda(s,t)$ (computing these ranks constitutes the decode step mentioned
previously). Previous work [6, 1] set the initial pumped $\vec{v}_{e}$ to be
distinct unit vectors. It turns out that for this choice of starting vectors,
it is possible to construct a single matrix $M$ (independent of a fixed choice
of $s$), such that rank queries to submatrices of $M$ correspond to the
answers we wish to output in the APC problem and its variants.

In Section 3.2 we describe how we employ the flow vector framework to prove
Theorem 1.1. Then in Section 3.3, we describe how we modify these methods to
prove Theorem 1.2.

###  3.2 All-Pairs Connectivity

Our starting point is the $\tilde{O}(m^{\omega})$ time algorithm for APC
presented in [6], which uses the flow vector encoding scheme outlined in
Section 3.1.

Let $K$ be an $m\times m$ matrix, whose rows and columns are indexed by edges
in the input graph. For each pair $(e,f)$ of edges, if the head of $e$
coincides with the tail of $f$, we set $K[e,f]$ to be a uniform random field
element in $\mathbb{F}$. Otherwise, $K[e,f]=0$. These field elements
correspond precisely to the coefficients used in the random linear
combinations of the flow vector framework. Define the matrix

$M=(I-K)^{-1}.$ (1)

Then [6] proves that with high probability, for any pair $(s,t)$ of vertices,
we have

$\operatorname{rank}M[E_{\textup{out}}(s),E_{\textup{in}}(t)]=\lambda(s,t).$
(2)

With this setup, the algorithm for APC is simple: first compute $M$ (the
encode step), and then for each pair of vertices $(s,t)$, return the value of
$\operatorname{rank}M[E_{\textup{out}}(s),E_{\textup{in}}(t)]$ as the
connectivity from $s$ to $t$ (the decode step).

By Equation 1, we can complete the encode step in $\tilde{O}(m^{\omega})$
time, simply by inverting an $m\times m$ matrix with entries from
$\mathbb{F}$. It turns out we can also complete the decode step in the same
time bound. So this gives an $\tilde{O}(m^{\omega})$ time algorithm for APC.

Suppose now we want to solve the $k$-APC problem. A simple trick (observed in
the proof of [1, Theorem 5.2] for example) in this setting can allow us to
speed up the runtime of the decode step. However, it is not at all obvious how
to speed up the encode step. To implement the flow vector scheme of Section
3.1 as written, it seems almost inherent that one needs to invert an $m\times
m$ matrix. Indeed, an inability to overcome this bottleneck is stated
explicitly as part of the motivation in [1] for focusing on the $k$-APVC
problem instead.

#### Our Improvement

The main idea behind our new algorithm for $k$-APC is to work with a low-rank
version of the matrix $K$ used in Equation 1 for the encode step.

Specifically, we construct certain random sparse matrices $L$ and $R$ with
dimensions $m\times kn$ and $kn\times m$ respectively. We then set $K=LR$, and
argue that with high probability, the matrix $M$ defined in Equation 1 for
this choice of $K$ satisfies

$\operatorname{rank}M[E_{\textup{out}}(s),E_{\textup{in}}(t)]=\min(k,\lambda(s,t)).$
(3)

This equation is just a $k$-bounded version of Equation 2. By Proposition 2.1,
we have

$M=(I-K)^{-1}=(I-LR)^{-1}=I+L(I-RL)^{-1}R.$

Note that $(I-RL)$ is a $kn\times kn$ matrix. So, to compute $M$ (and thus
complete the encode step) we no longer need to invert an $m\times m$ matrix!
Instead we just need to invert a matrix of size $kn\times kn$. This is
essentially where the $\tilde{O}\left((kn)^{\omega}\right)$ runtime in Theorem
1.1 comes from.

Conceptually, this argument corresponds to assigning flow vectors through the
graph by replacing random linear combinations with random “low-rank
combinations.” That is, for an edge $e\in E_{\textup{out}}(u)$ exiting a
vertex $u$, we define the flow vector at $e$ to be

$\vec{e}=\sum_{i=1}^{k}\left(\sum_{f\in
E_{\textup{in}}(u)}L_{i}[f,u]\vec{f}\right)\cdot R_{i}[u,e],$

where the inner summation is over all edges $f$ entering $u$, $\vec{f}$
denotes the flow vector assigned to edge $f$, and the $L_{i}[f,u]$ and
$R_{i}[u,e]$ terms correspond to random field elements uniquely determined by
the index $i$ and some $(\text{edge},\text{vertex})$ pair.

Here, unlike in the method described in Section 3.1, the coefficient in front
of $\vec{f}$ in its contribution to $\vec{e}$ is not uniquely determined by
the pair of edges $f$ and $e$. Rather, if edge $f$ enters node $u$, then it
has the same set of “weights” $L_{i}[f,u]$ it contributes to every flow vector
exiting $u$. However, since we use $k$ distinct weights, this restricted rule
for propagating flow vectors still suffices to compute $\min(k,\lambda(s,t))$.

A good way to think about the effect of this alternate approach is that now
for any vertex $v$ and any integer $\ell\leq k$, if some subset of $\ell$ flow
vectors assigned to edges in $E_{\textup{in}}(v)$ is independent, then we
expect that every subset of at most $\ell$ flow vectors assigned to edges in
$E_{\textup{out}}(v)$ is also independent. In the previous framework, this
result held even for $\ell>k$. By relaxing the method used to determine flow
vectors, we achieve a weaker condition, but this is still enough to solve
$k$-APC.

This modification makes the encode step more complicated (it now consists of
two parts: one where we invert a matrix, and one where we multiply that
inverse with other matrices), but speeds it up overall. To speed up the decode
step, we use a variant of an observation from the proof of [1, Theorem 5.2] to
argue that we can assume every vertex in our graph has indegree and outdegree
$k$. By Proposition 2.4 and Equation 3, this means we can compute
$\min(k,\lambda(s,t))$ for all pairs $(s,t)$ of vertices in
$\tilde{O}(k^{\omega}n^{2})$ time. So the bottleneck in our algorithm comes
from the encode step, which yields the $\tilde{O}\left((kn)^{\omega}\right)$
runtime.

###  3.3 All-Pairs Vertex Connectivity

Our starting point is the $\tilde{O}\left((kn)^{\omega}\right)$ time algorithm
in [1], which computes $\min(k,\nu(s,t))$ for all pairs of vertices $(s,t)$
which are not edges. That algorithm is based off a variant of the flow vector
encoding scheme outlined Section 3.1. Rather than assign vectors to edges, we
instead assign flow vectors to vertices (intuitively this is fine because we
are working with vertex connectivities in the $k$-APVC problem). The rest of
the construction is similar: we imagine pumping some initial vectors to $s$
and its out-neighbors, and then we propagate the flow through the graph so
that at the end, for any vertex $v$, the flow vector assigned to $v$ is a
random linear combination of flow vectors assigned to in-neighbors of
$v$.666Actually, this behavior only holds for vertices $v\not\in
V_{\textup{out}}[s].$ The rule for flow vectors assigned to vertices in
$V_{\textup{out}}[s]$ is a little more complicated, and depends on the values
of the initial pumped vectors.

Let $K$ be an $n\times n$ matrix, whose rows and columns are indexed by
vertices in the input graph. For each pair $(u,v)$ of vertices, if there is an
edge from $u$ to $v$, we set $K[u,v]$ to be a uniform random element in
$\mathbb{F}$. Otherwise, $K[u,v]=0$. These entries correspond precisely to
coefficients used in the random linear combinations of the flow vector
framework.

Now define the matrix

$M=(I-K)^{-1}.$ (4)

Then we argue that for any pair $(s,t)$ of vertices, we have

$\operatorname{rank}M[V_{\textup{out}}[s],V_{\textup{in}}[t]]=\begin{cases}\nu(s,t)+1&\text{if
}(s,t)\text{ is an edge}\\\ \nu(s,t)&\text{otherwise}.\end{cases}$ (5)

Previously, [1, Proof of Lemma 5.1] sketched a different argument, which shows
that $\operatorname{rank}M[V_{\textup{out}}(s),V_{\textup{in}}(t)]=\nu(s,t)$
when $(s,t)$ is not an edge. As we discuss in Section B.1, this claim does not
necessarily hold when $(s,t)$ is an edge.

We use Equation 5 to solve $k$-APVC. For the encode step, we compute $M$. By
Equation 4, we can do this by inverting an $n\times n$ matrix, which takes
$\tilde{O}(n^{\omega})$ time. For the decode step, by Equation 5 and
Proposition 2.4, we can compute $\min(k,\nu(s,t))$ for all pairs $(s,t)$ of
vertices in asymptotically

$\sum_{s,t}\left(\deg_{\text{out}}(s)\deg_{\text{in}}(t)+k^{\omega}\right)=m^{2}+k^{\omega}n^{2}$

time, where the sum is over all vertices $s$ and $t$ in the graph. The runtime
bound we get here for the decode step is far too high – naively computing the
ranks of submatrices is too slow if the graph has many high-degree vertices.

To avoid this slowdown, [1] employs a simple trick to reduce degrees in the
graph: we can add layers of $k$ new nodes to block off the ingoing and
outgoing edges from each vertex in the original graph. That is, for each
vertex $s$ in $G$, we add a set $S$ of $k$ new nodes, replace the edges in
$E_{\textup{out}}(s)$ with edges from $s$ to all the nodes in $S$, and add
edges from every node in $S$ to every vertex originally in
$V_{\textup{out}}(s)$. Similarly, for each vertex $t$ in $G$, we add a set $T$
of $k$ new nodes, replace the edges in $E_{\textup{in}}(t)$ with edges from
all the nodes in $T$ to $t$, and add edges from every vertex originally in
$V_{\textup{in}}(t)$ to every node in $T$.

It is easy to check that this transformation preserves the value of
$\min(k,\nu(s,t))$ for all pairs $(s,t)$ of vertices in the original graph
where $(s,t)$ is not an edge. Moreover, all vertices in the original graph
have indegree and outdegree exactly $k$ in the new graph. Consequently, the
decode step can now be implemented to run in $\tilde{O}(k^{\omega}n^{2})$
time. Unfortunately, this construction increases the number of vertices in the
graph from $n$ to $(2k+1)n$. As a consequence, in the encode step, the matrix
$K$ we work with is no longer $n\times n$, but instead is of size
$(2k+1)n\times(2k+1)n$. Now inverting $I-K$ to compute $M$ requires
$\tilde{O}\left((kn)^{\omega}\right)$ time, which is why [1] obtains this
runtime for their algorithm.

#### Our Improvement

Intuitively, the modification used by [1] to reduce degrees in the graph feels
very inefficient. This transformation makes the graph larger in order to “lose
information” about connectivity values greater than $k$. Rather than modify
the graph in this way, can we modify the flow vector scheme itself to speed up
the decode step? Our algorithm does this, essentially modifying the matrix of
flow vectors to simulate the effect of the previously described
transformation, without ever explicitly adding new nodes to the graph.

Instead of working directly with the matrix $M$ from Equation 4, for each pair
$(s,t)$ of vertices we define a $(k+1)\times(k+1)$ matrix

$M_{s,t}=B_{s}\left(M[V_{\textup{out}}[s],V_{\textup{in}}[t]]\right)C_{t}$

which is obtained from multiplying a submatrix of $M$ on the left and right by
small random matrices $B_{s}$ and $C_{t}$, with $k+1$ rows and columns
respectively. Since $B_{s}$ has $k+1$ rows and $C_{t}$ has $k+1$ columns, we
can argue that with high probability, Equation 5 implies that

$\operatorname{rank}M_{s,t}=\begin{cases}\min(k+1,\nu(s,t)+1)&\text{if
}(s,t)\text{ is an edge}\\\ \min(k+1,\nu(s,t))&\text{otherwise}.\end{cases}$

So we can compute $\min(k,\nu(s,t))$ from the value of
$\operatorname{rank}M_{s,t}$. This idea is similar to the preconditioning
method used in algorithms for computing matrix rank efficiently (see [5] and
the references therein). Conceptually, we can view this approach as a
modification of the flow vector framework. Let $d=\deg_{\text{out}}(s)$. As
noted in Section 3.1, previous work

  1. 1.

starts by pumping out distinct $d$-dimensional unit vectors to nodes in
$V_{\textup{out}}(s)$, and then

  2. 2.

computes the rank of all flow vectors of vertices in $V_{\textup{in}}(t)$.

In our work, we instead

  1. 1.

start by pumping out $(d+1)$ random $(k+1)$-dimensional vectors to nodes in
$V_{\textup{out}}[s]$, and then

  2. 2.

compute the rank of $(k+1)$ random linear combinations of flow vectors for
vertices in $V_{\textup{in}}[t]$.

This alternate approach suffices for solving the $k$-APVC problem, while
avoiding the slow $\tilde{O}((kn)^{\omega})$ encode step of previous work.

So, in the decode step of our algorithm, we compute $\min(k,\nu(s,t))$ for
each pair $(s,t)$ of vertices by computing the rank of the $(k+1)\times(k+1)$
matrix $M_{s,t}$, in $\tilde{O}(k^{\omega}n^{2})$ time overall.

Our encode step is more complicated than previous work, because not only do we
need to compute the inverse $(I-K)^{-1}$, we also have to construct the
$M_{s,t}$ matrices. Naively computing each $M_{s,t}$ matrix separately is too
slow, so we end up using an indirect approach to compute all entries of the
$M_{s,t}$ matrices _simultaneously_ , with just $O(k^{2})$ multiplications of
$n\times n$ matrices. This takes $\tilde{O}(k^{2}n^{\omega})$ time, which is
the bottleneck for our algorithm.

##  4 Flow Vector Encoding

The arguments in this section are similar to the arguments from [6, Section
2], but involve more complicated proofs because we work with low-rank random
matrices as opposed to generic random matrices.

Fix a source vertex $s$ in the input graph $G$. Let $d=\deg_{\text{out}}(s)$
denote the number of edges leaving $s$. Let $e_{1},\dots,e_{d}\in
E_{\textup{out}}(s)$ be the outgoing edges from $s$.

Take a prime $p=\Theta(m^{5})$. Let $\vec{u}_{1},\dots,\vec{u}_{d}$ be
distinct unit vectors in $\mathbb{F}_{p}^{d}$.

Eventually, we will assign each edge $e$ in $G$ a vector
$\vec{e}\in\mathbb{F}_{p}^{d}$, which we call a _flow vector_. These flow
vectors will be determined by a certain system of vector equations. To
describe these equations, we first introduce some symbolic matrices.

For each index $i\in[k]$, we define an $m\times n$ matrix $X_{i}$, whose rows
are indexed by edges of $G$ and columns are indexed by vertices of $G$, such
that for each edge $e=(u,v)$, entry $X_{i}[e,v]=x_{i,ev}$ is an indeterminate.
All entries in $X_{i}$ not of this type are zero.

Similarly, we define $n\times m$ matrices $Y_{i}$, with rows indexed by
vertices of $G$ and columns indexed by edges of $G$, such that for every edge
$f=(u,v)$, the entry $Y_{i}[u,f]=y_{i,uf}$ is an indeterminate. All entries in
$Y_{i}$ not of this type are zero.

Let $X$ be the $m\times kn$ matrix formed by horizontally concatenating the
$X_{i}$ matrices. Similarly, let $Y$ be the $kn\times m$ matrix formed by
vertically concatenating the $Y_{i}$ matrices. Then we define the matrix

$Z=XY=X_{1}Y_{1}+\dots+X_{k}Y_{k}.$ (6)

By construction, $Z$ is an $m\times m$ matrix, with rows and columns indexed
by edges of $G$, such that for any edges $e=(u,v)$ and $f=(v,w)$, we have

$Z[e,f]=\sum_{i=1}^{k}x_{i,ev}y_{i,vf}$ (7)

and all other entries of $Z$ are set to zero.

Consider the following procedure. We assign independent, uniform random values
from $\mathbb{F}_{p}$ to each variable $x_{i,ev}$ and $y_{i,uf}$. Let
$L_{i},L,R_{i},R$, and $K$ be the matrices over $\mathbb{F}_{p}$ resulting
from this assignment to $X_{i},X,Y_{i},Y$, and $Z$ respectively. In
particular, we have

$K=LR.$ (8)

Now, to each edge $e$, we assign a flow vector $\vec{e}\in\mathbb{F}_{p}^{d}$,
satisfying the following equalities:

  1. 1.

Recall that $e_{1},\dots,e_{d}$ are all the edges exiting $s$, and
$\vec{u}_{1},\dots,\vec{u}_{d}$ are distinct unit vectors in
$\mathbb{F}_{p}^{d}$. For each edge $e_{i}\in E_{\textup{out}}(s)$, we require
its flow vector satisfy

$\vec{e}_{i}=\left(\sum_{f\in E_{\textup{in}}(s)}\vec{f}\cdot
K[f,e_{i}]\right)+\vec{u}_{i}.$ (9)

  2. 2.

For each edge $e=(u,v)$ with $u\neq s$, we require its flow vector satisfy

$\vec{e}=\sum_{f\in E_{\textup{in}}(u)}\vec{f}\cdot K[f,e].$ (10)

A priori it is not obvious that flow vectors satisfying the above two
conditions exist, but we show below that they do (with high probability). Let
$H_{s}$ be the $d\times m$ matrix whose columns are indexed by edges in $G$,
such that the column associated with $e_{i}$ is $\vec{u}_{i}$ for each index
$i$, and the rest of the columns are zero vectors. Let $F$ be the $d\times m$
matrix, with columns indexed by edges in $G$, whose columns
$F[\ast,e]=\vec{e}$ are flow vectors for the corresponding edges. Then
Equations 9 and 10 are encapsulated by the simple matrix equation

$F=FK+H_{s}.$ (11)

The following lemma shows we can solve for $F$ in the above equation, with
high probability.

######  Lemma 4.1.

We have $\det(I-K)\neq 0$, with probability at least $1-1/m^{3}$.

######  Proof 4.2.

Since the input graph has no self-loops, by Equation 7 and the discussion
immediately following it, we know that the diagonal entries of the $m\times m$
matrix $Z$ are zero. By Equation 7, each entry of $Z$ is a polynomial of
degree at most two, with constant term set to zero. Hence, $\det(I-Z)$ is a
polynomial over $\mathbb{F}_{p}$ with degree at most $2m$, and constant term
equal to $1$. In particular, this polynomial is nonzero. Then by the Schwartz-
Zippel Lemma (Proposition 2.5), $\det(I-K)$ is nonzero with probability at
least

$1-2m/p\geq 1-1/m^{3}$

by setting $p\geq 2m^{4}$.

Suppose from now on that $\det(I-K)\neq 0$ (by Lemma 4.1, this occurs with
high probability). Then with this assumption, we can solve for $F$ in Equation
11 to get

$F=H_{s}(I-K)^{-1}=\frac{H_{s}\left(\text{adj}(I-K)\right)}{\det(I-K)}.$ (12)

This equation will allow us to relate ranks of collections of flow vectors to
connectivity values in the input graph.

######  Lemma 4.3.

For any vertex $t$ in $G$, with probability at least $1-2/m^{3}$, we have

$\operatorname{rank}F[\ast,E_{\textup{in}}(t)]\leq\lambda(s,t).$

######  Proof 4.4.

Abbreviate $\lambda=\lambda(s,t)$. Conceptually, this proof works by arguing
that the flow vectors assigned to all edges entering $t$ are linear
combinations of the flow vectors assigned to edges in a minimum $(s,t)$-cut of
$G$.

Let $C$ be a minimum $(s,t)$-cut. By Menger’s theorem, $|C|=\lambda$.

Let $S$ be the set of nodes reachable from $s$ without using an edge in $C$,
and let $T$ be the set of nodes which can reach $t$ without using an edge in
$C$. By definition of an $(s,t)$-cut, $S$ and $T$ partition the vertices in
$G$.

Let $E^{\prime}$ be the set of edges $e=(u,v)$ with $v\in T$.

Set $K^{\prime}=K[E^{\prime},E^{\prime}]$ and $F^{\prime}=F[\ast,E^{\prime}].$
Finally, let $H^{\prime}$ be a matrix whose columns are indexed by edges in
$E^{\prime}$, such that the column associated with an edge $e\in C$ is
$\vec{e}$, and all other columns are equal to $\vec{0}$.

Then by Equations 9 and 10, we have

$F^{\prime}=F^{\prime}K^{\prime}+H^{\prime}.$

Indeed, for any edge $e=(u,v)\in E^{\prime}$, if $u\in S$ then $e\in C$ so
$H^{\prime}[\ast,e]=\vec{e}$, and there can be no edge $f\in E^{\prime}$
entering $u$, so $(F^{\prime}K^{\prime})[\ast,e]=\vec{0}$. If instead $u\in
T$, then $H^{\prime}[\ast,e]=\vec{0}$, but every edge $f$ entering $u$ is in
$E^{\prime}$, so by Equation 10, we have
$(F^{\prime}K^{\prime})[\ast,e]=F^{\prime}[\ast,e]$ as desired.

Using similar reasoning to the proof of Lemma 4.1, we have
$\det(I-K^{\prime})\neq 0$ with probability at least $1-1/m^{3}$. If this
event occurs, we can solve for $F^{\prime}$ in the previous equation to get

$F^{\prime}=H^{\prime}(I-K^{\prime})^{-1}.$

Since $H^{\prime}$ has at most $\lambda$ nonzero columns,
$\operatorname{rank}H\leq\lambda$. So by the above equation,
$\operatorname{rank}F^{\prime}\leq\lambda$. By definition,
$E_{\textup{in}}(t)\subseteq E^{\prime}$. Thus $F[\ast,E_{\textup{in}}(t)]$ is
a submatrix of $F^{\prime}$. Combining this with the previous results, we see
that $\operatorname{rank}F[\ast,E_{\textup{in}}(t)]\leq\lambda$, as desired.
The claimed probability bound follows by a union bound over the events that
$I-K$ and $I-K^{\prime}$ are both invertible.

######  Lemma 4.5.

For any vertex $t$ in $G$, with probability at least $1-2/m^{3}$, we have

$\operatorname{rank}F[\ast,E_{\textup{in}}(t)]\geq\min(k,\lambda(s,t)).$

######  Proof 4.6.

Abbreviate $\lambda=\min(k,\lambda(s,t))$. Intuitively, our proof argues that
the presence of edge-disjoint paths from $s$ to $t$ leads to certain edges in
$E_{\textup{in}}(t)$ being assigned linearly independent flow vectors (with
high probability), which then implies the desired lower bound.

By Menger’s theorem, $G$ contains $\lambda$ edge-disjoint paths
$P_{1},\dots,P_{\lambda}$ from $s$ to $t$.

Consider the following assignment to the variables of the symbolic matrices
$X_{i}$ and $Y_{i}$. For each index $i\leq\lambda$ and edge $e=(u,v)$, we set
variable $x_{i,ev}=1$ if $e$ is an edge in $P_{i}$. Similarly, for each index
$i\leq\lambda$ and edge $f=(u,v)$, we set variable $y_{i,uf}=1$ if $f$ is an
edge in $P_{i}$. All other variables are set to zero. In particular, if
$i>\lambda$, then $X_{i}$ and $Y_{i}$ have all their entries set to zero. With
respect to this assignment, the matrix $X_{i}Y_{i}$ (whose rows and columns
are indexed by edges in the graph) has the property that $(X_{i}Y_{i})[e,f]=1$
if $f$ is the edge following $e$ on path $P_{i}$, and all other entries are
set to zero.

Then by Equation 6, we see that under this assignment, $Z[e,f]=1$ if $e$ and
$f$ are consecutive edges in some path $P_{i}$, and all other entries of $Z$
are set to zero. For this particular assignment, because the $P_{i}$ are edge-
disjoint paths, Equations 9 and 10 imply that the last edge of each path
$P_{i}$ is assigned a distinct $d$-dimensional unit vector. These vectors are
independent, so, $\operatorname{rank}F[\ast,E_{\textup{in}}(t)]=\lambda$ in
this case.

With respect to this assignment, this means that $F[\ast,E_{\textup{in}}(t)]$
contains a $\lambda\times\lambda$ full-rank submatrix. Let $F^{\prime}$ be a
submatrix of $F[\ast,E_{\textup{in}}(t)]$ with this property. Since
$F^{\prime}$ has full rank, we have $\det F^{\prime}\neq 0$ for the assignment
described above.

Now, before assigning values to variables, each entry of $\text{adj}(I-Z)$ is
a polynomial of degree at most $2m$. So by Equation 12, $\det F^{\prime}$ is
equal to some polynomial $P$ of degree at most $2\lambda m$, divided by
$(\det(I-Z))^{\lambda}$. We know $P$ is a nonzero polynomial, because we saw
above that $\det F^{\prime}$ is nonzero for some assignment of values to the
variables (and if $P$ were the zero polynomial, then $\det F^{\prime}$ would
evaluate to zero under every assignment).

By Lemma 4.1, with probability at least $1-1/m^{3}$, a random evaluation to
the variables will have $\det(I-Z)$ evaluate to a nonzero value. Assuming this
event occurs, by Schwartz-Zippel Lemma (Proposition 2.5), a random evaluation
to the variables in $Z$ will have $\det F^{\prime}\neq 0$ with probability at
least $1-(2\lambda m)/p\geq 1-1/m^{3}$ by setting $p\geq 2m^{5}.$

So by union bound, a particular $\lambda\times\lambda$ submatrix of
$F[\ast,E_{\textup{in}}(t)]$ will be full rank with probability at least
$1-2/m^{3}$. This proves the desired result.

######  Lemma 4.7.

Fix vertices $s$ and $t$. Define
$\lambda=\operatorname{rank}\leavevmode\nobreak\
(I-K)^{-1}[E_{\textup{out}}(s),E_{\textup{in}}(t)].$ With probability at least
$1-4/m^{3}$, we have $\min(k,\lambda)=\min(k,\lambda(s,t)).$

######  Proof 4.8.

The definition of $H_{s}$ together with Equation 12 implies that

$F[\ast,E_{\textup{in}}(t)]=(I-K)^{-1}[E_{\textup{out}}(s),E_{\textup{in}}(t)].$
(13)

By union bound over Lemmas 4.5 and 4.3, with probability at least $1-4/m^{3}$
the inequalities

$\lambda=\operatorname{rank}\leavevmode\nobreak\
(I-K)^{-1}[E_{\textup{out}}(s),E_{\textup{in}}(t)]=\operatorname{rank}F[\ast,E_{\textup{in}}(t)]\leq\lambda(s,t)$

and

$\lambda=\operatorname{rank}\leavevmode\nobreak\
(I-K)^{-1}[E_{\textup{out}}(s),E_{\textup{in}}(t)]=\operatorname{rank}F[\ast,E_{\textup{in}}(t)]\geq\min(k,\lambda(s,t))$

simultaneously hold. The desired result follows.

##  5 Connectivity Algorithm

In this section, we present our algorithm for $k$-APC.

##### Graph Transformation

We begin by modifying the input graph $G$ as follows. For every vertex $v$ in
$G$, we introduce two new nodes $v_{\text{out}}$ and $v_{\text{in}}$. We
replace each edge $(u,v)$ originally in $G$ is by the edge
$(u_{\text{out}},v_{\text{in}})$. We add $k$ parallel edges from $v$ to
$v_{\text{out}}$, and $k$ parallel edges from $v_{\text{in}}$ to $v$, for all
$u$ and $v$. We call vertices present in the graph before modification the
_original vertices_.

Suppose $G$ originally had $n$ nodes and $m$ edges. Then the modified graph
has $n_{\textup{new}}=3n$ nodes and $m_{\textup{new}}=m+2kn$ edges. For any
original vertices $s$ and $t$, edge-disjoint paths from $s$ to $t$ in the new
graph correspond to edge disjoint paths from $s$ to $t$ in the original graph.
Moreover, for any integer $\ell\leq k$, if the original graph contained $\ell$
edge-disjoint paths from $s$ to $t$, then the new graph contains $\ell$ edge-
disjoint paths from $s$ to $t$ as well.

Thus, for any original vertices $s$ and $t$, the value of
$\min(k,\lambda(s,t))$ remains the same in the old graph and the new graph.
So, it suffices to solve $k$-APC on the new graph. In this new graph, the
indegrees and outdegrees of every original vertex are equal to $k$. Moreover,
sets $E_{\textup{out}}(s)$ and $E_{\textup{in}}(t)$ are pairwise disjoint,
over all original vertices $s$ and $t$.

##### Additional Definitions

We make use of the matrices defined in Section 4, except now these matrices
are defined with respect to the modified graph. In particular, $K$, $L$, and
$R$ are now matrices with dimensions $m_{\textup{new}}\times
m_{\textup{new}}$, $m_{\textup{new}}\times n_{\textup{new}}$, and
$n_{\textup{new}}\times m_{\textup{new}}$ respectively.

Define $\tilde{L}$ to be the $kn\times n_{\textup{new}}$ matrix obtained by
vertically concatenating $L[E_{\textup{out}}(s),\ast]$ over all original
vertices $s$. Similarly, define $\tilde{R}$ to be the $n_{\textup{new}}\times
kn$ matrix obtained by horizontally concatenating $R[\ast,E_{\textup{in}}(t)]$
over all original vertices $t$.

##### The Algorithm

Using the above definitions, we present our approach for solving $k$-APC in
Algorithm 1.

Algorithm 1 Our algorithm for solving $k$-APC.

1:Compute the $n_{\textup{new}}\times n_{\textup{new}}$ matrix $(I-RL)^{-1}$.

2:Compute the $kn_{\textup{new}}\times kn_{\textup{new}}$ matrix
$M=\tilde{L}(I-RL)^{-1}\tilde{R}$.

3:For each pair $(s,t)$ of original vertices, compute
$\operatorname{rank}M[E_{\textup{out}}(s),E_{\textup{in}}(t)]$ and output this
as the value for $\min(k,\lambda(s,t))$.

######  Theorem 5.1.

With probability at least $1-5/(m_{\textup{new}})$, Algorithm 1 correctly
solves $k$-APC.

######  Proof 5.2.

By Lemma 4.1, with probability at least $1-1/(m_{\textup{new}})^{4}$ the
matrix $I-K$ is invertible. Going forward, we assume that $I-K$ is invertible.

By Lemma 4.7, with probability at least $1-4/(m_{\textup{new}})^{3}$, we have

$\operatorname{rank}(I-K)^{-1}[E_{\textup{out}}(s),E_{\textup{in}}(t)]=\min(k,\lambda(s,t))$
(14)

for any given original vertices $s$ and $t$. By union bound over all
$n^{2}\leq(m_{\textup{new}})^{2}$ pairs of original vertices $(s,t)$, we see
that Equation 14 holds for all original vertices $s$ and $t$ with probability
at least $1-4/(m_{\textup{new}})$.

Since $I-K$ is invertible, by Equation 8 and Proposition 2.1 we have

$(I-K)^{-1}=(I-LR)^{-1}=I+L(I-RL)^{-1}R.$

Using the above equation in Equation 14 shows that for original vertices $s$
and $t$, the quantity $\min(k,\lambda(s,t))$ is equal to the rank of

$(I+L(I-RL)^{-1}R)[E_{\textup{out}}(s),E_{\textup{in}}(t)]=L[E_{\textup{out}}(s),\ast](I-RL)^{-1}R[\ast,E_{\textup{in}}(t)]$

where we use the fact that $I[E_{\textup{out}}(s),E_{\textup{in}}(t)]$ is the
all zeroes matrix, since in the modified graph, $E_{\textup{out}}(s)$ and
$E_{\textup{in}}(t)$ are disjoint sets for all pairs of original vertices
$(s,t)$.

Then by definition of $\tilde{L}$ and $\tilde{R}$, the above equation and
discussion imply that

$\min(k,\lambda(s,t))=\operatorname{rank}\leavevmode\nobreak\
(\tilde{L}(I-RL)^{-1}\tilde{R})[E_{\textup{out}}(s),E_{\textup{in}}(t)]=\operatorname{rank}M[E_{\textup{out}}(s),E_{\textup{in}}(t)]$

which proves that Algorithm 1 outputs the correct answers.

A union bound over the events that $I-K$ is invertible and that Equation 14
holds for all $(s,t)$, shows that Algorithm 1 is correct with probability at
least $1-5/(m_{\textup{new}})$.

We are now ready to prove our main result.

See 1.1

######  Proof 5.3.

By Theorem 5.1, Algorithm 1 correctly solves the $k$-APC problem. We now argue
that Algorithm 1 can be implemented to run in $\tilde{O}((kn)^{\omega})$ time.

In step 1 of Algorithm 1, we need to compute $(I-RL)^{-1}$.

From the definitions of $R$ and $L$, we see that to compute $RL$, it suffices
to compute the products $R_{i}L_{j}$ for each pair of indices
$(i,j)\in[k]^{2}$. The matrix $R_{i}L_{j}$ is $n_{\textup{new}}\times
n_{\textup{new}}$, and its rows and columns are indexed by vertices in the
graph. Given vertices $u$ and $v$, let $E(u,v)$ denote the set of parallel
edges from $u$ to $v$. From the definitions of the $R_{i}$ and $L_{j}$
matrices, we see that for any vertices $u$ and $v$, we have

$(R_{i}L_{j})[u,v]=\sum_{e\in E(u,v)}R_{i}[u,e]L_{j}[e,v].$ (15)

As noted in Section 2, for all vertices $u$ and $v$ we may assume that
$|E(u,v)|\leq k$.

For each vertex $u$, define the $k\times\deg_{\text{out}}(u)$ matrix
$R^{\prime}_{u}$, with rows indexed by $[k]$ and columns indexed by edges
exiting $u$, by setting

$R^{\prime}_{u}[i,e]=R_{i}[u,e]$

for all $i\in[k]$ and $e\in E_{\textup{out}}(u)$.

Similarly, for each vertex $v$, define the $\deg_{\text{in}}(v)\times k$
matrix $L^{\prime}_{v}$ by setting

$L^{\prime}_{v}[e,j]=L_{j}[e,v]$

for all $e\in E_{\textup{in}}(v)$ and $j\in[k]$.

Finally, for each pair $(u,v)$ of vertices, define
$R^{\prime}_{uv}=R^{\prime}_{u}[\ast,E(u,v)]$ and
$L^{\prime}_{uv}=L^{\prime}_{v}[E(u,v),\ast]$. Then by Equation 15, we have

$(R_{i}L_{j})[u,v]=R^{\prime}_{uv}L^{\prime}_{uv}[i,j].$

Thus, to compute the $R_{i}L_{j}$ products, it suffices to build the
$R^{\prime}_{u}$ and $L^{\prime}_{v}$ matrices in
$O\left(km_{\textup{new}}\right)$ time, and then compute the
$R^{\prime}_{uv}L^{\prime}_{uv}$ products. We can do this by computing
$\left(n_{\textup{new}}\right)^{2}$ products of pairs of $k\times k$ matrices.
Since for every pair of vertices $(u,v)$, there are at most $k$ parallel edges
from $u$ to $v$, $km_{\textup{new}}\leq k^{2}n^{2}$, we can compute all the
$R_{i}L_{j}$ products, and hence the entire matrix $RL$, in
$\tilde{O}(n^{2}k^{\omega})$ time.

We can then compute $I-RL$ by modifying $O(kn)$ entries of $RL$. Finally, by
Proposition 2.3 we can compute $(I-RL)^{-1}$ in $\tilde{O}((kn)^{\omega})$
time.

So overall, step 1 of Algorithm 1 takes $\tilde{O}((kn)^{\omega})$ time.

In step 2 of Algorithm 1, we need to compute
$M=\tilde{L}(I-RL)^{-1}\tilde{R}$.

Recall that $\tilde{L}$ is a $kn\times n_{\textup{new}}$ matrix. By
definition, each row of $\tilde{L}$ has a single nonzero entry. Similarly,
$\tilde{R}$ is an $n_{\textup{new}}\times kn$ matrix, with a single nonzero
entry in each column.

Thus we can compute $M$, and complete step 2 of Algorithm 1 in
$\tilde{O}((kn)^{2})$ time.

Finally, in step 3 of Algorithm 1, we need to compute

$\operatorname{rank}M[E_{\textup{out}}(s),E_{\textup{in}}(t)]$ (16)

for each pair of original vertices $(s,t)$ in the graph. In the modified
graph, each original vertex has indegree and outdegree $k$, so each
$M[E_{\textup{out}}(s),E_{\textup{in}}(t)]$ is a $k\times k$ matrix. For any
fixed $(s,t)$, by Proposition 2.4 we can compute the rank of
$M[E_{\textup{out}}(s),E_{\textup{in}}(t)]$ in $\tilde{O}(k^{\omega})$ time.

So we can compute the ranks from Equation 16 for all $n^{2}$ pairs of original
vertices $(s,t)$ and complete step 3 of Algorithm 1 in
$\tilde{O}(k^{\omega}n^{2})$ time.

Thus we can solve $k$-APC in $\tilde{O}((kn)^{\omega})$ time overall, as
claimed.

##  6 Encoding Vertex Connectivities

Take a prime $p=\tilde{\Theta}(n^{5})$. Let $K$ be an $n\times n$ matrix,
whose rows and columns are indexed by vertices of $G$. For each pair $(u,v)$
of vertices, if $(u,v)$ is an edge in $G$, we set $K[u,v]$ to be a uniform
random element of $\mathbb{F}_{p}$. Otherwise, $K[u,v]=0$.

Recall from Section 2 that given a vertex $v$ in $G$, we let
$V_{\textup{in}}[v]=V_{\textup{in}}(v)\cup\left\\{v\right\\}$ be the set
consisting of $v$ and all in-neighbors of $v$, and
$V_{\textup{out}}[v]=V_{\textup{out}}(v)\cup\left\\{v\right\\}$ be the set
consisting of $v$ and all out-neighbors of $v$. The following
proposition777The result stated here differs from a similar claim used in [1,
Section 5]. We discuss this difference, and related subtleties, in Section
B.1. is based off ideas from [6, Section 2] and [1, Section 5]. We present a
complete proof of this result in Section B.2.

######  Proposition 6.1.

For any vertices $s$ and $t$ in $G$, with probability at least $1-3/n^{3}$,
the matrix $(I-K)$ is invertible and we have

$\operatorname{rank}\leavevmode\nobreak\
(I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}[t]]=\begin{cases}\nu(s,t)+1&\text{if
}(s,t)\text{ is an edge}\\\ \nu(s,t)&\text{otherwise.}\end{cases}$

Proposition 6.1 shows that we can compute vertex connectivities in $G$ simply
by computing ranks of certain submatrices of $(I-K)^{-1}$. However, these
submatrices could potentially be quite large, which is bad if we want to
compute the vertex connectivities quickly. To overcome this issue, we show how
to decrease the size of $(I-K)^{-1}$ while still preserving relevant
information about the value of $\nu(s,t)$.

######  Lemma 6.2.

Let $M$ be an $a\times b$ matrix over $\mathbb{F}_{p}$. Let $\Gamma$ be a
$(k+1)\times a$ matrix with uniform random entries from $\mathbb{F}_{p}$. Then
with probability at least $1-(k+1)/p$, we have

$\operatorname{rank}\Gamma M=\min(k+1,\operatorname{rank}M).$

######  Proof 6.3.

Since $\Gamma M$ has $k+1$ rows, $\operatorname{rank}(\Gamma M)\leq k+1$.

Similarly, since $\Gamma M$ has $M$ as a factor, $\operatorname{rank}(\Gamma
M)\leq\operatorname{rank}M$. Thus

$\operatorname{rank}\Gamma M\leq\min(k+1,\operatorname{rank}M).$ (17)

So, it suffices to show that $\Gamma M$ has rank at least
$\min(k+1,\operatorname{rank}M)$.

Set $r=\min(k+1,\operatorname{rank}M)$. Then there exist subsets $S$ and $T$
of row and column indices respectively, such that $|S|=|T|=r$ and $M[S,T]$ has
rank $r$. Now, let $U$ be an arbitrary set of $r$ rows in $\Gamma$. Consider
the matrix $M^{\prime}=(\Gamma M)[U,T]$.

We can view each entry of $M^{\prime}$ as a polynomial of degree at most $1$
in the entries of $\Gamma$. This means that $\det M^{\prime}$ is a polynomial
of degree at most $r$ in the entries of $\Gamma$. Moreover, if the submatrix
$\Gamma[U,T]=I$ happens to be the identity matrix, then $M^{\prime}=M[S,T]$.
This implies that $\det M^{\prime}$ is a nonzero polynomial in the entries of
$\Gamma$, because for some assignment of values to the entries of $\Gamma$,
this polynomial has nonzero evaluation $\det M[S,T]\neq 0$ (where we are using
the fact that $M[S,T]$ has full rank).

So by the Schwartz-Zippel Lemma (Proposition 2.5), the matrix $\Gamma M$ has
rank at least $r$, with probability at least $1-r/p$.

Together with Equation 17, this implies the desired result.

Now, to each vertex $u$ in the graph, we assign a $(k+1)$-dimensional column
vector $\vec{b}_{u}$ and a $(k+1)$-dimensional row vector $\vec{c}_{u}$.

Let $B$ be the $(k+1)\times n$ matrix formed by concatenating all of the
$\vec{b}_{u}$ vectors horizontally, and let $C$ be the $n\times(k+1)$ matrix
formed by concatenating all of the $\vec{c}_{u}$ vectors vertically. For each
pair of distinct vertices $(s,t)$, define the $(k+1)\times(k+1)$ matrix

$M_{s,t}=B[\ast,V_{\textup{out}}[s]]\left((I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}[t]]\right)C[V_{\textup{in}}[t],\ast].$
(18)

The following result is the basis of our algorithm for $k$-APVC.

######  Lemma 6.4.

For any vertices $s$ and $t$ in $G$, with probability at least $1-5/n^{3}$, we
have

$\operatorname{rank}M_{s,t}=\begin{cases}\min(k+1,\nu(s,t)+1)&\text{if
}(s,t)\text{ is an edge}\\\ \min(k+1,\nu(s,t))&\text{otherwise.}\end{cases}$

######  Proof 6.5.

Fix vertices $s$ and $t$. Then, by Proposition 6.1, we have

$\operatorname{rank}\leavevmode\nobreak\
(I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}[t]]=\begin{cases}\nu(s,t)+1&\text{if
}(s,t)\text{ is an edge}\\\ \nu(s,t)&\text{otherwise}\end{cases}$

with probability at least $1-3/n^{3}$. Assume the above equation holds.

Then, by setting $\Gamma=B[\ast,V_{\textup{out}}[s]]$ and
$M=(I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}[t]]$ in Lemma 6.2, we see
that with probability at least $1-1/n^{3}$ we have

$\operatorname{rank}B[\ast,V_{\textup{out}}[s]](I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}(t)]=\begin{cases}\min(k+1,\nu(s,t)+1)&\text{if
}(s,t)\text{ is an edge}\\\ \min(k+1,\nu(s,t))&\text{otherwise.}\end{cases}.$

Assume the above equation holds.

Finally, by setting $\Gamma=C^{\top}[\ast,V_{\textup{in}}(t)]$ and
$M=(B[\ast,V_{\textup{out}}[s]](I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}(t)])^{\top}$
in Lemma 6.2 and transposition, we see that with probability at least
$1-1/n^{3}$ we have

$\operatorname{rank}B[\ast,V_{\textup{out}}[s]]\left((I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}(t)]\right)C[V_{\textup{in}}(t),\ast]=\min(k+1,\nu(s,t)+1)$

if there is an edge from $s$ to $t$, and

$\operatorname{rank}B[\ast,V_{\textup{out}}[s]]\left((I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}(t)]\right)C[V_{\textup{in}}(t),\ast]=\min(k+1,\nu(s,t))$

otherwise. So by union bound, the desired result holds with probability at
least $1-5/n^{3}$.

##  7 Vertex Connectivity Algorithm

Let $A$ be the adjacency matrix of the graph $G$ with self-loops. That is, $A$
is the $n\times n$ matrix whose rows and columns are indexed by vertices of
$G$, and for every pair $(u,v)$ of vertices, $A[u,v]=1$ if $v\in
V_{\textup{out}}[u]$ (equivalently, $u\in V_{\textup{in}}[v]$), and $A[u,v]=0$
otherwise.

Recall the definitions of the $\vec{b}_{u}$ and $\vec{c}_{u}$ vectors, and the
$K,B,C$ and $M_{s,t}$ matrices from Section 6. For each $i\in[k+1]$, let
$P_{i}$ be the $n\times n$ diagonal matrix, with rows and columns indexed by
vertices of $G$, such that $P_{i}[u,u]=\vec{b}_{u}[i]$. Similarly, let $Q_{i}$
be the $n\times n$ diagonal matrix, with rows and columns indexed by vertices
of $G$, such that $Q_{i}[u,u]=\vec{c}_{u}[i]$.

With these definitions, we present our approach for solving $k$-APVC in
Algorithm 2.

Algorithm 2 Our algorithm for solving $k$-APVC.

1:Compute the $n\times n$ matrix $(I-K)^{-1}$.

2:For each pair $(i,j)\in[k+1]^{2}$ of indices, compute the $n\times n$ matrix
$D_{ij}=AP_{i}(I-K)^{-1}Q_{j}A^{\top}.$

3: For each pair $(s,t)$ of vertices, let $F_{s,t}$ be the $(k+1)\times(k+1)$
matrix whose $(i,j)$ entry is equal to $D_{ij}[s,t]$. If $(s,t)$ is an edge,
output $(\operatorname{rank}F_{s,t})-1$ as the value for $\min(k,\nu(s,t))$.
Otherwise, output $\min(k,\operatorname{rank}F_{s,t})$ as the value for
$\min(k,\nu(s,t))$.

The main idea of Algorithm 2 is to use Lemma 6.4 to reduce computing
$\min(k,\nu(s,t))$ for a given pair of vertices $(s,t)$ to computing the rank
of a corresponding $(k+1)\times(k+1)$ matrix, $M_{s,t}$. To make this approach
efficient, we compute the entries of all $M_{s,t}$ matrices simultaneously,
using a somewhat indirect argument.

######  Theorem 7.1.

With probability at least $1-5/n$, Algorithm 2 correctly solves $k$-APVC.

######  Proof 7.2.

We prove correctness of Algorithm 2 using the following claim.

######  Claim 1.

For all pairs of indices $(i,j)\in[k+1]^{2}$ and all pairs of vertices
$(s,t)$, we have

$M_{s,t}[i,j]=D_{ij}[s,t],$

where $D_{ij}$ is the matrix computed in step 2 of Algorithm 2.

By expanding out the expression for $D_{ij}$ from step 2 of Algorithm 2, we
have

$D_{ij}[s,t]=\sum_{u,v}A[s,u]P_{i}[u,u]\left((I-K)^{-1}[u,v]\right)Q_{j}[v,v]A[v,t],$

where the sum is over all vertices $u,v$ in the graph (here, we use the fact
that $P_{i}$ and $Q_{j}$ are diagonal matrices). By the definitions of $A$,
the $P_{i}$, and the $Q_{j}$ matrices, we have

$D_{ij}[s,t]=\sum_{\begin{subarray}{c}u\in V_{\textup{out}}[s]\\\ v\in
V_{\textup{in}}[t]\end{subarray}}\vec{b}_{u}[i]\left((I-K)^{-1}[u,v]\right)\vec{c}_{v}[j].$
(19)

On the other hand, the definition of $M_{s,t}$ from Equation 18 implies that

$M_{s,t}[i,j]=\sum_{\begin{subarray}{c}u\in V_{\textup{out}}[s]\\\ v\in
V_{\textup{in}}[t]\end{subarray}}B[i,u]\left((I-K)^{-1}[u,v]\right)C[v,j].$

Since $B[i,u]=\vec{b}_{u}[i]$ and $C[v,j]=\vec{c}_{v}[j]$, the above equation
and Equation 19 imply that

$M_{s,t}[i,j]=D_{ij}[s,t]$

for all $(i,j)$ and $(s,t)$, as desired.

By 1, the matrix $F_{s,t}$ computed in step 3 of Algorithm 2 is equal to
$M_{s,t}$. So by Lemma 6.4, for any fixed pair $(s,t)$ of vertices we have

$\operatorname{rank}F_{s,t}=\begin{cases}\min(k+1,\nu(s,t)+1)&\text{if
}(s,t)\text{ is an edge}\\\ \min(k+1,\nu(s,t))&\text{otherwise.}\end{cases}$
(20)

with probability at least $1-5/n^{3}$. Then by a union bound over all pairs of
vertices $(s,t)$, we see that Equation 20 holds for all pairs $(s,t)$, with
probability at least $1-5/n$.

Assume this event occurs. Then if $(s,t)$ is an edge, by Equation 20 we
correctly return

$(\operatorname{rank}F_{s,t})-1=\min(k+1,\nu(s,t)+1)-1=\min(k,\nu(s,t))$

as our answer for this pair.

Similarly, if $(s,t)$ is not an edge, by Equation 20 we correctly return

$\min(k,\operatorname{rank}F_{s,t})=\min(k,k+1,\nu(s,t))=\min(k,\nu(s,t))$

as our answer for this pair. This proves the desired result.

With Theorem 7.1 established, we can prove our result for vertex
connectivities.

See 1.2

######  Proof 7.3.

By Theorem 7.1, Algorithm 2 correctly solves the $k$-APVC problem. We now
argue that Algorithm 2 can be implemented to run in
$\tilde{O}(k^{2}n^{\omega})$ time.

In step 1 of Algorithm 2, we need to compute $(I-K)^{-1}$. Since $K$ is an
$n\times n$ matrix, by Proposition 2.3 we can complete this step in
$\tilde{O}(n^{\omega})$ time.

In step 2 of Algorithm 2, we need to compute $D_{ij}$ for each pair
$(i,j)\in[k+1]^{2}$. For each fixed pair $(i,j)$, the $D_{ij}$ matrix is
defined as a product of five $n\times n$ matrices whose entries we know, so
this step takes $\tilde{O}(k^{2}n^{\omega})$ time overall.

In step 3 of Algorithm 2, we need to construct each $F_{st}$ matrix, and
compute its rank. Since each $F_{st}$ matrix has dimensions $(k+1)\times(k+1)$
and its entries can be filled in simply by reading entries of the $D_{ij}$
matrices we have already computed, by Proposition 2.4 this step can be
completed in $\tilde{O}(k^{\omega}n^{2})$ time.

By adding up the runtimes for each of the steps and noting that $k\leq n$, we
see that Algorithm 2 solves $k$-APVC in $\tilde{O}(k^{2}n^{\omega})$ time, as
claimed.

##  8 Conclusion

In this paper, we presented algorithms solving $k$-APC and $k$-APVC in
$\tilde{O}((kn)^{\omega})$ and $\tilde{O}(k^{2}n^{\omega})$ time respectively.
Many open problems remain concerning the exact time complexity of these
problems. We highlight some open questions we find particularly interesting:

  1. 1.

The most relevant question to our work: can we solve $k$-APC or $k$-APVC
faster? Is it possible to solve $k$-APC in $\tilde{O}(k^{2}n^{\omega})$ time,
as fast as our algorithm for $k$-APVC? Could there be some moderately large
parameter values $k\geq n^{\Omega(1)}$ for which these problems can be solved
in $\tilde{O}(n^{\omega})$ time, matching the runtime for constant $k$?

  2. 2.

Can we get better conditional lower bounds for $k$-APC and $k$-APVC?
Currently, no conditional lower bound rules out the possibility that these
problems could, for example, be solved in $\tilde{O}(kn^{\omega})$ time. For
the APC and APVC problems, can the known $n^{\omega(1,2,1)-o(1)}$ conditional
lower bounds be improved888There is some evidence that better lower bounds may
be difficult to establish [13]. to $n^{4-o(1)}$ conditional lower bounds?

  3. 3.

Recently, [13] showed that there is a nondeterministic verifier for the APVC
problem, running in $O(n^{\omega(1,2,1)})$ time. Is there a nondeterministic
verifier for APC with the same runtime? Are there nondeterministic verifiers
for the $k$-APC and $k$-APVC problems, which run faster than the algorithms
from Theorems 1.1 and 1.2?

## References

  * [1] Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf.  Faster algorithms for all-pairs bounded min-cuts.  In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 7:1–7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ICALP.2019.7.
  * [2] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi.  APMF < APSP? Gomory-Hu tree for unweighted graphs in almost-quadratic time.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 1135–1146. IEEE, 2021.  doi:10.1109/FOCS52979.2021.00112.
  * [3] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 522–539. SIAM, 2021.  doi:10.1137/1.9781611976465.32.
  * [4] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022.  doi:10.1109/FOCS54457.2022.00064.
  * [5] Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau.  Fast matrix rank algorithms and applications.  Journal of the ACM, 60(5):1–25, October 2013.  doi:10.1145/2528404.
  * [6] Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung.  Graph connectivities, network coding, and expander graphs.  SIAM Journal on Computing, 42(3):733–751, January 2013.  doi:10.1137/110844970.
  * [7] M. J. Fischer and A. R. Meyer.  Boolean matrix multiplication and transitive closure.  In 12th Annual Symposium on Switching and Automata Theory (SWAT 1971). IEEE, October 1971.  doi:10.1109/swat.1971.4.
  * [8] François Le Gall and Florent Urrutia.  Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’18, page 1029–1046, USA, 2018. Society for Industrial and Applied Mathematics.
  * [9] Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemysław Uznański.  All-Pairs 2-Reachability in $O(n^{\omega}logn)$ Time.  In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 74:1–74:14, Dagstuhl, Germany, 2017\. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2017/7451, doi:10.4230/LIPIcs.ICALP.2017.74.
  * [10] Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, and Benyu Wang.  Tight conditional lower bounds for vertex connectivity problems, 2022\.  URL: https://arxiv.org/abs/2212.00359, doi:10.48550/ARXIV.2212.00359.
  * [11] Robert Krauthgamer and Ohad Trabelsi.  Conditional lower bounds for all-pairs max-flow.  ACM Trans. Algorithms, 14(4), aug 2018.  doi:10.1145/3212510.
  * [12] Rajeev Motwani and Prabhakar Raghavan.  Randomized Algorithms.  Cambridge University Press, August 1995.  doi:10.1017/cbo9780511814075.
  * [13] Ohad Trabelsi.  (Almost) ruling out SETH lower bounds for all-pairs max-flow, 2023\.  URL: https://arxiv.org/abs/2304.04667, doi:10.48550/ARXIV.2304.04667.
  * [14] Xiaowei Wu and Chenzi Zhang.  Efficient algorithm for computing all low s-t edge connectivities in directed graphs.  In Mathematical Foundations of Computer Science 2015, pages 577–588. Springer Berlin Heidelberg, 2015.  doi:10.1007/978-3-662-48054-0_48.

##  Appendix A Conjectures in Fine-Grained Complexity

In the Boolean Matrix Multiplication (BMM) problem, we are given $n\times n$
matrices $A$ and $B$ with entries in $\left\\{0,1\right\\}$, and are tasked
with computing, for each pair $(i,j)\in[n]^{2}$, whether there exists an index
$k$ such that $A[i,k]=B[k,j]=1$. Using matrix multiplication, we can solve BMM
in $O(n^{\omega})$ time.

The BMM hypothesis999The literature also refers to the Combinatorial BMM
hypothesis, an informal conjecture that no “combinatorial” algorithm for BMM
runs in $O(n^{3-\delta})$ time, for any constant $\delta>0$. posits that this
is essentially optimal, and asserts that there is no constant $\delta>0$ such
that BMM can be solved in $O(n^{\omega-\delta})$ time.

Let $k$ be a positive integer. In the $k$SAT problem, we are given a $k$-CNF
(a Boolean formula which can be written as a conjunction of clauses, where
each clause is the disjunction of at most $k$ Boolean literals) over $n$
variables, and tasked with determining if there is some assignment of values
to the variables which satisfies the $k$-CNF.

The Strong Exponential Time Hypothesis (SETH) conjectures that for any
constant $\delta>0$, there exists some positive integer $k$ such that $k$SAT
cannot be solved in $2^{(1-\delta)n}\operatorname{poly}(n)$ time.

In the $4$-Clique problem, we are given a graph $G$, and tasked with
determining if it contains a clique on four vertices (i.e., four distinct
vertices which are mutually adjacent).

Let $\omega(1,2,1)$ be the smallest positive real such that we can multiply an
$n\times n^{2}$ matrix with an $n^{2}\times n$ matrix in
$n^{\omega(1,2,1)+o(1)}$ time. It is known that $4$-Clique can be solved in
$O\left(n^{\omega(1,2,1)}\right)$ time. The $4$-Clique Conjecture101010This
conjecture also has informal counterpart in the literature, which states that
no “combinatorial” algorithm for $4$-Clique runs in $O(n^{4-\delta})$ time,
for any constant $\delta>0$. asserts that this runtime is essentially optimal,
in the sense that for any constant $\delta>0$, the $4$-Clique problem cannot
be solved in $O\left(n^{\omega(1,2,1)-\delta}\right)$ time.

##  Appendix B Vertex Connectivity Encoding Scheme

In Section B.1, we describe the result that [1] obtains for computing vertex
cuts, and explain how the claims in [1] differ from the arguments in this
work. In Section B.2, we present a proof of Proposition 6.1.

###  B.1 Discussion of Previous Vertex Cuts Algorithm

In [1], the authors present an $\tilde{O}((kn)^{\omega})$ time algorithm for
the $k$-Bounded All-Pairs Minimum Vertex Cut problem. In this problem, we are
given a directed graph $G$ on $n$ vertices, and are tasked with returning, for
every pair of vertices $(s,t)$, the size of a minimum $(s,t)$-vertex cut, if
this size is less than $k$. For pairs $(s,t)$ where the size of a minimum
$(s,t)$-vertex cut is at least $k$, we simply need to return the value $k$.

When $(s,t)$ is not an edge, Menger’s theorem implies that the size of a
minimum $(s,t)$-vertex cut is equal to the maximum number of internally
vertex-disjoint paths from $s$ to $t$. So, for such pairs $(s,t)$, the
$k$-Bounded All-Pairs Minimum Vertex Cut problem simply requires we compute
the value of $\min(k,\nu(s,t))$, as in the $k$-APVC problem.

However, when $(s,t)$ is an edge, as discussed in Section 2, no $(s,t)$-vertex
cut can exist. This is because no matter which vertices outside of $s$ and $t$
we delete, the resulting graph will always have a path of length one from $s$
to $t$.

In this case, it may be reasonable to define the “size of a minimum
$(s,t)$-vertex cut” to be $\infty$. With this convention, for pairs of
vertices $(s,t)$ which are edges, we simply need to return the value of $k$ in
the $k$-Bounded All-Pairs Minimum Vertex Cut problem. This is precisely what
the algorithm of [1] does.

In more detail, the argument sketched in [1, Proof of Lemma 5.1] argues that

$\operatorname{rank}\leavevmode\nobreak\
(I-K)^{-1}[V_{\textup{out}}(s),V_{\textup{in}}(t)]$ (21)

is equal to the size of a minimum $(s,t)$-vertex cut, for all pairs of
vertices $(s,t)$ which are not edges, with high probability (where $K$ is
defined as in Section 3.3).

The algorithm from [1, Proof of Theorem 5.2] first modifies the graph, and
then computes the value of Equation 21 for every pair of original vertices
$(s,t)$ with respect to the new graph, to compute the answers to the
$k$-Bounded All-Pairs Minimum Vertex Cut problem.

As described in Section 3.3, the graph is transformed by introducing for each
vertex $s$ a set $S$ of $k$ new nodes, adding edges from $s$ to each node in
$S$, adding edges from all nodes in $S$ to all out-neighbors of $s$ in the
original graph, and erasing all edges from $s$ to its original out-neighbors.
Similarly, the transformation also introduces for each vertex $t$ a set $T$ of
$k$ new nodes, adds edges from all in-neighbors of $t$ to the nodes in $T$,
adds edges from all nodes in $T$ to $t$, and erases all edges entering $t$
from its original in-neighbors.

If $(s,t)$ was not an edge in the original graph, then $(s,t)$ is still not an
edge in the new graph. In this scenario, the vertex connectivity from $s$ to
$t$ in the new graph turns out to be $\min(k,\nu(s,t))$. Since $(s,t)$ is not
an edge, the value $\nu(s,t)$ coincides with the size of a minimum
$(s,t)$-vertex cut. So in this case, returning the value of Equation 21
produces the correct answer for the $k$-Bounded All-Pairs Minimum Vertex Cut
problem.

Suppose now that $(s,t)$ is an edge in the original graph. Then $(s,t)$ will
not be an edge in the new graph, since the new out-neighbors of $s$ are all
distinct from the new in-neighbors of $t$. However, the transformation ensures
that in the new graph there are $k$ internally vertex-disjoint paths from $s$
to $t$, because each of the $k$ new out-neighbors of $s$ has an edge to each
of the $k$ new in-neighbors of $t$. Then in this case, returning the value of
Equation 21 just amounts to returning the value $k$.

So the algorithm of [1, Proof of Theorem 5.2] produces the correct answer for
the $k$-Bounded All-Pairs Minimum Vertex Cut problem when $(s,t)$ is an edge,
using the convention that the size of a minimum $(s,t)$-vertex cut is $\infty$
when $(s,t)$ is an edge.

In summary: the algorithm from [1] runs in $\tilde{O}((kn)^{\omega})$ time and
computes $\min(k,\nu(s,t))$ for all pairs of vertices $(s,t)$ such that
$(s,t)$ is not an edge, but for pairs where $(s,t)$ is an edge, does not
return any information about the value of $\nu(s,t)$.

##### Moving From Vertex Cuts to Vertex Connectivities

The quantity in Equation 21 differs from the expression we use Proposition
6.1, where we index the rows and columns by $V_{\textup{out}}[s]$ and
$V_{\textup{in}}[t]$, instead of $V_{\textup{out}}(s)$ and
$V_{\textup{in}}(t)$ respectively. For the purpose of solving $k$-APVC, we
need to work with a different submatrix from the one used in Equation 21,
because when $(s,t)$ is an edge, the expression in Equation 21 is not
necessarily equal to $\nu(s,t)$.

For example, suppose $G$ is a graph where $\deg_{\text{in}}(s)=0$,
$\deg_{\text{out}}(t)=1$, there is an edge from $s$ to $t$, and $\nu(s,t)=1$.
Then the proof sketch in [1, Proof of Lemma 5.1] (using the terminology of
Section 3.3) suggests pumping unit vectors to nodes in $V_{\textup{out}}(s)$,
using these initial vectors to determine flow vectors for all nodes, and then
computing the rank of the flow vectors assigned to nodes in
$V_{\textup{in}}(t)$. In this example, since $s$ has indegree zero and no
initial vector is pumped to it, it is assigned the flow vector
$\vec{s}=\vec{0}$. Since $V_{\textup{in}}(t)=\left\\{s\right\\}$ in this
example, the rank of flow vectors in $V_{\textup{in}}(t)$ is just zero, even
though $\nu(s,t)=1$.

This issue arises more generally in the proof suggested by [1, Proof of Lemma
5.1] whenever $(s,t)$ is an edge of the graph. Intuitively, this is because a
maximum collection of internally vertex-disjoint paths from $s$ to $t$ will
always include a path consisting of a single edge from $s$ to $t$, but if we
do not pump out a vector at $s$, this path will not contribute to the rank of
the flow vectors entering $t$.

To overcome this issue and correctly compute for vertex connectivities for all
pairs, we modify the expression from Equation 21 appropriately (by pumping out
an initial vector at the source $s$, and allowing the flow vector assigned to
$t$ to contribute to teh rank), which is why our statement of Proposition 6.1
involves computing the rank of a different submatrix.

The issue described above does not appear when dealing with edge connectivity,
essentially because in that case there is always a set of edges whose removal
destroys all $s$ to $t$ paths.

###  B.2 Proof of Vertex Connectivity Encoding

In this section, we provide a proof of Proposition 6.1, whose statement we
recall below.

See 6.1

Our proof of Proposition 6.1 is similar to the outline in [1, Section 5] and
is based off ideas from [6, Section 2], but involves several modifications
needed to address issues which arise when dealing with vertex connectivities.

Fix a source node $s$ and target node $t$ in the input graph $G$. Write
$v_{0}=s$. Suppose $s$ has outdegree $d=\deg_{\text{out}}(s)$. Let
$v_{1},\dots,v_{d}$ be the out-neighbors of $s$ from $V_{\textup{out}}(s)$.

Take a prime $p=\Theta(n^{5})$ (this is the same prime $p$ from Section 6).
Let $\vec{u}_{0},\dots,\vec{u}_{d}$ denote distinct unit vectors in
$\mathbb{F}_{p}^{d+1}$.

Eventually, we will assign each vertex $v$ in $G$ a vector
$\vec{v}\in\mathbb{F}_{p}^{d+1}$, which we call a _flow vector_. These flow
vectors are determined by a system of vector equations. To describe these
equations, we first need to introduce some symbolic matrices.

Let $Z$ be an $n\times n$ matrix, whose rows and columns are indexed by
vertices in $G$.

If $(u,v)$ is an edge, we set $Z[u,v]=z_{uv}$ to be an indeterminate, and
otherwise $Z[u,v]=0$.

Consider the following procedure. We assign independent, uniform random values
from the field $\mathbb{F}_{p}$ to each variable $z_{uv}$. Let $K$ be the
$n\times n$ matrix resulting from this assignment to the variables in $Z$
(this agrees with the definition of $K$ in Section 6).

Now, to each vertex $v$, we assign a flow vector $\vec{v}$, satisfying the
following equalities:

  1. 1.

Recall that $V_{\textup{out}}[s]=\left\\{v_{0},\dots,v_{d}\right\\}$. For each
vertex $v_{i}$, we require its flow vector satisfy

$\vec{v}_{i}=\left(\sum_{u\in V_{\textup{in}}(v_{i})}\vec{u}\cdot
K[u,v_{i}]\right)+\vec{u}_{i}.$ (22)

  2. 2.

For each vertex $v\not\in V_{\textup{out}}[s]$, we require its flow vector
satisfy

$\vec{v}=\sum_{u\in V_{\textup{in}}(v)}\vec{u}\cdot K[u,v].$ (23)

It is not obvious that such flow vectors exist, but we show below that they do
(with high probability over the random assignment to the $z_{uv}$ variables).
Let $H_{s}$ denote the $(d+1)\times n$ matrix whose columns are indexed by
vertices in $G$, such that the column associated with $v_{i}$ is $\vec{v}_{i}$
for each index $0\leq i\leq d$, and the rest of the columns are zero vectors.
Let $F$ be the $(d+1)\times n$ matrix, with columns indexed by vertices in
$G$, such that the column associated with a vertex $v$ is the corresponding
flow vector $\vec{v}$.

Then Equations 22 and 23 are captured by the matrix equation

$F=FK+H_{s}.$ (24)

We will prove that flow vectors $\vec{v}$ satisfying the above conditions
exist, by showing that we can solve for $F$ in Equation 24. To do this, we use
the following lemma.

######  Lemma B.1.

We have $\det(I-K)\neq 0$, with probability at least $1-1/n^{3}$.

######  Proof B.2.

Each entry of $Z$ is a polynomial of degree at most one with constant term
zero. Since the input graph has no self-loops, the diagonal entries of $Z$ are
all zeros.

Thus, $\det(I-Z)$ is a polynomial of degree at most $n$ and constant term $1$
(which means this polynomial is nonzero). So by the Schwartz-Zippel Lemma
(Proposition 2.5), $\det(I-K)$ is nonzero with probability at least $1-n/p\geq
1/n^{4}$ (by taking $p\geq n^{5})$ as claimed.

Suppose from now on that $\det(I-K)\neq 0$ (by Lemma B.1, this occurs with
high probability). In this case, the flow vectors are well-defined, and by
Equation 24 occur as columns of

$F=H_{s}(I-K)^{-1}=\frac{H_{s}\left(\text{adj}(I-K)\right)}{\det(I-K)}.$ (25)

######  Lemma B.3.

For any vertex $t$ in $G$, with probability at least $1-1/n^{3}$, we have

$\operatorname{rank}F[\ast,V_{\textup{in}}[t]]\leq\begin{cases}\nu(s,t)+1&\text{if
}(s,t)\text{ is an edge}\\\ \nu(s,t)&\text{otherwise}.\end{cases}$

######  Proof B.4.

Abbreviate $\nu=\nu(s,t)$. Conceptually, this proof works by arguing that the
flow vectors assigned to all in-neighbors of $t$ are linear combinations of
the flow vectors assigned to nodes in a minimum $(s,t)$-vertex cut of the
graph $G$ with edge $(s,t)$ removed.

Let $G^{\prime}$ be the graph $G$ with edge $(s,t)$ removed (if $(s,t)$ is not
an edge, then $G^{\prime}=G$). Let $C^{\prime}$ be a minimum $(s,t)$-vertex
cut of $G^{\prime}$. This means that $C^{\prime}$ is a minimum size set of
nodes (where $s,t\notin C^{\prime}$) such that deleting $C^{\prime}$ from
$G^{\prime}$ produces a graph with no $s$ to $t$ path. After removing the
nodes in $C^{\prime}$ from $G^{\prime}$, let $S$ be the set of vertices
reachable from $s$, and $T$ be the set of vertices which can reach $t$.

If $(s,t)$ is an edge, set $C=C^{\prime}\cup\left\\{s,t\right\\}$. Otherwise,
set $C=C^{\prime}$.

By Menger’s theorem, $|C|=\nu$ if $(s,t)$ is not an edge in $G$, and otherwise
$|C|=\nu+1$. This is because in addition to the edge $(s,t)$, we can find
$|C^{\prime}|$ internally-vertex disjoint paths from $s$ to $t$, so
$\nu(s,t)=|C^{\prime}|+1=|C|-1$.

Let $V^{\prime}$ be the set of vertices which are in $T$, or have an edge to a
vertex in $T$. Then set $K^{\prime}=K[V^{\prime},V^{\prime}]$ and
$F^{\prime}=F[\ast,V^{\prime}]$. Now define the matrix
$H^{\prime}=F^{\prime}-F^{\prime}K^{\prime}.$ By definition, the columns of
$H^{\prime}$ are indexed by vertices in $V^{\prime}$.

######  Claim 2.

For all $v\in V^{\prime}\setminus C$, we have $H^{\prime}[\ast,v]=\vec{0}$.

Take $v\in V^{\prime}\setminus C$.

Note that $v\neq s$. Indeed, if $(s,t)$ is an edge, then $s\in C$, so $v\neq
s$ is forced since $v\not\in C$. If $(s,t)$ is not an edge, then by definition
of a vertex cut, $s$ can have no edge to $T$ and $s$ is not in $T$, which
means that $s\not\in V^{\prime}$, again forcing $v\neq s$.

We first handle the case where $v\neq t$.

Case 1: $v\neq t$

In this case, by definition of a vertex cut, $v\in T$. Thus, the in-neighbors
of $v$ are all members of $V^{\prime}$. By the discussion at the beginning of
this proof, $v\neq s$.

We claim that $v\not\in V_{\textup{out}}(s)$. Indeed, suppose to the contrary
that $v\in V_{\textup{out}}(s)$. By the case assumption, $v\neq t$. By
definition, $v\not\in C$ and $v$ has an edge to $T$. This means there is a
path of length two from $s$ to a vertex in $T$, not using any vertices in $C$.
This contradicts the definition of an $(s,t)$-vertex cut. So it must be the
case that $v\not\in V_{\textup{out}}(s)$ as claimed.

So in this case, we have shown that for $v\in V^{\prime}\setminus C$, we have
$V_{\textup{in}}(v)\subseteq V^{\prime}$ and $v\not\in V_{\textup{out}}(s)$.
It follows from Equation 23 and the definitions of $F^{\prime}$ and
$K^{\prime}$ that

$(F^{\prime}K^{\prime})[\ast,v]=\sum_{u\in V_{\textup{in}}(v)\cap
V^{\prime}}\vec{u}\cdot K^{\prime}[u,v]=\sum_{u\in
V_{\textup{in}}(v)}\vec{u}\cdot K[u,v]=F[\ast,v]=F^{\prime}[\ast,v]$ (26)

which proves that

$H^{\prime}[\ast,v]=F^{\prime}[\ast,v]-(F^{\prime}K^{\prime})[\ast,v]=\vec{0}$

as desired. It remains to handle the case where $v\in V^{\prime}\setminus C$
has $v=t$.

Case 2: $v=t$

In this case, by definition of $C$, there must be no edge from $s$ to $t$.

Hence $t\not\in V_{\textup{out}}(s)$. Of course we have
$V_{\textup{in}}(t)\subseteq V^{\prime}$ by definition. So the calculation
from Equation 26 applies to $v=t$ as well, which means that
$H^{\prime}[\ast,t]=\vec{0}$.

Thus for all $v\in V^{\prime}\setminus C$, we have
$H^{\prime}[\ast,v]=\vec{0}$ as desired.

By 2, $H^{\prime}$ has at most $|C|$ nonzero columns. Thus,
$\operatorname{rank}H^{\prime}\leq|C|$.

Similar reasoning to the proof of Lemma B.1, shows that matrix $I-K^{\prime}$
is invertible, with probability at least $1-1/n^{3}$. So we can solve for
$F^{\prime}$ in the equation $H^{\prime}=F^{\prime}-F^{\prime}K^{\prime}$ to
get

$F^{\prime}=H^{\prime}(I-K^{\prime})^{-1}.$

Since $\operatorname{rank}H^{\prime}\leq|C|$, the above equation implies that
$\operatorname{rank}F^{\prime}\leq|C|$ as well.

By definition, $V_{\textup{in}}[t]\subseteq V^{\prime}$, so
$F[\ast,V_{\textup{in}}[t]]$ is a submatrix of $F^{\prime}$. It follows that

$\operatorname{rank}F[\ast,V_{\textup{in}}[t]]\leq|C|.$

Since $|C|=\nu+1$ if $(s,t)$ is an edge, and otherwise $|C|=\nu$, the desired
result follows.

######  Lemma B.5.

For any vertex $t$ in $G$, with probability at least $1-2/n^{3}$, we have

$\operatorname{rank}F[\ast,V_{\textup{in}}[t]]\geq\begin{cases}\nu(s,t)+1&\text{if
}(s,t)\text{ is an edge}\\\ \nu(s,t)&\text{otherwise}.\end{cases}$

######  Proof B.6.

Abbreviate $\nu=\nu(s,t)$. Intuitively, our proof will argue that the presence
of internally vertex-disjoint paths from $s$ to $t$ will lead to certain nodes
in $V_{\textup{in}}[t]$ being assigned linearly independent flow vectors (with
high probability), which then implies the desired lower bound.

By definition, $G$ contains $\nu$ internally-vertex disjoint paths
$P_{1},\dots,P_{\nu}$ from $s$ to $t$.

Consider the following assignment to the $z_{uv}$ variables of the matrix $Z$.
For each $(u,v)$, we set $z_{uv}=1$ if $(u,v)$ is an edge on one of the
$P_{i}$ paths. Otherwise, we set $z_{uv}=0$. For each vertex $v$, let
$\vec{v}$ denote the flow vector for $v$ with respect to this assignment. To
show the desired rank lower bound, it will help to first identify the values
of some of these flow vectors.

Let $\vec{u}_{0}$ denote the unit vector initially pumped out at vertex $s$
(as in Equation 22).

Take an arbitrary $P_{i}$ path.

First, suppose that $P_{i}$ is a path of length at least two. In this case,
let $a_{i}$ denote the second vertex in $P_{i}$, and $b_{i}$ denote the
penultimate vertex in $P_{i}$ (note that if $P_{i}$ has length exactly two,
then $a_{i}=b_{i}$). By definition, $a_{i}\in V_{\textup{out}}(s)$. Let
$\vec{u}_{i}$ be the unit vector initially pumped at node $a_{i}$ (as in
Equation 22). Then from our choice of assignment to the $z_{uv}$ variables, by
Equation 22 we have

$\vec{a}_{i}=\vec{u}_{0}+\vec{u}_{i}.$

Then by applying Equation 23 repeatedly to the vertices on the path from
$a_{i}$ to $b_{i}$ on $P_{i}$, we find that

$\vec{b_{i}}=\vec{u}_{0}+\vec{u}_{i}$ (27)

as well. The above equation characterizes the flow vectors for the penultimate
vertices of $P_{i}$ paths of length at least two. It remains to consider the
case where $P_{i}$ has length one. If $P_{i}$ has length one, it consists of a
single edge from $s$ to $t$. Then by Equation 22 we have

$\vec{s}=\vec{u}_{0}.$ (28)

We are now ready to show that the flow vectors for nodes in
$V_{\textup{in}}[t]$ together achieve the desired rank lower bound, for this
particular assignment of values to the $z_{uv}$ variables.

######  Claim 3.

With respect to the assignment where $z_{uv}=1$ if $(u,v)$ is an edge in a
$P_{i}$ path, and $z_{uv}=0$ otherwise, the rank of the flow vectors in
$V_{\textup{in}}[t]$ is at least $\nu+1$ if $(s,t)$ is an edge, and at least
$\nu$ otherwise.

We perform casework on whether $(s,t)$ is an edge or not.

Case 1: $(s,t)$ is not an edge

Suppose that $(s,t)$ is not an edge. Then every path $P_{i}$ has length at
least two. Equation 27 shows that the flow vectors in $V_{\textup{in}}(t)$
include
$\vec{u}_{0}+\vec{u}_{1},\vec{u}_{0}+\vec{u}_{2},\dots,\vec{u}_{0}+\vec{u}_{\nu}$.
Since the $\vec{u}_{i}$ are distinct unit vectors, these flow vectors have
rank at least $\nu$ as desired.

Case 2: $(s,t)$ is an edge

Suppose instead that $(s,t)$ is an edge. Then one of the paths in our maximum
collection of vertex-disjoint paths must be a direct edge from $s$ to $t$.
Without loss of generality, let $P_{\nu}$ be this path of length one (so that
$P_{i}$ is a path of length two for all $1\leq i\leq\nu-1$).

In this case, $t\in V_{\textup{out}}(s)$. Let $\vec{u}_{\nu}$ denote the unit
vector pumped out at $\vec{t}$.

By substituting Equations 27 and 28 into Equation 22, we get that

$\vec{t}=\vec{s}+\left(\sum_{i=1}^{\nu-1}\vec{b}_{i}\right)+\vec{u}_{\nu}=\nu\cdot\vec{u}_{0}+\left(\sum_{i=1}^{\nu-1}\vec{u}_{i}\right)+\vec{u}_{\nu}.$

By combining the above equation with Equations 27 and 28, we see that flow
vectors assigned to nodes in $V_{\textup{in}}[t]$, which include
$\vec{b}_{1},\dots,\vec{b}_{\nu-1},\vec{s}$, and $\vec{t}$, span the space
containing distinct unit vectors
$\vec{u}_{0},\vec{u}_{1},\dots,\vec{u}_{\nu}$, and hence have rank at least
$\nu+1$ as desired.

For convenience, in the remainder of this proof, we let $\tilde{\nu}$ denote
$\tilde{\nu}=\nu+1$ if $(s,t)$ is an edge, and set $\tilde{\nu}=\nu$
otherwise.

By 3, $\operatorname{rank}F[\ast,V_{\textup{in}}(t)]=\tilde{\nu}$. So,
$F[\ast,V_{\textup{in}}(t)]$ contains a full rank
$\tilde{\nu}\times\tilde{\nu}$ submatrix.

Let $F^{\prime}$ be such a submatrix.

Now, before assigning values to the $z_{uv}$ variables, each entry of
$\operatorname{adj}(I-Z)$ is a polynomial of degree at most $n$. So by
Equation 25, $\det F^{\prime}$ is equal to some polynomial $P$ of degree at
most $n\tilde{\nu}$, divided by the polynomial $(\det(I-Z))^{\tilde{\nu}}$.
Note that $\det(I-Z)$ is nonzero polynomial, since it has constant term equal
to $1$.

By the definition of $F^{\prime}$, we know that under the assignment of values
to the variables from the statement of 3, we have $\det(F^{\prime})\neq 0$.
Since as a polynomial

$\det(F^{\prime})=P/\left(\det(I-Z)\right)^{\tilde{\nu}},$ (29)

it must be the case that $P$ is a nonzero polynomial (because if $P$ was the
zero polynomial, then $\det(F^{\prime})$ would evaluate to zero under every
possible assignment).

By Lemma B.1, with probability at least $1-1/n^{3}$, the determinant
$\det(I-Z)\neq 0$ will be nonzero under a uniform random assignment to the
$z_{uv}$ variables. Assuming this event occurs, by the Schwartz-Zippel Lemma
(Proposition 2.5), a uniform random evaluation to the variables will
additionally have $P\neq 0$ with probability at least

$1-(2\tilde{\nu}n)/p\geq 1-1/n^{3}$

by setting $p\geq 2n^{5}$.

So by union bound, a uniform random assignment of values from $\mathbb{F}_{p}$
to the $z_{uv}$ variables will make $P$ and $\det(I-Z)$ nonzero simultaneously
with probability at least $1-2/n^{3}$.

If this happens, by Equation 29, we have $\det(F^{\prime})\neq 0$. This means
a particular $\tilde{\nu}\times\tilde{\nu}$ submatrix of
$F[\ast,V_{\textup{in}}(t)]$ will be full rank with the claimed probability,
which proves the desired result.

With these lemmas established, we can immediately prove the main result of
this section.

######  Proof B.7 (Proof of Proposition 6.1).

Fix a pair of distinct vertices $(s,t)$.

Substituting the definition of $H_{s}$ into Equation 25 implies that

$F[\ast,V_{\textup{in}}[t]]=(I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}[t]].$

By union bound over Lemmas B.3 and B.5, we see that

$\operatorname{rank}\leavevmode\nobreak\
(I-K)^{-1}[V_{\textup{out}}[s],V_{\textup{in}}[t]]=\operatorname{rank}F[\ast,V_{\textup{in}}[t]]=\begin{cases}\nu(s,t)+1&\text{if
}(s,t)\text{ is an edge}\\\ \nu(s,t)&\text{otherwise}\end{cases}$

with probability at least $1-3/n^{3}$.