# Join Sampling under Acyclic Degree Constraints and
(Cyclic) Subgraph Sampling

Ru Wang Yufei Tao
Department of Computer Science and Engineering
Chinese University of Hong Kong
{rwang21<EMAIL_ADDRESS>
###### Abstract

Given a (natural) join with an acyclic set of degree constraints (the join
itself does not need to be acyclic), we show how to draw a uniformly random
sample from the join result in $O(\mathit{polymat}/\max\\{1,\mathrm{OUT}\\})$
expected time (assuming data complexity) after a preprocessing phase of
$O(\mathrm{IN})$ expected time, where $\mathrm{IN}$, $\mathrm{OUT}$, and
$\mathit{polymat}$ are the join’s input size, output size, and polymatroid
bound, respectively. This compares favorably with the state of the art (Deng
et al. and Kim et al., both in PODS’23), which states that, in the absence of
degree constraints, a uniformly random sample can be drawn in
$\tilde{O}(\mathit{AGM}/\max\\{1,\mathrm{OUT}\\})$ expected time after a
preprocessing phase of $\tilde{O}(\mathrm{IN})$ expected time, where
$\mathit{AGM}$ is the join’s AGM bound and $\tilde{O}(.)$ hides a
$\operatorname*{polylog}(\mathrm{IN})$ factor. Our algorithm applies to every
join supported by the solutions of Deng et al. and Kim et al. Furthermore,
since the polymatroid bound is at most the AGM bound, our performance
guarantees are never worse, but can be considerably better, than those of Deng
et al. and Kim et al.

We then utilize our techniques to tackle directed subgraph sampling, a problem
that has extensive database applications and bears close relevance to joins.
Let $G=(V,E)$ be a directed data graph where each vertex has an out-degree at
most $\lambda$, and let $P$ be a directed pattern graph with a constant number
of vertices. The objective is to uniformly sample an occurrence of $P$ in $G$.
The problem can be modeled as join sampling with input size
$\mathrm{IN}=\Theta(|E|)$ but, whenever $P$ contains cycles, the converted
join has cyclic degree constraints. We show that it is always possible to
throw away certain degree constraints such that (i) the remaining constraints
are acyclic and (ii) the new join has asymptotically the same polymatroid
bound $\mathit{polymat}$ as the old one. Combining this finding with our new
join sampling solution yields an algorithm to sample from the original
(cyclic) join (thereby yielding a uniformly random occurrence of $P$) in
$O(\mathit{polymat}/\max\\{1,\mathrm{OUT}\\})$ expected time after $O(|E|)$
expected-time preprocessing, where $\mathrm{OUT}$ is the number of
occurrences. We also prove similar results for undirected subgraph sampling
and demonstrate how our techniques can be significantly simplified in that
scenario. Previously, the state of the art for (undirected/directed) subgraph
sampling uses $O(|E|^{\rho^{*}}/\max\\{1,\mathrm{OUT}\\})$ time to draw a
sample (after $O(|E|)$ expected-time preprocessing) where $\rho^{*}$ is the
fractional edge cover number of $P$. Our results are more favorable because
$\mathit{polymat}$ never exceeds but can be considerably lower than
$|E|^{\rho^{*}}$.

##  1 Introduction

In relational database systems, (natural) joins are acknowledged as notably
computation-intensive, with its cost surging drastically in response to
expanding data volumes. In the current big data era, the imperative to
circumvent excessive computation increasingly overshadows the requirement for
complete join results. A myriad of applications, including machine learning
algorithms, online analytical processing, and recommendation systems, can
operate effectively with random samples. This situation has sparked research
initiatives focused on devising techniques capable of producing samples from a
join result significantly faster than executing the join in its entirety. In
the realm of graph theory, the significance of join operations is mirrored in
their intrinsic connections to subgraph listing, a classical problem that
seeks to pinpoint all the occurrences of a pattern $P$ (for instance, a
directed 3-vertex cycle) within a data graph $G$ (such as a social network
where a directed edge symbolizes a “follow” relationship). Analogous to joins,
subgraph listing demands a vast amount of computation time, which escalates
rapidly with the sizes of $G$ and $P$. Fortunately, many social network
analyses do not require the full set of occurrences of $P$, but can function
well with only samples from those occurrences. This has triggered the
development of methods that can extract samples considerably faster than
finding all the occurrences.

This paper will revisit join sampling and subgraph sampling under a unified
“degree-constrained framework”. Next, we will first describe the framework
formally in Section 1.1, review the previous results in Section 1.2, and then
overview our results in Section 1.3.

###  1.1 Problem Definitions

Join Sampling. Let $\mathbf{att}$ be a finite set, with each element called an
attribute, and $\mathbf{dom}$ be a countably infinite set, with each element
called a value. For a non-empty set $\mathcal{X}\subseteq\mathbf{att}$ of
attributes, a tuple over $X$ is a function
$\textrm{\boldmath${u}$}:\mathcal{X}\rightarrow\mathbf{dom}$. For any non-
empty subset $\mathcal{Y}\subseteq\mathcal{X}$, we define
$\textrm{\boldmath${u}$}[\mathcal{Y}]$ — the projection of ${u}$ on $Y$ — as
the tuple ${v}$ over $\mathcal{Y}$ satisfying
$\textrm{\boldmath${v}$}(Y)=\textrm{\boldmath${u}$}(Y)$ for every attribute
$Y\in\mathcal{Y}$.

A relation $R$ is a set of tuples over the same set $\mathcal{Z}$ of
attributes; we refer to $\mathcal{Z}$ as the schema of $R$ and represent it as
$\mathit{schema}(R)$. The arity of $R$ is the size of $\mathit{schema}(R)$.
For any subsets $\mathcal{X}$ and $\mathcal{Y}$ of $\mathit{schema}(R)$
satisfying $\mathcal{X}\subset\mathcal{Y}$ (note: $\mathcal{X}$ is a proper
subset of $\mathcal{Y}$), define:

$\displaystyle\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R)$ $\displaystyle=$
$\displaystyle\max_{\textrm{tuple $\textrm{\boldmath${u}$}$ over
$\mathcal{X}$}}\Big{|}\Big{\\{}\textrm{\boldmath${v}$}[\mathcal{Y}]\mid\textrm{\boldmath${v}$}\in
R,\textrm{\boldmath${v}$}[\mathcal{X}]=\textrm{\boldmath${u}$}\Big{\\}}\Big{|}.$
(1)

For an intuitive explanation, imagine grouping the tuples of $R$ by
$\mathcal{X}$ and counting, for each group, how many distinct
$\mathcal{Y}$-projections are formed by the tuples therein. Then, the value
$\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R)$ corresponds to the maximum
count of all groups. It is worth pointing out that, when
$\mathcal{X}=\emptyset$, then $\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R)$
is simply $|\Pi_{\mathcal{Y}}(R)|$ where $\Pi$ is the standard “projection”
operator in relational algebra. If in addition
$\mathcal{Y}=\mathit{schema}(R)$, then
$\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R)$ equals $|R|$.

We define a join as a set $\mathcal{Q}$ of relations (some of which may have
the same schema). Let $\mathit{schema}(\mathcal{Q})$ be the union of the
attributes of the relations in $\mathcal{Q}$, i.e.,
$\mathit{schema}(\mathcal{Q})=\bigcup_{R\in Q}\mathit{schema}(R)$. Focusing on
“data complexity”, we consider only joins where both $\mathcal{Q}$ and
$\mathit{schema}(\mathcal{Q})$ have constant sizes. The result of
$\mathcal{Q}$ is a relation over $\mathit{schema}(\mathcal{Q})$ formalized as:

$\displaystyle\mathit{join}(\mathcal{Q})=\\{\textrm{tuple
$\textrm{\boldmath${u}$}$ over $\mathit{schema}(\mathcal{Q})$}\mid\forall
R\in\mathcal{Q}:\textrm{\boldmath${u}$}[\mathit{schema}(R)]\in R\\}.$

Define $\mathrm{IN}=\sum_{R\in\mathcal{Q}}|R|$ and
$\mathrm{OUT}=|\mathit{join}(\mathcal{Q})|$. We will refer to $\mathrm{IN}$
and $\mathrm{OUT}$ as the input size and output size of $Q$, respectively.

A join sampling operation returns a tuple drawn uniformly at random from
$\mathit{join}(\mathcal{Q})$ or declares
$\mathit{join}(\mathcal{Q})=\emptyset$. All such operations must be mutually
independent. The objective of the join sampling problem is to preprocess the
input relations of $\mathcal{Q}$ into an appropriate data structure that can
be used to perform join-sampling operations repeatedly.

We study the problem in the scenario where $\mathcal{Q}$ conforms to a set DC
of degree constraints. Specifically, each degree constraint has the form
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}|\mathcal{X}})$ where $\mathcal{X}$
and $\mathcal{Y}$ are subsets of $\mathit{schema}(\mathcal{Q})$ satisfying
$\mathcal{X}\subset\mathcal{Y}$ and $N_{\mathcal{Y}|\mathcal{X}}\geq 1$ is an
integer. A relation $R\in\mathcal{Q}$ is said to guard the constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}|\mathcal{X}})$ if

$\displaystyle\text{$\mathcal{Y}\subseteq\mathit{schema}(R)$, and
$\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R)\leq
N_{\mathcal{Y}|\mathcal{X}}$}.$

The join $\mathcal{Q}$ is consistent with DC — written as
$\mathcal{Q}\models\textsf{DC}$ — if every degree constraint in DC is guarded
by at least one relation in $\mathcal{Q}$. It is safe to assume that DC does
not have two constraints
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})$ and
$(\mathcal{X}^{\prime},\mathcal{Y}^{\prime},N_{\mathcal{Y}^{\prime}\mid\mathcal{X}^{\prime}})$
with $\mathcal{X}=\mathcal{X}^{\prime}$ and
$\mathcal{Y}=\mathcal{Y}^{\prime}$; otherwise, assuming
$N_{\mathcal{Y}\mid\mathcal{X}}\leq
N_{\mathcal{Y}^{\prime}\mid\mathcal{X}^{\prime}}$, the constraint
$(\mathcal{X}^{\prime},\mathcal{Y}^{\prime},N_{\mathcal{Y}^{\prime}\mid\mathcal{X}^{\prime}})$
is redundant and can be removed from DC.

In this work, we concentrate on “acyclic” degree dependency. To formalize this
notion, let us define a constraint dependency graph $G_{\textsf{DC}}$ as
follows. This is a directed graph whose vertex set is
$\mathit{schema}(\mathcal{Q})$ (i.e., each vertex of $G_{\textsf{DC}}$ is an
attribute in $\mathit{schema}(\mathcal{Q})$). For each degree constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}|\mathcal{X}})$ such that
$\mathcal{X}\neq\emptyset$, we add a (directed) edge $(X,Y)$ to
$G_{\textsf{DC}}$ for every pair
$(X,Y)\in\mathcal{X}\times(\mathcal{Y}-\mathcal{X})$. We say that the set DC
is acyclic if $G_{\textsf{DC}}$ is an acyclic graph; otherwise, DC is cyclic.

It is important to note that each relation $R\in\mathcal{Q}$ implicitly
defines a special degree constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}|\mathcal{X}})$ where
$\mathcal{X}=\emptyset$, $\mathcal{Y}=\mathit{schema}(R)$, and
$N_{\mathcal{Y}|\mathcal{X}}=|R|$. Such a constraint — known as a cardinality
constraint — is always assumed to be present in DC. As all cardinality
constraints have $\mathcal{X}=\emptyset$, they do not affect the construction
of $G_{\textsf{DC}}$. Consequently, if DC only contains cardinality
constraints, then $G_{\textsf{DC}}$ is empty and hence trivially acyclic.
Moreover, readers should avoid the misconception that “an acyclic
$G_{\textsf{DC}}$ implies $\mathcal{Q}$ being an acyclic join”; these two
acyclicity notions are unrelated. While the definition of an acyclic join is
not needed for our discussion, readers unfamiliar with this term may refer to
[2, Chapter 6.4].

Directed Graph Sampling. We are given a data graph $G=(V,E)$ and a pattern
graph $P=(V_{P},E_{P})$, both being simple directed graphs. The pattern graph
is weakly-connected111Namely, if we ignore the edge directions, then $P$
becomes a connected undirected graph. and has a constant number of vertices. A
simple directed graph $G_{\mathit{sub}}=(V_{\mathit{sub}},E_{\mathit{sub}})$
is a subgraph of $G$ if $V_{\mathit{sub}}\subseteq V$ and
$E_{\mathit{sub}}\subseteq E$. The subgraph $G_{\mathit{sub}}$ is an
occurrence of $P$ if they are isomorphic, namely, there is a bijection
$f:V_{\mathit{sub}}\rightarrow V_{P}$ such that, for any distinct vertices
$u_{1},u_{2}\in V_{\mathit{sub}}$, there is an edge $(u_{1},u_{2})\in
E_{\mathit{sub}}$ if and only if $(f(u_{1}),f(u_{2}))$ is an edge in $E_{P}$.
We will refer to $f$ as a isomorphism bijection between $P$ and
$G_{\mathit{sub}}$.

A subgraph sampling operation returns an occurrence of $P$ in $G$ uniformly at
random or declares the absence of any occurrence. All such operations need to
be mutually independent. The objective of the subgraph sampling problem is to
preprocess $G$ into a data structure that can support every subgraph-sampling
operation efficiently. We will study the problem under a degree constraint:
every vertex in $G$ has an out-degree at most $\lambda$.

Undirected Graph Sampling. The setup of this problem is the same as the
previous problem except that (i) both the data graph $G=(V,E)$ and the pattern
graph $P=(V_{P},E_{P})$ are simple undirected graphs, with $P$ being
connected; (ii) a subgraph $G_{\mathit{sub}}$ of $G$ is an occurrence of $P$
if $G_{\mathit{sub}}$ and $P$ are isomorphic in the undirected sense: there is
a isomorphism bijection $f:V_{\mathit{sub}}\rightarrow V_{P}$ between $P$ and
$G_{\mathit{sub}}$ such that, for any distinct $u_{1},u_{2}\in
V_{\mathit{sub}}$, an edge $\\{u_{1},u_{2}\\}$ exists in $E_{\mathit{sub}}$ if
and only if $\\{f(u_{1}),f(u_{2})\\}\in E_{P}$;222We represent a directed edge
as an ordered pair and an undirected edge as a set. and (iii) the degree
constraint becomes: every vertex in $G$ has a degree at most $\lambda$.

Math Conventions. For an integer $x\geq 1$, the notation $[x]$ denotes the set
$\\{1,2,...,x\\}$; as a special case, $[0]$ represents the empty set. Every
logarithm $\log(\cdot)$ has base $2$, and function $\exp_{2}(x)$ is defined to
be $2^{x}$. We use double curly braces to represent multi-sets, e.g.,
$\\{\mskip-5.0mu\\{1,1,1,2,2,3\\}\mskip-5.0mu\\}$ is a multi-set with 6
elements.

###  1.2 Related Work

Join Computation. Any algorithm correctly answering a join query $\mathcal{Q}$
must incur $\Omega(\mathrm{OUT})$ time just to output the $\mathrm{OUT}$
tuples in $\mathit{join}(\mathcal{Q})$. Hence, finding the greatest possible
value of $\mathrm{OUT}$ is an imperative step towards unraveling the time
complexity of join evaluation. A classical result in this regard is the AGM
bound [7]. To describe this bound, let us define the schema graph of
$\mathcal{Q}$ as a multi-hypergraph $\mathcal{G}=(\mathcal{V},\mathcal{E})$
where

$\displaystyle\mathcal{V}=\mathit{schema}(\mathcal{Q})\text{, and
}\mathcal{E}=\\{\mskip-5.0mu\\{\mathit{schema}(R)\mid
R\in\mathcal{Q}\\}\mskip-5.0mu\\}.$ (2)

Note that $\mathcal{E}$ is a multi-set because the relations in $\mathcal{Q}$
may have identical schemas. A fractional edge cover of $\mathcal{G}$ is a
function $w:\mathcal{E}\rightarrow[0,1]$ such that, for any $X\in\mathcal{V}$,
it holds that $\sum_{F\in\mathcal{E}:X\in F}w(F)\geq 1$ (namely, the total
weight assigned to the hyperedges covering $X$ is at least 1). Atserias,
Grohe, and Marx [7] showed that, given any fractional edge cover, it always
holds that $\mathrm{OUT}\leq\prod_{F\in\mathcal{E}}|R_{F}|^{w(F)}$, where
$R_{F}$ is the relation in $\mathcal{Q}$ whose schema corresponds to the
hyperedge $F$. The AGM bound is defined as
$\mathit{AGM}(\mathcal{Q})=\min_{w}\prod_{F\in\mathcal{E}}|R_{F}|^{w(F)}$.

The AGM bound is tight: given any hypergraph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$ and any set of positive integers
$\\{N_{F}\mid F\in\mathcal{E}\\}$, there is always a join $\mathcal{Q}$ such
that $\mathcal{Q}$ has $\mathcal{G}$ as the schema graph, $|R_{F}|=|N_{F}|$
for each $F\in\mathcal{E}$, and the output size $\mathrm{OUT}$ is
$\Theta(\mathit{AGM}(\mathcal{Q}))$. This has motivated the development of
algorithms [5, 14, 23, 25, 21, 32, 31, 33, 34, 28, 38] that can compute
$\mathit{join}(\mathcal{Q})$ in $\tilde{O}(\mathit{AGM}(\mathcal{Q}))$ time —
where $\tilde{O}(.)$ hides a factor polylogarithmic to the input size
$\mathrm{IN}$ of $\mathcal{Q}$ — and therefore are worst-case optimal up to an
$\tilde{O}(1)$ factor.

However, the tightness of the AGM bound relies on the assumption that all the
degree constraints on $\mathcal{Q}$ are purely cardinality constraints. In
reality, general degree constraints are prevalent, and their inclusion could
dramatically decrease the maximum output size $\mathrm{OUT}$. This observation
has sparked significant interest [13, 17, 21, 22, 24, 25, 30, 36] in
establishing refined upper bounds on $\mathrm{OUT}$ tailored for more complex
degree constraints. Most notably, Khamis et al. [25] proposed the entropic
bound, which is applicable to any set DC of degree constraints and is tight in
a strong sense (see Theorem 5.5 of [36]). Unfortunately, the entropic bound is
difficult to compute because it requires solving a linear program (LP)
involving infinitely many constraints (it remains an open problem whether the
computation is decidable). Not coincidentally, no join algorithm is known to
have a running time matching the entropic bound.

To circumvent the above issue, Khamis et al. [25] introduced the polymatroid
bound as an alternative, which we represent as $\mathit{polymat}(\textsf{DC})$
because this bound is fully decided by DC (i.e., any join
$\mathcal{Q}\models\textsf{DC}$ must satisfy
$\mathrm{OUT}\leq\mathit{polymat}(\textsf{DC})$). Section 2 will discuss
$\mathit{polymat}(\textsf{DC})$ in detail; for now, it suffices to understand
that (i) the polymatroid bound, although possibly looser than the entropic
bound, never exceeds the AGM bound, and (ii) $\mathit{polymat}(\textsf{DC})$
can be computed in $O(1)$ time under data complexity. Khamis et al. [25]
proposed an algorithm named PANDA that can evaluate an arbitrary join
$\mathcal{Q}\models\textsf{DC}$ in time
$\tilde{O}(\mathit{polymat}(\textsf{DC}))$.

Interestingly, when DC is acyclic, the entropic bound is equivalent to the
polymatroid bound [30]. In this scenario, Ngo [30] presented a simple
algorithm to compute any join $\mathcal{Q}\models\textsf{DC}$ in
$O(\mathit{polymat}(\textsf{DC}))$ time, after a preprocessing of
$O(\mathrm{IN})$ expected time.

Join Sampling. For an acyclic join (not to be confused with a join having an
acyclic set of degree constraints), it is possible to sample from the join
result in constant time, after a preprocessing of $O(\mathrm{IN})$ expected
time [39]. The problem becomes more complex when dealing with an arbitrary
(cyclic) join $\mathcal{Q}$, with the latest advancements presented in two
PODS’23 papers [14, 26]. Specifically, Kim et al. [26] described how to sample
in $\tilde{O}(\mathit{AGM}(\mathcal{Q})/\max\\{1,\mathrm{OUT}\\})$ expected
time, after a preprocessing of $\tilde{O}(\mathrm{IN})$ time. Deng et al. [14]
achieved the same guarantees using different approaches, and offered a
rationale explaining why the expected sample time
$O(\mathit{AGM}(\mathcal{Q})/\mathrm{OUT})$ can no longer be significantly
improved, even when $0<\mathrm{OUT}\ll\mathit{AGM}(\mathcal{Q})$, subject to
commonly accepted conjectures. We refer readers to [3, 10, 11, 14, 26, 39] and
the references therein for other results (now superseded) on join sampling.

Subgraph Listing. Let us start by clarifying the fractional edge cover number
$\rho^{*}(P)$ of a simple undirected pattern graph $P=(V_{P},E_{P})$. Given a
fractional edge cover of $P$ (i.e., function $w:E_{P}\rightarrow[0,1]$ such
that, for any vertex $X\in V_{P}$, we have $\sum_{F\in E_{P}:X\in F}w(F)\geq
1$), define $\sum_{F\in E_{P}}w(F)$ as the total weight of $w$. The value of
$\rho^{*}(P)$ is the smallest total weight of all fractional edge covers of
$P$. Given a directed pattern graph $P$, we define its fractional edge cover
number $\rho^{*}(P)$ as the value $\rho^{*}(P^{\prime})$ of the corresponding
undirected graph $P^{\prime}$ that is obtained from $P$ by ignoring all the
edge directions.

When $P$ has a constant size, it is well-known [4, 7] that any data graph
$G=(V,E)$ can encompass $O(|E|^{\rho^{*}(P)})$ occurrences of $P$. This holds
true both when $P$ and $G$ are directed and when they are undirected. This
upper bound is tight: in both the directed and undirected scenarios, for any
integer $m$, there is a data graph $G=(V,E)$ with $|E|=m$ edges that has
$\Omega(m^{\rho^{*}(P)})$ occurrences of $P$. Thus, a subgraph listing
algorithm is considered worst-case optimal if it finishes in
$\tilde{O}(|E|^{\rho^{*}(P)})$ time.

It is well-known that directed/undirected subgraph listing can be converted to
a join $\mathcal{Q}$ on binary relations (namely, relations of arity 2). The
join $\mathcal{Q}$ has an input size of $\mathrm{IN}=\Theta(|E|)$, and its AGM
bound is $\mathit{AGM}(\mathcal{Q})=\Theta(|E|^{\rho^{*}(P)})$. All
occurrences of $P$ in $G$ can be derived from $\mathit{join}(\mathcal{Q})$ for
free. Thus, any $\tilde{O}(\mathit{AGM}(\mathcal{Q}))$-time join algorithm is
essentially worst-case optimal for subgraph listing.

Assuming $P$ and $G$ to be directed, Jayaraman et al. [19] presented
interesting enhancement over the above transformation in the scenario where
each vertex of $G$ has an out-degree at most $\lambda$. The key lies in
examining the polymatroid bound of the join $\mathcal{Q}$ derived from
subgraph listing. As will be explained in Section 4, this join $\mathcal{Q}$
has a set DC of degree constraints whose constraint dependency graph
$G_{\textsf{DC}}$ coincides with $P$. Jayaraman et al. developed an algorithm
that lists all occurrences of $\mathcal{Q}$ in $G$ in
$O(\mathit{polymat}(\textsf{DC}))$ time (after a preprocessing of
$O(\mathrm{IN})$ expected time) and confirmed that this is worst-case optimal.
Their findings are closely related to our work, and we will delve into them
further when their specifics become crucial to our discussion.

There is a substantial body of literature on bounding the cost of subgraph
listing using parameters distinct from those already mentioned. These studies
typically concentrate on specific patterns (such as paths, cycles, and
cliques) or particular graphs (for instance, those that are sparse under a
suitable metric). We refer interested readers to [1, 8, 9, 12, 15, 18, 20, 27,
29, 37] and the references therein.

Subgraph Sampling. Fichtenberger, Gao, and Peng [16] described how to sample
an occurrence of the pattern $P$ in the data graph $G$ in
$O(|E|^{\rho^{*}(P)}/\max\\{1,\mathrm{OUT}\\})$ expected time, where
$\mathrm{OUT}$ is the number of occurrences of $P$ in $G$, after a
preprocessing of $O(|E|)$ expected time. In [14], Deng et al. clarified how to
deploy an arbitrary join sampling algorithm to perform subgraph sampling;
their approach ensures the same guarantees as in [16], baring an
$\tilde{O}(1)$ factor. The methods of [16, 14] are applicable in both
undirected and directed scenarios.

###  1.3 Our Results

For any join $\mathcal{Q}$ with an acyclic set DC of degree constraints, we
will demonstrate in Section 3 how to extract a uniformly random sample from
$\mathit{join}(\mathcal{Q})$ in
$O(\mathit{polymat}(\textsf{DC})/\max\\{1,\mathrm{OUT}\\})$ expected time,
following an initial preprocessing of $O(\mathrm{IN})$ expected time. This
performance is favorable when compared to the recent results of [14, 26]
(reviewed in Section 1.2), which examined settings where DC consists only of
cardinality constraints and is therefore trivially acyclic. As
$\mathit{polymat}(\textsf{DC})$ is at most but can be substantially lower than
$\mathit{AGM}(\mathcal{Q})$, our guarantees are never worse, but can be
considerably better, than those in [14, 26].

What if DC is cyclic? An idea, proposed in [30], is to discard enough
constraints to make the remaining set $\textsf{DC}^{\prime}$ of constraints
acyclic (while ensuring $\mathcal{Q}\models\textsf{DC}^{\prime}$). Our
algorithm can then be applied to draw a sample in
$O(\mathit{polymat}(\textsf{DC}^{\prime})/\max\\{1,\mathrm{OUT}\\})$ time.
However, this can be unsatisfactory because
$\mathit{polymat}(\textsf{DC}^{\prime})$ can potentially be much larger than
$\mathit{polymat}(\textsf{DC})$.

Our next contribution is to prove that, interestingly, the issue does not
affect subgraph listing/sampling. Consider first directed subgraph listing,
defined by a pattern graph $P$ and a data graph $G$ where every vertex has an
out-degree at most $\lambda$. This problem can be converted to a join
$\mathcal{Q}$ on binary relations, which is associated with a set DC of degree
constraints such that the constraint dependency graph $G_{\textsf{DC}}$ is
exactly $P$. Consequently, whenever $P$ contains a cycle, so does
$G_{\textsf{DC}}$, making DC cyclic. Nevertheless, we will demonstrate in
Section 4 the existence of an acyclic set
$\textsf{DC}^{\prime}\subset\textsf{DC}$ ensuring
$Q\models\textsf{DC}^{\prime}$ and
$\mathit{polymat}(\textsf{DC})=\Theta(\mathit{polymat}(\textsf{DC}^{\prime}))$.
This “magical” $\textsf{DC}^{\prime}$ has an immediate implication: Ngo’s join
algorithm in [30], when applied to $Q$ and $\textsf{DC}^{\prime}$ directly,
already solves directed subgraph listing optimally in
$O(\mathit{polymat}(\textsf{DC}^{\prime}))$ $=$
$O(\mathit{polymat}(\textsf{DC}))$ time. This dramatically simplifies — in
terms of both procedure and analysis — an algorithm of Jayaraman et al. [19]
(for directed subgraph listing, reviewed in Section 1.2) that has the same
guarantees.

The same elegance extends to directed subgraph sampling: by applying our new
join sampling algorithm to $\mathcal{Q}$ and the “magical”
$\textsf{DC}^{\prime}$, we can sample an occurrence of $P$ in $G$ using
$O(\mathit{polymat}(\textsf{DC})/\max\\{1,\mathrm{OUT}\\})$ expected time,
after a preprocessing of $O(|E|)$ expected time. As
$\mathit{polymat}(\textsf{DC})$ never exceeds but can be much lower than
$\mathit{AGM}(\mathcal{Q})=\Theta(|E|^{\rho^{*}(P)})$, our result compares
favorably with the state of the art [14, 26, 16] reviewed in Section 1.2.

Undirected subgraph sampling (where both $P$ and $G$ are undirected and each
vertex in $G$ has a degree at most $\lambda$) is a special version of its
directed counterpart and can be settled by a slightly modified version of our
directed subgraph sampling algorithm. However, it is possible to do better by
harnessing the undirected nature. In Section 5, we will first solve the
polymatroid bound into a closed-form expression, which somewhat unexpectedly
exhibits a crucial relationship to a well-known graph decomposition method.
This relationship motivates a surprisingly simple algorithm for undirected
subgraph sampling that offers guarantees analogous to those in the directed
scenario.

By virtue of the power of sampling, our findings have further implications on
other fundamental problems including output-size estimation, output
permutation, and small-delay enumeration. We will elaborate on the details in
Section 6.

##  2 Preliminaries

Set Functions, Polymatroid Bounds, and Modular Bounds. Suppose that
$\mathcal{S}$ is a finite set. We refer to a function
$h:2^{\mathcal{S}}\rightarrow{}_{\geq 0}$ as a set function over
$\mathcal{S}$, where ≥0 is the set of non-negative real values. Such a
function $h$ is said to be

  * •

zero-grounded if $h(\emptyset)=0$;

  * •

monotone if $h(\mathcal{X})\leq h(\mathcal{Y})$ for all
$\mathcal{X},\mathcal{Y}$ satisfying
$\mathcal{X}\subseteq\mathcal{Y}\subseteq\mathcal{S}$;

  * •

modular if $h(\mathcal{X})=\sum_{A\in\mathcal{X}}h(\\{A\\})$ holds for any
$\mathcal{X}\subseteq\mathcal{S}$;

  * •

submodular if $h(\mathcal{X}\cup\mathcal{Y})+h(\mathcal{X}\cap\mathcal{Y})\leq
h(\mathcal{X})+h(\mathcal{Y})$ holds for any
$\mathcal{X},\mathcal{Y}\subseteq\mathcal{S}$.

Define:

$\displaystyle\textsf{M}_{\mathcal{S}}$ $\displaystyle=$ the set of modular
set functions over $\mathcal{S}$ $\displaystyle\Gamma_{\mathcal{S}}$
$\displaystyle=$ the set of set functions over $\mathcal{S}$ that are zero-
grounded, monotone, submodular

Note that every modular function must be zero-grounded and monotone. Clearly,
$\textsf{M}_{\mathcal{S}}\subseteq\Gamma_{\mathcal{S}}$.

Consider $\mathcal{C}$ to be a set of triples, each having the form
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})$ where
$X\subset\mathcal{Y}\subseteq\mathcal{S}$ and
$N_{\mathcal{Y}\mid\mathcal{X}}\geq 1$ is an integer. We will refer to
$\mathcal{C}$ as a rule collection over $\mathcal{S}$ and to each triple
therein as a rule. Intuitively, the presence of a rule collection is to
instruct us to focus only on certain restricted set functions. Formally, these
are the set functions in:

$\displaystyle\mathcal{H}_{\mathcal{C}}=\big{\\{}\text{set function $h$ over
$\mathcal{S}$}\mid h(\mathcal{Y})-h(\mathcal{X})\leq\log
N_{\mathcal{Y}\mid\mathcal{X}},\hskip
5.69054pt\forall(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\mathcal{C}\big{\\}}.$
(3)

The polymatroid bound of $\mathcal{C}$ can now be defined as

$\displaystyle\mathit{polymat}(\mathcal{C})$ $\displaystyle=$
$\displaystyle\exp_{2}\Big{(}\max_{h\in\Gamma_{\mathcal{S}}\cap\mathcal{H}_{\mathcal{C}}}h(\mathcal{S})\Big{)}.$
(4)

Recall that $\exp_{2}(x)=2^{x}$. Similarly, the modular bound of $\mathcal{C}$
is defined as

$\displaystyle\mathit{modular}(\mathcal{C})$ $\displaystyle=$
$\displaystyle\exp_{2}\Big{(}\max_{h\in\textsf{M}_{\mathcal{S}}\cap\mathcal{H}_{\mathcal{C}}}h(\mathcal{S})\Big{)}.$
(5)

Join Output Size Bounds. Let us fix a join $\mathcal{Q}$ whose schema graph is
$\mathcal{G}=(\mathcal{V},\mathcal{E})$. Suppose that $\mathcal{Q}$ is
consistent with a set DC of degree constraints, i.e.,
$\mathcal{Q}\models\textsf{DC}$. As explained in Section 1.1, we follow the
convention that each relation of $\mathcal{Q}$ implicitly inserts a
cardinality constraint (i.e., a special degree constraint) to DC. Note that
the set DC is merely a rule collection over $\mathcal{V}$. The following lemma
was established by Khamis et al. [25]:

######  Lemma 2.1 ([25]).

The output size $\mathrm{OUT}$ of $\mathcal{Q}$ is at most
$\mathit{polymat}(\textsf{DC})$, i.e., the polymatroid bound of DC (as defined
in (4)).

How about $\mathit{modular}(\textsf{DC})$, i.e., the modular bound of
$\mathcal{V}$? As $\textsf{M}_{\mathcal{V}}\subseteq\Gamma_{\mathcal{V}}$, we
have $\mathit{modular}(\textsf{DC})\leq\mathit{polymat}(\textsf{DC})$ and the
inequality can be strict in general. However, an exception arises when DC is
acyclic, as proved in [30]:

######  Lemma 2.2 ([30]).

When DC is acyclic, it always holds that
$\mathit{modular}(\textsf{DC})=\mathit{polymat}(\textsf{DC})$, namely,
$\max_{h\in\Gamma_{\mathcal{V}}\cap\mathcal{H}_{\textsf{DC}}}h(\mathcal{V})=\max_{h\in\textsf{M}_{\mathcal{V}}\cap\mathcal{H}_{\textsf{DC}}}h(\mathcal{V})$.

As a corollary, when DC is acyclic, the value of
$\mathit{modular}(\textsf{DC})$ always serves as an upper bound of
$\mathrm{OUT}$. In our technical development, we will need to analyze the set
functions $h^{*}\in\Gamma_{\mathcal{V}}$ that realize the polymatriod bound,
i.e.,
$h^{*}(\mathcal{V})=\max_{h\in\Gamma_{\mathcal{V}}\cap\mathcal{H}_{\textsf{DC}}}h(\mathcal{V})$.
A crucial advantage provided by Lemma 2.2 is that we can instead scrutinize
those set functions $h^{*}\in\textsf{M}_{\mathcal{V}}$ realizing the modular
bound, i.e.,
$h^{*}(\mathcal{V})=\max_{h\in\textsf{M}_{\mathcal{V}}\cap\mathcal{H}_{\textsf{DC}}}h(\mathcal{V})$.
Compared to their submodular counterparts, modular set functions exhibit more
regularity because every $h\in\textsf{M}_{\mathcal{V}}$ is fully determined by
its value $h(\\{A\\})$ on each individual attribute $A\in\mathcal{V}$. In
particular, for any
$h\in\textsf{M}_{\mathcal{V}}\cap\mathcal{H}_{\textsf{DC}}$, it holds true
that $h(\mathcal{Y})-h(\mathcal{X})=\sum_{A\in\mathcal{Y}-\mathcal{X}}h(A)$
for any $\mathcal{X}\subset\mathcal{Y}\subseteq\mathcal{V}$. If we associate
each $A\in\mathcal{V}$ with a variable $\nu_{A}$, then
$\max_{h\in\textsf{M}_{\mathcal{V}}\cap\mathcal{H}_{\textsf{DC}}}h(\mathcal{V})$
— hence, also
$\max_{h\in\Gamma_{\mathcal{V}}\cap\mathcal{H}_{\textsf{DC}}}h(\mathcal{V})$ —
is precisely the optimal value of the following LP:

modular LP |  | max $\sum_{A\in\mathcal{V}}\nu_{A}$ subject to
---|---|---
|  $\sum\limits_{A\in\mathcal{Y}-\mathcal{X}}\nu_{A}\leq\log N_{\mathcal{Y}\mid\mathcal{X}}$ |  |  $\forall(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}$
|  $\nu_{A}\geq 0$ |  |  $\forall A\in\mathcal{V}$

We will also need to work with the LP’s dual. Specifically, if we associate a
variable $\delta_{\mathcal{Y}\mid\mathcal{X}}$ for every degree constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}$, then
the dual LP is:

dual modular LP |  | min $\sum\limits_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}}\delta_{\mathcal{Y}\mid\mathcal{X}}\cdot\log N_{\mathcal{Y}\mid\mathcal{X}}$ subject to
---|---|---
|  $\sum\limits_{\begin{subarray}{c}(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}\\\ A\in\mathcal{Y}-\mathcal{X}\end{subarray}}\delta_{\mathcal{Y}\mid\mathcal{X}}\geq 1$ |  |  $\forall A\in\mathcal{V}$
|  $\delta_{\mathcal{Y}\mid\mathcal{X}}\geq 0$ |  |  $\forall(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}$

##  3 Join Sampling under Acyclic Degree Dependency

This section serves as a proof of our first main result:

######  Theorem 3.1.

For any join $\mathcal{Q}$ consistent with an acyclic set DC of degree
constraints, we can build in $O(\mathrm{IN})$ expected time a data structure
that supports each join sampling operation in
$O(\mathit{polymat}(\textsf{DC})/\max\\{1,\mathrm{OUT}\\})$ expected time,
where $\mathrm{IN}$ and $\mathrm{OUT}$ are the input and out sizes of
$\mathcal{Q}$, respectively, and $\mathit{polymat}(\textsf{DC})$ is the
polymatroid bound of DC.

Basic Definitions. Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be the schema
graph of $\mathcal{Q}$, and $G_{\textsf{DC}}$ be the constraint dependency
graph determined by DC. For each hyperedge $F\in\mathcal{E}$, we denote by
$R_{F}$ the relation whose schema corresponds to $F$. Recall that every
constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}$ is
guarded by at least one relation in $\mathcal{Q}$. Among them, we arbitrarily
designate one relation as the constraint’s main guard, whose schema is
represented as $F(\mathcal{X},\mathcal{Y})$ (the main guard can then be
conveniently identified as $R_{F(\mathcal{X},\mathcal{Y})}$).

Set $k=|\mathcal{V}|$. As $G_{\textsf{DC}}$ is a DAG (acyclic directed graph),
we can order its $k$ vertices (i.e., attributes) into a topological order:
$A_{1},A_{2},...,A_{k}$. For each $i\in[k]$, define
$\mathcal{V}_{i}=\\{A_{1},A_{2},...,A_{i}\\}$; specially, define
$\mathcal{V}_{0}=\emptyset$. For any $i\in[k]$, define

$\displaystyle\textsf{DC}(A_{i})$ $\displaystyle=$
$\displaystyle\\{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}\mid
A_{i}\in\mathcal{Y}-\mathcal{X}\\}$ (6)

Fix an arbitrary $i\in[k]$ and an arbitrary constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})$.
Given a tuple ${w}$ over $\mathcal{V}_{i-1}$ (note: if $i=1$, then
$\mathcal{V}_{i-1}=\emptyset$ and ${w}$ is a null tuple) and a value
$a\in\mathbf{dom}$, we define a “relative degree” for $a$ as:

$\displaystyle\mathit{reldeg}_{i,\mathcal{X},\mathcal{Y}}(\textrm{\boldmath${w}$},a)$
$\displaystyle=$
$\displaystyle\frac{\big{|}\sigma_{A_{i}=a}(\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}))\big{|}}{\big{|}\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$})\big{|}}$
(7)

where $\sigma$ and $\ltimes$ are the standard selection and semi-join
operators in relational algebra, respectively. To understand the intuition
behind
$\mathit{reldeg}_{i,\mathcal{X},\mathcal{Y}}(\textrm{\boldmath${w}$},a)$,
imagine drawing a tuple ${u}$ from
$\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$})$
uniformly at random; then
$\mathit{reldeg}_{i,\mathcal{X},\mathcal{Y}}(\textrm{\boldmath${w}$},a)$ is
the probability to see $\textrm{\boldmath${u}$}(A_{i})=a$. Given a tuple ${w}$
over $\mathcal{V}_{i-1}$ and a value $a\in\mathbf{dom}$, define

$\displaystyle\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$},a)$
$\displaystyle=$
$\displaystyle\max_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})}\mathit{reldeg}_{i,\mathcal{X},\mathcal{Y}}(\textrm{\boldmath${w}$},a)$
(8) $\displaystyle\mathit{constraint}^{*}_{i}(\textrm{\boldmath${w}$},a)$
$\displaystyle=$
$\displaystyle\operatorname*{arg\,max}_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})}\mathit{reldeg}_{i,\mathcal{X},\mathcal{Y}}(\textrm{\boldmath${w}$},a).$
(9)

Specifically, $\mathit{constraint}^{*}_{i}(\textrm{\boldmath${w}$},a)$ returns
the constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})$
satisfying the condition
$\mathit{reldeg}_{i,\mathcal{X},\mathcal{Y}}(\textrm{\boldmath${w}$},a)=\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$},a)$.
If more than one constraint meets this condition, define
$\mathit{constraint}^{*}_{i}(\textrm{\boldmath${w}$},a)$ to be an arbitrary
one among those constraints.

Henceforth, we will fix an arbitrary optimal solution
$\\{\delta_{\mathcal{Y}\mid\mathcal{X}}\mid(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}\\}$
to the dual modular LP in Section 2. Thus:

$\displaystyle\prod_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}}N_{\mathcal{Y}\mid\mathcal{X}}^{\delta_{\mathcal{Y}\mid\mathcal{X}}}$
$\displaystyle=$
$\displaystyle\exp_{2}\Big{(}\sum\limits_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}}\delta_{\mathcal{Y}\mid\mathcal{X}}\cdot\log
N_{\mathcal{Y}\mid\mathcal{X}}\Big{)}=\exp_{2}\Big{(}\max_{h\in\textsf{M}_{\mathcal{V}}\cap\mathcal{H}_{\textsf{DC}}}h(\mathcal{V})\Big{)}$
$\displaystyle(\textrm{by \eqref{eqn:modular-C}})$ $\displaystyle=$
$\displaystyle\mathit{modular}(\textsf{DC})$ $\displaystyle(\textrm{by
Lemma~{}\ref{lmm:pre-modular-equals-polym}})$ $\displaystyle=$
$\displaystyle\mathit{polymat}(\textsf{DC}).$ (10)

Finally, for any $i\in[0,k]$ and any tuple ${w}$ over $\mathcal{V}_{i}$,
define:

$\displaystyle B_{i}(\textrm{\boldmath${w}$})$ $\displaystyle=$
$\displaystyle\prod_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}}\big{(}\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$})\big{)}^{\delta_{\mathcal{Y}\mid\mathcal{X}}}.$
(11)

Two observations will be useful later:

  * •

If $i=0$, then ${w}$ is a null tuple and
$B_{0}(\text{null})=\prod_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}}(\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}))^{\delta_{\mathcal{Y}\mid\mathcal{X}}}$,
which is at most
$\prod_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}}N_{\mathcal{Y}\mid\mathcal{X}}^{\delta_{\mathcal{Y}\mid\mathcal{X}}}=\mathit{polymat}(\textsf{DC})$.

  * •

If $i=k$ and $\textrm{\boldmath${w}$}\in\mathit{join}(\mathcal{Q})$, then
$R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}$ contains
exactly one tuple for any
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}$ and
thus $B_{k}(\textrm{\boldmath${w}$})=1$.

ADC-sample
---
0. |  $A_{1},A_{2},...,A_{k}\leftarrow$ a topological order of $G_{\textsf{DC}}$
1. |  $\textrm{\boldmath${w}$}_{0}\leftarrow$ a null tuple
2. |  for $i=1$ to $k$ do
3. |  | pick a constraint $(\mathcal{X}^{\circ},\mathcal{Y}^{\circ},N_{\mathcal{Y}^{\circ}\mid\mathcal{X}^{\circ}})$ uniformly at random from $\textsf{DC}(A_{i})$
4. |  |  $\textrm{\boldmath${u}$}^{\circ}\leftarrow$ a tuple chosen uniformly at random from $\Pi_{\mathcal{Y}^{\circ}}(R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}\ltimes\textrm{\boldmath${w}$}_{i-1})$
|  | /* note: if $i=1$, then $R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}\ltimes\textrm{\boldmath${w}$}_{i-1}=R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}$ */
5. |  |  $a_{i}\leftarrow\textrm{\boldmath${u}$}^{\circ}(A_{i})$
6. |  |  if $(\mathcal{X}^{\circ},\mathcal{Y}^{\circ},N_{\mathcal{Y}^{\circ}\mid\mathcal{X}^{\circ}})\neq\mathit{constraint}^{*}_{i-1}(\textrm{\boldmath${w}$}_{i-1},a_{i})$ then declare failure
7. |  |  $\textrm{\boldmath${w}$}_{i}\leftarrow$ the tuple over $\mathcal{V}_{i}$ formed by concatenating $\textrm{\boldmath${w}$}_{i-1}$ with $a_{i}$
8. |  | declare failure with probability $1-p_{\mathrm{pass}}(i,\textrm{\boldmath${w}$}_{i-1},\textrm{\boldmath${w}$}_{i})$, where $p_{\mathrm{pass}}$ is given in (12)
9. |  if $\textrm{\boldmath${w}$}_{k}[F]\in R_{F}$ for $\forall F\in\mathcal{E}$ then /* that is, $\textrm{\boldmath${w}$}_{k}\in\mathit{join}(\mathcal{Q})$ */
10. |  |  return $\textrm{\boldmath${w}$}_{k}$
Figure 1: Our sampling algorithm

Algorithm. Our sampling algorithm, named ADC-sample, is presented in Figure 1.
At a high level, it processes one attribute at a time according to the
topological order $A_{1},A_{2},...,A_{k}$. The for-loop in Lines 2-9 finds a
value $a_{i}$ for attribute $A_{i}$ ($i\in[k]$). The algorithm may fail to
return anything, but when it succeeds (i.e., reaching Line 10), the values
$a_{1},a_{2},...,a_{k}$ will make a uniformly random tuple from
$\mathit{join}(\mathcal{Q})$.

Next, we explain the details of the for-loop. The loop starts with values
$a_{1},a_{2},...,a_{i-1}$ already stored in a tuple
$\textrm{\boldmath${w}$}_{i-1}$ (i.e.,
$\textrm{\boldmath${w}$}_{i-1}(A_{j})=a_{j}$ for all $j\in[i-1]$). Line 3
randomly chooses a degree constraint
$(\mathcal{X}^{\circ},\mathcal{Y}^{\circ},N_{\mathcal{Y}^{\circ}\mid\mathcal{X}^{\circ}})$
from $\textsf{DC}(A_{i})$; see (6). Conceptually, next we identify the main
guard $R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}$ of this constraint,
semi-join the relation with $\textrm{\boldmath${w}$}_{i-1}$, and project the
semi-join result on $\mathcal{Y}^{\circ}$ to obtain
$\Pi_{\mathcal{Y}^{\circ}}(R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}\ltimes\textrm{\boldmath${w}$}_{i-1})$.
Then, Line 4 randomly chooses a tuple $\textrm{\boldmath${u}$}^{\circ}$ from
$\Pi_{\mathcal{Y}^{\circ}}(R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}\ltimes\textrm{\boldmath${w}$}_{i-1})$
and Line 5 takes $\textrm{\boldmath${u}$}^{\circ}(A_{i})$ as the value of
$a_{i}$ (note:
$A_{i}\in\mathcal{Y}^{\circ}-\mathcal{X}^{\circ}\subseteq\mathcal{Y}^{\circ}$).
Physically, however, we do not compute
$\Pi_{\mathcal{Y}^{\circ}}(R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}\ltimes\textrm{\boldmath${w}$}_{i-1})$
during the sample process. Instead, with proper preprocessing (discussed
later), we can acquire the value $a_{i}$ in $O(1)$ time. Continuing, Line 6
may declare failure and terminate ADC-sample, but if we get past this line,
$(\mathcal{X}^{\circ},\mathcal{Y}^{\circ},N_{\mathcal{Y}^{\circ}\mid\mathcal{X}^{\circ}})$
must be exactly
$\mathit{constraint}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},a_{i})$; see (9).
As clarified later, the check at Line 6 can be performed in $O(1)$ time. We
now form a tuple $\textrm{\boldmath${w}$}_{i}$ that takes value $a_{j}$ on
attribute $A_{j}$ for each $j\in[i]$ (Line 7). Line 8 allows us to pass with
probability

$\displaystyle
p_{\mathrm{pass}}(i,\textrm{\boldmath${w}$}_{i-1},\textrm{\boldmath${w}$}_{i})$
$\displaystyle=$
$\displaystyle\frac{B_{i}(\textrm{\boldmath${w}$}_{i})}{B_{i-1}(\textrm{\boldmath${w}$}_{i-1})}\cdot\frac{1}{\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},\textrm{\boldmath${w}$}_{i}(A_{i}))}$
(12)

or otherwise terminate the algorithm by declaring failure. As proved later,
$p_{\mathrm{pass}}(i,\textrm{\boldmath${w}$}_{i-1},\textrm{\boldmath${w}$}_{i})$
cannot exceed 1 (Lemma 3.2); moreover, this value can be computed in $O(1)$
time. The overall execution time of ADC-sample is constant.

Analysis. Next we prove that the value in (12) serves as a legal probability
value.

######  Lemma 3.2.

For every $i\in[k]$, we have
$p_{\mathrm{pass}}(i,\textrm{\boldmath${w}$}_{i-1},\textrm{\boldmath${w}$}_{i})\leq
1$.

###### Proof.

Consider an arbitrary constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})$.
Recall that ADC-sample processes the attributes by the topological order
$A_{1},...,A_{k}$. In the constrained dependency graph $G_{\textsf{DC}}$,
every attribute of $\mathcal{X}$ has an out-going edge to $A_{i}$. Hence, all
the attributes in $\mathcal{X}$ must be processed prior to $A_{i}$. This
implies that all the tuples in
$R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1}$ must have
the same projection on $\mathcal{X}$. Therefore,
$\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1})$
equals
$|\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1})|$.
By the same reasoning,
$\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i})$
equals
$|\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i})|$.
We thus have:

$\displaystyle\frac{\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i})}{\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1})}$
$\displaystyle=$
$\displaystyle\frac{|\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i})|}{|\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1})|}$
(13) $\displaystyle=$
$\displaystyle\frac{\big{|}\sigma_{A_{i}=a_{i}}(\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1}))\big{|}}{\big{|}\Pi_{\mathcal{Y}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1})\big{|}}$
$\displaystyle=$
$\displaystyle\mathit{reldeg}_{i,\mathcal{X},\mathcal{Y}}(\textrm{\boldmath${w}$}_{i-1},a_{i})$
$\displaystyle\leq$
$\displaystyle\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},a_{i}).$

On the other hand, for any constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\notin\textsf{DC}(A_{i})$,
it trivially holds that

$\displaystyle\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i})$
$\displaystyle\leq$
$\displaystyle\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1})$
(14)

because $R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i}$ is
a subset of
$R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1}$.

We can now derive

$\displaystyle
p_{\mathrm{pass}}(i,\textrm{\boldmath${w}$}_{i-1},\textrm{\boldmath${w}$}_{i})$
$\displaystyle=$
$\displaystyle\frac{1}{\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},a_{i})}\prod_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}}\Big{(}\frac{\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i})}{\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1})}\Big{)}^{\delta_{\mathcal{Y}\mid\mathcal{X}}}$
$\displaystyle(\textrm{by \eqref{eqn:proof:p-pass:help2}})$
$\displaystyle\leq$
$\displaystyle\frac{1}{\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},a_{i})}\prod_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})}\Big{(}\frac{\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i})}{\mathit{deg}_{\mathcal{Y}\mid\mathcal{X}}(R_{F(\mathcal{X},\mathcal{Y})}\ltimes\textrm{\boldmath${w}$}_{i-1})}\Big{)}^{\delta_{\mathcal{Y}\mid\mathcal{X}}}$
$\displaystyle(\textrm{by \eqref{eqn:proof:p-pass:help1}})$
$\displaystyle\leq$
$\displaystyle\frac{1}{\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},a_{i})}\prod_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})}\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},a_{i})^{\delta_{\mathcal{Y}\mid\mathcal{X}}}$
$\displaystyle=$
$\displaystyle\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},a_{i})^{\big{(}\sum_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})}\delta_{\mathcal{Y}\mid\mathcal{X}}\big{)}-1}\leq
1.$

The last step used
$\sum_{(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}(A_{i})}\delta_{\mathcal{Y}\mid\mathcal{X}}\geq
1$ guaranteed by the dual modular LP. ∎

Next, we argue that every result tuple
$\textrm{\boldmath${v}$}\in\mathit{join}(\mathcal{Q})$ is returned by ADC-
sample with the same probability. For this purpose, let us define two random
events for each $i\in[k]$:

  * •

event E1$(i)$:
$(\mathcal{X}^{\circ},\mathcal{Y}^{\circ},N_{\mathcal{Y}^{\circ}\mid\mathcal{X}^{\circ}})=\mathit{constraint}^{*}_{i}(\textrm{\boldmath${w}$}_{i-1},\textrm{\boldmath${v}$}(A_{i}))$
in the $i$-th loop of ADC-sample;

  * •

event E2$(i)$: Line 8 does not declare failure in the $i$-th loop of ADC-
sample.

The probability for ADC-sample to return ${v}$ can be derived as follows.

$\displaystyle\mathbf{Pr}[\textrm{\boldmath${v}$}\text{ returned}]$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{k}\mathbf{Pr}[a_{i}=\textrm{\boldmath${v}$}(A_{i}),\text{\bf
E1}(i),\text{\bf
E2}(i)\mid\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]]$
(15) $\displaystyle(\textrm{if $i=1$, then
$\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]$
becomes $\textrm{\boldmath${w}$}_{0}=\textrm{\boldmath${v}$}[\emptyset]$,
which is vacuously true})$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{k}\Big{(}\mathbf{Pr}[a_{i}=\textrm{\boldmath${v}$}(A_{i}),\text{\bf
E1}(i)\mid\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]]\cdot$
$\displaystyle\hskip 14.22636pt\mathbf{Pr}[\text{\bf E2}(i)\mid\text{\bf
E1}(i),a_{i}=\textrm{\boldmath${v}$}(A_{i}),\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]]\Big{)}.$

Observe

$\displaystyle\mathbf{Pr}[a_{i}=\textrm{\boldmath${v}$}(A_{i}),\text{\bf
E1}(i)\mid\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]]$
(16) $\displaystyle=$ $\displaystyle\mathbf{Pr}[\text{\bf
E1}(i)\mid\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]]\cdot\mathbf{Pr}[a_{i}=\textrm{\boldmath${v}$}(A_{i})\mid\text{\bf
E1}(i),\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]]$
$\displaystyle=$
$\displaystyle\frac{1}{|\textsf{DC}(A_{i})|}\cdot\frac{\big{|}\sigma_{A_{i}=\textrm{\boldmath${v}$}(A_{i})}(\Pi_{\mathcal{Y}}(R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}\ltimes\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]))\big{|}}{\big{|}\Pi_{\mathcal{Y}}(R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}\ltimes\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}])\big{|}}$
$\displaystyle(\textrm{note:
$(\mathcal{X}^{\circ},\mathcal{Y}^{\circ},N_{\mathcal{Y}^{\circ}\mid\mathcal{X}^{\circ}})=\mathit{constraint}^{*}_{i}(\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}],\textrm{\boldmath${v}$}(A_{i}))$,
due to {\bf E1}$(i)$ and
$\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]]$})$
$\displaystyle=$
$\displaystyle\frac{1}{|\textsf{DC}(A_{i})|}\cdot\mathit{reldeg}_{i,\mathcal{X}^{\circ},\mathcal{Y}^{\circ}}(\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}],\textrm{\boldmath${v}$}(A_{i}))=\frac{1}{|\textsf{DC}(A_{i})|}\cdot\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}],\textrm{\boldmath${v}$}(A_{i})).$

On the other hand:

$\displaystyle\mathbf{Pr}[\text{\bf E2}(i)\mid\text{\bf
E1}(i),a_{i}=\textrm{\boldmath${v}$}(A_{i}),\textrm{\boldmath${w}$}_{i-1}=\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}]]$
$\displaystyle=$ $\displaystyle
p_{\mathrm{pass}}(i,\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}],\textrm{\boldmath${v}$}[\mathcal{V}_{i}])$
$\displaystyle(\textrm{by \eqref{eqn:p-pass}})$ $\displaystyle=$
$\displaystyle\frac{B_{i}(\textrm{\boldmath${v}$}[\mathcal{V}_{i}])}{B_{i-1}(\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}])}\cdot\frac{1}{\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}],\textrm{\boldmath${v}$}(A_{i}))}.$
(17)

Plugging (16) and (17) into (15) yields

$\displaystyle\mathbf{Pr}[\textrm{\boldmath${v}$}\text{ returned}]$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{k}\frac{B_{i}(\textrm{\boldmath${v}$}[\mathcal{V}_{i}])}{B_{i-1}(\textrm{\boldmath${v}$}[\mathcal{V}_{i-1}])}\cdot\frac{1}{|\textsf{DC}(A_{i})|}=\frac{B_{k}(\textrm{\boldmath${v}$}[\mathcal{V}_{k}])}{B_{0}(\textrm{\boldmath${v}$}[\mathcal{V}_{0}])}\cdot\prod_{i=1}^{k}\frac{1}{|\textsf{DC}(A_{i})|}$
$\displaystyle=$
$\displaystyle\frac{1}{B_{0}(\text{null})}\cdot\prod_{i=1}^{k}\frac{1}{|\textsf{DC}(A_{i})|}.$

As the above is identical for every
$\textrm{\boldmath${v}$}\in\mathit{join}(\mathcal{Q})$, we can conclude that
each tuple in the join result gets returned by ADC-sample with the same
probability. As an immediate corollary, each run of ADC-sample successfully
returns a sample from $\mathit{join}(\mathcal{Q})$ with probability

$\displaystyle\frac{\mathrm{OUT}}{B_{0}(\text{null})}\cdot\prod_{i=1}^{k}\frac{1}{|\textsf{DC}(A_{i})|}\geq\frac{\mathrm{OUT}}{\mathit{polymat}(\textsf{DC})}\cdot\prod_{i=1}^{k}\frac{1}{|\textsf{DC}(A_{i})|}=\Omega\Big{(}\frac{\mathrm{OUT}}{\mathit{polymat}(\textsf{DC})}\Big{)}.$

In Appendix A, we will explain how to preprocess the relations of
$\mathcal{Q}$ in $O(\mathrm{IN})$ expected time to ensure that ADC-sample
completes in $O(1)$ time.

Performing a Join Sampling Operation. Recall that this operation must either
return a uniformly random sample of $\mathit{join}(\mathcal{Q})$ or declare
$\mathit{join}(\mathcal{Q})=\emptyset$. To support this operation, we execute
two threads concurrently. The first thread repeatedly invokes ADC-sample until
it successfully returns a sample. The other thread runs Ngo’s algorithm in
[30] to compute $\mathit{join}(\mathcal{Q})$ in full, after which we can
declare $\mathit{join}(\mathcal{Q})\neq\emptyset$ or sample from
$\mathit{join}(\mathcal{Q})$ in constant time. As soon as one thread finishes,
we manually terminate the other one.

This strategy guarantees that the join operation completes in
$O(\mathit{polymat}(\textsf{DC})/\max\\{1,\mathrm{OUT}\\})$ time. To explain
why, consider first the scenario where $\mathrm{OUT}\geq 1$. In this case, we
expect to find a sample with $O(\mathit{polymat}(\textsf{DC})/\mathrm{OUT})$
repeats of ADC-sample. Hence, the first thread finishes in
$O(\mathit{polymat}(\textsf{DC})/\mathrm{OUT})$ expected sample time. On the
other hand, if $\mathrm{OUT}=0$, the second thread will finish in
$O(\mathit{polymat}(\textsf{DC}))$ time. This concludes the proof of Theorem
3.1.

Remarks. When DC has only cardinality constraints (is thus “trivially”
acyclic), ADC-sample simplifies into the sampling algorithm of Kim et al.
[26]. In retrospect, two main obstacles prevent an obvious extension of their
algorithm to an arbitrary acyclic DC. The first is identifying an appropriate
way to deal with constraints
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}$ where
$\mathcal{X}\neq\emptyset$ (such constraints are absent in the degenerated
context of [26]). The second obstacle involves determining how to benefit from
a topological order (attribute ordering is irrelevant in [26]); replacing the
order with a non-topological one may ruin the correctness of ADC-sample.

##  4 Directed Subgraph Sampling

Given a directed pattern graph $P=(V_{P},E_{P})$ and a directed data graph
$G=(V,E)$, we use $\mathit{occ}(G,P)$ to represent the set of occurrences of
$P$ in $G$. Every vertex in $G$ has an out-degree at most $\lambda$. Our goal
is to design an algorithm to sample from $\mathit{occ}(G,P)$ efficiently.

Let us formulate the “polymatroid bound” for this problem. Given an integer
$m\geq 1$, an integer $\lambda\in[1,m]$, and a pattern $P=(V_{P},E_{P})$,
first build a rule collection $\mathcal{C}$ over $V_{P}$ as follows: for each
edge $(X,Y)\in E_{P}$, add to $\mathcal{C}$ two rules:
$(\emptyset,\\{X,Y\\},m)$ and $(\\{X\\},$ $\\{X,Y\\},$ $\lambda)$. Then, the
directed polymatriod bound of $m$, $\lambda$, and $P$ can be defined as

$\displaystyle\mathit{polymat}_{\mathit{dir}}(m,\lambda,P)$ $\displaystyle=$
$\displaystyle\mathit{polymat}(\mathcal{C})$ (18)

where $\mathit{polymat}(\mathcal{C})$ follows the definition in (4).

This formulation reflects how directed subgraph listing can be processed as a
join. Consider a companion join $\mathcal{Q}$ constructed from $G$ and $P$ as
follows. The schema graph of $\mathcal{Q}$, denoted as
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, is exactly $P=(V_{P},E_{P})$ (i.e.,
$\mathcal{V}=V_{P}$ and $\mathcal{E}=E_{P}$). For every edge $F=(X,Y)\in
E_{P}$, create a relation $R_{F}\in\mathcal{Q}$ by inserting, for each edge
$(x,y)$ in the data graph $G$, a tuple ${u}$ with
$\textrm{\boldmath${u}$}(X)=x$ and $\textrm{\boldmath${u}$}(Y)=y$ into
$R_{F}$. The rule collection $\mathcal{C}$ can now be regarded as a set DC of
degree constraints with which $\mathcal{Q}$ is consistent, i.e.,
$\mathcal{Q}\models\textsf{DC}=\mathcal{C}$. The constraint dependence graph
$G_{\textsf{DC}}$ is precisely $P$. It is immediate that
$\mathit{polymat}_{\mathit{dir}}(|E|,\lambda,P)=\mathit{polymat}(\textsf{DC})$.
To find all the occurrences in $\mathit{occ}(G,P)$, it suffices to compute
$\mathit{join}(\mathcal{Q})$. Specifically, every tuple
$\textrm{\boldmath${u}$}\in\mathit{join}(\mathcal{Q})$ that uses a distinct
value on every attribute in $\mathcal{V}$ ($=V_{P}$) matches a unique
occurrence in $\mathit{occ}(G,P)$. Conversely, every occurrence in
$\mathit{occ}(G,P)$ matches the same number $c$ of tuples in
$\mathit{join}(\mathcal{Q})$, where $c\geq 1$ is a constant equal to the
number of automorphisms of $P$. If we denote
$\mathrm{OUT}=|\mathit{occ}(G,P)|$ and
$\mathrm{OUT}_{\mathcal{Q}}=|\mathit{join}(\mathcal{Q})|$, it follows that
$c\cdot\mathrm{OUT}\leq\mathrm{OUT}_{\mathcal{Q}}\leq\mathit{polymat}(\textsf{DC})=\mathit{polymat}_{\mathit{dir}}(|E|,\lambda,P)$.

The above observation suggests how directed subgraph sampling can be reduced
to join sampling. First, sample a tuple ${u}$ from
$\mathit{join}(\mathcal{Q})$ uniformly at random. Then, check whether
$\textrm{\boldmath${u}$}(A)=\textrm{\boldmath${u}$}(A^{\prime})$ for any two
distinct attributes $A,A^{\prime}\in\mathcal{V}$. If so, declare failure;
otherwise, declare success and return the unique occurrence matching the tuple
${u}$. The success probability equals
$c\cdot\mathrm{OUT}/\mathrm{OUT}_{\mathcal{Q}}$. In a success event, every
occurrence in $\mathit{occ}(G,P)$ has the same probability to be returned.

When $P$ is acyclic, so is $G_{\textsf{DC}}$, and thus our algorithm in
Theorem 3.1 can be readily applied to handle a subgraph sampling operation. To
analyze the performance, consider first $\mathrm{OUT}\geq 1$. We expect to
draw $O(\mathrm{OUT}_{\mathcal{Q}}/\mathrm{OUT})$ samples from
$\mathit{join}(\mathcal{Q})$ until a success event. As Theorem 3.1 guarantees
retrieving a sample from $\mathit{join}(\mathcal{Q})$ in
$O(\mathit{polymat}(\textsf{DC})/\mathrm{OUT}_{\mathcal{Q}})$ expected time,
overall we expect to sample an occurrence from $\mathit{occ}(G,P)$ in

$\displaystyle
O\Big{(}\frac{\mathit{polymat}(\textsf{DC})}{\mathrm{OUT}_{\mathcal{Q}}}\cdot\frac{\mathrm{OUT}_{\mathcal{Q}}}{\mathrm{OUT}}\Big{)}=O\Big{(}\frac{\mathit{polymat}(\textsf{DC})}{\mathrm{OUT}}\Big{)}$

time. To prepare for the possibility of $\mathrm{OUT}=0$, we apply the “two-
thread approach” in Section 3. We run a concurrent thread that executes Ngo’s
algorithm in [30], which finds the whole $\mathit{join}(\mathcal{Q})$, and
hence $\mathit{occ}(G,P)$, in $O(\mathit{polymat}(\textsf{DC}))$ time, after
which we can declare $\mathit{occ}(G,P)=\emptyset$ or sample from
$\mathit{occ}(G,P)$ in $O(1)$ time. By accepting whichever thread finishes
earlier, we ensure that the operation completes in
$O(\mathit{polymat}(\textsf{DC})/\max\\{1,\mathrm{OUT}\\})$ time.

The main challenge arises when $P$ is cyclic. In this case, $G_{\textsf{DC}}$
(which equals $P$) is cyclic. Thus, DC becomes a cyclic set of degree
constraints, rendering neither Theorem 3.1 nor Ngo’s algorithm in [30]
applicable. We overcome this challenge with the lemma below.

######  Lemma 4.1.

If DC is cyclic, we can always find an acyclic subset
$\textsf{DC}^{\prime}\subset\textsf{DC}$ satisfying
$\mathit{polymat}(\textsf{DC}^{\prime})=\Theta(\mathit{polymat}(\textsf{DC}))$.

The proof is presented in Appendix B. Because $\mathcal{Q}\models\textsf{DC}$
and $\textsf{DC}^{\prime}$ is a subset of DC, we know that $\mathcal{Q}$ must
be consistent with $\textsf{DC}^{\prime}$ as well, i.e.,
$\mathcal{Q}\models\textsf{DC}^{\prime}$. Therefore, our Theorem 3.1 can now
be used to extract a sample from $\mathit{join}(\mathcal{Q})$ in
$O(\mathit{polymat}_{\mathit{dir}}(\textsf{DC}^{\prime})/\max\\{1,\mathrm{OUT}_{\mathcal{Q}}\\})$
time. Importantly, Lemma 4.1 also permits us to directly apply Ngo’s algorithm
in [30] to compute $\mathit{join}(\mathcal{Q})$ in
$O(\mathit{polymat}(\textsf{DC}^{\prime}))$ time. Therefore, we can now apply
the two-thread technique to sample from $\mathit{occ}(G,P)$ in

$\displaystyle
O\Big{(}\frac{\mathit{polymat}(\textsf{DC}^{\prime})}{\max\\{1,\mathrm{OUT}\\}}\Big{)}=O\Big{(}\frac{\mathit{polymat}(\textsf{DC})}{\max\\{1,\mathrm{OUT}\\}}\Big{)}=O\Big{(}\frac{\mathit{polymat}_{\mathit{dir}}(|E|,\lambda,P)}{\max\\{1,\mathrm{OUT}\\}}\Big{)}$

time. We thus have arrived yet:

######  Theorem 4.2.

Let $G=(V,E)$ be a simple directed data graph, where each vertex has an out-
degree at most $\lambda$. Let $P=(V_{P},E_{P})$ be a simple weakly-connected
directed pattern graph with a constant number of vertices. We can build in
$O(|E|)$ expected time a data structure that supports each subgraph sampling
operation in
$O(\mathit{polymat}_{\mathit{dir}}(|E|,\lambda,P)/\max\\{1,\mathrm{OUT}\\})$
expected time, where $\mathrm{OUT}$ is the number of occurrences of $P$ in
$G$, and $\mathit{polymat}_{\mathit{dir}}(|E|,\lambda,P)$ is the directed
polymatrioid bound in (18).

Remarks. For subgraph listing, Jayaraman et al. [19] presented a sophisticated
method that also enables the application of Ngo’s algorithm in [30] to a
cyclic $P$. Given the companion join $\mathcal{Q}$, they employ the degree
uniformization technique [21] to generate $t=O(\operatorname*{polylog}|E|)$
new joins $\mathcal{Q}_{1},\mathcal{Q}_{2},...,\mathcal{Q}_{t}$ such that
$\mathit{join}(\mathcal{Q})=\bigcup_{i=1}^{t}\mathit{join}(\mathcal{Q}_{i})$.
For each $i\in[t]$, they construct an acyclic set $\textsf{DC}_{i}$ of degree
constraints (which is not always a subset of DC) with the property
$\sum_{i=1}^{t}\mathit{polymat}(\textsf{DC}_{i})\leq\mathit{polymat}(\textsf{DC})$.
Each join $\mathcal{Q}_{i}$ ($i\in[t]$) can then be processed by Ngo’s
algorithm in $O(\mathit{polymat}(\textsf{DC}_{i}))$ time, thus giving an
algorithm for computing $\mathit{join}(\mathcal{Q})$ (and hence
$\mathit{occ}(G,P)$) in $O(\mathit{polymat}(\textsf{DC}))$ time. On the other
hand, Lemma 4.1 facilitates a direct application of Ngo’s algorithm to
$\mathcal{Q}$, implying the non-necessity of degree uniformization in subgraph
listing. We believe that this simplification is noteworthy and merits its own
dedicated exposition, considering the critical nature of the subgraph listing
problem. In the absence of Lemma 4.1, integrating our join-sampling algorithm
with the methodology of [19] for the purpose of subgraph sampling would
require substantially more effort. Our proof of Lemma 4.1 does draw upon the
analysis of [19], as discussed in depth in Appendix B.

##  5 Undirected Subgraph Sampling

Given an undirected pattern graph $P=(V_{P},E_{P})$ and an undirected data
graph $G=(V,E)$, we use $\mathit{occ}(G,P)$ to represent the set of
occurrences of $P$ in $G$. Every vertex in $G$ has a degree at most $\lambda$.
Our goal is to design an algorithm to sample from $\mathit{occ}(G,P)$
efficiently.

We formulate the “polymatroid bound” of this problem through a reduction to
its directed counterpart. For $P=(V_{P},E_{P})$, create a directed pattern
$P^{\prime}=(V_{P}^{\prime},E_{P}^{\prime})$ as follows. First, set
$V_{P}^{\prime}=V_{P}$. Second, for every edge $\\{X,Y\\}\in E_{P}$, add to
$E_{P}$ two directed edges $(X,Y)$ and $(Y,X)$. Now, given an integer $m\geq
1$, an integer $\lambda\in[1,m]$, and an undirected pattern $P=(V_{P},E_{P})$,
the undirected polymatroid bound of $m$, $\lambda$, and $P$ is defined as

$\displaystyle\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)$ $\displaystyle=$
$\displaystyle\mathit{polymat}_{\mathit{dir}}(m,\lambda,P^{\prime})$ (19)

where the function $\mathit{polymat}_{\mathit{dir}}$ is defined in (18).

Our formulation highlights how undirected subgraph sampling can be reduced to
the directed version. From $G=(V,E)$, construct a directed graph
$G^{\prime}=(V^{\prime},E^{\prime})$ by setting $V^{\prime}=V$, and for every
edge $\\{x,y\\}\in E$, adding to $E^{\prime}$ two directed edges $(x,y)$ and
$(y,x)$. Every occurrence in $\mathit{occ}(G,P)$ matches the same number (a
constant) of occurrences in $\mathit{occ}(G^{\prime},P^{\prime})$. By
resorting to Theorem 4.2, we can obtain an algorithm to sample from
$\mathit{occ}(G,P)$ in
$O(\mathit{polymat}_{\mathit{undir}}(2|E|,\lambda,P)/\max\\{1,\mathrm{OUT}\\})$
time (where $\mathrm{OUT}=|\mathit{occ}(G,P)|$) after a preprocessing of
$O(|E|)$ expected time. We omit the details because they will be superseded by
another simpler approach to be described later.

Unlike $\mathit{polymat}_{\mathit{dir}}(m,\lambda,P)$, which is defined
through an LP, we can solve the undirected counterpart
$\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)$ into a closed form. It is
always possible [35, 33, 6] to decompose $P$ into vertex-disjoint subgraphs
$\pentagon_{1},\pentagon_{2},...,\pentagon_{\alpha}$,
$\star_{1},\star_{2},...,$ and $\star_{\beta}$ (for some integers
$\alpha,\beta\geq 0$) such that

  * •

$\pentagon_{i}$ is an odd-length cycle for each $i\in[\alpha]$;

  * •

$\star_{j}$ is a star333A star is an undirected graph where one vertex, called
the center, has an edge to every other vertex, and each non-center vertex has
degree 1. for each $j\in[\beta]$;

  * •

$\sum_{i=1}^{\alpha}\rho^{*}(\pentagon_{i})+\sum_{j=1}^{\beta}\rho^{*}(\star_{j})=\rho^{*}(P)$;
see Section 1.2 for the definition of the fractional edge cover number
function $\rho^{*}(.)$.

We will refer to $(\pentagon_{1},...,\pentagon_{\alpha}$, $\star_{1},...,$
$\star_{\beta})$ as a fractional edge-cover decomposition of $P$. Define:

$\displaystyle k_{\mathit{cycle}}$ $\displaystyle=$ total number of vertices
in $\pentagon_{1},...,\pentagon_{\alpha}$ (20) $\displaystyle
k_{\mathit{star}}$ $\displaystyle=$ $\displaystyle\text{total number of
vertices in $\star_{1},...,\star_{\beta}$}.$ (21)

We establish the lemma below in Appendix C.

######  Lemma 5.1.

If $k$ is the number of vertices in $P$, then

$\displaystyle\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)=\begin{cases}m\cdot\lambda^{k-2}&\text{if
}\lambda\leq\sqrt{m},\\\
m^{\frac{k_{\mathit{cycle}}}{2}+\beta}\cdot\lambda^{k_{\mathit{star}}-2\beta}&\text{if
}\lambda>\sqrt{m}\end{cases}$ (22)

As shown in Appendix D, for $k=O(1)$, the expression in (22) asymptotically
matches an upper bound of $|\mathit{occ}(G^{\prime},P)|$ — for any
$G^{\prime}$ with $m$ edges and maximum vertex-degree at most $\lambda$ —
easily derived from a fractional edge-cover decomposition. The same appendix
will also prove that, for a wide range of $m$ and $\lambda$ values, there
exists a graph $G^{\prime}$ with $m$ edges and maximum vertex degree at most
$\lambda$ guaranteeing the following simultaneously for all patterns $P$ with
$k$ vertices: $|\mathit{occ}(G^{\prime},P)|$ is no less than the expression’s
value, up to a factor of $1/(4k)^{k}$. This implies that, when $k$ is a
constant, the expression asymptotically equals
$\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)$. More effort is required to
prove that the expression equals
$\mathit{polymat}_{\mathit{undir}}(m,\lambda,P))$ precisely, as we demonstrate
in Appendix C.

Lemma 5.1 points to an alternative strategy to perform undirected subgraph
sampling without joins. Identify an arbitrary spanning tree $\mathcal{T}$ of
the pattern $P=(V_{P},E_{P})$. Order the vertices of $V_{P}$ as
$A_{1},A_{2},...,A_{k}$ such that, for any $i\in[2,k]$, vertex $A_{i}$ is
adjacent in $\mathcal{T}$ to a (unique) vertex $A_{j}$ with $j\in[i-1]$. Now
construct a map $f:V_{P}\rightarrow V$ as follows (recall that $V$ is the
vertex set of the data graph $G=(V,E)$). First, take an edge $\\{u,v\\}$
uniformly at random from $E$, and choose one of the following with an equal
probability: (i) $f(A_{1})=u,f(A_{2})=v$, or (ii) $f(A_{1})=v,f(A_{2})=u$.
Then, for every $i\in[3,k]$, decide $f(A_{i})$ as follows. Suppose that
$A_{i}$ is adjacent to $A_{j}$ for some (unique) $j\in[1,i-1]$. Toss a coin
with probability $\mathit{deg}(f(A_{j}))/\lambda$, where
$\mathit{deg}(f(A_{j}))$ is the degree of vertex $f(A_{j})$ in $G$. If the
coin comes up tails, declare failure and terminate. Otherwise, set $f(A_{i})$
to a neighbor of $f(A_{j})$ in $G$ picked uniformly at random. After
finalizing the map $f(.)$, check whether $\\{f(A_{i})\mid i\in[k]\\}$ induces
a subgraph of $G$ isomorphic to $P$. If so, accept $f$ and return this
subgraph; otherwise, reject $f$. To guarantee a sample or declare
$\mathit{occ}(G,P)=\emptyset$, apply the “two-thread approach” by (i)
repeating the algorithm until acceptance and (ii) concurrently running an
algorithm for computing the whole $\mathit{occ}(G,P)$ in
$O(\mathit{polymat}_{\mathit{undir}}(|E|,\lambda,P))$ time444For this purpose,
use Ngo’s algorithm in [30] to find all occurrences in
$\mathit{occ}(G^{\prime},P^{\prime})$ — see our earlier definitions of
$G^{\prime}$ and $P^{\prime}$ — which is possible due to Lemma 4.1.. As proved
in Appendix E, this ensures the expected sample time
$O(|E|\cdot\lambda^{k-2}/\max\\{1,\mathrm{OUT}\\})$ after a preprocessing of
$O(|E|)$ expected time.

The above algorithm suffices for the case $\lambda\leq\sqrt{|E|}$. Consider
now the case $\lambda>\sqrt{|E|}$. We will construct a map $f:V_{P}\rightarrow
V$ according to a given fractional edge-cover decomposition
$(\pentagon_{1},...,\pentagon_{\alpha}$, $\star_{1},...,$ $\star_{\beta})$.
For each $i\in[\alpha]$, use the algorithm of [16] to uniformly sample an
occurrence of $\pentagon_{i}$ — denoted as $G_{\mathit{sub}}(\pentagon_{i})$ —
in
$O(|E|^{\rho^{*}(\pentagon_{i})}/\max\\{1,|\mathit{occ}(G,\pentagon_{i})|\\})$
expected time. Let $f_{\pentagon_{i}}$ be a map from the vertex set of
$\pentagon_{i}$ to that of $G_{\mathit{sub}}(\pentagon_{i})$, chosen uniformly
at random from all the isomorphism bijections (defined in Section 1.1) between
$\pentagon_{i}$ and $G_{\mathit{sub}}(\pentagon_{i})$. For each $j\in[\beta]$,
apply our earlier algorithm to uniformly sample an occurrence of $\star_{j}$ —
denoted as $G_{\mathit{sub}}(\star_{j})$ — in
$O(|E|\cdot\lambda^{k_{j}}/\max\\{1,|\mathit{occ}(G,\star_{j})|\\})$ expected
time, where $k_{j}$ is the number of vertices in $\star_{j}$. Let
$f_{\star_{j}}$ be a map from the vertex set of $\star_{j}$ to that of
$G_{\mathit{sub}}(\star_{j})$, chosen uniformly at random from all the
polymorphism bijections between $\star_{j}$ and $G_{\mathit{sub}}(\star_{j})$.
If any of $\pentagon_{1},...,\pentagon_{\alpha}$, $\star_{1},...,$
$\star_{\beta}$ has no occurrences, declare $\mathit{occ}(G,P)=\emptyset$ and
terminate. Otherwise, the functions in $\\{f_{\pentagon_{i}}\mid
i\in[\alpha]\\}$ and $\\{f_{\star_{j}}\mid j\in[\beta]\\}$ together determine
the map $f$ we aim to build. Check whether $\\{f(A)\mid A\in V\\}$ induces a
subgraph of $G$ isomorphic to $P$. If so, accept $f$ and return this subgraph;
otherwise, reject $f$. Repeat until acceptance and concurrently run an
algorithm for computing the whole $\mathit{occ}(G,P)$ in
$O(\mathit{polymat}_{\mathit{undir}}(|E|,\lambda,P))$ time. As proved in
Appendix E, this ensures the expected sample time
$O(|E|^{\frac{k_{\mathit{cycle}}}{2}+\beta}\cdot\lambda^{k_{\mathit{star}}-2\beta}/\max\\{1,\mathrm{OUT}\\})$
after a preprocessing of $O(|E|)$ expected time.

We can now conclude with our last main result:

######  Theorem 5.2.

Let $G=(V,E)$ be a simple undirected data graph, where each vertex has a
degree at most $\lambda$. Let $P=(V_{P},E_{P})$ be a simple connected pattern
graph with a constant number of vertices. We can build in $O(|E|)$ expected
time a data structure that supports each subgraph sampling operation in
$O(\mathit{polymat}_{\mathit{undir}}(|E|,\lambda,P)/\max\\{1,\mathrm{OUT}\\})$
expected time, where $\mathrm{OUT}$ is the number of occurrences of $P$ in
$G$, and $\mathit{polymat}_{\mathit{undir}}(|E|,\lambda,P)$ is the undirected
polymatrioid bound in (22).

##  6 Concluding Remarks

Our new sampling algorithms imply new results on several other fundamental
problems. We will illustrate this with respect to evaluating a join
$\mathcal{Q}$ consistent with an acyclic set DC of degree constraints. Similar
implications also apply to subgraph sampling.

  * •

By standard techniques [11, 14], we can estimate the output size
$\mathrm{OUT}$ up to a relative error $\epsilon$ with high probability (i.e.,
at least $1-1/\mathrm{IN}^{c}$ for an arbitrarily large constant $c$) in time
$\tilde{O}(\frac{1}{\epsilon^{2}}\frac{\mathit{polymat}(\textsf{DC})}{\max\\{1,\mathrm{OUT}\\}})$
after a preprocessing of $O(\mathrm{IN})$ expected time.

  * •

Employing a technique in [14], we can, with high probability, report all the
tuples in $\mathit{join}(\mathcal{Q})$ with a delay of
$\tilde{O}(\frac{\mathit{polymat}(\textsf{DC})}{\max\\{1,\mathrm{OUT}\\}})$.
In this context, ‘delay’ refers to the maximum interval between the reporting
of two successive result tuples, assuming the presence of a placeholder tuple
at the beginning and another at the end.

  * •

In addition to the delay guarantee, our algorithm in the second bullet can,
with high probability, report the tuples of $\mathit{join}(\mathcal{Q})$ in a
random permutation. This means that each of the $\mathrm{OUT}!$ possible
permutations has an equal probability of being the output.

All of the results presented above compare favorably with the current state of
the art as presented in [14]. This is primarily due to the superiority of
$\mathit{polymat}(\textsf{DC})$ over $\mathit{AGM}(\mathcal{Q})$. In addition,
our findings in the last two bullet points also complement Ngo’s algorithm as
described in [30] in a satisfying manner.

## Appendix

##  Appendix A Implementing ADC-Sample with Indexes

We preprocess each constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}$ as
follows. Let $R\in Q$ be its main guard, i.e.,
$R=R_{F(\mathcal{X},\mathcal{Y})}$. For each $i\in[k]$ and each tuple
$\textrm{\boldmath${w}$}\in\Pi_{\mathit{schema}(R)\cap\mathcal{V}_{i}}(R)$,
define

$\displaystyle R_{\mathcal{Y}}(i,\textrm{\boldmath${w}$})$ $\displaystyle=$
$\displaystyle\\{\textrm{\boldmath${u}$}[\mathcal{Y}]\mid\textrm{\boldmath${u}$}\in
R,\textrm{\boldmath${u}$}[\mathit{schema}(R)\cap\mathcal{V}_{i}]=\textrm{\boldmath${w}$}\\}$

which we refer to as a fragment.

During preprocessing, we compute and store
$R_{\mathcal{Y}}(i,\textrm{\boldmath${w}$})$ for every $i\in[k]$ and
$\textrm{\boldmath${w}$}\in\Pi_{\mathit{schema}(R)\cap\mathcal{V}_{i}}(R)$.
Next, we will explain how to do so for an arbitrary $i\in[k]$. First, group
all the tuples of $R$ by the attributes in
$\mathit{schema}(R)\cap\mathcal{V}_{i}$, which can be done in $O(\mathrm{IN})$
expected time by hashing. Then, perform the following steps for each group in
turn. Let ${w}$ be the group’s projection on
$\mathit{schema}(R)\cap\mathcal{V}_{i}$. We compute the group tuples’
projections onto $\mathcal{Y}$ and eliminate duplicate projections, the
outcome of which is precisely $R_{\mathcal{Y}}(i,\textrm{\boldmath${w}$})$ and
is stored using an array. With hashing, this requires expected time only
linear to the group’s size. Therefore, the total cost of generating the
fragments $R_{\mathcal{Y}}(i,\textrm{\boldmath${w}$})$ of all
$\textrm{\boldmath${w}$}\in\Pi_{\mathit{schema}(R)\cap\mathcal{V}_{i}}(R)$ is
$O(\mathrm{IN})$ expected.

After the above preprocessing, given any $i\in[k]$, constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}$,
tuple ${w}$ over $\mathcal{V}_{i-1}$, and value $a\in\mathbf{dom}$, we can
compute
$\mathit{reldeg}_{i,\mathcal{X},\mathcal{Y}}(\textrm{\boldmath${w}$},a)$
defined in (7) in constant time. For convenience, let
$R=R_{F(\mathcal{X},\mathcal{Y})}$. To compute
$|\Pi_{\mathcal{Y}}(R\ltimes\textrm{\boldmath${w}$})|$ (the denominator of
(7)), first obtain
$\textrm{\boldmath${w}$}_{1}=\textrm{\boldmath${w}$}[\mathit{schema}(R)\cap\mathcal{V}_{i-1}]$.
Then, $\Pi_{\mathcal{Y}}(R\ltimes\textrm{\boldmath${w}$})$ is just the
fragment $R_{\mathcal{Y}}(i-1,\textrm{\boldmath${w}$}_{1})$, which has been
pre-stored. The size of this fragment can be retrieved using
$\textrm{\boldmath${w}$}_{1}$ in $O(1)$ time. Similarly, to compute
$|\sigma_{A_{i}=a}(\Pi_{\mathcal{Y}}(R\ltimes\textrm{\boldmath${w}$}))|$ (the
numerator of (7)), we can first obtain $\textrm{\boldmath${w}$}_{2}$, which is
a tuple over $\mathit{schema}(R)\cap\mathcal{V}_{i}$ that shares the values of
$\textrm{\boldmath${w}$}_{1}$ on all the attributes in
$\mathit{schema}(R)\cap\mathcal{V}_{i-1}$ and additionally uses value $a$ on
attribute $A_{i}$. Then,
$\sigma_{A_{i}=a}(\Pi_{\mathcal{Y}}(R\ltimes\textrm{\boldmath${w}$}))$ is just
the fragment $R_{\mathcal{Y}}(i,\textrm{\boldmath${w}$}_{2})$, which has been
pre-stored. The size of this fragment can be fetched using
$\textrm{\boldmath${w}$}_{2}$ in $O(1)$ time.

As a corollary, given any $i\in[k]$, tuple ${w}$ over $\mathcal{V}_{i-1}$, and
value $a\in\mathbf{dom}$, we can compute
$\mathit{reldeg}^{*}_{i}(\textrm{\boldmath${w}$},a)$ and
$\mathit{constraint}^{*}_{i}(\textrm{\boldmath${w}$},a)$ — defined in (8) and
(9), respectively — in constant time.

It remains to explain how to implement Line 4 of ADC-sample (Figure 1). Here,
we want to randomly sample a tuple from
$\Pi_{\mathcal{Y}^{\circ}}(R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}\ltimes\textrm{\boldmath${w}$}_{i-1})$.
Again, for convenience, let
$R=R_{F(\mathcal{X}^{\circ},\mathcal{Y}^{\circ})}$. Obtain
$\textrm{\boldmath${w}$}^{\prime}=\textrm{\boldmath${w}$}_{i-1}[\mathit{schema}(R)\cap\mathcal{V}_{i-1}]$.
Then, $\Pi_{\mathcal{Y}}(R\ltimes\textrm{\boldmath${w}$}_{i-1})$ is just the
fragment $R_{\mathcal{Y}}(i-1,\textrm{\boldmath${w}$}^{\prime})$, which has
been stored in an array. The starting address and size of the array can be
acquired using $\textrm{\boldmath${w}$}^{\prime}$ in $O(1)$ time, after which
a sample can be drawn from the fragment in constant time.

##  Appendix B Proof of Lemma 4.1

Let us rephrase the problem as follows. Let $P=(V_{P},E_{P})$ be a cyclic
pattern graph. Given an integer $m\geq 1$ and an integer $\lambda\in[1,m]$,
define DC to be a set of degree constraints over $V_{P}$ that contains two
constraints for each edge $(X,Y)\in E_{P}$: $(\emptyset,\\{X,Y\\},m)$ and
$(\\{X\\},$ $\\{X,Y\\},$ $\lambda)$. The constraint dependence graph
$G_{\textsf{DC}}$ is exactly $P$ and, hence, is cyclic. We want to prove the
existence of an acyclic $\textsf{DC}^{\prime}\subset\textsf{DC}$ such that
$\mathit{polymat}(\textsf{DC}^{\prime})=\mathit{polymat}(\textsf{DC})$. We
will first tackle the situation where $\lambda>\sqrt{m}$ before proceeding to
the opposite scenario. The former case presents a more intriguing line of
argumentation than the latter.

Case ${\lambda>\sqrt{m}}$. For every edge $(X,Y)\in
G_{\textsf{DC}}=(V_{P},E_{P})$, define two variables: $x_{X,Y}$ and $z_{X,Y}$.
Jayaraman et al. [19] showed that, for $\lambda>\sqrt{m}$,
$\mathit{polymat}(\textsf{DC})$ is, up to a constant factor, the optimal value
of the following LP (named LP(+) following [19]):

LP(+) [19] |  | min $\sum\limits_{(X,Y)\in E_{P}}x_{X,Y}\log m+z_{X,Y}\log\lambda$ subject to
---|---|---
|  $\sum\limits_{(X,A)\in E_{P}}(x_{X,A}+z_{X,A})+\sum\limits_{(A,Y)\in
E_{P}}x_{A,Y}\geq 1$ $\forall A\in V_{P}$
|  $x_{X,Y}\geq 0$, $z_{X,Y}\geq 0$ $\forall(X,Y)\in E_{P}$

######  Lemma B.1.

There exists an optimal solution to LP(+) satisfying the condition that the
edges in $\\{(X,Y)\in E_{P}\mid z_{X,Y}>0\\}$ induce an acyclic subgraph of
$G_{\textsf{DC}}$.

We note that while the above lemma is not expressly stated in [19], it can be
extrapolated from the analysis presented in Section H.2 of [19]. Nevertheless,
the argument laid out in [19] is quite intricate. Our proof, which will be
presented below, incorporates news ideas beyond their argument and is
considerably shorter. Specifically, these new ideas are evidenced in the way
we formulate a novel LP optimal solution in (23)-(26).

###### Proof of Lemma B.1.

Consider an arbitrary optimal solution to LP(+) that sets
$x_{X,Y}=x^{*}_{X,Y}$ and $z_{X,Y}=z^{*}_{X,Y}$ for each $(X,Y)\in E_{P}$. If
the edge set $\\{(X,Y)\in E_{P}\mid z^{*}_{X,Y}>0\\}$ induces an acyclic
graph, we are done. Next, we consider that $G_{\textsf{DC}}$ contains a cycle.

Suppose that $(A_{1},A_{2})$ is the edge in the cycle with the smallest
$z^{*}_{A_{1},A_{2}}$ (breaking ties arbitrarily). Let $(A_{2},A_{3})$ be the
edge succeeding $(A_{1},A_{2})$ in the cycle. It thus follows that
$z^{*}_{A_{2},A_{3}}\geq z^{*}_{A_{1},A_{2}}$. Define

$\displaystyle x^{\prime}_{A_{2},A_{3}}$ $\displaystyle=$ $\displaystyle
x^{*}_{A_{2},A_{3}}+z^{*}_{A_{1},A_{2}}$ (23) $\displaystyle
x^{\prime}_{A_{1},A_{2}}$ $\displaystyle=$ $\displaystyle x^{*}_{A_{1},A_{2}}$
(24) $\displaystyle z^{\prime}_{A_{2},A_{3}}$ $\displaystyle=$ $\displaystyle
0$ (25) $\displaystyle z^{\prime}_{A_{1},A_{2}}$ $\displaystyle=$
$\displaystyle 0$ (26)

For every edge $(X,Y)\in E_{P}\setminus\\{(A_{1},A_{2}),(A_{2},A_{3})\\}$, set
$x^{\prime}_{X,Y}=x^{*}_{X,Y}$ and $z^{\prime}_{X,Y}=z^{*}_{X,Y}$. It is easy
to verify that, for every vertex $A\in V_{P}$, we have

$\displaystyle\sum\limits_{(X,A)\in
E_{P}}(x^{\prime}_{X,A}+z^{\prime}_{X,A})+\sum\limits_{(A,Y)\in
E_{P}}x^{\prime}_{A,Y}\geq\sum\limits_{(X,A)\in
E_{P}}(x^{*}_{X,A}+z^{*}_{X,A})+\sum\limits_{(A,Y)\in E_{P}}x^{*}_{A,Y}.$

Therefore, $\\{x^{\prime}_{X,Y},z^{\prime}_{X,Y}\mid(X,Y)\in E_{P}\\}$ serves
as a feasible solution to LP(+). However:

$\displaystyle\Big{(}\sum\limits_{(X,Y)\in E_{P}}x^{\prime}_{X,Y}\log
m+z^{\prime}_{X,Y}\log\lambda\Big{)}-\Big{(}\sum\limits_{(X,Y)\in
E_{P}}x^{*}_{X,Y}\log m+z^{*}_{X,Y}\log\lambda\Big{)}$ (27) $\displaystyle=$
$\displaystyle z^{*}_{A_{1},A_{2}}\log
m-(z^{*}_{A_{1},A_{2}}+z^{*}_{A_{2},A_{3}})\log\lambda$ $\displaystyle\leq$
$\displaystyle z^{*}_{A_{1},A_{2}}\log m-2\cdot
z^{*}_{A_{1},A_{2}}\log\lambda$ $\displaystyle<$ $\displaystyle 0$

where the last step used the fact $\lambda^{2}>m$. This contradicts the
optimality of $\\{x^{*}_{X,Y},z^{*}_{X,Y}\mid(X,Y)\in E_{P}\\}$. ∎

We now build a set $\textsf{DC}^{\prime}$ of degree constraints as follows.
First, take an optimal solution $\\{x^{*}_{X,Y},z^{*}_{X,Y}\mid(X,Y)\in
E_{P}\\}$ to LP(+) promised by Lemma B.1. Add to $\textsf{DC}^{\prime}$ a
constraint $(X,\\{X,Y\\},\lambda)$ for every $(X,Y)\in E_{P}$ satisfying
$z^{*}_{X,Y}>0$. Then, for every edge $(X,Y)\in E_{P}$, add to
$\textsf{DC}^{\prime}$ a constraint $(\emptyset,\\{X,Y\\},m)$. The
$\textsf{DC}^{\prime}$ thus constructed must be acyclic. Denote by
$G_{\textsf{DC}^{\prime}}=(V_{P}^{\prime},E_{P}^{\prime})$ the degree
constraint graph of $\textsf{DC}^{\prime}$. Note that $V_{P}=V_{P}^{\prime}$
and $E_{P}^{\prime}\subset E_{P}$.

######  Lemma B.2.

The $\textsf{DC}^{\prime}$ constructed in the above manner satisfies
$\mathit{polymat}(\textsf{DC}^{\prime})=\Theta(\mathit{polymat}(\textsf{DC}))$.

###### Proof.

We will first establish
$\mathit{polymat}(\textsf{DC}^{\prime})\geq\mathit{polymat}(\textsf{DC})$.
Remember that $\mathit{polymat}(\textsf{DC}^{\prime})$ is the optimal value of
the modular LP (in its primal form) defined by $\textsf{DC}^{\prime}$, as
described in Section 2. Similarly, $\mathit{polymat}(\textsf{DC})$ is the
optimal value of the modular LP defined by DC. Given that
$\textsf{DC}^{\prime}\subset\textsf{DC}$, the LP defined by
$\textsf{DC}^{\prime}$ incorporates only a subset of the constraints found in
the LP defined by DC. Therefore, it must be the case that
$\mathit{polymat}(\textsf{DC}^{\prime})\geq\mathit{polymat}(\textsf{DC})$.

The rest of the proof will show
$\mathit{polymat}(\textsf{DC}^{\prime})=O(\mathit{polymat}(\textsf{DC}))$,
which will establish the lemma. Consider the following LP:

LP${{}^{(+)}_{1}}$ |  | min $\sum\limits_{(X,Y)\in E_{P}}x_{X,Y}\log m+z_{X,Y}\log\lambda$ subject to
---|---|---
|  $\sum\limits_{(X,A)\in E_{P}}x_{X,A}+\sum\limits_{(A,Y)\in
E_{P}}x_{A,Y}+\sum\limits_{(X,A)\in E^{\prime}_{P}}z_{X,A}\geq 1$ $\forall
A\in\mathcal{V}_{P}$
|  $x_{X,Y}\geq 0$, $z_{X,Y}\geq 0$ $\forall(X,Y)\in E_{P}$

The condition $(X,A)\in E^{\prime}_{P}$ in the first inequality marks the
difference between LP${}^{(+)}_{1}$ and LP(+). Note that the two LPs have the
same objective function.

Claim 1: LP${}^{(+)}_{1}$ and LP(+) have the same optimal value.

To prove the claim, first observe that any feasible solution
$\\{x_{X,Y},z_{X,Y}\mid(X,Y)\in E_{P}\\}$ to LP${}^{(+)}_{1}$ is also a
feasible solution to LP(+). Hence, the optimal value of LP(+) cannot exceed
that of LP${}^{(+)}_{1}$. On the other hand, recall that earlier we have
identified an optimal solution $\\{x^{*}_{X,Y},$ $z^{*}_{X,Y}\mid(X,Y)\in
E_{P}\\}$ to LP(+). By how $\textsf{DC}^{\prime}$ is built from that solution
and how $G_{\textsf{DC}^{\prime}}=(V^{\prime}_{P},E^{\prime}_{P})$ is built
from $\textsf{DC}^{\prime}$, it must hold that $z^{*}_{X,Y}=0$ for every
$(X,Y)$ $\in$ $E_{P}\setminus E^{\prime}_{P}$. Hence,
$\\{x^{*}_{X,Y},z^{*}_{X,Y}\mid(X,Y)\in E_{P}\\}$ makes a feasible solution to
LP${}^{(+)}_{1}$. This implies that $\\{x^{*}_{X,Y},z^{*}_{X,Y}\mid(X,Y)\in
E_{P}\\}$ must be an optimal solution to LP${}^{(+)}_{1}$. Claim 1 now
follows.

Consider another LP:

LP${{}^{(+)}_{2}}$ |  | min $\sum\limits_{(X,Y)\in E_{P}}x_{X,Y}\log m+\sum\limits_{(X,Y)\in E_{P}^{\prime}}z_{X,Y}\log\lambda$ subject to
---|---|---
|  $\sum\limits_{(X,A)\in E_{P}}x_{X,A}+\sum\limits_{(A,Y)\in
E_{P}}x_{A,Y}+\sum\limits_{(X,A)\in E^{\prime}_{P}}z_{X,A}\geq 1$ $\forall
A\in\mathcal{V}_{P}$
|  $x_{X,Y}\geq 0$ $\forall(X,Y)\in E_{P}$
|  $z_{X,Y}\geq 0$ $\forall(X,Y)\in E^{\prime}_{P}$

LP${{}^{(+)}_{2}}$ differs from LP${{}^{(+)}_{1}}$ in that the former drops
the variables $z_{X,Y}$ of those edges $(X,Y)\in E_{P}\setminus
E^{\prime}_{P}$. This happens both in the constraints and the objective
function.

Claim 2: LP${}^{(+)}_{1}$ and LP${}^{(+)}_{2}$ have the same optimal value.

To prove the claim, first observe that, given a feasible solution
$\\{x_{X,Y}\mid(X,Y)\in E_{P}\\}\cup\\{z_{X,Y}\mid(X,$ $Y)$ $\in
E^{\prime}_{P}\\}$ to LP${}^{(+)}_{2}$, we can extend it into a feasible
solution to LP${}^{(+)}_{1}$ by padding $Z_{X,Y}$ $=$ $0$ for each $(X,Y)\in
E_{P}\setminus E^{\prime}_{P}$. Hence, the optimal value of LP${}^{(+)}_{1}$
cannot exceed that of LP${}^{(+)}_{2}$. On the other hand, as mentioned
before, $\\{x^{*}_{X,Y},z^{*}_{X,Y}\mid(X,Y)\in E_{P}\\}$ is an optimal
solution to LP${}^{(+)}_{1}$. In this solution, $z^{*}_{X,Y}=0$ for every
$(X,Y)\in E_{P}\setminus E^{\prime}_{P}$. Thus, $\\{x^{*}_{X,Y}\mid(X,Y)\in
E_{P}\\}\cup\\{z^{*}_{X,Y}\mid(X,Y)\in E^{\prime}_{P}\\}$ makes a feasible
solution to LP${}^{(+)}_{2}$, achieving the same objective function value as
the optimal value of LP${}^{(+)}_{1}$. Claim 2 now follows.

Finally, notice that LP${}^{(+)}_{2}$ is exactly the dual modular LP defined
by $\textsf{DC}^{\prime}$. Hence,
$\log(\mathit{polymat}(\textsf{DC}^{\prime}))$ is exactly the optimal value of
LP${}^{(+)}_{2}$. Thus,
$\mathit{polymat}(\textsf{DC}^{\prime})=O(\mathit{polymat}(\textsf{DC}))$ can
now be derived from the above discussion and the fact that
$\log(\mathit{polymat}(\textsf{DC}))$ is asymptotically the optimal value of
LP(+). ∎

Case ${\lambda\leq\sqrt{m}}$. Let us first define several concepts. A directed
star refers to a directed graph where there are $t\geq 2$ vertices, among
which one vertex, designated the center, has $t-1$ edges (in-coming and out-
going edges combined), and every other vertex, called a petal, has only one
edge (which can be an in-coming or out-going edge). Now, consider a directed
bipartite graph between $U_{1}$ and $U_{2}$, each being an independent sets of
vertices (an edge may point from one vertex in $U_{1}$ to a vertex in $U_{2}$,
or vice versa). A directed star cover of the bipartite graph is a set of
directed stars such that

  * •

each directed star is a subgraph of the bipartite graph,

  * •

no two directed stars share a common edge, and

  * •

every vertex in $U_{1}\cup U_{2}$ appears in exactly one directed star.

A directed star cover is minimum if it has the least number of edges, counting
all directed stars in the cover.

Next, we review an expression about $\mathit{polymat}(\textsf{DC})$ derived in
[19]. Find all the strongly connected components (SCCs) of
$G_{\textsf{DC}}=(V_{P},E_{P})$. Adopting terms from [19], an SCC is
classified as (i) a source if it has no in-coming edge from another SCC, or a
non-source otherwise; (ii) trivial if it consists of a single vertex, or non-
trivial otherwise. Define:

  * •

$S$ = the set of vertices in $G_{\textsf{DC}}$ each forming a trivial source
SCC by itself.

  * •

$T$ = the set of vertices in $G_{\textsf{DC}}$ receiving an in-coming edge
from at least one vertex in $S$.

Take a minimum directed star cover of the directed bipartite graph induced by
$S$ and $T$. Define

  * •

$S_{1}$ = the set of vertices in $S$ each serving as the center of some
directed star in the cover.

  * •

$S_{2}=S\setminus S_{1}$.

  * •

$T_{2}$ = the set of vertices in $T$ each serving as the center of some
directed star in the cover.

  * •

$T_{1}=T\setminus T_{2}$.

Note that the meanings of the symbols $S_{1},S_{2},T_{1}$, and $T_{2}$ follow
exactly those in [19] for the reader’s convenience (in particular, note the
semantics of $T_{1}$ and $T_{2}$).

We now introduce three quantities:

  * •

$c_{1}$: the number of non-trivial source SCCs;

  * •

$n_{1}$: the total number of vertices in non-trivial source SCCs;

  * •

$n_{2}=|V_{P}|-n_{1}-|S|-|T|$.

Jayaraman et al. [19] showed:

$\displaystyle\mathit{polymat}_{\mathit{dir}}(m,\lambda,P)$ $\displaystyle=$
$\displaystyle\Theta\Big{(}m^{c_{1}+|S|}\cdot\lambda^{n_{1}+n_{2}+|T_{1}|-2c_{1}-|S_{1}|}\Big{)}.$
(28)

Let $G^{\prime}_{\textsf{DC}}=(V^{\prime}_{P},E_{P}^{\prime})$ be an arbitrary
weakly-connected acyclic subgraph of $G_{\textsf{DC}}$ satisfying all the
conditions below.

  * •

$V_{P}=V_{P}^{\prime}$.

  * •

$E_{P}^{\prime}$ contains all the edges in the minimum directed star cover
identified earlier.

  * •

In each non-trivial source SCC, every vertex, except for one, has one in-
coming edge included in $E^{\prime}_{P}$. We will refer to the vertex $X$ with
no in-coming edges in $E^{\prime}_{P}$ as the SCC’s root. The fact that every
other vertex $Y$ in the SCC has an in-coming edge in $E^{\prime}_{P}$ implies
$(X,Y)\in E^{\prime}_{P}$ for at least one $Y$. We designate one such $(X,Y)$
as the SCC’s main edge.

  * •

In each non-trivial non-source SCC, every vertex has an in-coming edge
included in $E^{\prime}_{P}$.

It is rudimentary to verify that such a subgraph $G^{\prime}_{\textsf{DC}}$
must exist.

From $G_{\textsf{DC}}=(V_{P},E_{P})$ and
$G^{\prime}_{\textsf{DC}}=(V_{P}^{\prime},E_{P}^{\prime})$, we create a set
$\textsf{DC}^{\prime}$ of degree constraints as follows.

  * •

For each edge $(X,Y)\in E_{P}$ (note: not $E_{P}^{\prime}$), add a constraint
$(\emptyset,\\{X,Y\\},m)$ to $\textsf{DC}^{\prime}$.

  * •

We inspect each directed star in the minimum directed star cover and
distinguish two possibilities.

    * –

Scenario 1: The star’s center $X$ comes from $S_{1}$. Let the star’s petals be
$Y_{1},Y_{2},...,Y_{t}$ for some $t\geq 1$; the ordering of the petals does
not matter. For each $i\in[t-1]$, we add a constraint
$(\\{X\\},\\{X,Y_{i}\\},\lambda)$ to $\textsf{DC}^{\prime}$. We will refer to
$(X,Y_{t})$ as the star’s main edge.

    * –

Scenario 2: The star’s center $X$ comes from $T_{2}$. Nothing needs to be
done.

  * •

Consider now each non-trivial source SCC. Remember that every vertex $Y$,
other than the SCC’s root, has an in-coming edge $(X,Y)\in E_{P}^{\prime}$.
For every such $Y$, if $(X,Y)$ is not the SCC’s main edge, add a constraint
$(\\{X\\},\\{X,Y\\},\lambda)$ to $\textsf{DC}^{\prime}$.

  * •

Finally, we examine each non-source SCC. As mentioned, every vertex $Y$ in
such an SCC has an in-coming edge $(X,Y)\in E_{P}^{\prime}$. For every $Y$,
add a constraint $(\\{X\\},\\{X,Y\\},\lambda)$ to $\textsf{DC}^{\prime}$.

The rest of the proof will show
$\mathit{polymat}(\textsf{DC}^{\prime})=\Theta(\mathit{polymat}(\textsf{DC}))$.
As $\textsf{DC}^{\prime}\subset\textsf{DC}$, we must have
$\mathit{polymat}(\textsf{DC}^{\prime})\geq\mathit{polymat}(\textsf{DC})$
following the same reasoning used in the $\lambda>\sqrt{m}$ case.

We will now proceed to argue that
$\mathit{polymat}(\textsf{DC}^{\prime})=O(\mathit{polymat}(\textsf{DC}))$.
Recall that $\log(\mathit{polymat}(\textsf{DC}^{\prime}))$ is the optimal
value of the dual modular LP of $\textsf{DC}^{\prime}$ (see Section 2). On the
other hand, the value of $\mathit{polymat}(\textsf{DC})$ satisfies (28). In
the following, we will construct a feasible solution to the dual modular LP of
$\textsf{DC}^{\prime}$ under which the LP’s objective function achieves the
value of

$\displaystyle\Big{(}(c_{1}+|S|)\cdot\log
m\Big{)}+(n_{1}+n_{2}+|T_{1}|-2c_{1}-|S_{1}|)\cdot\log\lambda$ (29)

which will be sufficient for proving Lemma B.1.

The dual modular LP associates every constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}^{\prime}$
with a variable $\delta_{\mathcal{Y}\mid\mathcal{X}}$. We determine these
variables’ values as follows.

  * •

For every constraint
$(\mathcal{X},\mathcal{Y},N_{\mathcal{Y}\mid\mathcal{X}})\in\textsf{DC}^{\prime}$
where $N_{\mathcal{Y}\mid\mathcal{X}}=\lambda$, set
$\delta_{\mathcal{Y}\mid\mathcal{X}}=1$.

  * •

Consider each directed star in the minimum directed star.

    * –

Scenario 1: The star’s center $X$ comes from $S_{1}$. For the star’s main edge
$(X,Y)$, the constraint $(\emptyset,\\{X,Y\\},m)$ exists in
$\textsf{DC}^{\prime}$. Set $\delta_{\\{X,Y\\}\mid\emptyset}=1$.

    * –

Scenario 2: The star’s center $X$ comes from $T_{2}$. For every petal $Y$ of
the star, the constraint $(\emptyset,\\{X,Y\\},m)$ exists in
$\textsf{DC}^{\prime}$. Set $\delta_{\\{X,Y\\}\mid\emptyset}=1$.

  * •

Consider each non-trivial source SCC. Let $(X,Y)$ be the main edge of the SCC.
The constraint $(\emptyset,\\{X,Y\\},m)$ exists in $\textsf{DC}^{\prime}$. Set
$\delta_{\\{X,Y\\}\mid\emptyset}=1$.

The other variables that have not yet been mentioned are all set to 0.

It is tedious but straightforward to verify that all the constraints of the
dual modular LP are fulfilled. To confirm that the objective function indeed
evaluates to (29), observe:

  * •

There are $c_{1}+|S|$ constraints of the form $(\emptyset,\\{X,Y\\},m)$ with
$\delta_{\\{X,Y\\}\mid\emptyset}=1$. Specifically, $c_{1}$ of them come from
the roots of the non-trivial source SCCs, $|S_{1}|$ of them come from the star
center vertices in $S_{1}$, and $|S_{2}|$ of them come from the petal vertices
in $S_{2}$.

  * •

There are $n_{1}+n_{2}+|T_{1}|-2c_{1}-|S_{1}|$ of the form
$(\\{X\\},\\{X,Y\\},\lambda)$ with $\delta_{\\{X,Y\\}\mid\\{X\\}}=1$.
Specifically, $n_{1}-2c_{1}$ of them come from the non-main edges of the non-
trivial source SCCs, $n_{2}$ of them come from the vertices that are not in
any non-trivial source SCC and are not in $S\cup T$, and $|T_{1}|-|S_{1}|$ of
them come from the petal vertices that are (i) in $T_{1}$ but (ii) not in the
main edges of their respective stars.

We now conclude the whole proof of Lemma 4.1.

##  Appendix C Proof of Lemma 5.1

By definition, $\log(\mathit{polymat}_{\mathit{undir}}(m,\lambda,P))$ equals
the optimal value of the following LP:

Polymatroid LP: maximize $h(V_{P})$, from all set functions $h(\cdot)$ over
$V_{P}$, subject to
---
(I) |  $h(\emptyset)=0$
(II) |  $h(\\{X,Y\\})\leq\log m$ $\forall\\{X,Y\\}\in E_{P}$
(III) |  $h(\\{X,Y\\})-h(\\{X\\})\leq\log\lambda$ $\forall\\{X,Y\\}\in E_{P}$
(IV) |  $h(\mathcal{X}\cup\mathcal{Y})+h(\mathcal{X}\cap\mathcal{Y})\leq h(\mathcal{X})+h(\mathcal{Y})$ $\forall\mathcal{X},\mathcal{Y}\subseteq V_{P}$
(V) |  $h(\mathcal{X})\leq h(\mathcal{Y})$ $\forall\mathcal{X}\subseteq\mathcal{Y}\subseteq V_{P}$

To see that the above is an instance of linear programming, one can view a set
function $h$ over $V_{P}$ as a point in a $2^{|V_{P}|}$-dimensional space,
where each dimension is a different subset of $V_{P}$. Consequently, for any
subset $\mathcal{X}\subseteq V_{P}$, $h(\mathcal{X})$ can be regarded as the
“coordinate” of this point on the dimension $\mathcal{X}$.

###  C.1 Upper Bounding the Objective Function

First, we will show that (22) is an upper bound of
$\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)$. More precisely, for every
feasible solution $h(.)$ to the polymatroid LP, we will prove:

$\displaystyle h(V_{P})$ $\displaystyle\leq$ $\displaystyle\log
m+(k-2)\log\lambda$ (30) $\displaystyle h(V_{P})$ $\displaystyle\leq$
$\displaystyle(k_{\mathit{cycle}}/2+\beta)\log
m+(k_{\mathit{star}}-2\beta)\log\lambda.$ (31)

This implies that $\exp_{2}(h(V_{P}))$ is always bounded by the right hand
side of (22) and, hence, so is
$\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)$.

Proof of (30). Let us order the vertices in $V_{P}$ as $A_{1},A_{2},...,A_{k}$
with the property that, for each $i\in[2,k]$, the vertex $A_{i}$ is adjacent
in $P$ to at least one vertex $A_{j}$ with $j<i$. We will denote this value of
$j$ as $\mathit{back}(i)$. Such an ordering definitely exists because $P$ is
connected. For $i\geq 3$, define $A_{[i]}=\\{A_{1},A_{2},...,A_{i}\\}$.

To start with, let us observe that, by the constraint (IV) of the polymatroid
LP, the inequality

$\displaystyle h(A_{[i]})+h(A_{\mathit{back}(i)})\leq
h(A_{[i-1]})+h(A_{\mathit{back}(i)},A_{i})$ (32)

holds for all $i\in[2,k]$. Thus:

$\displaystyle h(V_{P})$ $\displaystyle=$ $\displaystyle
h(A_{1},A_{2})+\sum_{i=3}^{k}h(A_{[i]})-h(A_{[i-1]})$
$\displaystyle(\textrm{by \eqref{eqn:polymat:upper1-help}})$
$\displaystyle\leq$ $\displaystyle
h(A_{1},A_{2})+\sum_{i=3}^{k}h(A_{\mathit{back}(i)},A_{i})-h(A_{\mathit{back}(i)})$
$\displaystyle\leq$ $\displaystyle\log m+(k-2)\log\lambda.$

The last step used constraints (II) and (III) of the polymatroid LP.

Proof of (31). For each cycle $\pentagon_{i}$ ($i\in[\alpha]$) in the
fractional edge-cover decomposition of $P$, define $V(\pentagon_{i})$ as the
set of vertices in $\pentagon_{i}$ and set
$k(\pentagon_{i})=|V(\pentagon_{i})|$. Likewise, for each star $\star_{j}$
($j\in[\beta]$), define $V(\star_{j})$ as the set of vertices in $\star_{j}$
and set $k(\star_{j})=|V(\star_{j})|$. We aim to prove

$\displaystyle\text{for each $i\in[\alpha]$:
}h(V(\pentagon_{i}))\leq(k(\pentagon_{i})/2)\log m;$ (33)
$\displaystyle\text{for each $j\in[\beta]$: }h(V(\star_{j}))\leq\log
m+(k(\star_{j})-2)\log\lambda.$ (34)

Once this is done, we can establish (31) as follows. First, from constraint
(IV), we know $h(\mathcal{X}\cup\mathcal{Y})\leq
h(\mathcal{X})+h(\mathcal{Y})$ for any disjoint
$\mathcal{X},\mathcal{Y}\subseteq V_{P}$; call this the disjointness rule.
Then, we can derive

$\displaystyle h(V_{P})$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{\alpha}h(V(\pentagon_{i}))+\sum_{j=1}^{\beta}h(V(\star_{j}))\hskip
5.69054pt(\textrm{disjointness rule})$ $\displaystyle(\textrm{by
\eqref{eqn:polymat:upper2-help1}, \eqref{eqn:polymat:upper2-help2}})$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{\alpha}\frac{k(\pentagon_{i})}{2}\log
m+\sum_{j=1}^{\beta}(\log m+(k(\star_{j})-2)\log\lambda)$ $\displaystyle=$
$\displaystyle(k_{\mathit{cycle}}/2+\beta)\log
m+(k_{\mathit{star}}-2\beta)\log\lambda$

as desired.

We proceed to prove (33). Let us arrange the vertices of $\pentagon_{i}$ in
clockwise order as $X_{1},X_{2},...,X_{k(\pentagon_{i})}$. For $t\geq 3$,
define $X_{[t]}=\\{X_{1},X_{2},...,X_{t}\\}$. Applying the disjointness rule,
we get

$\displaystyle h(V(\pentagon_{i}))$ $\displaystyle\leq$ $\displaystyle
h(X_{1},X_{k(\pentagon_{i})})+\sum_{t=2}^{k(\pentagon_{i})-1}h(X_{t}).$ (35)

Equipped with the above, we can derive

$\displaystyle k(\pentagon_{i})\cdot\log m\hskip 5.69054pt(\textrm{by
constraint (II)})$
$\displaystyle\geq\Big{(}\sum_{t=1}^{k(\pentagon_{i})-1}h(X_{t},X_{t+1})\Big{)}+h(\\{X_{k(\pentagon_{i})},X_{1}\\})$
$\displaystyle(\textrm{the next few steps will apply constraint (IV)})$
$\displaystyle\geq
h(X_{[3]})+h(X_{2})+\Big{(}\sum_{t=3}^{k(\pentagon_{i})-1}h(X_{t},X_{t+1})\Big{)}+h(X_{k(\pentagon_{i})},X_{1})$
$\displaystyle\geq
h(X_{[4]})+h(X_{2})+h(X_{3})+\Big{(}\sum_{t=4}^{k(\pentagon_{i})-1}h(X_{t},X_{t+1})\Big{)}+h(X_{k(\pentagon_{i})},X_{1})$
$\displaystyle...$ $\displaystyle\geq
h(X_{[k(\pentagon_{i})]})+\Big{(}\sum_{t=2}^{k(\pentagon_{i})-1}h(X_{t})\Big{)}+h(X_{k(\pentagon_{i})},X_{1})$
$\displaystyle(\textrm{the next step applies \eqref{eqn:polymat:upper2-help3}
and $V(\pentagon_{i})=X_{[k(\pentagon_{i})]}$})$ $\displaystyle\geq 2\cdot
h(V(\pentagon_{i}))\hskip 14.22636pt$

as claimed in (33).

It remains to prove (34). Let us label the vertices in $\star_{j}$ as
$Y_{1},Y_{2},...,$ $Y_{k(\star_{j})}$ with $Y_{1}$ being the center vertex.
For $t\geq 3$, define $Y_{[t]}=\\{Y_{1},$ $Y_{2},...,Y_{t}\\}$. Then:

$\displaystyle h(V(\star_{j}))$ $\displaystyle=$ $\displaystyle
h(Y_{1},Y_{2})+\sum_{t=3}^{k(\star_{j})}h(Y_{[t]})-h(Y_{[t-1]})$
$\displaystyle(\textrm{by constraint (IV)})$ $\displaystyle\leq$
$\displaystyle
h(Y_{1},Y_{2})+\sum_{t=3}^{k(\star_{j})}(h(Y_{1},Y_{t})-h(Y_{1}))$
$\displaystyle(\textrm{by constraints (II), (III)})$ $\displaystyle\leq$
$\displaystyle\log m+(k(\star_{j})-2)\log\lambda$

as claimed in (34).

###  C.2 Constructing an Optimal Set Function

To prove Lemma 5.1, we still need to show that
$\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)$ is at least the right hand
side of (22). For this purpose, it suffices to prove (i) when
$\lambda\leq\sqrt{m}$, there is a feasible set function $h^{*}$ whose
$h^{*}(V_{P})$ equals the right hand side of (30), and (ii) when
$\lambda>\sqrt{m}$, there is a feasible set function $h^{*}$ whose
$h^{*}(V_{P})$ equals the right hand side of (31). This subsection will
construct these set functions explicitly.

Case $\lambda\leq\sqrt{m}$. In this scenario, the function $h^{*}$ is easy to
design. For each $\mathcal{X}\subseteq V_{P}$, set

$\displaystyle h^{*}(\mathcal{X})=\begin{cases}0&\text{if
$\mathcal{X}=\emptyset$}\\\ \log
m+(|\mathcal{X}|-2)\log\lambda&\text{otherwise}\end{cases}$ (36)

Obviously, $h^{*}(V_{P})=\log m+(|V_{P}|-2)\log\lambda$, as needed. It remains
to explain why this $h^{*}$ is a feasible solution to the polymatroid LP. We
prove as follows.

Constraints (I), (II), and (III) are trivial to verify and omitted. Regarding
(IV), first note that the constraint is obviously true if $\mathcal{X}$ or
$\mathcal{Y}$ is empty. If neither of them is empty, we can derive:

$\displaystyle
h^{*}(\mathcal{X}\cup\mathcal{Y})+h^{*}(\mathcal{X}\cap\mathcal{Y})$
$\displaystyle=$ $\displaystyle 2\log
m+(|\mathcal{X}\cup\mathcal{Y}|+|\mathcal{X}\cap\mathcal{Y}|-4)\log\lambda$
(37) $\displaystyle=$ $\displaystyle 2\log
m+(|\mathcal{X}|+|\mathcal{Y}|-4)\log\lambda$ $\displaystyle=$ $\displaystyle
h^{*}(\mathcal{X})+h^{*}(\mathcal{Y})$

as needed. Now, consider constraint (V). If $\mathcal{X}=\emptyset$, the
constraint holds because $h^{*}(\mathcal{Y})=\log
m+(|\mathcal{Y}|-2)\log\lambda\geq\log m-\log\lambda\geq 0$. If
$X\neq\emptyset$, then

$\displaystyle h^{*}(\mathcal{X})$ $\displaystyle=$ $\displaystyle\log
m+(|\mathcal{X}|-2)\log\lambda$ $\displaystyle\leq$ $\displaystyle\log
m+(|\mathcal{Y}|-2)\log\lambda$ $\displaystyle=$ $\displaystyle
h^{*}(\mathcal{Y}).$

Case $\lambda>\sqrt{m}$. Let us look at the fractional edge-cover
decomposition of $P$: $(\pentagon_{1},...,\pentagon_{\alpha}$,
$\star_{1},...,$ $\star_{\beta})$. As before, for each $i\in[\alpha]$, define
$V(\pentagon_{i})$ as the set of vertices in the cycle $\pentagon_{i}$; for
each $j\in[\beta]$, define $V(\star_{j})$ as the set of vertices in the star
$\star_{j}$.

To design the function $h^{*}$, for each $\mathcal{X}\subseteq V_{P}$, we
choose the value $h^{*}(\mathcal{X})$ by the following rules.

  * •

(Rule 1): If $\mathcal{X}=\emptyset$, then $h^{*}(\mathcal{X})=0$.

  * •

(Rule 2): if $\mathcal{X}\subseteq V(\pentagon_{i})$ for some $i\in[\alpha]$
but $\mathcal{X}\neq\emptyset$, then
$h^{*}(\mathcal{X})=\frac{|\mathcal{X}|}{2}\log m$.

  * •

(Rule 3): if $\mathcal{X}\subseteq V(\star_{j})$ for some $j\in[\beta]$ but
$\mathcal{X}\neq\emptyset$, then $h^{*}(\mathcal{X})=\log
m+(|\mathcal{X}|-2)\log\lambda$.

  * •

(Rule 4): Suppose that none of the above rules applies. For each
$i\in[\alpha]$, define $\mathcal{Y}_{i}=\mathcal{X}\cap V(\pentagon_{i})$;
similarly, for each $j\in[\beta]$, define $\mathcal{Z}_{j}=\mathcal{X}\cap
V(\star_{j})$. Then:

$\displaystyle h^{*}(\mathcal{X})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}(\mathcal{Y}_{i})+\sum_{j=1}^{\beta}h^{*}(\mathcal{Z}_{j}).$
(38)

The above equation is well-defined because each $h^{*}(\mathcal{Y}_{i})$ can
be computed using Rules 1 and 2, and each $h^{*}(\mathcal{Z}_{j})$ can be
computed using Rules 1 and 3.

As a remark, our construction ensures that (38) holds for all
$\mathcal{X}\subseteq V_{P}$.

It is easy to check that
$h^{*}(V_{P})=\sum_{i=1}^{\alpha}h^{*}(V(\pentagon_{i}))+\sum_{j=1}^{\beta}h^{*}(V(\star_{j}))$,
which is $(k_{\mathit{cycle}}/2+\beta)\log
m+(k_{\mathit{star}}-2\beta)\log\lambda$, as needed. It suffices to verify the
feasibility of $h^{*}$.

Constraint (I) is guaranteed by Rule 1. Next, we will discuss constraints (II)
and (III) together. The verification is easy (and hence omitted) if
$\\{X,Y\\}$ is a cycle edge or a star edge. Now, consider that $\\{X,Y\\}$ is
neither a cycle edge nor a star edge. By the properties of fractional edge-
cover decomposition, one of the following must occur:

  * •

(C-1) $X$ and $Y$ are in two different cycles;

  * •

(C-2) $X$ and $Y$ are in two different stars;

  * •

(C-3) one of $X$ and $Y$ is in a cycle and the other is in a star.

In all the above scenarios, it holds that
$h^{*}(\\{X,Y\\})=h^{*}(\\{X\\})+h^{*}(\\{Y\\})$. Thus, to confirm (II), it
suffices to show $h^{*}(\\{X\\})+h^{*}(\\{Y\\})\leq\log m$, and to confirm
(III), it suffices to show $h(\\{Y\\})\leq\log\lambda$. It is rudimentary to
verify both of these inequalities using Rules 2 and 3 and the fact $\log
m<2\log\lambda$.

Constraint (IV) is trivially true if either $\mathcal{X}$ or $\mathcal{Y}$ is
empty. Now, assume that neither is empty. If
$\mathcal{X},\mathcal{Y}\subseteq\mathcal{V}(\pentagon_{i})$ for some
$i\in[\alpha]$, we have:

$\displaystyle
h^{*}(\mathcal{X}\cup\mathcal{Y})+h^{*}(\mathcal{X}\cap\mathcal{Y})$
$\displaystyle=\frac{|\mathcal{X}\cap\mathcal{Y}|+|\mathcal{X}\cup\mathcal{Y}|}{2}\log
m$ $\displaystyle=\frac{|\mathcal{X}|+|\mathcal{Y}|}{2}\log m$
$\displaystyle=h^{*}(\mathcal{X})+h^{*}(\mathcal{Y}).$

If $\mathcal{X},\mathcal{Y}\subseteq\mathcal{V}(\star_{j})$ for some
$j\in[\beta]$, the reader can verify (IV) with the same derivation in (37).

Next, we consider arbitrary $\mathcal{X},\mathcal{Y}\subseteq\mathcal{V}$.
Define for each $i\in[\alpha]$ and $j\in[\beta]$:

$\displaystyle\mathcal{X}^{\mathit{cycle}}_{i}$ $\displaystyle=$
$\displaystyle\mathcal{X}\cap\mathcal{V}(\pentagon_{i})$ (39)
$\displaystyle\mathcal{X}^{\mathit{star}}_{j}$ $\displaystyle=$
$\displaystyle\mathcal{X}\cap\mathcal{V}(\star_{j})$ (40)
$\displaystyle\mathcal{Y}^{\mathit{cycle}}_{i}$ $\displaystyle=$
$\displaystyle\mathcal{Y}\cap\mathcal{V}(\pentagon_{i})$ (41)
$\displaystyle\mathcal{Y}^{\mathit{star}}_{j}$ $\displaystyle=$
$\displaystyle\mathcal{Y}\cap\mathcal{V}(\star_{j}).$ (42)

We can derive:

$\displaystyle h^{*}(\mathcal{X}\cup\mathcal{Y})$ $\displaystyle(\textrm{by
Rule 4})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}((\mathcal{X}\cup\mathcal{Y})\cap\mathcal{V}(\pentagon_{i}))+\sum_{j=1}^{\beta}h^{*}((\mathcal{X}\cup\mathcal{Y})\cap\mathcal{V}(\star_{j}))$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}(\mathcal{X}^{\mathit{cycle}}_{i}\cup\mathcal{Y}^{\mathit{cycle}}_{i})+\sum_{j=1}^{\beta}h^{*}(\mathcal{X}^{\mathit{star}}_{j}\cup\mathcal{Y}^{\mathit{star}}_{j})$

and similarly:

$\displaystyle h^{*}(\mathcal{X}\cap\mathcal{Y})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}((\mathcal{X}\cap\mathcal{Y})\cap\mathcal{V}(\pentagon_{i}))+\sum_{j=1}^{\beta}h^{*}((\mathcal{X}\cap\mathcal{Y})\cap\mathcal{V}(\star_{j}))$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}(\mathcal{X}^{\mathit{cycle}}_{i}\cap\mathcal{Y}^{\mathit{cycle}}_{i})+\sum_{j=1}^{\beta}h^{*}(\mathcal{X}^{\mathit{star}}_{j}\cap\mathcal{Y}^{\mathit{star}}_{j}).$

Recall that (IV) has been validated in the scenario where (i) $\mathcal{X}$
and $\mathcal{Y}$ are contained in the same cycle, or (ii) they are contained
in the same star. Thus, it holds for each $i\in[\alpha]$ and $j\in[\beta]$
that

$\displaystyle
h^{*}(\mathcal{X}^{\mathit{cycle}}_{i}\cup\mathcal{Y}^{\mathit{cycle}}_{i})+h^{*}(\mathcal{X}^{\mathit{cycle}}_{i}\cap\mathcal{Y}^{\mathit{cycle}}_{i})\leq
h^{*}(\mathcal{X}^{\mathit{cycle}}_{i})+h^{*}(\mathcal{Y}^{\mathit{cycle}}_{i})$
(43) $\displaystyle
h^{*}(\mathcal{X}^{\mathit{star}}_{j}\cup\mathcal{Y}^{\mathit{star}}_{j})+h^{*}(\mathcal{X}^{\mathit{star}}_{j}\cap\mathcal{Y}^{\mathit{star}}_{j})\leq
h^{*}(\mathcal{X}^{\mathit{star}}_{j})+h^{*}(\mathcal{Y}^{\mathit{star}}_{j}).$
(44)

Equipped with these facts, we get:

$\displaystyle
h^{*}(\mathcal{X}\cup\mathcal{Y})+h^{*}(\mathcal{X}\cap\mathcal{Y})$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}(\mathcal{X}^{\mathit{cycle}}_{i}\cup\mathcal{Y}^{\mathit{cycle}}_{i})+h^{*}(\mathcal{X}^{\mathit{cycle}}_{i}\cap\mathcal{Y}^{\mathit{cycle}}_{i})+$
$\displaystyle\sum_{j=1}^{\beta}h^{*}(\mathcal{X}^{\mathit{star}}_{j}\cup\mathcal{Y}^{\mathit{star}}_{j})+h^{*}(\mathcal{X}^{\mathit{star}}_{j}\cap\mathcal{Y}^{\mathit{star}}_{j})$
$\displaystyle(\textrm{by \eqref{eqn:app:h*-verification-help2} and
\eqref{eqn:app:h*-verification-help3}})$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}(\mathcal{X}^{\mathit{cycle}}_{i})+h^{*}(\mathcal{Y}^{\mathit{cycle}}_{i})+\sum_{j=1}^{\beta}h^{*}(\mathcal{X}^{\mathit{star}}_{j})+h^{*}(\mathcal{Y}^{\mathit{star}}_{j})$
$\displaystyle(\textrm{by Rule 4})$ $\displaystyle=$ $\displaystyle
h^{*}(\mathcal{X})+h^{*}(\mathcal{Y}).$

This verifies the correctness of constraint (IV).

Finally, let us look at (V). This constraint is trivially met if
$\mathcal{X}=\emptyset$. Next, we assume that $\mathcal{X}$ is not empty. If
$\mathcal{Y}$ is a subset of $\mathcal{V}(\pentagon_{i})$ for some
$i\in[\alpha]$, then, by Rule 2,
$h^{*}(\mathcal{X})=\frac{|\mathcal{X}|}{2}\log
m\leq\frac{|\mathcal{Y}|}{2}\log m=h^{*}(\mathcal{Y})$. If $\mathcal{Y}$ is a
subset of $\mathcal{V}(\star_{j})$ for some $j\in[\beta]$, then, by Rule 3,
$h^{*}(\mathcal{X})=\log m+(|\mathcal{X}|-2)\log\lambda\leq\log
m+(|\mathcal{Y}|-2)\log\lambda=h^{*}(\mathcal{Y})$.

It remains to consider the situation where $\mathcal{Y}$ can be any subset of
$\mathcal{V}$. Using the definitions in (39)-(42), we have:

$\displaystyle h^{*}(\mathcal{X})$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}(\mathcal{X}^{\mathit{cycle}}_{i})+\sum_{j=1}^{\beta}h^{*}(\mathcal{X}^{\mathit{star}}_{j})\hskip
8.53581pt(\textrm{by Rule 4})$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{\alpha}h^{*}(\mathcal{Y}^{\mathit{cycle}}_{i})+\sum_{j=1}^{\beta}h^{*}(\mathcal{Y}^{\mathit{star}}_{j})$
(we have verified (V) in the scenario where $\mathcal{Y}$ is contained in a
cycle or a star) $\displaystyle(\textrm{by Rule 4})$ $\displaystyle=$
$\displaystyle h^{*}(\mathcal{Y})$

as needed to verify constraint (V).

##  Appendix D Equation (22) as an Output Size Bound and Its Tightness

We will start by proving that (22) is an asymptotic upper bound on
$|\mathit{occ}(G,P)|$ for any graph $G$ that has $m$ edges and a maximum
vertex-degree at most $\lambda$. First, we will prove that
$|\mathit{occ}(G,P)|=O(m\cdot\lambda^{k-2})$ (recall that $k$ is the number of
vertices in $P$). Identify an arbitrary spanning tree $\mathcal{T}$ of the
pattern $P$. It is rudimentary to verify that $\mathcal{T}$ has
$O(m\cdot\lambda^{k-2})$ occurrences in $G$,555There are $O(m)$ choices to map
an arbitrary edge $\mathcal{T}$ to an edge in $G$, and then $\lambda$ choices
to map each of the $k-2$ remaining vertices of $\mathcal{T}$ to a vertex in
$G$. implying that the number of occurrences of $P$ is also
$O(m\cdot\lambda^{k-2})$. Next, we will demonstrate that
$|\mathit{occ}(G,P)|=O(m^{\frac{k_{\mathit{cycle}}}{2}+\beta}\cdot\lambda^{k_{\mathit{star}}-2\beta})$.
For each $i\in[\alpha]$, let $k(\pentagon_{i})$ be the number of vertices in
$\pentagon_{i}$; for each $j\in[\beta]$, let $k(\star_{j})$ be the number of
vertices in $\star_{j}$. The fractional edge cover number of $\pentagon_{i}$
($i\in[\alpha]$) is $\rho^{*}(\pentagon_{i})=k(\pentagon_{i})/2$; this means
$\sum_{i=1}^{k}\rho^{*}(\pentagon_{i})=k(\pentagon_{i})/2=k_{\mathit{cycle}}/2$.
For each $i\in[\alpha]$, the pattern $\pentagon_{i}$ can have
$O(m^{\rho^{*}(\pentagon_{i})})$ occurrences in $G$. For each $j\in[\beta]$,
by our earlier analysis, the pattern $\star_{j}$ can have
$O(m^{k(\star_{j})-2})$ occurrences in $G$. Thus, the number of occurrences of
$P$ must be asymptotically bounded by

$\displaystyle\prod_{i=1}^{\alpha}m^{\rho^{*}(\pentagon_{i})}\cdot\prod_{j=1}^{\beta}m\cdot\lambda^{k(\star_{j})-2}=m^{\frac{k_{\mathit{cycle}}}{2}+\beta}\cdot\lambda^{k_{\mathit{star}}-2\beta}.$

The rest of this section will concentrate on the tightness of (22) as an upper
bound of $|\mathit{occ}(G,P)|$. Our objective is to prove:

######  Theorem D.1.

Fix an arbitrary integer $k\geq 2$. For any values of $m$ and $\lambda$
satisfying $m\geq\max\\{16k^{2},64\\}$ and $k\leq\lambda\leq m/(4k)$, there is
an undirected simple graph $G^{*}$ satisfying all the conditions below:

  * •

$G^{*}$ has at most $m$ edges and and a maximum vertex degree at most
$\lambda$;

  * •

For any undirected simple pattern graph $P=(V_{P},E_{P})$ that has $k$
vertices, the number of occurrences of $P$ in $G^{*}$ is at least
$\frac{1}{(4k)^{k}}\cdot\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)$, where
$\mathit{polymat}_{\mathit{undir}}(m,\lambda,P)$ is given in (22).

It is worth noting that we aim to construct a single $G^{*}$ that is a “bad”
input for all possible patterns (with $k$ vertices) simultaneously. Our proof
will deal with the case $k\leq\lambda<\sqrt{m}$ and the case
$\sqrt{m}\leq\lambda\leq m/(4k)$ separately.

Remark. The main challenge in the proof is to establish the factor
$\frac{1}{(4k)^{k}}$. There exist lower bound arguments [19, 36] that can be
used in our context to build a hard instance for each individual pattern $P$.
A naive way to form a single hard input $G^{*}$ is to combine the hard
instances of all possible patterns having $k$ vertices. But this would
introduce a gigantic factor roughly $1/2^{\Omega(k^{2})}$.

###  D.1 Case $k\leq\lambda<\sqrt{m}$

In this scenario, $G^{*}$ only needs to be the graph that consists of $\lfloor
m/\binom{\lambda}{2}\rfloor$ independent $\lambda$-cliques.666When
$\lambda<\sqrt{m}$, $\binom{\lambda}{2}=\frac{\lambda^{2}-\lambda}{2}<m$.
Hence, $G^{*}$ contains at least one clique. An occurrence of $P$ can be
formed by mapping $V_{P}$ to $k$ arbitrary distinct vertices in one
$\lambda$-clique. The number of occurrences of $P$ in $G^{*}$ is at least

$\displaystyle\big{\lfloor}\frac{m}{{\lambda\choose
2}}\big{\rfloor}\cdot{\lambda\choose k}$ $\displaystyle(\textrm{applying
${\lambda\choose k}\geq(\lambda/k)^{k}$})$ $\displaystyle\geq$
$\displaystyle\Big{(}\frac{2m}{\lambda^{2}-\lambda}-1\Big{)}\cdot(\lambda/k)^{k}$
$\displaystyle(\textrm{as $m>\lambda^{2}-\lambda$})$ $\displaystyle>$
$\displaystyle\frac{m}{\lambda^{2}-\lambda}\cdot(\lambda/k)^{k}$
$\displaystyle(\textrm{as $k\geq 2$})$ $\displaystyle>$
$\displaystyle\frac{1}{k^{k}}\cdot
m\cdot\lambda^{k-2}=\frac{1}{k^{k}}\cdot\mathit{polymat}_{\mathit{undir}}(m,\lambda,P).$

###  D.2 Case $\sqrt{m}\leq\lambda\leq m/(4k)$

We construct $G^{*}$ as follows. First, create three disjoint sets of
vertices: $V_{A},V_{B}$, and $V_{C}$, whose sizes are $\lceil\lambda/4\rceil$,
$\lceil m/(4\lambda)\rceil$, and $\lceil\sqrt{m}/4\rceil$. Because
$\lambda\leq\frac{m}{4k}$ and $m\geq 16k^{2}$, each of $V_{A}$, $V_{B}$, and
$V_{C}$ has a size at least $k$. Then, decide the edges of $G^{*}$ in the way
below:

  * •

Add an edge between each pair of vertices in $V_{B}\cup V_{C}$ (thereby
producing a clique of $\lceil m/(4\lambda)\rceil+\lceil\sqrt{m}/4\rceil$
vertices).

  * •

Add an edge $\\{u,v\\}$ for each vertex pair $(u,v)\in V_{A}\times V_{B}$.

Next, we show that $G^{*}$ has at most $m$ edges through a careful
calculation. First, the number of edges between $V_{A}$ and $V_{B}$ is

$\displaystyle\lceil\lambda/4\rceil\cdot\lceil m/(4\lambda)\rceil$
$\displaystyle\leq$ $\displaystyle(\lambda/4+1)\cdot(m/(4\lambda)+1)$
$\displaystyle=$ $\displaystyle m/16+\lambda/4+m/(4\lambda)+1$
$\displaystyle(\textrm{as $\sqrt{m}\leq\lambda\leq m$})$ $\displaystyle\leq$
$\displaystyle 5m/16+\sqrt{m}/4+1$ $\displaystyle(\textrm{as $16\leq m$})$
$\displaystyle\leq$ $\displaystyle 7m/16.$

The number of edges between $V_{B}$ and $V_{C}$ is:

$\displaystyle\lceil m/(4\lambda)\rceil\cdot\lceil\sqrt{m}/4\rceil$
$\displaystyle\leq$ $\displaystyle(m/(4\lambda)+1)\cdot(\sqrt{m}/4+1)$
$\displaystyle=$ $\displaystyle m^{1.5}/(16\lambda)+m/(4\lambda)+\sqrt{m}/4+1$
$\displaystyle(\textrm{as $\sqrt{m}\leq\lambda$})$ $\displaystyle\leq$
$\displaystyle m/16+\sqrt{m}/2+1$ $\displaystyle(\textrm{as $16\leq m$})$
$\displaystyle\leq$ $\displaystyle m/4.$

The number of edges between vertices in $V_{B}$ is:

$\displaystyle\lceil m/(4\lambda)\rceil\cdot(\lceil m/(4\lambda)\rceil-1)/2$
$\displaystyle\leq$ $\displaystyle(m/(4\lambda)+1)\cdot(m/(4\lambda))/2$
$\displaystyle=$ $\displaystyle m^{2}/(32\lambda^{2})+m/(8\lambda)$
$\displaystyle(\textrm{as $\sqrt{m}\leq\lambda$})$ $\displaystyle\leq$
$\displaystyle m/32+\sqrt{m}/8\leq 5m/32$

The number of edges between vertices in $V_{C}$ is:

$\displaystyle\lceil\sqrt{m}/4\rceil\cdot(\lceil\sqrt{m}/4-1)/2$
$\displaystyle\leq$ $\displaystyle(\sqrt{m}/4+1)\cdot(\sqrt{m}/4)/2$
$\displaystyle=$ $\displaystyle m/32+\sqrt{m}/8\leq 5m/32.$

Thus, the total number of edges in $G^{*}$ is at most
$7m/16+m/4+5m/32+5m/32=m$.

The maximum vertex degree in $G^{*}$ is decided by the vertices in $V_{B}$ and
equals

$\displaystyle\lceil\lambda/4\rceil+\lceil
m/(4\lambda)\rceil-1+\lceil\sqrt{m}/4\rceil$ $\displaystyle\leq$
$\displaystyle\lambda/4+m/(4\lambda)+\sqrt{m}/4+2$ $\displaystyle(\textrm{as
$\lambda\geq\sqrt{m}$})$ $\displaystyle\leq$ $\displaystyle
3\lambda/4+2\leq\lambda.$

Therefore, $G^{*}$ satisfies the requirement in the first bullet of Theorem
D.1.

The rest of the proof will focus on the theorem’s second bullet. Let $P$ be an
arbitrary pattern with $k$ vertices, and take a fractional edge-cover
decomposition of $P$: $(\pentagon_{1},$ $...,$ $\pentagon_{\alpha},$
$\star_{1},$ $...,\star_{\beta})$. Define $k_{\mathit{star}}$ and
$k_{\mathit{cycle}}$ in the same way as in (21) and (20). We claim:

######  Lemma D.2.

There is an integer $s\in[0,\beta]$ under which we can divide the vertices of
$P$ into disjoint sets $U_{A}$, $U_{B}$ and $U_{C}$ such that

  * •

$|U_{A}|=k_{\mathit{star}}-\beta-s$, $|U_{B}|=\beta-s$,
$|U_{C}|=k_{\mathit{cycle}}+2s$;

  * •

$P$ has no edges between $U_{A}$ and $U_{C}$;

  * •

$P$ has no edges between any two vertices in $U_{A}$.

The proof of the lemma is non-trivial and deferred to the end of this section.
An occurrence of $P$ in $G^{*}$ can be formed through the three steps below:

  1. 1.

Map $U_{A}$ to $|U_{A}|$ distinct vertices in $V_{A}$.

  2. 2.

Map $U_{B}$ to $|U_{B}|$ distinct vertices in $V_{B}$.

  3. 3.

Map $U_{C}$ to $|U_{C}|$ distinct vertices in $V_{C}$.

Each step is carried out independently from the other steps. Hence, the number
of occurrences of $P$ in $G^{*}$ is at least

$\displaystyle\binom{\lambda/4}{k_{\mathit{star}}-\beta-s}\cdot\binom{\frac{m}{4\lambda}}{\beta-s}\cdot\binom{\sqrt{m}/4}{k_{\mathit{cycle}}+2s}$
$\displaystyle\geq$
$\displaystyle\big{(}\frac{\lambda/4}{k_{\mathit{star}}-\beta-s}\big{)}^{k_{\mathit{star}}-\beta-s}\cdot\big{(}\frac{\frac{m}{4\lambda}}{\beta-s}\big{)}^{\beta-s}\cdot\big{(}\frac{\sqrt{m}/4}{k_{\mathit{cycle}}+2s}\big{)}^{k_{\mathit{cycle}}+2s}$
$\displaystyle\geq$
$\displaystyle\frac{\lambda^{k_{\mathit{star}}-\beta-s}}{4^{k_{\mathit{star}}-\beta-s}\cdot
k^{k_{\mathit{star}}-\beta-s}}\cdot\frac{m^{\beta-s}}{4^{\beta-s}\cdot\lambda^{\beta-s}\cdot
k^{\beta-s}}\cdot\frac{m^{k_{\mathit{cycle}}/2+s}}{4^{k_{\mathit{cycle}}+2s}\cdot
k^{k_{\mathit{cycle}}+2s}}$ $\displaystyle=$
$\displaystyle\frac{1}{(4k)^{k}}\cdot
m^{\frac{k_{\mathit{cycle}}}{2}+\beta}\cdot\lambda^{k_{\mathit{star}}-2\beta}=\frac{1}{(4k)^{k}}\cdot\mathit{polymat}_{\mathit{undir}}(m,\lambda,P).$

Proof of Lemma D.2. With each vertex $X$ in the pattern graph
$P=(V_{P},E_{P})$, we associate a variable $\nu(X)\geq 0$ (equivalently, $\nu$
is a function from $V_{P}$ to ≥0). Consider the following LP defined on these
variables.

vertex-pack LP max $\sum_{X\in V_{P}}\nu(X)$ subject to
---
|  $\sum\limits_{X:X\in F}\nu(X)\leq 1$ $\forall F\in E_{P}$
|  $\nu(X)\geq 0$ $\forall X\in V_{P}$

A feasible solution $\nu$ is said to be half-integral if
$\nu(X)\in\\{0,\frac{1}{2},1\\}$ for each $X\in V_{P}$.

Consider any fractional edge-cover decomposition of $P$:
$(\pentagon_{1},...,\pentagon_{\alpha},\star_{1},...,\star_{\beta})$. Recall
that each star $\star_{j}$ ($j\in[\beta]$) contains a vertex designated as the
center. We refer to every other vertex in the star as a petal.

######  Lemma D.3.

For the vertex-pack LP, there exists a half-integral optimal solution
$\\{\nu^{*}(X)\mid X\in V_{P}\\}$ satisfying all the conditions below.

  * •

$\nu^{*}(X)=0.5$ for every vertex $X$ in
$\pentagon_{1},...\pentagon_{\alpha}$.

  * •

For every $j\in[\beta]$, the function $\nu^{*}$ has the properties below.

    * –

If $\star_{j}$ has at least two edges, then $\nu^{*}(X)=0$ holds for the
star’s center $X$ and $\nu^{*}(Y)=1$ holds for every petal $Y$.

    * –

If $\star_{j}$ has only one edge $\\{X,Y\\}$ — in which case we call
$\star_{j}$ a “one-edge star” — then $\nu^{*}(X)+\nu^{*}(Y)=1$.

###### Proof.

Let us first define the dual of vertex-pack LP. Associate each edge $F\in
E_{P}$ with a variable $w(F)\geq 0$ (equivalently, $w$ is a function from
$E_{P}$ to ≥0). Then, the dual is:

edge-cover LP min $\sum_{F\in E_{P}}w(F)$ subject to
---
|  $\sum\limits_{F\in E_{P}:X\in F}w(F)\geq 1$ $\forall X\in V_{P}$
|  $w(F)\geq 0$ $\forall F\in E_{P}$

The given fractional edge-cover decomposition implies an optimal solution
$\\{w^{*}(F)\mid F\in E_{p}\\}$ to the edge-cover LP satisfying:

  * •

$w^{*}(F)=0.5$ for every edge $F$ in $\pentagon_{1},...\pentagon_{\alpha}$;

  * •

$w^{*}(F)=1$ for every edge $F$ in $\star_{1},...,\star_{\beta}$;

  * •

$w^{*}(F)=0$ for every other edge $F\in E_{p}$.

By the complementary slackness theorem, the function $w^{*}$ implies an
optimal solution $\\{\nu^{\prime}(X)\mid X\in V_{P}\\}$ to the vertex-pack LP
with the properties below.

  * •

P1: For every edge $\\{X,Y\\}\in E_{p}$, if $w^{*}(\\{X,Y\\})>0$, then
$\nu^{\prime}(X)+\nu^{\prime}(Y)=1$.

  * •

P2: For every vertex $X$ satisfying $\sum_{X\in F}w^{*}(F)>1$,
$\nu^{\prime}(X)=0$.

From the above, we can derive additional properties of the solution
$\\{\nu^{\prime}(X)\mid X\in V_{P}\\}$.

  * •

P3: $\nu^{\prime}(X)=0.5$ for every vertex $X$ in
$\pentagon_{1},...,\pentagon_{\alpha}$. To see why, consider any
$\pentagon_{i}$ ($i\in[\alpha]$). Let $X_{1},X_{2},...,X_{\ell}$ (for some
$\ell\geq 3$) be the vertices of $\pentagon_{i}$ in clockwise order. Property
P1 yields $\ell$ equations: $\nu^{\prime}(X_{j})+\nu^{\prime}(X_{j+1})=1$ for
$j\in[\ell-1]$ and $\nu^{\prime}(X_{\ell})+\nu^{\prime}(X_{1})=1$. Solving the
system of these equations gives $\nu^{\prime}(X_{j})=0.5$ for each
$j\in[\ell]$.

  * •

For every $j\in[\beta]$, we have:

    * –

P4-1: If $\star_{j}$ has at least two edges, then $\nu^{\prime}(X)=0$ holds
for the star’s center $X$ and $\nu^{\prime}(Y)=1$ for every petal $Y$. To see
why, notice that $\sum_{F\in E_{P}:X\in F}w^{*}(F)$ is precisely the number of
edges in $\star_{j}$ and, hence, $\sum_{F\in E_{P}:X\in F}w^{*}(F)>1$. Thus,
P2 asserts $\nu^{\prime}(X)=0$. It then follows from P1 that
$\nu^{\prime}(Y)=1-\nu^{\prime}(X)=1$ for every petal $Y$.

    * –

P4-2: If $\star_{j}$ has only one edge $\\{X,Y\\}$, then
$\nu^{\prime}(X)+\nu^{\prime}(Y)=1$. This directly follows from ${\bf P1}$ and
the fact that $w^{*}(\\{X,Y\\})=1$.

Now, we show how to construct $\nu^{*}(.)$. If $\nu^{\prime}(.)$ is already
half-integral, then we set $\nu^{*}(X)=\nu^{\prime}(X)$ for all $X\in V_{P}$
and finish. Otherwise, set

  * •

$\nu^{*}(X)=\nu^{\prime}(X)$ for every $X\in V_{P}$ with
$\nu^{\prime}(X)\in\\{0,1,\frac{1}{2}\\}$;

  * •

$\nu^{*}(X)=0$ for every $X\in V_{P}$ with $0<\nu^{\prime}(X)<1/2$;

  * •

$\nu^{*}(X)=1$ for every $X\in V_{P}$ with $1/2<\nu^{\prime}(X)<1$.

We need to verify that $\nu^{*}(.)$ meets the conditions listed in the
statement of Lemma D.3. Clearly, $\nu^{*}(X)=\nu^{\prime}(X)=1/2$ for every
vertex $X$ in $\pentagon_{1},...\pentagon_{\alpha}$ (property P3). For each
$j\in[\beta]$, if $\star_{j}$ has at least two edges, then
$\nu^{*}(X)=\nu^{\prime}(X)=0$ holds for the star’s center $X$ and
$\nu^{*}(Y)=\nu^{\prime}(Y)=1$ holds for every petal $Y$ (property P4-1). If
$\star_{j}$ has only one edge $\\{X,Y\\}$ — that is, $\star_{j}$ is a one-edge
star — property P4-2 tells us that $\nu^{\prime}(X)+\nu^{\prime}(Y)=1$. If
$\nu^{\prime}(X)=\nu^{\prime}(Y)=1/2$, then $\nu^{*}(X)+\nu^{*}(Y)=1/2+1/2=1$.
Otherwise, one vertex of $\\{X,Y\\}$ — say $X$ — satisfies
$0<\nu^{\prime}(X)<1/2$, and the other vertex satisfies
$1/2<\nu^{\prime}(Y)<1$. Our construction ensures that
$\nu^{*}(X)+\nu^{*}(Y)=0+1=1$.

It remains to check that $\\{\nu^{*}(X)\mid X\in V_{P}\\}$ is indeed an
optimal solution to the vertex-pack LP. First, we prove the the solution’s
feasibility. For this purpose, given any edge $F=\\{X,Y\\}\in E_{P}$, we must
show $\nu^{*}(X)+\nu^{*}(Y)\leq 1$. Assume there exists an edge
$F=\\{X,Y\\}\in E_{P}$ such that $\nu^{*}(X)+\nu^{*}(Y)>1$. Because
$\nu^{*}(.)$ is half-integral, in this situation at least one vertex in
$\\{X,Y\\}$ — say $X$ — must receive value $\nu^{*}(X)=1$. We proceed
differently depending on the value of $\nu^{*}(Y)$.

  * •

$\nu^{*}(Y)=1/2$. By how $\nu^{*}$ is constructed from $\nu^{\prime}$, in this
case we must have $\nu^{\prime}(X)>1/2$ and $\nu^{\prime}(Y)=1/2$. But then
$\nu^{\prime}(X)+\nu^{\prime}(Y)>1$, violating the fact that $\nu^{\prime}(.)$
is a feasible solution to the vertex-pack LP.

  * •

$\nu^{*}(Y)=1$. By how $\nu^{*}$ is constructed, we must have