# Parameterizing the Permanent:
Hardness for $K_{8}$-minor-free graphs

Radu Curticapean Mingji Xia IT University of Copenhagen and Basic Algorithms
Research Copenhagen (BARC), Copenhagen, Denmark. BARC is supported by Villum
Foundation Grant No. 16582.State Key Laboratory of Computer Science, Institute
of Software, Chinese Academy of Sciences, University of Chinese Academy of
Sciences, Beijing, China. Supported by NSFC 61932002.

###### Abstract

In the 1960s, statistical physicists discovered a fascinating algorithm for
counting perfect matchings in _planar_ graphs. Valiant later showed that the
same problem is $\mathsf{\\#P}$-hard for _general_ graphs. Since then, the
algorithm for planar graphs was extended to bounded-genus graphs, to graphs
excluding $K_{3,3}$ or $K_{5}$, and more generally, to any graph class
excluding a fixed minor $H$ that can be drawn in the plane with a single
crossing. This stirred up hopes that counting perfect matchings might be
polynomial-time solvable for graph classes excluding _any_ fixed minor $H$.
Alas, in this paper, we show $\mathsf{\\#P}$-hardness for $K_{8}$-minor-free
graphs by a simple and self-contained argument.

##  1 Introduction

A _perfect matching_ in a graph $G$ is an edge-subset $M\subseteq E(G)$ such
that every vertex of $G$ has exactly one incident edge in $M$. Counting
perfect matchings is a central and very well-studied problem in counting
complexity. It already starred in Valiant’s seminal paper [23] that introduced
the complexity class $\mathsf{\\#P}$, where it was shown that counting perfect
matchings is $\mathsf{\\#P}$-complete. The problem has driven progress in
approximate counting and underlies the so-called holographic algorithms [24,
6, 4, 5]. It also occurs outside of counting complexity, e.g., in statistical
physics, via the partition function of the _dimer model_ [21, 16, 17]. In
algebraic complexity theory, the matrix _permanent_ is a very well-studied
algebraic variant of the problem of counting perfect matchings [1]. Evaluating
permanents is equivalent to counting perfect matchings in bipartite graphs:
Given a bipartite input graph $G$ on $n+n$ vertices with its $n\times n$ bi-
adjacency matrix $A$, the permanent $\mathrm{per}(A)$ counts exactly the
perfect matchings in $G$.

### Algorithms for restricted graph classes

A long line of research, dating back to the 1960s, identified structural
restrictions on $G$ that facilitate the problem of counting perfect matchings.
Statistical physics gave the first examples of useful restrictions: On the
graphs $G$ of _regular lattices_ , it turns out that perfect matchings are
counted by the determinants of highly structured matrices whose eigenvalues
can be derived explicitly [21, 16]. This approach was later generalized to
arbitrary _planar graphs_ $G$: More precisely, and very surprisingly, it is
possible to flip the signs of some entries in the adjacency matrix of a planar
graph $G$ to obtain a matrix $A$ such that $\sqrt{\det(A)}$ counts the perfect
matchings in $G$ [17]. The entries to be flipped are determined by a so-called
_Pfaffian orientation_ of $G$, which can be computed in linear time for planar
graphs. Overall, a polynomial-time algorithm for counting perfect matchings in
planar graphs follows, the so-called _FKT method_(an acronym for the names of
their inventors Fisher, Kasteleyn, and Temperley).

Little [18] and Vazirani [26] later generalized the FKT method from planar
graphs to the more general class of graphs excluding $K_{3,3}$ as a minor.
Such graphs can be obtained inductively by “gluing together” planar graphs and
$K_{5}$. Little showed that $K_{3,3}$-free graphs still admit a Pfaffian
orientation by combining Pfaffian orientations of the individual parts, and
Vazirani later obtained a polynomial-time and poly-logarithmic space algorithm
for finding such an orientation.

Still working with Pfaffian orientations, it was shown by Gallucio and Loebl
[14] and Tesler [22] that perfect matchings can be counted in time
$4^{g}n^{O(1)}$ for graphs $G$ that are embedded on a surface of genus $g$. In
other words, the problem is fixed-parameter tractable in the parameter $g$.
These algorithms use Pfaffian orientations to express the number of perfect
matchings in $G$ as a linear combination of $4^{g}$ determinants. A simplified
algorithm by the authors [11] bypasses the explicit use of Pfaffian
orientations and instead reduces in a black-box manner to $4^{g}$ instances of
counting perfect matchings in planar graphs.

The mold of Pfaffian orientations was broken by Straub, Thierauf and Wagner
[20], and Curticapean [7], who independently designed polynomial-time
algorithms for counting perfect matchings in graphs excluding a $K_{5}$-minor.
As such graphs do not necessarily admit Pfaffian orientations, a different
algorithmic approach was needed: In hindsight, the new algorithms transferred
the protrusion replacement technique from parameterized complexity [2] into
the counting setting.

Moreover, a standard dynamic programming approach shows that counting perfect
matchings is fixed-parameter tractable in graphs of bounded tree-width $t$.
This can be improved to $2^{t}n^{O(1)}$ time [25], where the base $2$ is
optimal under the strong exponential-time hypothesis [10].

### Towards excluding general fixed minors

We observe that any tractable graph class listed above excludes some fixed
minor $H$. That is, starting from a graph $G$ in the class, it is not possible
to obtain $H$ by deleting edges/vertices and contracting edges. For example,
planar graphs exclude $K_{3,3}$ and $K_{5}$, bounded-genus graphs exclude
sufficiently large complete graphs, and bounded-treewidth graphs even exclude
large grids. It is therefore natural to ask whether we can count perfect
matchings in _any_ graph class excluding fixed minors.

On the positive side, Curticapean [7] and Eppstein and Vazirani [13] lifted
the algorithms for $K_{3.3}$-minor-free and $K_{5}$-minor-free graphs to
$H$-minor-free graphs for any graph $H$ that can be drawn in the plane with a
single crossing, for example, $H=K_{3,3}$ and $H=K_{5}$. (Note that excluding
single-crossing minors $H$ yields different graph classes than the class of
single-crossing graphs themselves, for which an immediate reduction to the FKT
method is possible.) In fact, these algorithms run in fixed-parameter
tractable time $f(k)n^{O(1)}$ for some function $f$ depending only on the size
$k$ of an excluded single-crossing minor. Note that the exponent of $n$ does
not grow with $k$.

On the negative side, parameterized complexity rules out such fixed-parameter
tractable algorithms for counting perfect matchings in _$k$ -apex graphs_
[11]; these are the graphs that are planar up to deleting $k$ vertices. More
precisely, it was previously shown by the authors that counting perfect
matchings is $\mathsf{\\#W[1]}$-hard on $k$-apex graphs, suggesting that
algorithms for this problem require $n^{g(k)}$ time for $g\in\omega(1)$. As
$k$-apex graphs exclude $K_{k+5}$-minors, algorithms for counting perfect
matchings in $K_{t}$-free graphs in turn require $n^{g(t)}$ time for
$g\in\omega(1)$. It could however still be possible that, for any fixed
$t\in\mathbb{N}$, some polynomial-time algorithm counts perfect matchings in
$K_{t}$-free graphs, with an exponent depending on $t$.

In fact, such algorithms seemed within close reach: Robertson and Seymour’s
graph structure theorem [19] shows that graphs $G$ excluding a fixed $H$-minor
can be obtained as clique-sums of particular graphs that are near-embeddable
on surfaces of fixed genus. Very roughly speaking, this means that $G$ is
glued together from certain pieces, similar to graphs excluding $K_{3,3}$ or
$K_{5}$ but with some “upgrades”. These upgrades involve raising the _genus_
in the decomposition pieces (from $0$ to some constant depending on $H$),
adding a constant number of _apex_ vertices (vertices that can connect
arbitrarily to the remainder of the piece), and adding a constant number of
_vortices_ (graphs of bounded path-width that are aligned with the boundary of
a face).

Counting perfect matchings supports most of these upgrades: The problem is
fixed-parameter tractable in bounded-genus graphs, while apex vertices can be
handled by brute-force in $n^{O(1)}$ time, and the gluing operation can be
handled as in the simpler case of excluded single-crossing minors. Therefore,
it only remains to handle vortices. However, even a minimal example of
vortices was unresolved: We say that a _ring blowup_ is a graph obtained from
a drawing of a planar graph by cloning each vertex on the outer face into two
copies, as shown in the left part of Figure 1. In the terminology of the graph
structure theorem, ring blowups are certain planar graphs with a single
vortex. Progress towards polynomial-time algorithms for counting perfect
matchings in $H$-minor-free graphs was halted because such algorithms were not
even known for ring blowups.

### Our results

$u$
---
$u^{1}$
---
$u^{2}$
---
$v$
---
$v^{2}$
---
$v^{1}$
---
Figure 1: A ring blowup.

We show that counting perfect matchings remains $\mathsf{\\#P}$-hard in ring
blowups. Known general results in graph minor theory [15] then already imply
the existence of a graph $H$ such that counting perfect matchings is
$\mathsf{\\#P}$-hard in $H$-minor-free graphs. The particularly simple
structure of ring blowups however allows us to exclude $K_{8}$-minors from
them in a self-contained way. (Note that ring blowups _can_ contain
$K_{7}$-minors, as Figure 5 shows.) We then obtain our main theorem:

######  Theorem 1.

Counting perfect matchings is $\mathsf{\\#P}$-hard in graphs excluding
$K_{8}$-minors.

A weaker version of this theorem was previously announced in a survey on
parameterized counting [9]. To prove Theorem 1, we reduce from the
$\mathsf{\\#P}$-hard problem of counting perfect matchings in a graph $G$. Our
reduction hinges upon a particular _sign-crossing gadget_ (see Figure 2) that
can be used to remove crossings at the cost of disrupting the perfect matching
count: After inserting a sign-crossing gadget between crossing edges $e,f\in
E(G)$, perfect matchings that contain _both_ $e$ and $f$ are counted with a
factor $-1$, and only perfect matchings containing _at most one_ of $e$ or $f$
are counted properly. Such sign-crossing gadgets were previously used in the
theory of matchgates [3] and in the hardness proof for counting perfect
matchings in $k$-apex graphs [11]. In our proof, sign-crossings are used to
transform $G$ into a ring blowup while preserving the perfect matching count.
By a surprisingly simple construction, we can ensure that sign-crossings come
in equivalent pairs, so that any $-1$ factors introduced by sign-crossings
cancel via $(-1)^{2}=1$.

##  2 Preliminaries

To give a self-contained proof of Theorem 1, we first state some preliminaries
from counting complexity and graph minor theory. Graphs will be undirected and
may be edge-weighted; we implicitly consider $w:E(G)\to\mathbb{Q}$ to be the
weight function. Given a vertex $v\in V(G)$, we write $I(v)$ for the set of
edges incident with $v$. Furthermore, given a set $S\subseteq V(G)$, we write
$G[S]$ for the subgraph of $G$ induced by $S$.

###  2.1 Counting perfect matchings and gadgets

We define counting problems as functions
$\mathrm{\\#A}:\\{0,1\\}^{*}\to\mathbb{Q}$, where inputs (graphs, formulas,
numbers) are implicitly encoded as bitstrings. For example, $\mathrm{\\#SAT}$
asks to count the satisfying assignments to Boolean formulas. Likewise, when
given as input a graph with edge-weights from a constant-sized111The
assumption of $|W|=\mathcal{O}(1)$ ensures that $\\#\mathrm{PerfMatch}(G)$ can
be represented with polynomially many bits. set $W\subseteq\mathbb{Q}$, the
problem $\\#\mathrm{PerfMatch}$ asks to determine the quantity

$\\#\mathrm{PerfMatch}(G)=\sum_{\begin{subarray}{c}M\subseteq
E(G)\,\mathrm{is}\,\mathrm{a}\\\
\mathrm{perfect}\,\mathrm{matching}\end{subarray}}\prod_{e\in M}w(e).$ (1)

We say that $\mathrm{\\#A}$ admits a polynomial-time Turing reduction to
$\mathrm{\\#B}$ if $\mathrm{\\#A}$ can be solved in polynomial time with an
oracle for $\mathrm{\\#B}$, and we say that $\mathrm{\\#B}$ is
$\mathsf{\\#P}$-hard if $\mathrm{\\#SAT}$ admits such a reduction to
$\mathrm{\\#B}$. Our hardness proofs are based on the following theorem:

$e$
---
$f$
---
$e_{1}$
---
$e_{2}$
---
$f_{1}$
---
$f_{2}$
---

$-1$
---

(a) The sign-crossing gadget is inserted into a crossing between edges $e,f$.
The gadget is drawn into a small disk to avoid introducing further crossings.
We call $e_{1},e_{2},f_{1},f_{2}$ the _external edges_ of the gadget.

$1$
---
$1$
---
$-1$
---
$0$
---
$1$
---
$0$
---
$\emptyset$
---
(b) The top row shows, up to symmetry in the last two cases, the possible
configurations with $0,2$ or $4$ external edges. The middle row shows the
possible extensions by matchings within the gadget. The bottom row lists the
total weighted sums of these extensions.

Figure 2: The planar sign-crossing gadget introduced by Cai and Gorenstein
[3].

######  Theorem 2 ([23, 12]).

Counting perfect matchings is $\mathsf{\\#P}$-hard, even for unweighted
$3$-regular graphs.

The problem of counting perfect matchings behaves well under insertion of
gadgets; in the context of this problem, gadgets are called _matchgates_. For
example, given a drawing of a not necessarily planar graph $G$ with a crossing
involving edges $e,f\in E(G)$, we can replace the crossing by the planar
_sign-crossing gadget_ from Cai and Gorenstein [3], as shown in Figure 2a. The
resulting graph essentially counts perfect matchings in $G$, but with a
significant twist: Any perfect matching $M\subseteq E(G)$ containing both $e$
and $f$ is weighted by an additional factor of $-1$. In other words, every
perfect matching $M$ incurs a factor

$\displaystyle\chi_{e,f}(M)$
$\displaystyle:=\begin{cases}-1&\\{e,f\\}\subseteq M,\\\
1&\text{otherwise.}\end{cases}$ (2)

Note that a “perfectly planarizing” crossing gadget that does not introduce
negative signs would render counting perfect matchings polynomial-time
solvable by reduction to the FKT method. It can even be shown unconditionally
that no such gadget exists [3].

The claimed functionality of the sign-crossing gadget follows from standard
techniques in the area of so-called Holant problems, see [24, 3, 8]. In the
following, we give a self-contained proof.

######  Lemma 3.

Let $G$ be a weighted graph that is drawn in the plane with crossing edges
$e,f\in E(G)$ of weight $1$, and let $G^{\prime}$ be obtained by inserting a
sign-crossing gadget as in Figure 2a. Then, with $\chi_{e,f}$ as in (2), we
have

$\\#\mathrm{PerfMatch}(G^{\prime})=\sum_{\begin{subarray}{c}M\subseteq
E(G)\,\mathrm{is}\,\mathrm{a}\\\
\mathrm{perfect}\,\mathrm{matching}\end{subarray}}\chi_{e,f}(M)\prod_{e\in
M}w(e).$

###### Proof.

Let $X=\\{e_{1},e_{2},f_{1},f_{2}\\}$ be the external edges of the sign-
crossing gadget $S$ inserted at $e,f$. Let $G^{\prime\prime}=G-V(S)$ be the
graph obtained from $G$ by removing all gadget vertices. For a subset
$T\subseteq X$ of external edges, write $V(T)$ for the endpoints of edges in
$T$. We observe that any perfect matching $M\subseteq E(G^{\prime})$ can be
obtained by first choosing a subset $T\subseteq X$ and afterwards extending
$T$ by _independently_ choosing perfect matchings in $S-V(T)$ and
$G^{\prime\prime}-V(T)$. It follows that

$\\#\mathrm{PerfMatch}(G^{\prime})=\sum_{T\subseteq X}\left(\prod_{e\in
T}w(e)\right)\cdot\underbrace{\\#\mathrm{PerfMatch}(S-V(T))}_{=:f(T)}\,\cdot\
\\#\mathrm{PerfMatch}(G^{\prime\prime}-V(T)).$ (3)

We observe that any set $T\subseteq X$ with $f(T)\neq 0$ has even cardinality,
as $S-V(T)$ would otherwise have an odd number of vertices, and hence, no
perfect matchings. The values of $f(T)$ for sets $T\subseteq X$ of even
cardinality are calculated in Figure 2b: Each column shows such a set $T$ in
the top row and lists the perfect matchings of $S-V(T)$ below. The value
$\\#\mathrm{PerfMatch}(S-V(T))$ is then obtained in the bottom row as the $\pm
1$-weighted count of the listed perfect matchings.

The calculations from Figure 2b show that any set $T\subseteq X$ with
$f(T)\neq 0$ is _consistent_ in the sense that it includes none/both of
$\\{e_{1},e_{2}\\}$ and none/both of $\\{f_{1},f_{2}\\}$. Given such a
consistent set $T$, define $\tilde{T}\subseteq\\{e,f\\}$ by forgetting the
subscripts in $T$: Include $e$ into $\tilde{T}$ iff
$\\{e_{1},e_{2}\\}\subseteq T$, and likewise for $f$. The term in (3)
corresponding to $T$ counts precisely those perfect matchings $M$ in $G$ with
$M\cap\\{e,f\\}=\tilde{T}$, except that $f(T)$ introduces a factor of $-1$ if
$\tilde{T}=\\{e,f\\}$. This proves the lemma. ∎

If several crossings are replaced by sign-crossing gadgets, an inductive
application of Lemma 3 shows that the factors introduced by sign-crossing
gadgets multiply. A particularly interesting situation occurs when edges are
drawn as curves rather than straight lines, as two edges $e$ and $f$ may then
cross more than once. Our corollary supports this case, which will prove very
useful in the next section.

######  Corollary 4.

Let $G$ be an unweighted graph that is drawn in the plane. Choose
$t\in\mathbb{N}$ crossings and write $e_{i},f_{i}\in E(G)$ for the edges
involved in the $i$-th crossing. Let $G^{\prime}$ be obtained by inserting a
sign-crossing gadget at each of the $t$ chosen crossings. Then we have

$\\#\mathrm{PerfMatch}(G^{\prime})=\sum_{\begin{subarray}{c}M\subseteq
E(G)\,\mathrm{is}\,\mathrm{a}\\\
\mathrm{perfect}\,\mathrm{matching}\end{subarray}}\prod_{i=1}^{t}\chi_{e_{i},f_{i}}(M).$

###  2.2 Graph minor theory

A graph $H$ is a _minor_ of $G$, written $H\preceq G$, if $H$ can be obtained
by repeated edge deletions and contractions and vertex deletions. This is
equivalent to the existence of a minor model of $H$ in $G$:

######  Definition 5.

A _minor model_ of $H$ in $G$ is a collection of pairwise disjoint branch sets
$S_{v}\subseteq V(G)$ for $v\in V(H)$ such that (i) each set $S_{v}$ for $v\in
V(H)$ induces a connected subgraph of $G$, and (ii) for every edge $uv\in
E(H)$, some edge of $G$ runs between $S_{u}$ and $S_{v}$.

For example, the colored sets in Figure 5 show minor models of $K_{7}$ in ring
blowups. The _Hadwiger number_ $\eta(G)$ of a graph $G$ is the maximum
$k\in\mathbb{N}$ with $K_{k}\preceq G$.

A plane graph is a planar graph that is given together with a concrete planar
embedding. We define a particular graph class from plane graphs by “blowing
up” their outer faces, see Figure 1.

$G$
---
$S$
---
$G^{\prime}$
---
Figure 3: A clique-sum.

######  Definition 6.

Given a plane graph $\hat{Q}$ with outer face $O$, the _blowup_ of $\hat{Q}$
is the graph obtained by successively replacing each vertex $v\in O$ by two
clones $v^{1},v^{2}$ having the same neighborhood as $v$, and then adding the
edge $v^{1}v^{2}$. We call $v^{1}$ and $v^{2}$ _blowup vertices_. A _ring
blowup_ is any subgraph of the blowup $Q$ of a plane graph $\hat{Q}$. We also
call $\hat{Q}$ a _reduct_ of $Q$.

The notion of clique-sums will feature prominently in Section 4.

######  Definition 7.

Let $G$ and $G^{\prime}$ be two graphs that share a common vertex-set
$S=V(G)\cap V(G^{\prime})$, which is a clique in $G$ and $G^{\prime}$. A
_clique-sum_ $G\oplus_{S}G^{\prime}$ is any graph that can be obtained from
the union $G\cup G^{\prime}$ by deleting some edges with both endpoints in
$S$.

A standard separator argument bounds the Hadwiger number of clique-sums by
that of their constituents, see [15, Lemma 2.1] for a proof.

######  Fact 8.

For any graphs $G,G^{\prime}$ and any clique-sum $G\oplus_{S}G^{\prime}$ for
$S=V(G)\cap V(G^{\prime})$, we have
$\eta(G\oplus_{S}G^{\prime})\leq\max\\{\eta(G),\eta(G^{\prime})\\}$.

For a proof sketch, note that no fixed minor model of $K_{t}$ can place some
branch sets entirely within $V(G)\setminus S$ and others entirely within
$V(G^{\prime})\setminus S$. It follows that all branch sets intersect $V(G)$
or all intersect $V(G^{\prime})$. In the first case, we can delete all
vertices from $V(G^{\prime})\setminus S$ without losing edges between branch
sets, since $S$ is a clique. The second case is symmetric.

##  3 Reducing to ring blowups

In this section, we show how to transform any unweighted graph $G$ into a ring
blowup while preserving the value of $\\#\mathrm{PerfMatch}$. The main idea,
spelled out in Lemma 9 and illustrated in Figure 4, is to arrange the vertices
of $G$ on a circle and then bend the edges of $G$ to push crossings across the
perimeter of the circle, where blowups will take care of them. As an edge $e$
is bent, it will introduce new crossings with other edges $g$, but our
construction ensures that any edge $g$ crossed while bending $e$ is crossed
_exactly twice_. When we then introduce sign-crossing gadgets at these
crossings, any $-1$ factors from gadgets are guaranteed to come in pairs, so
the overall product of these factors is $1$. Hence, going from $G$ to
$G^{\prime}$, the value of $\\#\mathrm{PerfMatch}$ is preserved via Corollary
4. In Lemma 10, we then use a standard reduction in counting complexity to
remove the $-1$ weights introduced into $G^{\prime}$ by sign-crossings.

######  Lemma 9.

Let $G$ be an unweighted graph with $n$ vertices and $m$ edges. In polynomial
time, we can construct a ring blowup $G^{\prime}$ on $O(n+m^{3})$ vertices and
edge-weights $\pm 1$ such that
$\\#\mathrm{PerfMatch}(G)=\\#\mathrm{PerfMatch}(G^{\prime})$ holds and all
edges incident with blowup vertices of $G^{\prime}$ have weight $1$.

###### Proof.

As shown in Figure 4a, we first place $V(G)$ on a circle $C$ in the plane and
draw the edges of $G$ as straight lines inside of $C$. The placement is chosen
such that no three edges intersect in the same point and every ray from the
center to the perimeter of $C$ contains at most one point that is a crossing
or vertex of $G$. Both conditions can be ensured by perturbing an arbitrary
placement of $V(G)$ on $C$.

The circle divides the plane into two regions; we call the induced subgraphs
of $G$ contained in these regions (both including $C$) the _outer_ and _inner_
part of $G$. Initially, the outer part only contains $C$.

Let $s\in O(m^{2})$ be the number of crossings in our drawing of $G$ and let
$P_{1},\ldots,P_{s}\in\mathbb{R}^{2}$ be their locations. For each $i\in[s]$,
shoot a ray from the center of $C$ to $P_{i}$ and write $\ell_{i}$ for the
segment of this ray from $P_{i}$ to the perimeter of $C$. Note that distinct
rays are disjoint and contain no vertices of $G$. For $i\in[s]$ in sequence,
write $e_{i},f_{i}\in E(G)$ for the edges involved in crossing $P_{i}$, write
$m_{i}$ for the number of edges crossed by segment $\ell_{i}$ and enumerate
the crossed edges as $g_{i,1},\ldots,g_{i,m_{i}}\in E(G)$. We bend $e_{i}$ and
$f_{i}$ in a sufficiently narrow neighborhood of $\ell_{i}$ to cross $C$, as
shown in the middle part of Figure 4b. For any $j\in[m_{i}]$, this process
adds two crossings between $e_{i},g_{i,j}$ and two crossings between
$f_{i},g_{i,j}$.

(a) Initial drawing of $G$ with circle $C$ (dashed) that induces an inner part
(shaded) and outer part. The segments $\ell_{i}$ extending from crossings to
$C$ are drawn as red lines.

$G$
---
$G^{\prime}$
---
$e_{i}$
---
$f_{i}$
---
$g_{i,1}$
---
$g_{i,2}$
---
$g_{i,3}$
---
$\scriptstyle{v_{1}}$
---
$\scriptstyle{v_{2}}$
---
$\scriptstyle{v_{3}}$
---
$\scriptstyle{v_{4}}$
---
(b) Left: The $i$-th crossing, involving edges $e_{i},f_{i}$, and the edges
$g_{i,j}$ crossed by segment $\ell_{i}$. Middle: The edges $e_{i}$ and $f_{i}$
are bent towards the outer part along $\ell_{i}$. Each edge $g_{i,j}$ now
crosses each of $e_{i}$ and $f_{i}$ twice. Right: Inserting sign-crossing
gadgets and dragging the top vertices $v_{1},\ldots,v_{4}$ of outermost
crossing gadgets onto $C$. The dark ellipses show that $G^{\prime}$ is a ring
blowup.

Figure 4: How Lemma 9 moves crossings to the outer part of $G$ to obtain a
ring blowup $G^{\prime}$.

After all original crossings $P_{1},\ldots,P_{s}$ are processed, we insert a
sign-crossing gadget at each crossing in the inner part of $G$, as shown in
the right part of Figure 4b. Note that no sign-crossing gadgets are inserted
at crossings in the outer part. To simplify the subsequent argument, we drag
some vertices of the sign-crossing gadgets onto $C$, as shown in Figure 4b.
Overall, we obtain a new graph $G^{\prime}$ with edge-weights $1$ and $-1$,
and we obtain from Corollary 4 that

$\displaystyle\\#\mathrm{PerfMatch}(G^{\prime})$
$\displaystyle=\sum_{M}\prod_{i=1}^{s}\prod_{j=1}^{m_{i}}\underbrace{\chi_{e_{i},g_{i,j}}^{2}(M)}_{=1}\cdot\underbrace{\chi_{f_{i},g_{i,j}}^{2}(M)}_{=1}=\\#\mathrm{PerfMatch}(G).$
(4)

Taking inventory, while going from $G$ to $G^{\prime}$, we replaced all
crossings from the inner part with planar gadgets and added no new crossings
to the inner part, as different segments $\ell_{i},\ell_{j}$ are disjoint. Via
sign-crossings, we added $O(\sum_{i}m_{i})=O(sm)=O(m^{3})$ vertices into the
inner part, where we recall that $m_{i}$ is the number of crossings between
segment $\ell_{i}$ and the edges in $G$. Each crossing is contained in the
outer part and involves edges $v_{1}v_{3}$ and $v_{2}v_{4}$ for some
consecutive block of vertices $v_{1},\ldots,v_{4}$ on the circle $C$. The
vertex blocks of different crossings are disjoint, so we can define a reduct
of $G^{\prime}$ by identifying $v_{1}=v_{2}$ and $v_{3}=v_{4}$ in each block,
as shown in Figure 4b. Then also no edges of weight $-1$ are incident with
blowup vertices. This shows that $G^{\prime}$ is a ring blowup satisfying the
specifications of the lemma. ∎

To conclude this section, we remark that negative edge-weights can be removed
from the graphs constructed before while staying in the graph class of ring
blowups.

######  Lemma 10.

The problem $\\#\mathrm{PerfMatch}$ restricted to the graphs from Lemma 9
(that is, ring blowups with edge-weights $\pm 1$ such that edges of weight
$-1$ are not incident with blowup vertices) admits a polynomial-time Turing
reduction to $\\#\mathrm{PerfMatch}$ in unweighted ring blowups.

A standard proof of this lemma, see e.g. [8], replaces occurrences of the
weight $-1$ with an indeterminate $x$; this turns the number of perfect
matchings in an $n$-vertex graph into a polynomial $p\in\mathbb{Z}[x]$ of
degree at most $d=n/2$. This polynomial can be evaluated at non-negative
integer inputs $0,\ldots,d$ via planar gadgets, and the value $p(-1)$ can then
be recovered from $p(0),\ldots,p(d)$ via polynomial interpolation. As Lemma 9
guarantees that edges of weight $-1$ are not incident with blowup vertices,
the planar gadgets introduced in Lemma 10 can be contained within the inner
part of the resulting graphs.

Combining Theorem 2 (the $\mathsf{\\#P}$-hardness of counting perfect
matchings in $3$-regular graphs) with Lemmas 9 and 10, we immediately obtain:

######  Theorem 11.

The problem $\\#\mathrm{PerfMatch}$ is $\mathsf{\\#P}$-hard in unweighted ring
blowups.

In fact, our proof even shows that $\\#\mathrm{PerfMatch}$ is
$\mathsf{\\#P}$-hard in graphs $G$ that are obtained from plane graphs by
adding edges $v_{1}v_{3}$ and $v_{2}v_{4}$ between disjoint blocks of
consecutive vertices $v_{1},\ldots,v_{4}$ on the outer face. For the arguments
in Section 4, we will however need fully general ring blowups.

##  4 Bounding the Hadwiger number

In this section, we bound the Hadwiger number of ring blowups by $7$. First,
we show in Lemma 13 that it suffices to consider _simple ring blowups_ , that
is, blowups of plane graphs that have all but $\leq 3$ vertices on the outer
face. In Lemma 15, we iteratively remove certain _complications_ from simple
ring blowups. When this process terminates, we obtain graphs that can be
handled by trivial arguments in Lemma 16.

######  Definition 12.

A _simple ring_ is a plane graph $Q$ with outer face $O$ such that $Q-O$ is a
complete graph with $\leq 3$ vertices. We call $W=V(Q)\setminus O$ the _inner
face_ of $Q$.222Technically, this need not be a face. A _simple ring blowup_
is any subgraph of the blowup of a simple ring. (Equivalently, a graph is a
simple ring blowup if it has a simple ring as reduct.)

In the following lemma, we adapt an argument by Joret and Wood [15, Lemma 3.4]
to make ring blowups simple without decreasing their Hadwiger number. See
Figure 5 for an illustration of the process; the last drawing shows an example
of a simple ring blowup with a single vertex on the inner face. The lemma
repeatedly uses the fact that, given a minor model of a graph $H$ in another
graph $G$, contracting an edge contained a branch set canonically induces a
minor model of $H$ in the resulting graph.

(a) The initial graph $G$ with a minor model of $K_{7}$, indicated by vertex
colors. For clarity, edges contained in branch sets are also colored.

(b) Steps 1-2 removed vertices not contained in branch sets and contracted the
turquoise branch set, which contains no blowup vertices.

(c) Step 3 successively contracted all edges that run between blowup vertices
and non-blowup vertices. The result is a simple ring blowup.

Figure 5: How Lemma 13 cleans up a ring blowup while maintaining a
$K_{t}$-minor.

######  Lemma 13.

For any ring blowup $G$, there is a simple ring blowup $Q$ with
$\eta(G)\leq\eta(Q)$.

###### Proof.

We abbreviate $t=\eta(G)$. The lemma holds for $t\leq 4$, since there clearly
are simple ring blowups containing $K_{4}$-minors. We may therefore assume
$t\geq 5$ in the following.

Let $\hat{G}$ be a reduct of $G$, with outer face $O$, and let $G$ be drawn as
a blowup of $\hat{G}$. Fix a minor model $S_{1},\ldots,S_{t}\subseteq V(G)$ of
$K_{t}$ in $G$, define $G^{\prime}:=G$ and proceed as follows.

  1. 1.

Delete from $G^{\prime}$ all vertices not contained in $S_{1}\cup\ldots\cup
S_{t}$. Then the sets $S_{1},\ldots,S_{t}$ still yield a minor model of
$K_{t}$ in the resulting graph, still called $G^{\prime}$, as no edges between
branch sets were deleted.

  2. 2.

Contract every branch set $S_{i}$ that does not contain blowup vertices. This
yields a minor model of $K_{t}$ in the resulting graph, still called
$G^{\prime}$. The $\ell\leq t$ vertices $W=\\{w_{1},\ldots,w_{\ell}\\}$
resulting from the contraction induce a planar drawing of $K_{\ell}$, so we
have $\ell\leq 4$. We may even assume $\ell=3$: Otherwise, if $\ell=4$, then
one of the vertices, say $w_{4}$, would be enclosed by the cycle on
$W\setminus\\{w_{4}\\}$ in the drawing of $G^{\prime}$. But then $w_{4}$
cannot have edges to the $t-\ell$ other branch sets, so the $t$ overall branch
sets cannot form a minor model of $K_{t}$ for $t\geq 5$.

  3. 3.

For every edge $uv$ fully contained in a branch set, where $u$ is a blowup
vertex and $v$ is not, contract $uv$ into $u$. This still yields a minor model
of $K_{t}$ in the resulting graph $G^{\prime}$.

Summing up, we see that $G^{\prime}$ contains a $K_{t}$-minor, so it suffices
to prove that $G^{\prime}$ is a simple ring blowup. Note that the $\leq 3$
vertices in $W$ form a clique in $G^{\prime}$, and all other vertices are
blowup vertices. By applying the operations used to transform $G$ into
$G^{\prime}$ on the reduct of $G$, we obtain a reduct of $G^{\prime}$ that is
a simple ring, thus proving the lemma. ∎

By removing certain structures that we call “complications”, simple ring
blowups can be simplified even further. In the following, it will be useful to
work with the reducts.

$\oplus_{\\{u,v\\}}$
---
$u$
---
$v$
---
$\oplus_{\\{w,u_{1},u_{3}\\}}$
---
$w$
---
$u_{1}$
---
$u_{2}$
---
$u_{3}$
---
$u_{4}$
---
(a)
---
(b)
---
$\hat{P}$
---
$\hat{Q}[T]$
---
$\hat{Q}[R]$
---
$\hat{Q}[L]$
---
Figure 6: This figure exemplifies complications in a simple ring $\hat{Q}$ and
illustrates the main steps in the proof of Lemma 15. The outer face of
$\hat{Q}$ is drawn as a thick line. When ignoring shading and the encircled
drawings, the figure illustrates complications of both types (marked red). The
shading and encircled drawings indicate the clique-sums arising in the proof
of Lemma 15.

######  Definition 14.

Given a simple ring $\hat{Q}$ with outer face $O$ and inner face $W$, a
_complication_ in $\hat{Q}$ is

  1. (a)

any edge between vertices $u,v\in O$ that are not consecutive in the cyclic
order of $O$, or

  2. (b)

given a vertex $w\in W$, any neighbor $o\in O$ of $w$ after its first two
neighbors in the cyclic order of $O$.

Figure 6 illustrates complications of the different types. We show in the
following lemma that it suffices to bound the Hadwiger number of the blowups
of triangulated complication-free simple rings. Here, we say that a graph is
_triangulated_ if every face but its outer face is a triangle.

######  Lemma 15.

If $\eta(Z)\leq 7$ holds for the blowup $Z$ of any triangulated and
complication-free simple ring $\hat{Z}$, then $\eta(Q)\leq 7$ holds for any
simple ring blowup $Q$.

###### Proof.

Let $\hat{Q}$ be a simple ring with complications, outer face $O$, and inner
face $W$. Let $Q$ be the blowup of $\hat{Q}$. We may assume $\hat{Q}$ to be
triangulated; this can be ensured by adding edges, which does not decrease
$\eta(Q)$.

The goal is to decompose $\hat{Q}$ along clique-sums into simple rings with
strictly less complications; the triangulation will be kept intact along the
way. Using Fact 8 inductively, it will therefore suffice to bound $\eta(Z)$
when $Z$ is the blowup of a triangulated and complication-free ring $\hat{Z}$.
The following notation will be useful: For vertex sets $S\subseteq
V(\hat{Q})$, let $B(S)$ be obtained by replacing each vertex $v\in S\cap O$
with $v^{1},v^{2}$.

We start by removing all type-a complications. To this end, consider a type-a
complication involving $u,v\in O$. Then there exist sets $L,R\subseteq
V(\hat{Q})$ such that $\hat{Q}$ is a clique-sum
$\hat{Q}[L]\oplus_{S}\hat{Q}[R]$, as shown in the left part of Figure 6. This
in turn means that the blowup $Q$ is a clique-sum
$Q[B(L)]\oplus_{B(S)}Q[B(R)]$. Via Fact 8, it suffices to show that $Q[B(L)]$
and $Q[B(R)]$ are $K_{8}$-minor-free. But $Q[B(L)]$ and $Q[B(R)]$ are the
blowups of $\hat{Q}[L]$ and $\hat{Q}[R]$, which are triangulated simple rings
with at least one type-a complication less. By induction, we may therefore
assume in the following that all type-a complications are processed.

Now consider a type-b complication, with $w\in W$ and consecutive neighbors
$u_{1},u_{2},u_{3}\in O$ of $w$ in the cyclic order of $O$. Note that we may
indeed assume the neighbors to be consecutive, since all type-a complications
were processed. Let us define $S=\\{w,u_{1},u_{3}\\}$ and
$T=S\cup\\{u_{2}\\}$. Then $\hat{Q}$ is a clique-sum
$\hat{P}\oplus_{S}\hat{Q}[T]$ for the simple ring $\hat{P}$ obtained from
$\hat{Q}$ by removing $u_{2}$ and adding the edge $u_{1}u_{3}$, as shown in
the right part of Figure 6. This in turn implies that $Q$ is a clique-sum
$P\oplus_{B(S)}Q[B(T)]$, where $P$ is the blowup of $\hat{P}$. We observe that
$Q[B(T)]$ has only $7$ vertices, so it suffices to exclude $K_{8}$ from $P$,
where $\hat{P}$ is a triangulated simple ring that still has no type-a
complications, and one type-b complication less. By induction, we may
therefore assume that $\hat{Q}$ has no complications at all. This proves the
lemma. ∎

Finally, an elementary case distinction allows us to handle complication-free
ring blowups.

######  Lemma 16.

For any triangulated and complication-free simple ring $\hat{Z}$ with blowup
$Z$, we have $\eta(Z)\leq 7$.

###### Proof.

Let $O$ and $W$ with $|W|\leq 3$ be the outer and inner faces of $\hat{Z}$.
Every edge $e\in E(\hat{Z})$ either has both endpoints in $W$, one endpoint in
$O$ and $W$ each, or both endpoints of $e$ lie consecutively on $O$ (since $Z$
has no type-a complications.) If $W$ is empty, then we have $|V(\hat{Z})|\leq
3$, since $Z$ is triangulated. This already implies $\eta(Z)\leq|V(Z)|\leq 6$.

If $W$ is non-empty, then any vertex $w\in W$ has $\leq 2$ neighbors in $O$,
since $\hat{Z}$ has no type-b complications. Furthermore, since $\hat{Z}$ is
triangulated, any pair of vertices in $W$ shares a neighbor in $O$, because
$\hat{Z}$ would otherwise contain a chordless cycle of length $4$. This
implies the following:

  * •

If $|W|\leq 2$, then $|O|\leq 2$ and thus $\eta(Z)\leq|V(Z)|\leq 6$.

  * •

If $|W|=3$, then $\hat{Z}$ and its blowup $Z$ are the following graphs, where
$|V(Z)|=9$ and $|E(Z)|=30$.
$\hat{Z}$
---
$Z$
---

To obtain a $K_{8}$-minor from $Z$, one vertex must be deleted or one edge
must be contracted. Deleting a vertex removes at least $6$ edges. Contracting
an edge reduces the number of edges by least $3$, since every edge in $Z$ is
contained in some $K_{4}$-subgraph (shown above as colored blobs) and
contracting an edge of $K_{4}$ yields a $K_{3}$, thus losing $3$ edges. It
follows that any $8$-vertex minor of $Z$ has at most $27<|E(K_{8})|$ edges and
therefore cannot be $K_{8}$.

This covers all cases for $|W|$, thus proving the lemma. ∎

The proof of Theorem 1 is now immediate.

###### Proof of Theorem 1.

By Theorem 11, the problem $\\#\mathrm{PerfMatch}$ is $\mathsf{\\#P}$-hard in
unweighted ring blowups $G$. It remains to show that $G$ excludes
$K_{8}$-minors. By Lemma 13, we have $\eta(G)\leq\eta(Q)$ for some simple ring
blowup $Q$. By Lemma 15, we have $\eta(Q)\leq 7$ if $\eta(Z)\leq 7$ holds for
all blowups of triangulated and complication-free ring graphs $\hat{Z}$, which
in turn is true by Lemma 16. ∎

##  5 Conclusion and outlook

We showed that the FKT method for planar graphs cannot be extended to graphs
excluding arbitrary fixed minors. However, our work leaves open an exhaustive
classification of the minors whose exclusion renders $\\#\mathrm{PerfMatch}$
polynomial-time solvable. This is not an artifact of our analysis: As Figure 5
shows, the graphs constructed by our reduction _can_ contain $K_{7}$-minors,
so our reduction inherently fails to address the open case of $K_{7}$-minor-
free $\\#\mathrm{PerfMatch}$. This prompts the obvious question:

######  Question 17.

What is the complexity of $\\#\mathrm{PerfMatch}$ in graphs excluding $K_{6}$
or $K_{7}$? More generally, given any fixed graph $H$, what is the complexity
of $H$-minor-free $\\#\mathrm{PerfMatch}$?

Turning towards a bigger picture, it is also interesting to investigate which
other counting problems benefit from excluded minors. This can be studied
systematically in the framework of _Holant problems_ , of which counting
perfect matchings constitutes a representative example.

In a future version of this paper, we rule out $\exp(o(\sqrt{n}))$ time
algorithms for $\\#\mathrm{PerfMatch}$ with edge-weights $\pm 1$ under the
exponential-time hypothesis. This lower bound introduces various complications
that we eschewed here in favor of a self-contained and simple presentation.
Note that graphs excluding fixed minors have tree-width $O(\sqrt{n})$, and
therefore standard algorithms for counting perfect matchings in graphs of
bounded tree-width yield matching $\exp(O(\sqrt{n}))$ time upper bounds on
$H$-minor-free graphs.

## References

  * [1] Manindra Agrawal.  Determinant versus permanent.  In Proceedings of the 25th International Congress of Mathematicians, ICM 2006, volume 3, pages 985–997, 2006.
  * [2] Hans L. Bodlaender, Fedor V. Fomin, Daniel Lokshtanov, Eelko Penninkx, Saket Saurabh, and Dimitrios M. Thilikos.  (meta) kernelization.  In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA, pages 629–638. IEEE Computer Society, 2009.
  * [3] Jin-Yi Cai and Aaron Gorenstein.  Matchgates revisited.  Theory of Computing, 10:167–197, 2014.
  * [4] Jin-Yi Cai and Pinyan Lu.  Holographic algorithms: From art to science.  In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, STOC ’07, pages 401–410, New York, NY, USA, 2007. ACM.
  * [5] Jin-Yi Cai, Pinyan Lu, and Mingji Xia.  Holographic algorithms by Fibonacci gates and holographic reductions for hardness.  In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 644–653. IEEE Computer Society, 2008\.
  * [6] Jin-Yi Cai, Pinyan Lu, and Mingji Xia.  Holographic algorithms with matchgates capture precisely tractable planar #CSP.  CoRR, abs/1008.0683, 2010.  Also appeared in FOCS 2010.
  * [7] Radu Curticapean.  Counting perfect matchings in graphs that exclude a single-crossing minor.  CoRR, abs/1406.4056, 2014.
  * [8] Radu Curticapean.  The simple, little and slow things count: on parameterized counting complexity.  PhD thesis, Saarland University, 2015.
  * [9] Radu Curticapean.  Counting problems in parameterized complexity.  In Christophe Paul and Michal Pilipczuk, editors, 13th International Symposium on Parameterized and Exact Computation, IPEC 2018, August 20-24, 2018, Helsinki, Finland, volume 115 of LIPIcs, pages 1:1–1:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [10] Radu Curticapean and Dániel Marx.  Tight conditional lower bounds for counting perfect matchings on graphs of bounded treewidth, cliquewidth, and genus.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1650–1669. SIAM, 2016.
  * [11] Radu Curticapean and Mingji Xia.  Parameterizing the permanent: Genus, apices, minors, evaluation mod 2k.  In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 994–1009. IEEE Computer Society, 2015.
  * [12] Paul Dagum and Michael Luby.  Approximating the permanent of graphs with large factors.  Theor. Comput. Sci., 102(2):283–305, 1992.
  * [13] David Eppstein and Vijay V. Vazirani.  NC algorithms for computing a perfect matching, the number of perfect matchings, and a maximum flow in one-crossing-minor-free graphs.  In Christian Scheideler and Petra Berenbrink, editors, The 31st ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2019, Phoenix, AZ, USA, June 22-24, 2019, pages 23–30. ACM, 2019.
  * [14] Anna Galluccio and Martin Loebl.  On the theory of Pfaffian orientations. I. Perfect matchings and permanents.  Electronic Journal of Combinatorics, 6, 1998.
  * [15] Gwenaël Joret and David R. Wood.  Complete graph minors and the graph minor structure theorem.  Journal of Combinatorial Theory, Series B, 103(1):61–74, 2013.
  * [16] Pieter W. Kasteleyn.  The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice.  Physica, 27(12):1209 – 1225, 1961.
  * [17] Pieter W. Kasteleyn.  Graph Theory and Crystal Physics.  In Graph Theory and Theoretical Physics, pages 43–110. Academic Press, 1967.
  * [18] Charles Little.  An extension of Kasteleyn’s method of enumerating the 1-factors of planar graphs.  In Combinatorial Mathematics, LNCS, pages 63–72. 1974.
  * [19] Neil Robertson and Paul D. Seymour.  Graph minors. XVI. excluding a non-planar graph.  J. Comb. Theory, Ser. B, 89(1):43–76, 2003.
  * [20] Simon Straub, Thomas Thierauf, and Fabian Wagner.  Counting the number of perfect matchings in ${K}_{5}$-free graphs.  In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 66–77, 2014.
  * [21] H. N. V. Temperley and Michael E. Fisher.  Dimer problem in statistical mechanics - an exact result.  Philosophical Magazine, 6(68):1478–6435, 1961.
  * [22] Glenn Tesler.  Matchings in graphs on non-orientable surfaces.  J. Comb. Theory, Ser. B, 78(2):198–231, 2000.
  * [23] Leslie G. Valiant.  The complexity of computing the permanent.  Theor. Comput. Sci., 8:189–201, 1979.
  * [24] Leslie G. Valiant.  Holographic algorithms.  SIAM J. Comput., 37(5):1565–1594, 2008.
  * [25] Johan M. M. van Rooij, Hans L. Bodlaender, and Peter Rossmanith.  Dynamic programming on tree decompositions using generalised fast subset convolution.  In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009\. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 566–577. Springer, 2009.
  * [26] Vijay V. Vazirani.  NC algorithms for computing the number of perfect matchings in ${K}_{3,3}$-free graphs and related problems.  Inf. Comput., 80(2):152–164, 1989.


# A Note on Dynamic Bidirected Dyck-Reachability with Cycles

Qirun Zhang  School of Computer Science, Georgia Institute of Technology

###### Abstract

Recently, Li et al. (2022) presented a dynamic Dyck-reachability algorithm for
bidirected graphs. The basic idea is based on updating edge weights in a data
structure called the _merged graph_ $G_{m}$. As noted in Krishna et al.
(2023), the edge deletion procedure described in the algorithm of Li et al.
(2022) cannot properly update the weights in the presence of cycles in
$G_{m}$. This note discusses the cycle case and the time complexity.

##  1 Merged Graph $G_{m}$

$w$$u$$v$$(_{1}$$(_{1}$ (a) Input bidirected graph $G$. Note that for each
open-parenthesis-labeled edge $u\xrightarrow{(_{i}}v$, there exists a close-
parenthesis-labeled edge $v\xrightarrow{)_{i}}u$, and vice versa. We omit
close-parenthesis-labeled edges for brevity.

$w$$uv$$(_{1}$ (b) Merged graph $G_{m}$ used in bidirected Dyck-reachability
algorithms.

$w$$uv$$(_{1},2$ (c) Weighted merged graph $G_{m}$ used in Li et al. (2022)’s
dynamic bidirected Dyck-reachability algorithm.

Figure 1: Bidirected Dyck-reachability.

The algorithm proposed by Li et al. (2022) utilizes a core data structure
called the merged graph $G_{m}$. This data structure realizes the equivalence
relation for bidirected Dyck-reachability (Zhang et al., 2013; Chatterjee et
al., 2018). Consider an input (bidirected) graph $G$, if two nodes $u$ and $v$
in $G$ are Dyck-reachable, we can merge them and obtain a more compact graph
representation $G_{m}$. Each node in $G_{m}$ represents a set of Dyck-
reachable nodes in $G$, and each edge represents the corresponding merged
edges in $G$. Consider the example in Figure 1. Figure 1(a) gives the input
bidirected graph, and Figure 1(b) gives the corresponding merged graph
$G_{m}$. In this example, nodes $u$ and $v$ are Dyck-reachable in $G$, and
they are represented by the same representative node $uv$ in $G_{m}$.

##  2 Cycles in Merged Graphs

Cycles may exist in the merged graph $G_{m}$. Figure 2 gives such an example.
This example is a slightly modified version of Figure 10 in Krishna et al.
(2023), where the cycles have been extended.

The distinction between the acyclic case (Figure 1) and the cyclic case
(Figure 2) is that, in the acyclic case, nodes $u$ and $v$ are merged due to
an anchor node $w$. However, in the cyclic case, upon observing the merged
graph $G_{m}$ in Figure 2(b) alone, there are two anchor nodes $w$ and
$x_{1}y_{1}$, where $x_{1}y_{1}$ depends on $w$. Specifically, with reference
to the input graph in Figure 2(a), it is evident that the merging of $u$ and
$v$ is a result of node $w$. The merging of nodes $x_{1}$ and $y_{1}$ is due
to $w$ as well, which subsequently leads to the potential merging of $n$ and
$v$ where they have already been merged. Therefore, the merging of $u$ and $v$
does not depend on the merging of $x_{1}$ and $y_{1}$. In the merged graph
$G_{m}$ in Figure 2(b), we can see that the nodes $x_{1}y_{1}$ and $uv$ are in
a cycle. Consequently, it appears that the merged node $x_{1}y_{1}$ is
responsible for the merging of $u$ and $v$.

$w$$u$$x_{1}$$x_{2}$$v$$y_{1}$$y_{2}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$
(a) Input bidirected graph. We omit all close-parenthesis-labeled edges for
brevity.

$w$$uv$$x_{1}y_{1}$$x_{2}y_{2}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$ (b) Merged graph
$G_{m}$ used in bidirected Dyck-reachability algorithms.

$w$$uv$$x_{1}y_{1}$$x_{2}y_{2}$$(_{1},2$$(_{1},2$$(_{1},2$$(_{1},2$ (c)
Weighted merged graph used in Li et al. (2022)’s dynamic bidirected Dyck-
reachability algorithm.

Figure 2: Bidirected Dyck-reachability with cycles.

##  3 Dynamic Bidirected Dyck-Reachability Algorithm

The dynamic algorithm proposed by Li et al. (2022) relies on the merged graph
$G_{m}$. The high-level idea is to assign weights to each edge in $G_{m}$
based on the number of merged edges in the original graph $G$. In Figures 1(c)
and 2(c), we can see examples of weighted merged graphs, where each edge
represents two merged edges from the corresponding input graphs in Figures
1(a) and 2(a), respectively. Upon insertion or deletion of an edge, the
weights are updated accordingly. If the weight of an outgoing edge from a
representative node $n^{\prime}$ in $G_{m}$ changes to $1$, it means that the
input graph nodes represented by $n^{\prime}$ may no longer be Dyck-reachable
in $G$. In such cases, we need to potentially split the representative node
$n^{\prime}$. This approach works well when $G_{m}$ is acyclic.

If the merged graph $G_{m}$ contains cycles, it becomes challenging to track
the anchor nodes. For example, in the weighted merged graph $G_{m}$ shown in
Figure 2(c), nodes $w$ and $x_{1}y_{1}$ appear to be the anchor nodes that
create the representative node $uv$ in $G_{m}$ based solely on their weights.
As a result, they become indistinguishable. However, according to the
discussion in Section 2, node $uv$ is created before the creation of
$x_{1}y_{1}$ ,and node $x_{1}y_{1}$ actually depends on $w$.

Now, consider the removal of the edge $v\xrightarrow{(_{1}}w$ in Figure 2(a).
Figure 3(a) depicts the input graph after the edge removal. As noted in
Krishna et al. (2023), after removing this edge in $G$, the deletion algorithm
given in Li et al. (2022) cannot properly split the node $uv$ because it is
still connected to a spurious anchor node $x_{1}y_{1}$ in $G_{m}$ (Figure
3(b)). The root cause of this problem is that the weight condition (Definition
4.2) given in Li et al. (2022) only holds when a merging node $x$ in $G_{m}$
is formed after the formation of its corresponding anchor node $y$, meaning
that $x$ depends on $y$. In the presence of cycles, as illustrated in Figure
2(b), nodes $uv$ and $x_{1}y_{1}$ are merged simultaneously, indicating that
they are mutually dependent and both nodes depend on $w$.

The dynamic algorithm (Algorithm 1) in Li et al. (2022) should be extended to
handle cycles. The insertion algorithm remains the same. For edge deletion, we
should apply the following steps. Assume the removal of an edge
$e=u\xrightarrow{(_{i}}v$ in $G$.

  1. (i):

_Tracking cycles._ Perform a DFS from the representative node resp_node(u) in
$G_{m}$ by traversing only the incoming edges. Then, collect all nodes
involved in a cycle and store them in a set $N_{c}$.

  2. (ii):

_Splitting nodes._ If $N_{c}==\emptyset$, call the original DynamicDeletion
procedure (_i.e._ , Algorithm 3 in Li et al. (2022)). Otherwise, for each
$n\in N_{c}$, split $n$ in the merged graph $G_{m}$, and run Opt-Dyck’
(Chatterjee et al., 2018; Li et al., 2022) on $G_{m}$.

$w$$u$$x_{1}$$x_{2}$$v$$y_{1}$$y_{2}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$$(_{1}$
(a) Bidirected graph after removing $v\xrightarrow{(_{1}}w$.

$w$$uv$$x_{1}y_{1}$$x_{2}y_{2}$$(_{1},1$$(_{1},2$$(_{1},2$$(_{1},2$ (b)
Weighted merged graph $G_{m}$ computed by DynamicDeletion in Li et al. (2022).

$w$$u$$x_{1}$$x_{2}$$v$$y_{1}$$y_{2}$$(_{1},1$$(_{1},1$$(_{1},1$$(_{1},1$$(_{1},1$$(_{1},1$$(_{1},1$
(c) Weighted merged graph $G_{m}$ computed by the extended algorithm in
Section 3.

Figure 3: Handling bidirected Dyck-reachability with cycles.

Recall the example of removing $v\xrightarrow{(_{1}}w$ in Figure 2(a). The
extended algorithm traverses the nodes in $G_{m}$ (Figure 2(b)) and creates
the set $N_{c}=\\{uv,x_{2}y_{2},x_{1}y_{1}\\}$. Then, it splits the nodes in
$N_{c}$ and generates a graph that is identical to the input graph shown in
Figure 3(a). After running the Opt-Dyck’ algorithm, we obtain the weighted
merged graph as shown in Figure 3(c).

##  4 Discussion

The extended algorithm presented in Section 3 splits all strongly-connected-
component (SCC) nodes in the merged graph $G_{m}$ and applies the optimal
static Dyck-reachability algorithm Opt-Dyck’ (Chatterjee et al., 2018; Li et
al., 2022). The correctness follows Opt-Dyck’. If the merged graph $G_{m}$
does not contain any cycles, the DynamicDeletion procedure correctly handles
edge deletions (Li et al., 2022). Among all the operations in this algorithm,
the most expensive step is the edge merging associated with node splitting,
even in the acyclic case. The worst-case complexity of the algorithm by Li et
al. (2022) is quadratic (Krishna et al., 2023). Consider lines 4-6 in the
split_further procedure (Procedure 4 in Li et al. (2022)). In the worst-case
scenario, a particular node in $G_{m}$ may have $O(n)$ outgoing edges, where
each of these edges could represent $O(n)$ original edges in the input graph
$G$. The complexity analysis of lines 12-18 in procedure split_further and
step (ii) in our extended algorithm (Section 3) is similar. Therefore, the
overall time complexity of the extended algorithm for dynamic Dyck-
reachability is $O(n^{2})$.

Handling cycles in the merged graph $G_{m}$ is nontrivial. One possible
improvement to our extended algorithm in Section 3 is to eliminate the DFS in
step (i) by dynamically maintaining the topological ordering in $G_{m}$
(Bender et al., 2016). To improve the $O(n^{2})$ time complexity, it is
crucial to effectively handle node splitting. Notably, a recent result by
Krishna et al. (2023) maintains Dyck SCCs through multiple layers of
abstractions and handles edge deletion in $O(n\cdot\alpha(n))$ time.

### Acknowledgments

We would like to thank Andreas Pavlogiannis for communicating the results, as
well as the POPL’24 organizers for their assistance.

## References

  * Bender et al. [2016] Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Robert E. Tarjan.  A new approach to incremental cycle detection and related problems.  _ACM Trans. Algorithms_ , 12(2):14:1–14:22, 2016.
  * Chatterjee et al. [2018] Krishnendu Chatterjee, Bhavya Choudhary, and Andreas Pavlogiannis.  Optimal dyck reachability for data-dependence and alias analysis.  _Proc. ACM Program. Lang._ , 2(POPL):30:1–30:30, 2018.  doi: 10.1145/3158118.  URL https://doi.org/10.1145/3158118.
  * Krishna et al. [2023] Shankaranarayanan Krishna, Aniket Lal, Andreas Pavlogiannis, and Omkar Tuppe.  On-the-fly static analysis via dynamic bidirected dyck reachability.  _CoRR_ , abs/2311.04319, 2023.  doi: 10.48550/ARXIV.2311.04319.  URL https://doi.org/10.48550/arXiv.2311.04319.
  * Li et al. [2022] Yuanbo Li, Kris Satya, and Qirun Zhang.  Efficient algorithms for dynamic bidirected dyck-reachability.  _Proc. ACM Program. Lang._ , 6(POPL):1–29, 2022.
  * Zhang et al. [2013] Qirun Zhang, Michael R. Lyu, Hao Yuan, and Zhendong Su.  Fast algorithms for dyck-cfl-reachability with applications to alias analysis.  In Hans-Juergen Boehm and Cormac Flanagan, editors, _ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, Seattle, WA, USA, June 16-19, 2013_ , pages 435–446. ACM, 2013.