<figure><img src="image_30.png" /><figcaption>Figure 1 Four points in three dimensions. With the monoid (Z, max) we have f({p, r, s}) = 8.</figcaption></figure>

## 3.2 Range Trees

Consider dimension $i \in \{1, \dots, d\}$ and enumerate the points in $Q$ as $q^{(1)}, \dots, q^{(r)}$ such that $q_i^{(j)} \le q_i^{(j+1)}$, for instance by ordering after the $i$th coordinate and breaking ties lexicographically. Define $\text{med}_i(Q)$ to be the median point $q^{(\lceil r/2 \rceil)}$, and similarly $\text{min}_i(Q) = q^{(1)}$ and $\text{max}_i(Q) = q^{(r)}$. Set

$$Q_L = \{q^{(1)}, \dots, q^{(\lceil r/2 \rceil)}\}, \quad Q_R = \{q^{(1+\lceil r/2 \rceil)}, \dots, q^{(r)}\}. \qquad (8)$$

For $i \in \{1, \dots, d\}$, the range tree $R_i(Q)$ for $Q$ is a node $x$ with the following attributes:

- $L[x]$, a reference to range tree $T_i(Q_L)$, called the left child of $x$. Only exists if $|Q| > 1$.

- $R[x]$, a reference to range tree $T_i(Q_R)$, called the right child of $x$. Only exists if $|Q| > 1$.

- $D[x]$, a reference to range tree $T_{i+1}(Q)$, called the secondary, associate, or higher-dimensional structure. Only exists for $i < d$.

- $l[x] = \text{min}_i(Q)$.

- $r[x] = \text{max}_i(Q)$.

- $f[x] = f(Q)$. Only exists for $i = d$.

## Construction

Constructing a range tree for $Q$ is a straightforward recursive procedure:

**► Algorithm C (Construction).** Given integer $i \in \{1, \dots, d\}$ and a list $Q$ of points, this algorithm constructs the range tree $R_i(Q)$ with root $x$.

**C1** [Base case $Q = \{q\}$.] Recursively construct $D[x] = T_{i+1}(Q)$ if $i < d$, otherwise set $f[x] = f(q)$. Set $l[x] = r[x] = q_i$. Return $x$.

**C2** [Find median.] Determine $q = \text{med}_i Q$, $l[x] = \text{min}_i(Q)$, $r[x] = \text{max}_i(Q)$.

**C3** [Split $Q$.] Let $Q_L$ and $Q_R$ as given by (8), note that both are nonempty.

**C4** [Recurse.] Recursively construct $L[x] = R_i(Q_L)$ from $Q_L$. Recursively construct $R[x] = R_i(Q_R)$ from $Q_R$. If $i < d$ then recursively construct $D[x] = T_{i+1}(Q)$. If $i = d$ then set $f[x] = f[L[x]] \oplus f[R[x]]$.

The data structure can be viewed as a collection of binary trees whose nodes $x$ represent various subsets $P_x$ of the original point set $P$. In the interest of analysis, we now introduce a scheme for naming the individual nodes $x$, and thereby also the subsets $P_x$. Each node $x$ is identified by a string of letters from {L, R, D} as follows. Associate with $x$ a set of points, often called the *canonical subset* of $x$, as follows. For the empty string $\epsilon$ we set $P_\epsilon = P$. In general, if $Q = P_x$ then $P_{xL} = Q_L$, $P_{xR} = Q_R$ and $P_{xD} = Q$. The strings over {L, R, D} can be understood as uniquely describing a path through in the data structure; for instance, L means ‘go left’, i.e., to the left subtree, the one stored at $L[x]$’ and D means ‘go to the next dimension’, i.e., to the subtree stored at $D[x]$.’ The name of a node now describes the unique path that reaches it.
<figure><img src="image_34.png" /><figcaption>Figure 1 Four points in three dimensions. With the monoid (Z, max) we have f({p, r, s}) = 8.</figcaption></figure>

## 3.2 Range Trees

Consider dimension $i \in \{1, \dots, d\}$ and enumerate the points in $Q$ as $q^{(1)}, \dots, q^{(r)}$ such that $q_i^{(j)} \le q_i^{(j+1)}$, for instance by ordering after the $i$th coordinate and breaking ties lexicographically. Define $\text{med}_i(Q)$ to be the median point $q^{(\lceil r/2 \rceil)}$, and similarly $\text{min}_i(Q) = q^{(1)}$ and $\text{max}_i(Q) = q^{(r)}$. Set

$$Q_L = \{q^{(1)}, \dots, q^{(\lceil r/2 \rceil)}\}, \quad Q_R = \{q^{(1+\lceil r/2 \rceil)}, \dots, q^{(r)}\}. \qquad (8)$$

For $i \in \{1, \dots, d\}$, the range tree $R_i(Q)$ for $Q$ is a node $x$ with the following attributes:

- $L[x]$, a reference to range tree $T_i(Q_L)$, called the left child of $x$. Only exists if $|Q| > 1$.

- $R[x]$, a reference to range tree $T_i(Q_R)$, called the right child of $x$. Only exists if $|Q| > 1$.

- $D[x]$, a reference to range tree $T_{i+1}(Q)$, called the secondary, associate, or higher-dimensional structure. Only exists for $i < d$.

- $l[x] = \text{min}_i(Q)$.

- $r[x] = \text{max}_i(Q)$.

- $f[x] = f(Q)$. Only exists for $i = d$.

## Construction

Constructing a range tree for $Q$ is a straightforward recursive procedure:

**► Algorithm C (Construction).** Given integer $i \in \{1, \dots, d\}$ and a list $Q$ of points, this algorithm constructs the range tree $R_i(Q)$ with root $x$.

**C1** [Base case $Q = \{q\}$.] Recursively construct $D[x] = T_{i+1}(Q)$ if $i < d$, otherwise set $f[x] = f(q)$. Set $l[x] = r[x] = q_i$. Return $x$.

**C2** [Find median.] Determine $q = \text{med}_i Q$, $l[x] = \text{min}_i(Q)$, $r[x] = \text{max}_i(Q)$.

**C3** [Split $Q$.] Let $Q_L$ and $Q_R$ as given by (8), note that both are nonempty.

**C4** [Recurse.] Recursively construct $L[x] = R_i(Q_L)$ from $Q_L$. Recursively construct $R[x] = R_i(Q_R)$ from $Q_R$. If $i < d$ then recursively construct $D[x] = T_{i+1}(Q)$. If $i = d$ then set $f[x] = f[L[x]] \oplus f[R[x]]$.

The data structure can be viewed as a collection of binary trees whose nodes $x$ represent various subsets $P_x$ of the original point set $P$. In the interest of analysis, we now introduce a scheme for naming the individual nodes $x$, and thereby also the subsets $P_x$. Each node $x$ is identified by a string of letters from {L, R, D} as follows. Associate with $x$ a set of points, often called the *canonical subset* of $x$, as follows. For the empty string $\epsilon$ we set $P_\epsilon = P$. In general, if $Q = P_x$ then $P_{xL} = Q_L$, $P_{xR} = Q_R$ and $P_{xD} = Q$. The strings over {L, R, D} can be understood as uniquely describing a path through in the data structure; for instance, L means ‘go left’, i.e., to the left subtree, the one stored at $L[x]$’ and D means ‘go to the next dimension’, i.e., to the subtree stored at $D[x]$. The name of a node now describes the unique path that reaches it.
<figure><img src="image_31.png" /><figcaption>Figure 2 Part of the range tree for the points from Fig. 1. The label of node $x$ appears in red on the arrow pointing to $x$. Nodes contain $l[x]:r[x]$. The references $L[x]$ and $R[x]$ appear as children in a binary tree using usual drawing conventions. The reference $D[x]$ appears as a dashed arrow (possibly interrupted); the placement on the page follows no other logic than economy of layout and readability. References $D[x]$ from leaf nodes, such as $D[LL]$ leading to node LLD, are not shown; this conceals 12 single-node trees. The ‘3rd-dimensional nodes,’ whose names contain two Ds, show the values $f[x]$ next to the node. To ease comprehension, leaf nodes are decorated with their canonical subset, which is a singleton from $\{p, q, r, s\}$. The reader can infer the canonical subset for an internal node as the union of leaves of the subtree; for instance, $P_{DR} = \{r, s\}$. However, note that these point sets are not explicitly stored in the data structure.</figcaption></figure>

**Lemma 6.** Let $n = |P|$. Algorithm C computes the $d$-dimensional range tree for $P$ in time linear in $nd \cdot B(n, d)$.

**Proof.** We run Algorithm C on input $P$ and $i = 1$.

Disregarding the recursive calls, the running time of algorithm C on input $i$ and $Q$ is dominated by Steps C2 and C3, i.e., splitting $Q$ into two sets of equal size. It is known that this task can be performed in time linear in $|Q|$ [4]. Thus, the running time for constructing $R_i(Q)$ is linear in $|Q|$ plus the time spent in recursive calls.

This means that we can bound the running time for constructing $T_1(P)$ by bounding the sizes of the sets $P_x$ associated with every node $x$ in the data structure. If for a moment $X$ denotes the set of all these nodes then we want to bound

$$ \sum_{x \in X} |P_x| = \sum_{x \in X} |\{p \in P: p \in P_x\}| = \sum_{p \in P} |\{x \in X: p \in P_x\}|. $$

Thus, we need to determine, for given $p \in P$, the number of subsets $P_x$ in which $p$ appears. By construction, there are fewer than $d$ occurrences of $D$ in $x$. Moreover, if $x$ contains more than $h$ occurrences of either L or R then $P_x$ is empty. Thus, $x$ has at most $h+d$ letters. For two different strings $x$ and $x'$ that agree on the positions of $D$, the sets $P_x$ and $P_{x'}$ are disjoint, so $p$ appears in at most one of them. We conclude that the number of sets $P_x$ such that $p \in P_x$ is bounded by the number of ways to arrange fewer than $d$ many Ds and at most $h$ non-Ds. Using the identity $\binom{a+0}{0} + \cdots + \binom{a+b}{b} = \binom{a+b+1}{b}$ repeatedly, we compute

$$ \begin{aligned} \sum_{i=0}^{d-1} \sum_{j=0}^{h} \binom{i+j}{j} &= \sum_{i=0}^{d-1} \binom{i+h+1}{h} = \sum_{i=0}^{d-1} \binom{i+h+1}{i+1} = \\ (-1) + \sum_{i=0}^{d} \binom{i+h}{i} &= \binom{h+d+1}{d} - 1 = \frac{h+d+1}{h+1} \binom{h+d}{d} - 1 \le d \binom{d+h}{d}. \end{aligned} $$

The bound follows from aggregating this contribution over all $p \in P$.

<figure><img src="image_32.png" /></figure>
<figure><img src="image_35.png" /><figcaption>Figure 2 Part of the range tree for the points from Fig. 1. The label of node $x$ appears in red on the arrow pointing to $x$. Nodes contain $l[x]:r[x]$. The references $L[x]$ and $R[x]$ appear as children in a binary tree using usual drawing conventions. The reference $D[x]$ appears as a dashed arrow (possibly interrupted); the placement on the page follows no other logic than economy of layout and readability. References $D[x]$ from leaf nodes, such as $D[LL]$ leading to node LLD, are not shown; this conceals 12 single-node trees. The ‘3rd-dimensional nodes,’ whose names contain two Ds, show the values $f[x]$ next to the node. To ease comprehension, leaf nodes are decorated with their canonical subset, which is a singleton from $\{p, q, r, s\}$. The reader can infer the canonical subset for an internal node as the union of leaves of the subtree; for instance, $P_{DR} = \{r, s\}$. However, note that these point sets are not explicitly stored in the data structure.</figcaption></figure>

**Lemma 6.** Let $n = |P|$. Algorithm C computes the $d$-dimensional range tree for $P$ in time linear in $nd \cdot B(n, d)$.

**Proof.** We run Algorithm C on input $P$ and $i = 1$.

Disregarding the recursive calls, the running time of algorithm C on input $i$ and $Q$ is dominated by Steps C2 and C3, i.e., splitting $Q$ into two sets of equal size. It is known that this task can be performed in time linear in $|Q|$ [4]. Thus, the running time for constructing $R_i(Q)$ is linear in $|Q|$ plus the time spent in recursive calls.

This means that we can bound the running time for constructing $T_1(P)$ by bounding the sizes of the sets $P_x$ associated with every node $x$ in the data structure. If for a moment $X$ denotes the set of all these nodes then we want to bound

$$ \sum_{x \in X} |P_x| = \sum_{x \in X} |\{p \in P: p \in P_x\}| = \sum_{p \in P} |\{x \in X: p \in P_x\}|. $$

Thus, we need to determine, for given $p \in P$, the number of subsets $P_x$ in which $p$ appears. By construction, there are fewer than $d$ occurrences of $D$ in $x$. Moreover, if $x$ contains more than $h$ occurrences of either L or R then $P_x$ is empty. Thus, $x$ has at most $h + d$ letters. For two different strings $x$ and $x'$ that agree on the positions of $D$, the sets $P_x$ and $P_{x'}$ are disjoint, so $p$ appears in at most one of them. We conclude that the number of sets $P_x$ such that $p \in P_x$ is bounded by the number of ways to arrange fewer than $d$ many Ds and at most $h$ non-Ds. Using the identity $\binom{a+0}{0} + \cdots + \binom{a+b}{b} = \binom{a+b+1}{b}$ repeatedly, we compute

$$ \begin{aligned} \sum_{i=0}^{d-1} \sum_{j=0}^{h} \binom{i+j}{j} &= \sum_{i=0}^{d-1} \binom{i+h+1}{h} = \sum_{i=0}^{d-1} \binom{i+h+1}{i+1} = \\ (-1) + \sum_{i=0}^{d} \binom{i+h}{i} &= \binom{h+d+1}{d} - 1 = \frac{h+d+1}{h+1} \binom{h+d}{d} - 1 \le d \binom{d+h}{d}. \end{aligned} $$

The bound follows from aggregating this contribution over all $p \in P$.

<figure><img src="image_36.png" /></figure>
Search

In this section, we fix two sequences of integers $l_1, \dots, l_d$ and $r_1, \dots, r_d$ describing the query box $B$ given by

$$B = [l_1, r_1] \times \dots \times [l_d, r_d].$$

**► Algorithm Q (Query).** Given integer $i \in \{1, \dots, d\}$, a query box $B$ as above and a range tree $R_i(Q)$ with root $x$ for a set of points $Q$ such that every point $q \in Q$ satisfies $l_j \le q_j \le r_j$ for $j \in \{1, \dots, i-1\}$, this algorithm returns $\bigoplus \{f(q): q \in Q \cap B\}$.

**Q1** [Empty?] If the data structure is empty, or $l_i > r[x]$, or $l[x] > r_i$, then return the identity in the underlying monoid $M$.

**Q2** [Done?] If $i = d$ and $l_d \le \min_d[x]$ and $\max_d[x] \le r_d$ then return $f[x]$.

**Q3** [Next dimension?] If $i < d$ and $l_i \le l[x]$ and $r[x] \le r_i$ then query the range tree at $D[x]$ for dimension $i+1$. Return the resulting value.

**Q4** [Split.] Query the range tree $L[x]$ for dimension $i$; the result is a value $f_L$. Query the range tree $R[x]$ for dimension $i$; the result is a value $f_R$. Return $f_L \oplus f_R$.

To prove correctness, we show that this algorithm is correct for each point set $Q = P_x$.

**► Lemma 7.** Let $i = D(x) + 1$, where $D(x)$ is the number of Ds in $x$. Assume that $P_x$ is such that $l_j \le p_i \le r_j$ for all $j \in \{1, \dots, i-1\}$ for each $p \in P_x$. Then the query algorithm on input $x$ and $i$ returns $f(B \cap P_x)$.

**Proof.** Backwards induction in $|x|$.

If $|x| = h + d$ then $P_x$ is the empty set, in which case the algorithm correctly returns the identity in $M$.

If the algorithm executes Step Q2 then $B$ is satisfied for all $q \in P_x$, in which case the algorithm correctly returns $f[x] = f(P_x)$.

If the algorithm executes Step Q3 then $B$ satisfies the condition in the lemma for $i+1$, and the number of Ds in $P_{xD}$ is $i+1$, and $D[x]$ store the $(i+1)$th range tree for $P_{xD}$. Thus, by induction the algorithm returns $f(P_{xD} \cap B)$, which equals $f(P_x \cap B)$ because $P_{xD} = P_x$.

Otherwise, by induction, $f_L = f(P_{xL} \cap B)$ and $f_R = f(P_{xR} \cap B)$. Since $P_{xL} \cup P_{xR} = P_x$, we have $f(P_x \cap B) = f((P_{xL} \cap B) \cup (P_{xR} \cap P)) = f_L \oplus f_R$. ◀

**► Lemma 8.** If $x$ is the root of the range tree for $P$ then on input $i = 1, x$, and $B$, the query algorithm returns $f(P \cap B)$ in time linear in $2^d B(n, d)$.

**Proof.** Correctness follows from the previous lemma.

For the running time, we first observe that the query algorithm does constant work in each visited node. Thus it suffices to bound the number of visited nodes as

$$2^d \binom{h+d}{d} \quad (d \ge 1, h \ge 0). \qquad (9)$$

We will show by induction in $d$ that (9) holds for every call to a $d$-dimensional range tree for a point set $P_x$, where $h = \lceil \log |P_x| \rceil$. The two easy cases are Q1 and Q2, which incur no additional nodes to be visited, so the number of visited nodes is 1, which is bounded by (9). Step Q3 leads to a recursive call for a $(d-1)$-dimensional range tree over the same point set $P_{xD} = P_x$, and we verify

$$1 + 2^{d-1} \binom{h+d-1}{d-1} \le 2^d \binom{h+d}{d}.$$
Search

In this section, we fix two sequences of integers $l_1, \dots, l_d$ and $r_1, \dots, r_d$ describing the query box $B$ given by

$$B = [l_1, r_1] \times \dots \times [l_d, r_d].$$

**► Algorithm Q (Query).** Given integer $i \in \{1, \dots, d\}$, a query box $B$ as above and a range tree $R_i(Q)$ with root $x$ for a set of points $Q$ such that every point $q \in Q$ satisfies $l_j \le q_j \le r_j$ for $j \in \{1, \dots, i-1\}$, this algorithm returns $\bigoplus \{f(q): q \in Q \cap B\}$.

**Q1** [Empty?] If the data structure is empty, or $l_i > r[x]$, or $l[x] > r_i$, then return the identity in the underlying monoid $M$.

**Q2** [Done?] If $i = d$ and $l_d \le \min_d[x]$ and $\max_d[x] \le r_d$ then return $f[x]$.

**Q3** [Next dimension?] If $i < d$ and $l_i \le l[x]$ and $r[x] \le r_i$ then query the range tree at $D[x]$ for dimension $i+1$. Return the resulting value.

**Q4** [Split.] Query the range tree $L[x]$ for dimension $i$; the result is a value $f_L$. Query the range tree $R[x]$ for dimension $i$; the result is a value $f_R$. Return $f_L \oplus f_R$.

To prove correctness, we show that this algorithm is correct for each point set $Q = P_x$.

**► Lemma 7.** Let $i = D(x) + 1$, where $D(x)$ is the number of Ds in $x$. Assume that $P_x$ is such that $l_j \le p_i \le r_j$ for all $j \in \{1, \dots, i-1\}$ for each $p \in P_x$. Then the query algorithm on input $x$ and $i$ returns $f(B \cap P_x)$.

**Proof.** Backwards induction in $|x|$.

If $|x| = h + d$ then $P_x$ is the empty set, in which case the algorithm correctly returns the identity in $M$.

If the algorithm executes Step Q2 then $B$ is satisfied for all $q \in P_x$, in which case the algorithm correctly returns $f[x] = f(P_x)$.

If the algorithm executes Step Q3 then $B$ satisfies the condition in the lemma for $i+1$, and the number of Ds in $P_{xD}$ is $i+1$, and $D[x]$ store the $(i+1)$th range tree for $P_{xD}$. Thus, by induction the algorithm returns $f(P_{xD} \cap B)$, which equals $f(P_x \cap B)$ because $P_{xD} = P_x$.

Otherwise, by induction, $f_L = f(P_{xL} \cap B)$ and $f_R = f(P_{xR} \cap B)$. Since $P_{xL} \cup P_{xR} = P_x$, we have $f(P_x \cap B) = f((P_{xL} \cap B) \cup (P_{xR} \cap P)) = f_L \oplus f_R$. ◀

**► Lemma 8.** If $x$ is the root of the range tree for $P$ then on input $i = 1, x$, and $B$, the query algorithm returns $f(P \cap B)$ in time linear in $2^d B(n, d)$.

**Proof.** Correctness follows from the previous lemma.

For the running time, we first observe that the query algorithm does constant work in each visited node. Thus it suffices to bound the number of visited nodes as

$$2^d \binom{h+d}{d} \quad (d \ge 1, h \ge 0). \qquad (9)$$

We will show by induction in $d$ that (9) holds for every call to a $d$-dimensional range tree for a point set $P_x$, where $h = \lceil \log |P_x| \rceil$. The two easy cases are Q1 and Q2, which incur no additional nodes to be visited, so the number of visited nodes is 1, which is bounded by (9). Step Q3 leads to a recursive call for a $(d-1)$-dimensional range tree over the same point set $P_{xD} = P_x$, and we verify

$$1 + 2^{d-1} \binom{h+d-1}{d-1} \le 2^d \binom{h+d}{d}.$$
The interesting case is Step Q4. We need to follow two paths from $x$ to the leaves of the binary tree of $x$. Consider the leaves $l$ and $r$ in the subtree rooted at $x$ associated with the points $\min_i(P_x)$ and $\max_i(P_x)$ as defined in Sec. 3.2. We describe the situation of the path $Y$ from $l$ to $x$; the other case is symmetrical. At each internal node $y \in Y$, the algorithm chooses Step Q4 (because $l_i \ge l[y]$). There are two cases for what happens at $yL$ and $yR$. If $l_i \le \min_i(P_y)$ then $P_{yR}$ satisfies $l_i \le \min_i(P_{yR}) \le r_i$, so the call to $yR$ will choose Step Q3. By induction, this incurs $2^{d-1} \binom{d-1+i}{d-1}$ visits, where $i$ is the height of $y$. In the other case, the call to $yL$ will choose Step Q1, which incurs no extra visits. Thus, the number of nodes visited on the left path is at most

$$h + \sum_{i=0}^{h-1} 2^{d-1} \binom{d-1+i}{d-1},$$

and the total number of nodes visited is at most twice that:

$$2h + 2^d \sum_{i=0}^{h-1} \binom{d-1+i}{d-1} \le 2^d \sum_{i=0}^{h} \binom{d-1+i}{d-1} = 2^d \binom{d+h}{d}.$$

<figure><img src="image_33.png" /></figure>

## 3.3 Discussion

The textbook analysis of range trees, and similar $d$-dimensional spatial algorithms and data structures sets up a recurrence relation like

$$r(n, d) = 2r(n/2, d) + r(n, d-1),$$

for the construction and

$$r(n, d) = \max\{r(n/2, d), r(n, d-1)\},$$

for the query time. One then observes that $n \log^d n$ and $\log^d n$ are the solutions to these recurrences. This analysis goes back to Bentley's original paper [3].

Along the lines of the previous section, one can show that the functions $n \cdot B(n, d)$ and $B(n, d)$ solve these recurrences as well. A detailed derivation can be found in [13], which also contains combinatorial arguments of how to interpret the binomial coefficients in the context of spatial data structures. A later paper of Chan [7] also takes the recurrences as a starting point, and observes asymptotically improved solution for the related question of dominance queries.

# 4 Graph Distances

We present the algorithm for computing the diameter. The construction closely follows Cabello and Knauer [6], but uses the range tree bounds from Section 3. The analysis is extended to superconstant dimension as in Abboud et al. [1]. Using the approximate treewidth construction of Bodlaender et al. [5], we can pay more attention to the parameters of the recursive decomposition into small-size separators.

## 4.1 Preliminaries

We consider an undirected graph $G$ with $n$ vertices and $m$ edges with nonnegative integer weights. The set of vertices is $V(G)$. For a vertex subset $U$ we write $G[U]$ for the induced subgraph.
The interesting case is Step Q4. We need to follow two paths from $x$ to the leaves of the binary tree of $x$. Consider the leaves $l$ and $r$ in the subtree rooted at $x$ associated with the points $\min_i(P_x)$ and $\max_i(P_x)$ as defined in Sec. 3.2. We describe the situation of the path $Y$ from $l$ to $x$; the other case is symmetrical. At each internal node $y \in Y$, the algorithm chooses Step Q4 (because $l_i \ge l[y]$). There are two cases for what happens at $yL$ and $yR$. If $l_i \le \min_i(P_y)$ then $P_{yR}$ satisfies $l_i \le \min_i(P_{yR}) \le r_i$, so the call to $yR$ will choose Step Q3. By induction, this incurs $2^{d-1} \binom{d-1+i}{d-1}$ visits, where $i$ is the height of $y$. In the other case, the call to $yL$ will choose Step Q1, which incurs no extra visits. Thus, the number of nodes visited on the left path is at most

$$h + \sum_{i=0}^{h-1} 2^{d-1} \binom{d-1+i}{d-1},$$

and the total number of nodes visited is at most twice that:

$$2h + 2^d \sum_{i=0}^{h-1} \binom{d-1+i}{d-1} \le 2^d \sum_{i=0}^{h} \binom{d-1+i}{d-1} = 2^d \binom{d+h}{d}.$$

## 3.3 Discussion

The textbook analysis of range trees, and similar $d$-dimensional spatial algorithms and data structures sets up a recurrence relation like

$$r(n, d) = 2r(n/2, d) + r(n, d-1),$$

for the construction and

$$r(n, d) = \max\{r(n/2, d), r(n, d-1)\},$$

for the query time. One then observes that $n \log^d n$ and $\log^d n$ are the solutions to these recurrences. This analysis goes back to Bentley's original paper [3].

Along the lines of the previous section, one can show that the functions $n \cdot B(n, d)$ and $B(n, d)$ solve these recurrences as well. A detailed derivation can be found in [13], which also contains combinatorial arguments of how to interpret the binomial coefficients in the context of spatial data structures. A later paper of Chan [7] also takes the recurrences as a starting point, and observes asymptotically improved solution for the related question of dominance queries.

# 4 Graph Distances

We present the algorithm for computing the diameter. The construction closely follows Cabello and Knauer [6], but uses the range tree bounds from Section 3. The analysis is extended to superconstant dimension as in Abboud et al. [1]. Using the approximate treewidth construction of Bodlaender et al. [5], we can pay more attention to the parameters of the recursive decomposition into small-size separators.

## 4.1 Preliminaries

We consider an undirected graph $G$ with $n$ vertices and $m$ edges with nonnegative integer weights. The set of vertices is $V(G)$. For a vertex subset $U$ we write $G[U]$ for the induced subgraph.
## 4:10 Multivariate Analysis of Orthogonal Range Searching and Graph Distances

A path from $u$ to $v$ is called a $u,v$-path and denoted $P$. The length of a path, denoted $l(P)$, is the sum of its edge lengths.

The distance from vertex $u$ to vertex $v$, denoted $d(u, v)$, is the minimum length of shortest $u, v$-path. The Wiener index of $G$, denoted $wien(G)$ is $\sum_{u,v \in V(G)} d(u, v)$. The eccentricity of a vertex $u$, denoted $e(u)$ is given by $e(u) = \max\{d(u, v): v \in V(G)\}$. The diameter of $G$, denoted $diam(G)$ is $\max\{e(u): u \in V(G)\}$. The radius of $G$, denoted $rad(G)$ is $\min\{e(u): u \in V(G)\}$.

## 4.2 Separation

A vertex subset $Z$ separates $X$ and $Y$ if every $x, y$-path with $x \in X$ and $y \in Y$ contains a vertex from $Z$. A skew $k$-separator tree of $G$ is a binary tree such that each node $t$ of $T$ is associated with a vertex set $Z_t \subseteq V(G)$ such that

* $|Z_t| \le k$,

* If $L_t$ and $R_t$ denote the vertices of $G$ associated with the left and right subtrees of $t$, respectively, then $Z_t$ separates $L_t$ and $R_t$ and

$$ \frac{n}{k+1} \le |L_t \cup Z_t| \le \frac{nk}{k+1}, \qquad (10) $$

* $T$ remains a skew $k$-separator even if edges between vertices of $Z_t$ are added.

It is known that such a tree can be found from a tree decomposition, and an approximate tree decomposition can be found in single-exponential time. We summarise these results in the following lemma:

**Lemma 9** ([6, Lemma 3] with [5, Theorem 1]). For a given $n$-vertex input graph $G$, a skew $(5 \cdot \text{tw}(G) + 4)$-separator tree can be computed in time $n \exp O(\text{tw}(G))$.

## 4.3 Algorithm

We follow the construction of [6].

Given graph $G$, let $S_{x,w}$ denote the set of shortest $x, w$-paths. We refine the notion of eccentricity to a subset $W$ of vertices. Formally,

$$ e(x, W) = \max_{w \in W} \{l(P): P \in S_{x,w}\}. $$

We will consider a situation where $V(G) = X \cup Y$ with separator $Z = X \cap Y$. We can then compute $e(x)$ as $\max\{e(x, X), e(x, Y)\}$ for each $x \in X$. The first term is found recursively in $G[X]$; the interesting part is the computation of $e(x, Y)$.

Enumerate $Z = \{z_1, \dots, z_k\}$. For $i \in \{1, \dots, k\}$ define the $i$th eccentricity $e_i(x, Y)$ as the maximum distance from $x$ to any vertex in $Y$ 'via $z_i$.' Formally,

$$ e_i(x, Y) = \max_{y \in Y} \{l(P): P \in S_{x,y}, z_i \in V(P)\}. $$

See Figure 3 for a small example.

**Lemma 10.** If $Z$ separates $X$ and $Y$ then $e(x, Y) = \max_{i=1}^k e_i(x, Y)$ for $x \in X$.

**Proof.** A shortest $x, y$-path with $y \in Y$ must contain a vertex from $Z$, say $z_i$. Thus, $e(x, Y) \le e_i(x, Y)$. Conversely, $e(x, Y) \ge e_j(x, Y)$ for all $j \in \{1, \dots, k\}$ from the definition. $\blacksquare$

Now we can write the eccentricity via $z_i$ as the distance to $z_i$ plus a range query:
## 4:10 Multivariate Analysis of Orthogonal Range Searching and Graph Distances

A path from $u$ to $v$ is called a $u,v$-path and denoted $P$. The length of a path, denoted $l(P)$, is the sum of its edge lengths.

The distance from vertex $u$ to vertex $v$, denoted $d(u, v)$, is the minimum length of shortest $u, v$-path. The Wiener index of $G$, denoted $wien(G)$ is $\sum_{u,v \in V(G)} d(u, v)$. The eccentricity of a vertex $u$, denoted $e(u)$ is given by $e(u) = \max\{d(u, v): v \in V(G)\}$. The diameter of $G$, denoted $diam(G)$ is $\max\{e(u): u \in V(G)\}$. The radius of $G$, denoted $rad(G)$ is $\min\{e(u): u \in V(G)\}$.

## 4.2 Separation

A vertex subset $Z$ separates $X$ and $Y$ if every $x, y$-path with $x \in X$ and $y \in Y$ contains a vertex from $Z$. A skew $k$-separator tree $T$ of $G$ is a binary tree such that each node $t$ of $T$ is associated with a vertex set $Z_t \subseteq V(G)$ such that

* $|Z_t| \le k$,

* If $L_t$ and $R_t$ denote the vertices of $G$ associated with the left and right subtrees of $t$, respectively, then $Z_t$ separates $L_t$ and $R_t$ and

$$ \frac{n}{k+1} \le |L_t \cup Z_t| \le \frac{nk}{k+1}, \qquad (10) $$

* $T$ remains a skew $k$-separator even if edges between vertices of $Z_t$ are added.

It is known that such a tree can be found from a tree decomposition, and an approximate tree decomposition can be found in single-exponential time. We summarise these results in the following lemma:

**Lemma 9** ([6, Lemma 3] with [5, Theorem 1]). For a given $n$-vertex input graph $G$, a skew $(5 \cdot \text{tw}(G) + 4)$-separator tree can be computed in time $n \exp O(\text{tw}(G))$.

## 4.3 Algorithm

We follow the construction of [6].

Given graph $G$, let $S_{x,w}$ denote the set of shortest $x, w$-paths. We refine the notion of eccentricity to a subset $W$ of vertices. Formally,

$$ e(x, W) = \max_{w \in W} \{l(P): P \in S_{x,w}\}. $$

We will consider a situation where $V(G) = X \cup Y$ with separator $Z = X \cap Y$. We can then compute $e(x)$ as $\max\{e(x, X), e(x, Y)\}$ for each $x \in X$. The first term is found recursively in $G[X]$; the interesting part is the computation of $e(x, Y)$.

Enumerate $Z = \{z_1, \dots, z_k\}$. For $i \in \{1, \dots, k\}$ define the $i$th eccentricity $e_i(x, Y)$ as the maximum distance from $x$ to any vertex in $Y$ 'via $z_i$.' Formally,

$$ e_i(x, Y) = \max_{y \in Y} \{l(P): P \in S_{x,y}, z_i \in V(P)\}. $$

See Figure 3 for a small example.

**Lemma 10.** If $Z$ separates $X$ and $Y$ then $e(x, Y) = \max_{i=1}^k e_i(x, Y)$ for $x \in X$.

**Proof.** A shortest $x, y$-path with $y \in Y$ must contain a vertex from $Z$, say $z_i$. Thus, $e(x, Y) \le e_i(x, Y)$. Conversely, $e(x, Y) \ge e_j(x, Y)$ for all $j \in \{1, \dots, k\}$ from the definition. ◀

Now we can write the eccentricity via $z_i$ as the distance to $z_i$ plus a range query:
<figure><img src="image_34.png" /><figcaption>Figure 3 Left: Example with $Z = \{z_1, z_2, z_3\}$ and $Y = Z \cup \{y, y', y''\}$. We have $e(x, Y) = 5$ (along $xz_1y$) and $e(x', Y) = 3$. For the case $i = 3$ we see $e_3(x, Y) = 4$ along $xz_3y''$, because there are no shortest paths from $x$ via $z_3$ to $y$ or $y'$, and the one-edge path $xz_3$ itself is shorter. Similarly, $e_3(x', Y) = 3$ (along $x'z_3y'$). Right: The corresponding points in $\mathbb{Z}^2$, only the first two coordinates are shown, and only for the points in $Y \setminus Z$. The points corresponding to $y'$ and $y''$ both belong to the rectangle for $x'$, certifying that there are shortest $x'$, $y'$- and $x'$, $y''$-paths through $z_3$. Right: Over $R_{x'}$, the point $p_{y'}$ maximises $f$. We have $e_3(x', Y) = l(x'z_3y') = d(x', z_3) + f(p_{y'}) = 1 + 2 = 3$.</figcaption></figure>

**Lemma 11.** Let $i \in \{1, \dots, k\}$ and assume $\{z_1, \dots, z_k\}$ separates X and Y. Define for each $y \in Y$ the $k$-dimensional point

$$p_y = \begin{pmatrix} d(z_i, y) - d(z_1, y) \\ \vdots \\ d(z_i, y) - d(z_k, y) \end{pmatrix} \quad \text{with } f(p_y) = d(z_i, y). \qquad (11)$$

Define for each $x \in X$ the rectangle

$$R_x = \times_{j=1}^{k} [-\infty, d(x, z_j) - d(x, z_i)]. \qquad (12)$$

Then

$$e_i(x, Y) = d(x, z_i) + \max_{y: p_y \in R_x} f(p_y).$$

**Proof.** Consider a shortest $x, y$-path $P$ containing $z_i \in Z$. No other $x, y$-path is shorter than $P$, so in particular we have

$$d(x, z_i) + d(z_i, y) \le d(x, z_j) + d(z_j, y), \quad j \in \{1, \dots, k\},$$

equivalently,

$$d(z_i, y) - d(z_j, y) \le d(x, z_j) - d(x, z_i), \quad j \in \{1, \dots, k\}. \qquad (13)$$

which means $p_y \in R_x$. Moreover, if $y$ is chosen so that $P$ attains the eccentricity $e_i(x, Y)$ then $e_i(x, Y) = l(P) = d(x, z_i) + d(z_i, y)$ and $p_y$ maximises $f(p_y) = d(z_i, y)$ over the points in $R_x$. ◀

One observes that the $i$th coordinate of $p_y$ is always 0 and of $R_y$ is always $[-\infty, 0]$, so the reduction is actually to a $(k-1)$-dimensional range query instance. However, we are mainly interested in the asymptotic dependency on $k$, so we avoid this possible (but tedious) improvement.

We are ready for the algorithm.

**Algorithm E (Eccentricities).** Given an undirected, connected graph $G$ with nonnegative integer weights and a skew $k$-separator tree with root $t$, this algorithm computes the eccentricity $e(v)$ of every vertex $v \in V(G)$. We write $Z = Z_t$, $X = L_t \cup Z_t$, and $Y = R_t \cup Z_t$.
<figure><img src="image_37.png" /><figcaption>**Figure 3** Left: Example with $Z = \{z_1, z_2, z_3\}$ and $Y = Z \cup \{y, y', y''\}$. We have $e(x, Y) = 5$ (along $xz_1y$) and $e(x', Y) = 3$. For the case $i = 3$ we see $e_3(x, Y) = 4$ along $xz_3y''$, because there are no shortest paths from $x$ via $z_3$ to $y$ or $y'$, and the one-edge path $xz_3$ itself is shorter. Similarly, $e_3(x', Y) = 3$ (along $x'z_3y'$). Right: The corresponding points in $\mathbb{Z}^2$, only the first two coordinates are shown, and only for the points in $Y \setminus Z$. The points corresponding to $y'$ and $y''$ both belong to the rectangle for $x'$, certifying that there are shortest $x'$, $y'$- and $x'$, $y''$-paths through $z_3$. Right: Over $R_{x'}$, the point $p_{y'}$ maximises $f$. We have $e_3(x', Y) = l(x'z_3y') = d(x', z_3) + f(p_{y'}) = 1 + 2 = 3$.</figcaption></figure>

**Lemma 11.** Let $i \in \{1, \dots, k\}$ and assume $\{z_1, \dots, z_k\}$ separates X and Y. Define for each $y \in Y$ the $k$-dimensional point

$$p_y = \begin{pmatrix} d(z_i, y) - d(z_1, y) \\ \vdots \\ d(z_i, y) - d(z_k, y) \end{pmatrix} \quad \text{with } f(p_y) = d(z_i, y). \qquad (11)$$

Define for each $x \in X$ the rectangle

$$R_x = \times_{j=1}^{k} [-\infty, d(x, z_j) - d(x, z_i)]. \qquad (12)$$

Then

$$e_i(x, Y) = d(x, z_i) + \max_{y: p_y \in R_x} f(p_y).$$

**Proof.** Consider a shortest $x, y$-path $P$ containing $z_i \in Z$. No other $x, y$-path is shorter than $P$, so in particular we have

$$d(x, z_i) + d(z_i, y) \le d(x, z_j) + d(z_j, y), \quad j \in \{1, \dots, k\},$$

equivalently,

$$d(z_i, y) - d(z_j, y) \le d(x, z_j) - d(x, z_i), \quad j \in \{1, \dots, k\}. \qquad (13)$$

which means $p_y \in R_x$. Moreover, if $y$ is chosen so that $P$ attains the eccentricity $e_i(x, Y)$ then $e_i(x, Y) = l(P) = d(x, z_i) + d(z_i, y)$ and $p_y$ maximises $f(p_y) = d(z_i, y)$ over the points in $R_x$. ◀

One observes that the $i$th coordinate of $p_y$ is always 0 and of $R_y$ is always $[-\infty, 0]$, so the reduction is actually to a $(k-1)$-dimensional range query instance. However, we are mainly interested in the asymptotic dependency on $k$, so we avoid this possible (but tedious) improvement.

We are ready for the algorithm.

**Algorithm E (Eccentricities).** Given an undirected, connected graph $G$ with nonnegative integer weights and a skew $k$-separator tree with root $t$, this algorithm computes the eccentricity $e(v)$ of every vertex $v \in V(G)$. We write $Z = Z_t$, $X = L_t \cup Z_t$, and $Y = R_t \cup Z_t$.
4:12 Multivariate Analysis of Orthogonal Range Searching and Graph Distances

E1 [Base case.] If $n/\ln n < 4k(k+1)$ find all distances using Dijkstra's algorithm. Terminate.

E2 [Distances from separator.] Compute $d(z, v)$ for each $z \in Z$, $v \in V(G)$ using $k$ applications of Dijkstra's algorithm. Compute $e(z, Y) = \max_{y \in Y} d(z, y)$ for each $z \in Z$.

E3 [Add shortcuts.] For each pair $z, z' \in Z$, add the edge $zz'$ to $G$, weighted by $d(z, z')$. Remove duplicate edges, retaining the shortest.

E4.1 [Start iterating over $\{z_1, \dots, z_k\}$.] Let $i=1$.

E4.2 [Build range tree for $z_i$.] Construct a $k$-dimensional range tree for the points $\{p_y: y \in Y\}$ given by (11) using the monoid ($\mathbb{Z}$, $\max$).

E4.3 [Query range tree.] For each $x \in X$, query the rectangle $R_x$ given by (12) and add $d(x, z_i)$. The result is $e_i(x, Y)$ by Lemma 11.

E4.4 [Next $z_i$.] If $i < k$ then increase $i$ and go to E4.1.

E5 [Recurse on $G[X]$ and combine.] Recursively compute the distances in $G[X]$ using the left subtree of $t$ as a skew $k$-separator tree. The result are eccentricities $e(x, X)$ for each $x \in X$. For each $x \in X$, set $e(x, Y) = \max_{i=1}^k e_i(x, Y)$ from Step E4.3, then set $e(x) = \max\{e(x, X), e(x, Y)\}$.

E6 [Flip.] Repeat Steps E4-5 with the roles of $X$ and $Y$ exchanged.

4.4 Running Time

► Lemma 12. *The running time of Algorithm E is $O(n \cdot B(n, k) \cdot 2^k k^2 \log n)$.*

We omit the proof. We can now establish Theorem 1 for diameter and radius.

**Proof of Thm. 1, distances.** To compute all eccentricities for a given graph we find a $k$-skew separator for $k = 5 \operatorname{tw}(G) + 4$ using Lemma 9 in time $n \exp O(\operatorname{tw}(G))$. We then run Algorithm E, using Lemma 12 to bound the running time. From the eccentricities, the radius and diameter can be computed in linear time using their definition. ◀

Algorithm E can be modified to compute the Wiener index, as described in [6, Sec. 4], completing the proof of Theorem 1. The main observation is that the sum of distances between all pair $u, v \in V(G)$ can be written as pairwise distances within $X$, within $Y$, and between $X$ and $Y$, carefully subtracting contributions from these sums that were included twice. The orthogonal range queries for vertex $x \in X$ now need to report the sum of distances to every $y \in Y$, rather than just the value of the maximum distance $e(x; Y)$. To this end, we use the monoid of positive integer tuples $(d, r)$ with the operation $(d, r) \oplus (d', r') = (d + d', r + r')$ with identity element $(0, 0)$. The value associated with vertex $x$ in Step E4.2 is $f(p(y)) = (1, d(z_i, y))$. To avoid overcounting, the definition of $R_x$ and $e_i(x, Y)$ have to be changed carefully.

References

1 Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, Va, USA, January 10-12, 2016*, pages 377–391. SIAM, 2016. doi:10.1137/1.9781611974331.ch28.

2 Matthias Bentert and André Nichterlein. Parameterized Complexity of Diameter. *CoRR*, abs/1802.10048, 2018. arXiv:1802.10048.

3 Jon Louis Bentley. Multidimensional Divide-and-Conquer. *Commun. ACM*, 23(4):214–229, 1980. doi:10.1145/358841.358850.
4:12 Multivariate Analysis of Orthogonal Range Searching and Graph Distances

E1 [Base case.] If $n/\ln n < 4k(k+1)$ find all distances using Dijkstra's algorithm. Terminate.

E2 [Distances from separator.] Compute $d(z, v)$ for each $z \in Z$, $v \in V(G)$ using $k$ applications of Dijkstra's algorithm. Compute $e(z, Y) = \max_{y \in Y} d(z, y)$ for each $z \in Z$.

E3 [Add shortcuts.] For each pair $z, z' \in Z$, add the edge $zz'$ to $G$, weighted by $d(z, z')$. Remove duplicate edges, retaining the shortest.

E4.1 [Start iterating over $\{z_1, \dots, z_k\}$.] Let $i=1$.

E4.2 [Build range tree for $z_i$.] Construct a $k$-dimensional range tree for the points $\{p_y: y \in Y\}$ given by (11) using the monoid ($\mathbb{Z}$, $\max$).

E4.3 [Query range tree.] For each $x \in X$, query the rectangle $R_x$ given by (12) and add $d(x, z_i)$. The result is $e_i(x, Y)$ by Lemma 11.

E4.4 [Next $z_i$.] If $i < k$ then increase $i$ and go to E4.1.

E5 [Recurse on $G[X]$ and combine.] Recursively compute the distances in $G[X]$ using the left subtree of $t$ as a skew $k$-separator tree. The result are eccentricities $e(x, X)$ for each $x \in X$. For each $x \in X$, set $e(x, Y) = \max_{i=1}^k e_i(x, Y)$ from Step E4.3, then set $e(x) = \max\{e(x, X), e(x, Y)\}$.

E6 [Flip.] Repeat Steps E4-5 with the roles of $X$ and $Y$ exchanged.

4.4 Running Time

► Lemma 12. *The running time of Algorithm E is $O(n \cdot B(n, k) \cdot 2^k k^2 \log n)$.*

We omit the proof. We can now establish Theorem 1 for diameter and radius.

**Proof of Thm. 1, distances.** To compute all eccentricities for a given graph we find a $k$-skew separator for $k = 5 \operatorname{tw}(G) + 4$ using Lemma 9 in time $n \exp O(\operatorname{tw}(G))$. We then run Algorithm E, using Lemma 12 to bound the running time. From the eccentricities, the radius and diameter can be computed in linear time using their definition. ◀

Algorithm E can be modified to compute the Wiener index, as described in [6, Sec. 4], completing the proof of Theorem 1. The main observation is that the sum of distances between all pair $u, v \in V(G)$ can be written as pairwise distances within $X$, within $Y$, and between $X$ and $Y$, carefully subtracting contributions from these sums that were included twice. The orthogonal range queries for vertex $x \in X$ now need to report the sum of distances to every $y \in Y$, rather than just the value of the maximum distance $e(x; Y)$. To this end, we use the monoid of positive integer tuples $(d, r)$ with the operation $(d, r) \oplus (d', r') = (d + d', r + r')$ with identity element $(0, 0)$. The value associated with vertex $x$ in Step E4.2 is $f(p(y)) = (1, d(z_i, y))$. To avoid overcounting, the definition of $R_x$ and $e_i(x, Y)$ have to be changed carefully.

References

1 Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In *Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, Va, USA, January 10-12, 2016*, pages 377–391. SIAM, 2016. doi:10.1137/1.9781611974331.ch28.

2 Matthias Bentert and André Nichterlein. Parameterized Complexity of Diameter. *CoRR*, abs/1802.10048, 2018. arXiv:1802.10048.

3 Jon Louis Bentley. Multidimensional Divide-and-Conquer. *Commun. ACM*, 23(4):214–229, 1980. doi:10.1145/358841.358850.
4. Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan. Time Bounds for Selection. *J. Comput. Syst. Sci.*, 7(4):448–461, 1973. doi:10.1016/S0022-0000(73)80033-9.

5. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. An $O(c^k n)$ 5-approximation algorithm for treewidth. *SIAM J. Comput.*, 45(2):317–378, 2016. doi:10.1137/130947374.

6. Sergio Cabello and Christian Knauer. Algorithms for bounded treewidth with orthogonal range searching. *Comput. Geom.*, 42(9):815–824, 2009. doi:10.1016/j.comgeo.2009.02.001.

7. Timothy M. Chan. All-Pairs Shortest Paths with Real Weights in $O(n^3/\log n)$ Time. *Algorithmica*, 50(2):236–243, 2008. doi:10.1007/s00453-007-9062-1.

8. Bernard Chazelle. Lower Bounds for Orthogonal Range Searching: I. The Reporting Case. *J. Assoc. Comput. Mach.*, 37(2):200–212, 1990. doi:10.1145/77600.77614.

9. Thore Husfeldt. Computing Graph Distances Parameterized by Treewidth and Diameter. In *11th International Symposium on Parameterized and Exact Computation (IPEC 2016)*, volume 63 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 16:1–16:11, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.IPEC.2016.16.

10. Russel Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? *J. Comput. Syst. Sci.*, 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.

11. Der-Tsai Lee and Chakkuen K. Wong. Quintary Trees: A File Structure for Multidimensional Database Systems. *ACM Trans. Database Syst.*, 5(3):339–353, 1980. doi:10.1145/320613.320618.

12. George S. Lueker. A Data Structure for Orthogonal Range Queries. In *19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978*, pages 28–34. IEEE Computer Society, 1978. doi:10.1109/SFCS.1978.1.

13. Louis Monier. Combinatorial Solutions of Multidimensional Divide-and-Conquer Recurrences. *J. Algorithms*, 1(1):60–74, 1980. doi:10.1016/0196-6774(80)90005-X.

14. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In *Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013*, pages 515–524, 2013. doi:10.1145/2488608.2488673.

15. Qiaosheng Shi. *Efficient algorithms for network center/covering location optimization problems*. PhD thesis, School of Computing Science, Simon Fraser University, 2008.

16. Dan E. Willard. New data structures for orthogonal range queries. *SIAM J. Comput.*, 14(1):232–253, 1985. doi:10.1137/0214019.

17. Virginia Vassilevska Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk). In *10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece*, pages 17–29, 2015. doi:10.4230/LIPIcs.IPEC.2015.17.
4. Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan. Time Bounds for Selection. *J. Comput. Syst. Sci.*, 7(4):448–461, 1973. doi:10.1016/S0022-0000(73)80033-9.

5. Hans L. Bodlaender, Pål Grønås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk. An $O(c^k n)$ 5-approximation algorithm for treewidth. *SIAM J. Comput.*, 45(2):317–378, 2016. doi:10.1137/130947374.

6. Sergio Cabello and Christian Knauer. Algorithms for bounded treewidth with orthogonal range searching. *Comput. Geom.*, 42(9):815–824, 2009. doi:10.1016/j.comgeo.2009.02.001.

7. Timothy M. Chan. All-Pairs Shortest Paths with Real Weights in $O(n^3/\log n)$ Time. *Algorithmica*, 50(2):236–243, 2008. doi:10.1007/s00453-007-9062-1.

8. Bernard Chazelle. Lower Bounds for Orthogonal Range Searching: I. The Reporting Case. *J. Assoc. Comput. Mach.*, 37(2):200–212, 1990. doi:10.1145/77600.77614.

9. Thore Husfeldt. Computing Graph Distances Parameterized by Treewidth and Diameter. In *11th International Symposium on Parameterized and Exact Computation (IPEC 2016)*, volume 63 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 16:1–16:11, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.IPEC.2016.16.

10. Russel Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? *J. Comput. Syst. Sci.*, 63(4):512–530, 2001. doi:10.1006/jcss.2001.1774.

11. Der-Tsai Lee and Chakkuen K. Wong. Quintary Trees: A File Structure for Multidimensional Database Systems. *ACM Trans. Database Syst.*, 5(3):339–353, 1980. doi:10.1145/320613.320618.

12. George S. Lueker. A Data Structure for Orthogonal Range Queries. In *19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978*, pages 28–34. IEEE Computer Society, 1978. doi:10.1109/SFCS.1978.1.

13. Louis Monier. Combinatorial Solutions of Multidimensional Divide-and-Conquer Recurrences. *J. Algorithms*, 1(1):60–74, 1980. doi:10.1016/0196-6774(80)90005-X.

14. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In *Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013*, pages 515–524, 2013. doi:10.1145/2488608.2488673.

15. Qiaosheng Shi. *Efficient algorithms for network center/covering location optimization problems*. PhD thesis, School of Computing Science, Simon Fraser University, 2008.

16. Dan E. Willard. New data structures for orthogonal range queries. *SIAM J. Comput.*, 14(1):232–253, 1985. doi:10.1137/0214019.

17. Virginia Vassilevska Williams. Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk). In *10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece*, pages 17–29, 2015. doi:10.4230/LIPIcs.IPEC.2015.17.
<figure><img src="image_35.png" /></figure>
<figure><img src="image_38.png" /></figure>
# A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

## Kustaa Kangas

Department of Computer Science, Aalto University, Espoo, Finland
juho-kustaa.kangas@aalto.fi

## Mikko Koivisto

Department of Computer Science, University of Helsinki, Helsinki, Finland
mikko.koivisto@helsinki.fi

## Sami Salonen

Department of Computer Science, University of Helsinki, Helsinki, Finland
sami.m.salonen@helsinki.fi

### Abstract

We consider the problem of counting the linear extensions of an *n*-element poset whose cover graph has treewidth at most *t*. We show that the problem can be solved in time $\tilde{O}(n^{t+3})$, where $\tilde{O}$ suppresses logarithmic factors. Our algorithm is based on fast multiplication of multivariate polynomials, and so differs radically from a previous $\tilde{O}(n^{t+4})$-time inclusion-exclusion algorithm. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters *n* and *t* alone, fixing of which leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. For selecting an efficient tree decomposition we adopt the method of empirical hardness models, and show that it typically enables picking a tree decomposition that is significantly more efficient than a random optimal-width tree decomposition.

**2012 ACM Subject Classification** Theory of computation → Algorithm design techniques, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** Algorithm selection, empirical hardness, linear extension, multiplication of polynomials, tree decomposition

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.5

**Funding** This work was partially supported by the Academy of Finland, Grant 276864, "Supple Exponential Algorithms."

**Acknowledgements** We thank the anonymous reviewers for constructive suggestions, most of which are implemented in the present version of the paper.

## 1 Introduction

Consider a partially ordered set (*V*, ≺), or *poset* for short, formed by an *n*-element set *V* and an irreflexive and transitive binary relation ≺ on *V*, called a *partial order*. Another partial order < on *V* is a *linear extension* of ≺ if it contains ≺ and for any distinct elements *x*, *y* ∈ *V* either *x* < *y* or *y* < *x*. The problem of counting linear extensions (#LE) asks the number of linear extensions of a given poset; equivalent to #LE is the problem of counting the topological sorts of a given directed (acyclic) graph. The problem has applications in numerous areas, for example, in sequence analysis [22], sorting [27], preference reasoning [21], convex rank tests [24], partial order plans [25], and learning graphical models [32, 26].

<figure><img src="image_36.png" /></figure>
# A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

## Kustaa Kangas

Department of Computer Science, Aalto University, Espoo, Finland
juho-kustaa.kangas@aalto.fi

## Mikko Koivisto

Department of Computer Science, University of Helsinki, Helsinki, Finland
mikko.koivisto@helsinki.fi

## Sami Salonen

Department of Computer Science, University of Helsinki, Helsinki, Finland
sami.m.salonen@helsinki.fi

## Abstract

We consider the problem of counting the linear extensions of an *n*-element poset whose cover graph has treewidth at most *t*. We show that the problem can be solved in time $\tilde{O}(n^{t+3})$, where $\tilde{O}$ suppresses logarithmic factors. Our algorithm is based on fast multiplication of multivariate polynomials, and so differs radically from a previous $\tilde{O}(n^{t+4})$-time inclusion-exclusion algorithm. We also investigate the algorithm from a practical point of view. We observe that the running time is not well characterized by the parameters *n* and *t* alone, fixing of which leaves large variance in running times due to uncontrolled features of the selected optimal-width tree decomposition. For selecting an efficient tree decomposition we adopt the method of empirical hardness models, and show that it typically enables picking a tree decomposition that is significantly more efficient than a random optimal-width tree decomposition.

**2012 ACM Subject Classification** Theory of computation → Algorithm design techniques, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** Algorithm selection, empirical hardness, linear extension, multiplication of polynomials, tree decomposition

**Digital Object Identifier** 10.4230/LIPIcs.IPEC.2018.5

**Funding** This work was partially supported by the Academy of Finland, Grant 276864, "Supple Exponential Algorithms."

**Acknowledgements** We thank the anonymous reviewers for constructive suggestions, most of which are implemented in the present version of the paper.

# 1 Introduction

Consider a partially ordered set (*V*, ≺), or *poset* for short, formed by an *n*-element set *V* and an irreflexive and transitive binary relation ≺ on *V*, called a *partial order*. Another partial order < on *V* is a *linear extension* of ≺ if it contains ≺ and for any distinct elements *x*, *y* ∈ *V* either *x* < *y* or *y* < *x*. The problem of counting linear extensions (#LE) asks the number of linear extensions of a given poset; equivalent to #LE is the problem of counting the topological sorts of a given directed (acyclic) graph. The problem has applications in numerous areas, for example, in sequence analysis [22], sorting [27], preference reasoning [21], convex rank tests [24], partial order plans [25], and learning graphical models [32, 26].

<figure><img src="image_39.png" /></figure>
5:2 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

The #LE problem is #P-complete [11] but admits a fully polynomial approximation scheme [13]. The best known asymptotic bounds for the expected running time are $O(\epsilon^{-2}n^3 \log^2 \ell \log n)$ [6] and $O(\epsilon^{-2}n^5 \log^2 n)$ [30], where $\ell$ is the number of linear extensions and $\epsilon$ the allowed relative error. These bounds, while polynomial, become prohibitively large in practice if, say, one requires an accuracy of $\epsilon = 0.01$ and $n$ is around one hundred.

Exact and parameterized algorithms offer an alternative approach to design practical algorithms for the problem. For the required number of arithmetic operations, the best known worst-case bound is $O(2^n n)$ in general, which is achieved by a simple dynamic programming algorithm. For several special instance classes better bounds are known: $O(n^w w)$ for width-$w$ posets, $O(n^2)$ for series-parallel posets [23], and $O(n^2)$ also for posets whose cover graph is a forest [5]; the *cover graph* of a poset $(V, \prec)$ is the directed graph $(V, E)$ where the edge set $E$ is the transitive reduction of $\prec$ (a.k.a. Hasse diagram). If parameterized by the treewidth of the cover graph, $t$, the problem can be solved with $O(n^{t+3})$ arithmetic operations by an inclusion-exclusion algorithm [17]. On the other hand, the problem parameterized by $t$ is $W[1]$-hard [14], and so it may be difficult, or even impossible, to find an algorithm that runs in time $O(f(t)n^d)$ for some computable function $f$ and constant $d$.

1.1 Theoretical contributions

In this paper, we give a new algorithm that exploits small treewidth. Write $\tilde{O}(f)$ as a shorthand for $f(\log f)^{O(1)}$. We prove the following in Section 3.

**► Theorem 1 (Main).** The linear extensions of a given $n$-element poset can be counted with $\tilde{O}(n^{t+3})$ bit-operations, where $t$ is the treewidth of the cover graph of the poset.

We state the bound in terms of bit-complexity to emphasize the fact that the dominating computations deal with large integers. Indeed, the bounds stated in the previous paragraph refer to the number of arithmetic operations. Thus, in particular, our bound improves the previous bound of Kangas et al. [17] by a factor of $n$. For large $n$ and small $t$ the improvement is relatively significant; for instance, for $t=2$ the bound is reduced from $\tilde{O}(n^6)$ to $\tilde{O}(n^5)$.

Perhaps more importantly, the design of our algorithm is very different from that of the inclusion-exclusion algorithm. In the latter, the idea is to view a linear extension as a bijective mapping and then remove the global bijectivity constraint by inclusion-exclusion, similarly to previous applications to matrix permanent [29], Hamiltonian path [18], and set partitioning [19], but incurring only a polynomial overhead. Once the bijectivity constraint is removed, what remains is a collection of simpler subproblems with local constraints. The subproblems can be handled by standard routines that exploit small treewidth [7, 12]; see Section 2.4 for some additional details.

The present algorithm, in contrast, takes care of the bijectivity constraint within dynamic programming along a tree decomposition and is, with this respect, similar to a folklore $t^{O(t)}n$-time algorithm for the Hamiltonian path problem. However, #LE being $W[1]$-hard one may expect it to require a significantly larger dynamic programming table. We give a formulation, where each node of a tree decomposition is associated with $\Theta(n^{t+1})$ counts. This formulation leads to a challenge: a step in the dynamic program that combines two (or more) arrays of such counts appears to require a quadratic number of arithmetic operations, $\Theta(n^{2t+2})$, if implemented in a straightforward manner. Fortunately, we discover that the key ingredient of the step takes a form of multidimensional convolution, which we can compute efficiently using known (deep) results for fast multiplication of multivariate polynomials.

Concerning space complexity we only make a couple of observations here: Both our algorithm and the inclusion-exclusion algorithm by Kangas et al. [17] require $\tilde{O}(n^{t+2})$ bits of
5:2 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

The #LE problem is #P-complete [11] but admits a fully polynomial approximation scheme [13]. The best known asymptotic bounds for the expected running time are $O(\epsilon^{-2}n^3 \log^2 \ell \log n)$ [6] and $O(\epsilon^{-2}n^5 \log^2 n)$ [30], where $\ell$ is the number of linear extensions and $\epsilon$ the allowed relative error. These bounds, while polynomial, become prohibitively large in practice if, say, one requires an accuracy of $\epsilon = 0.01$ and $n$ is around one hundred.

Exact and parameterized algorithms offer an alternative approach to design practical algorithms for the problem. For the required number of arithmetic operations, the best known worst-case bound is $O(2^n n)$ in general, which is achieved by a simple dynamic programming algorithm. For several special instance classes better bounds are known: $O(n^w w)$ for width-$w$ posets, $O(n^2)$ for series-parallel posets [23], and $O(n^2)$ also for posets whose cover graph is a forest [5]; the *cover graph* of a poset $(V, \prec)$ is the directed graph $(V, E)$ where the edge set $E$ is the transitive reduction of $\prec$ (a.k.a. Hasse diagram). If parameterized by the treewidth of the cover graph, $t$, the problem can be solved with $O(n^{t+3})$ arithmetic operations by an inclusion-exclusion algorithm [17]. On the other hand, the problem parameterized by $t$ is $W[1]$-hard [14], and so it may be difficult, or even impossible, to find an algorithm that runs in time $O(f(t)n^d)$ for some computable function $f$ and constant $d$.

1.1 Theoretical contributions

In this paper, we give a new algorithm that exploits small treewidth. Write $\tilde{O}(f)$ as a shorthand for $f(\log f)^{O(1)}$. We prove the following in Section 3.

► **Theorem 1 (Main).** *The linear extensions of a given $n$-element poset can be counted with $\tilde{O}(n^{t+3})$ bit-operations, where $t$ is the treewidth of the cover graph of the poset.*

We state the bound in terms of bit-complexity to emphasize the fact that the dominating computations deal with large integers. Indeed, the bounds stated in the previous paragraph refer to the number of arithmetic operations. Thus, in particular, our bound improves the previous bound of Kangas et al. [17] by a factor of $n$. For large $n$ and small $t$ the improvement is relatively significant; for instance, for $t=2$ the bound is reduced from $\tilde{O}(n^6)$ to $\tilde{O}(n^5)$.

Perhaps more importantly, the design of our algorithm is very different from that of the inclusion-exclusion algorithm. In the latter, the idea is to view a linear extension as a bijective mapping and then remove the global bijectivity constraint by inclusion-exclusion, similarly to previous applications to matrix permanent [29], Hamiltonian path [18], and set partitioning [19], but incurring only a polynomial overhead. Once the bijectivity constraint is removed, what remains is a collection of simpler subproblems with local constraints. The subproblems can be handled by standard routines that exploit small treewidth [7, 12]; see Section 2.4 for some additional details.

The present algorithm, in contrast, takes care of the bijectivity constraint within dynamic programming along a tree decomposition and is, with this respect, similar to a folklore $t^{O(t)}n$-time algorithm for the Hamiltonian path problem. However, #LE being $W[1]$-hard one may expect it to require a significantly larger dynamic programming table. We give a formulation, where each node of a tree decomposition is associated with $\Theta(n^{t+1})$ counts. This formulation leads to a challenge: a step in the dynamic program that combines two (or more) arrays of such counts appears to require a quadratic number of arithmetic operations, $\Theta(n^{2t+2})$, if implemented in a straightforward manner. Fortunately, we discover that the key ingredient of the step takes a form of multidimensional convolution, which we can compute efficiently using known (deep) results for fast multiplication of multivariate polynomials.

Concerning space complexity we only make a couple of observations here: Both our algorithm and the inclusion-exclusion algorithm by Kangas et al. [17] require $\tilde{O}(n^{t+2})$ bits of
space; this can be reduced by a factor about linear in $n$ by carrying the computations modulo
several small relative primes and constructing the final output using the Chinese remainder
theorem. The simple dynamic programming algorithm requires $\tilde{O}(2^n)$ bits of space.

## 1.2 Empirical contributions

In the second part of the paper we address the practical value of the algorithm. Given that
the present algorithm is technically more convoluted than the inclusion-exclusion algorithm,
it is natural to ask, whether the improvement in the asymptotic worst case time requirement
can be realized in practice. Our interest is particularly in instances where $t$ is small (at most
four) and $n$ ranging up to a few hundred.

A well known challenge in practical implementation of tree-decomposition based algorithms
is that finding an optimal-width tree decomposition may be insufficient for minimizing the
computational cost: the running time of the dynamic programming algorithm can be sensitive
to the shape of the tree decomposition. Bodlaender and Fomin [9] addressed this issue from
a theoretical viewpoint by studying the complexity of finding a tree decomposition that
minimizes a sum of costs associated with each node of a tree decomposition. In their *f-cost*
framework the cost of a node is allowed to depend only on the width of the node (i.e., the size
of the associated bag; see Section 2). Recently, Abseher et al. [1, 2] presented a more general
and more practical heuristic approach. Their *htd* library [1] allows a user to generate a
variety of optimal-width tree decompositions and also (locally) optimize a given cost function.
Moreover, they proposed and evaluated [2] a method to learn an appropriate cost function,
or regression model, from collected empirical data on running times on varying instances.
The method can be viewed as an instantiation of the method of empirical hardness models
[20] for the algorithm selection problem [28].

Following these ideas we have implemented and tested our algorithm for \#LE using
a collection of synthetically generated instances (posets) together with a variety of tree
decompositions generated by htd for each instance. We will report on and discuss our
preliminary observations, which suggest that selecting the tree decomposition using a learned
regression model can make a difference, at least for the smallest treewidth ($t=2$): compared
to the median running time over generated tree decompositions, the selected one typically
yields almost an order-of-magnitude speedup.

## 1.3 Organization

Some preliminary material is given in Section 2. Section 3 is devoted to proving Theorem 1.
In Section 4 we describe some implementation details and report on empirical results. We
conclude in Section 5 by highlighting the main observations and some open questions.

# 2 Preliminaries

In this section we introduce some basic terminology, notation, and facts.

## 2.1 Basic notation

We denote by $\mathbb{N}$ the set of natural numbers $\{0, 1, 2, \dots\}$. For two sets $S$ and $U$ we write $S^U$
for the set of functions from $U$ to $S$. If $m \in \mathbb{N}$ we write $[m]$ for the set $\{1, \dots, m\}$. By $S^m$
we denote the set of $m$-tuples $a = (a_i)_{i=1}^m$ with $a_i \in S$.
space; this can be reduced by a factor about linear in $n$ by carrying the computations modulo several small relative primes and constructing the final output using the Chinese remainder theorem. The simple dynamic programming algorithm requires $\tilde{O}(2^n)$ bits of space.

## 1.2 Empirical contributions

In the second part of the paper we address the practical value of the algorithm. Given that the present algorithm is technically more convoluted than the inclusion-exclusion algorithm, it is natural to ask, whether the improvement in the asymptotic worst case time requirement can be realized in practice. Our interest is particularly in instances where $t$ is small (at most four) and $n$ ranging up to a few hundred.

A well known challenge in practical implementation of tree-decomposition based algorithms is that finding an optimal-width tree decomposition may be insufficient for minimizing the computational cost: the running time of the dynamic programming algorithm can be sensitive to the shape of the tree decomposition. Bodlaender and Fomin [9] addressed this issue from a theoretical viewpoint by studying the complexity of finding a tree decomposition that minimizes a sum of costs associated with each node of a tree decomposition. In their f-cost framework the cost of a node is allowed to depend only on the width of the node (i.e., the size of the associated bag; see Section 2). Recently, Abseher et al. [1, 2] presented a more general and more practical heuristic approach. Their htd library [1] allows a user to generate a variety of optimal-width tree decompositions and also (locally) optimize a given cost function. Moreover, they proposed and evaluated [2] a method to learn an appropriate cost function, or regression model, from collected empirical data on running times on varying instances. The method can be viewed as an instantiation of the method of empirical hardness models [20] for the algorithm selection problem [28].

Following these ideas we have implemented and tested our algorithm for \#LE using a collection of synthetically generated instances (posets) together with a variety of tree decompositions generated by htd for each instance. We will report on and discuss our preliminary observations, which suggest that selecting the tree decomposition using a learned regression model can make a difference, at least for the smallest treewidth ($t=2$): compared to the median running time over generated tree decompositions, the selected one typically yields almost an order-of-magnitude speedup.

## 1.3 Organization

Some preliminary material is given in Section 2. Section 3 is devoted to proving Theorem 1. In Section 4 we describe some implementation details and report on empirical results. We conclude in Section 5 by highlighting the main observations and some open questions.

# 2 Preliminaries

In this section we introduce some basic terminology, notation, and facts.

## 2.1 Basic notation

We denote by $\mathbb{N}$ the set of natural numbers $\{0, 1, 2, \dots\}$. For two sets $S$ and $U$ we write $S^U$ for the set of functions from $U$ to $S$. If $m \in \mathbb{N}$ we write $[m]$ for the set $\{1, \dots, m\}$. By $S^m$ we denote the set of $m$-tuples $a = (a_i)_{i=1}^m$ with $a_i \in S$.
5:4 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

The restriction of a function $\alpha: U \to S$ to a subset $A \subset U$ is defined in the standard manner and denoted by $\alpha|_A$; conversely, we say that $\alpha$ is an extension of $\alpha|_A$. We also denote by $\alpha^{v \to i}$ the extension of $\alpha$ that we obtain by mapping an added element $v \notin U$ to $i$.

We use the Iverson's bracket notation: for a proposition $P$, the expression $[P]$ evaluates to 1 if $P$ is true, and to 0 otherwise.

2.2 Factorials and multiplication of polynomials

Let $a = (a_1, \dots, a_k) \in \mathbb{N}^k$. We denote $a! := a_1! \cdots a_k!$ and $|a| := a_1 + \cdots + a_k$. Since $|a|!/a!$ is a multinomial coefficient, we have the following.

► **Fact 2.** If $a$ is a tuple of nonegative integers, then $a!$ divides $|a|!$.

Another fact we need concerns the complexity of multiplying two multivariate polynomials that are sparse in the sense that their total degree is given an upper bound, while the degrees of the individual variables may be large (not larger than the total degree, of course). We assume that a polynomial is represented by a list of its coefficients. The following result can be obtained by a straightforward specialization of a more general and detailed bound due to van der Hoeven and Lecerf [31, Cor. 4].

**Fact 3.** Two $k$-variate polynomials with $\tilde{O}(n)$-bit integer coefficients and total degree at most $n$ can be multiplied with $\tilde{O}((n^{k})(n+k))$ bit-operations.<fnref n="1" />

For univariate polynomials the bound is quadratic in $n$ because the coefficients can be large.

2.3 Tree decomposition

**Definition 4 (Tree decomposition).** A tree decomposition of a graph $G = (V, E)$ is a pair $(T, B)$ where $T = (I, F)$ is a tree and $B$ maps each $x \in I$ to a bag $B_x \subseteq V$ such that

1. for each $v \in V$, the set $\{x \in I : v \in B_x\}$ induces a nonempty connected subtree of $T$,

2. for each $uv \in E$, there exists $x \in I$ with $u, v \in B_x$.

The width of the tree decomposition is the size of its largest bag minus one, $\max_{x \in I} |B_x| - 1$, and the treewidth of a graph is the minimum width over all its tree decompositions.

For a graph of treewidth $t$, we can find a tree decomposition of width $t$ in time $t^{O(t^3)n}$ using Bodlaender's algorithm [8] or in time $\tilde{O}(nt^{t+2})$ using the approach of Arnborg et al. [4].

A tree decomposition is *rooted* if the edges of the tree are directed so that there is a unique node, the *root*, that has no parent. Clearly, one obtains a rooted tree decomposition by simply choosing one node as the root and directing the edges accordingly.

**Definition 5 (Nice tree decomposition).** A rooted tree decomposition $(T, B)$ of a graph $G = (V, E)$ is *nice* if each node $x$ of $T$ is of one of the following types:

(leaf) $x$ has no children and $|B_x| = 1$;

(introduce) $x$ has a unique child $y$ and $B_x = B_y \cup \{v\}$ for some $v \in V \setminus B_y$;

(forget) $x$ has a unique child $y$ and $B_x = B_y \setminus \{v\}$ for some $v \in B_y$;

(join) $x$ has exactly two children $y, z$ and $B_x = B_y = B_z$.

We can convert a given tree decomposition of width $t$ and $O(n)$ nodes into a nice tree decomposition of width $t$ and $O(tn)$ nodes in time $t^{O(1)n}$ [10].

<footnote n="1">¹ In fact, this result assumes we have access to a $\tilde{\Omega}(n)$-bit prime $p$ and to a primitive element (i.e., generator) of $\mathbb{F}_p^*$, a multiplicative field of order $p$. Finding such numbers seem hard, theoretically: no deterministic polynomial time algorithm is known for the former, and no polynomial time algorithm is known for the latter. The result thus concerns the non-uniform model of computational complexity.</footnote>
5:4 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

The restriction of a function $\alpha: U \to S$ to a subset $A \subset U$ is defined in the standard manner and denoted by $\alpha|_A$; conversely, we say that $\alpha$ is an extension of $\alpha|_A$. We also denote by $\alpha^{v \to i}$ the extension of $\alpha$ that we obtain by mapping an added element $v \notin U$ to $i$.

We use the Iverson's bracket notation: for a proposition $P$, the expression $[P]$ evaluates to 1 if $P$ is true, and to 0 otherwise.

## 2.2 Factorials and multiplication of polynomials

Let $a = (a_1, \dots, a_k) \in \mathbb{N}^k$. We denote $a! := a_1! \cdots a_k!$ and $|a| := a_1 + \cdots + a_k$. Since $|a|!/a!$ is a multinomial coefficient, we have the following.

**Fact 2.** If $a$ is a tuple of nonegative integers, then $a!$ divides $|a|!$.

Another fact we need concerns the complexity of multiplying two multivariate polynomials that are sparse in the sense that their total degree is given an upper bound, while the degrees of the individual variables may be large (not larger than the total degree, of course). We assume that a polynomial is represented by a list of its coefficients. The following result can be obtained by a straightforward specialization of a more general and detailed bound due to van der Hoeven and Lecerf [31, Cor. 4].

**Fact 3.** Two $k$-variate polynomials with $\tilde{O}(n)$-bit integer coefficients and total degree at most $n$ can be multiplied with $\tilde{O}((n^k)^{(n+k)})$ bit-operations.<fnref n="1" />

For univariate polynomials the bound is quadratic in $n$ because the coefficients can be large.

## 2.3 Tree decomposition

**Definition 4 (Tree decomposition).** A tree decomposition of a graph $G = (V, E)$ is a pair $(T, B)$ where $T = (I, F)$ is a tree and $B$ maps each $x \in I$ to a bag $B_x \subseteq V$ such that

1. for each $v \in V$, the set $\{x \in I : v \in B_x\}$ induces a nonempty connected subtree of $T$,

2. for each $uv \in E$, there exists $x \in I$ with $u, v \in B_x$.

The width of the tree decomposition is the size of its largest bag minus one, $\max_{x \in I} |B_x| - 1$, and the treewidth of a graph is the minimum width over all its tree decompositions.

For a graph of treewidth $t$, we can find a tree decomposition of width $t$ in time $t^{O(t^3)n}$ using Bodlaender's algorithm [8] or in time $\tilde{O}(n^{t+2})$ using the approach of Arnborg et al. [4].

A tree decomposition is rooted if the edges of the tree are directed so that there is a unique node, the *root*, that has no parent. Clearly, one obtains a rooted tree decomposition by simply choosing one node as the root and directing the edges accordingly.

**Definition 5 (Nice tree decomposition).** A rooted tree decomposition $(T, B)$ of a graph $G = (V, E)$ is *nice* if each node $x$ of $T$ is of one of the following types:

(leaf) $x$ has no children and $|B_x| = 1$;

(introduce) $x$ has a unique child $y$ and $B_x = B_y \cup \{v\}$ for some $v \in V \setminus B_y$;

(forget) $x$ has a unique child $y$ and $B_x = B_y \setminus \{v\}$ for some $v \in B_y$;

(join) $x$ has exactly two children $y, z$ and $B_x = B_y = B_z$.

We can convert a given tree decomposition of width $t$ and $O(n)$ nodes into a nice tree decomposition of width $t$ and $O(tn)$ nodes in time $t^{O(1)n}$ [10].

<footnote n="1">¹ In fact, this result assumes we have access to a $\tilde{\Omega}(n)$-bit prime $p$ and to a primitive element (i.e., generator) of $\mathbb{F}_p^*$, a multiplicative field of order $p$. Finding such numbers seem hard, theoretically: no deterministic polynomial time algorithm is known for the former, and no polynomial time algorithm is known for the latter. The result thus concerns the non-uniform model of computational complexity.</footnote>
## 2.4 Counting linear extensions via inclusion-exclusion

Kangas et al. [17] showed that the number of linear extensions of a poset $(V, \prec)$ whose cover graph is $G = (V, E)$ is given by the formula

$$ \sum_{k=1}^{n} \binom{n}{k} (-1)^{n-k} \sum_{\tau} \prod_{uv \in E} [\tau(u) < \tau(v)], $$

where $\tau$ runs over all functions from $V$ to $[k]$.

Supposing $G$ has treewidth $t$, it is well known that there is an elimination ordering $v_1, \dots, v_n$ of the vertices, such that when removing the vertices from the graph in this order and always connecting the neighbors of the removed vertex, the size of the largest clique in the obtained graphs is $t+1$. The $n$-dimensional inner summation over the variables $\tau(v_i)$, for $i \in [n]$, can be processed iteratively along such an ordering, the $i$th one-dimensional summation over $\tau(v_i)$ requiring $O(n_i k^{t+1})$ additions and multiplications of $O(n \log n)$-bit numbers, for some $n_1, \dots, n_n$ that sum up to $O(n)$. In total, the evaluation of the inclusion-exclusion formula thus requires $\tilde{O}(n^{t+4})$ bit-operations. We omit a more detailed treatment of the algorithm, as the method applied for computing the inner summation is standard. (The original analysis of Kangas et al. [17] use a looser bound of $n_i = O(n)$ for each $i$, arriving at a bound that is larger by a factor of $n$.)

# 3 The algorithm – proof of Theorem 1

We implement a standard recipe of designing a tree-decomposition based algorithm. The outline of the algorithm is as follows.

A1 Compute the cover graph of the input poset.

A2 Find a minimum-width nice tree decomposition of the cover graph.

A3 Run dynamic programming over the nice tree decomposition.

We will next consider each step in detail. We will see that the last step dominates our asymptotic running time bounds.

## 3.1 Computing the cover graph

The cover graph $G = (V, E)$ is obtained by computing the transitive reduction of the input poset $(V, \prec)$. The transitive reduction can be computed in time $O(|V| \cdot |\prec|)$ [3], which is $O(n^{t+2})$ for all $t \ge 1$.

## 3.2 Finding a minimum-width nice tree decomposition

As mentioned in Section 2, if the cover graph has treewidth $t$, then a width-$t$ nice tree decomposition of the cover graph can be found in $\tilde{O}(n^{t+2})$ time.

## 3.3 Dynamic programming

Suppose now that a width-$t$ nice tree decomposition $(T, B)$ of the cover graph $G$ is available. Our idea will be to associate each node of $T$ with an array of numbers such that (i) the numbers at the root node are sufficient for computing the number of linear extensions and (ii) the array of a node can be computed from the arrays of its child nodes.
## 2.4 Counting linear extensions via inclusion-exclusion

Kangas et al. [17] showed that the number of linear extensions of a poset $(V, \prec)$ whose cover graph is $G = (V, E)$ is given by the formula

$$ \sum_{k=1}^{n} \binom{n}{k} (-1)^{n-k} \sum_{\tau} \prod_{uv \in E} [\tau(u) < \tau(v)], $$

where $\tau$ runs over all functions from $V$ to $[k]$.

Supposing $G$ has treewidth $t$, it is well known that there is an elimination ordering $v_1, \dots, v_n$ of the vertices, such that when removing the vertices from the graph in this order and always connecting the neighbors of the removed vertex, the size of the largest clique in the obtained graphs is $t+1$. The $n$-dimensional inner summation over the variables $\tau(v_i)$, for $i \in [n]$, can be processed iteratively along such an ordering, the $i$th one-dimensional summation over $\tau(v_i)$ requiring $O(n_i k^{t+1})$ additions and multiplications of $O(n \log n)$-bit numbers, for some $n_1, \dots, n_n$ that sum up to $O(n)$. In total, the evaluation of the inclusion-exclusion formula thus requires $\tilde{O}(n^{t+4})$ bit-operations. We omit a more detailed treatment of the algorithm, as the method applied for computing the inner summation is standard. (The original analysis of Kangas et al. [17] use a looser bound of $n_i = O(n)$ for each $i$, arriving at a bound that is larger by a factor of $n$.)

# 3 The algorithm – proof of Theorem 1

We implement a standard recipe of designing a tree-decomposition based algorithm. The outline of the algorithm is as follows.

A1 Compute the cover graph of the input poset.

A2 Find a minimum-width nice tree decomposition of the cover graph.

A3 Run dynamic programming over the nice tree decomposition.

We will next consider each step in detail. We will see that the last step dominates our asymptotic running time bounds.

## 3.1 Computing the cover graph

The cover graph $G = (V, E)$ is obtained by computing the transitive reduction of the input poset $(V, \prec)$. The transitive reduction can be computed in time $O(|V| \cdot |\prec|)$ [3], which is $O(n^{t+2})$ for all $t \ge 1$.

## 3.2 Finding a minimum-width nice tree decomposition

As mentioned in Section 2, if the cover graph has treewidth $t$, then a width-$t$ nice tree decomposition of the cover graph can be found in $\tilde{O}(n^{t+2})$ time.

## 3.3 Dynamic programming

Suppose now that a width-$t$ nice tree decomposition $(T, B)$ of the cover graph $G$ is available. Our idea will be to associate each node of $T$ with an array of numbers such that (i) the numbers at the root node are sufficient for computing the number of linear extensions and (ii) the array of a node can be computed from the arrays of its child nodes.
5:6 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

The following notation will be useful. Denote by $V_x$ the set of vertices covered by the subtree of $T$ rooted at $x$, that is, $V_x$ is the union of the bags $B_y$ of nodes $y$ to which there is a directed path from $x$. Write $n_x$ for the size $|V_x|$ and $E_x$ for set of edges in the induced graph $G[V_x]$.

Now, for each node $x \in T$ and injection $\alpha \in [n_x]^{B_x}$, define $\ell_x(\alpha)$ as the number of bijections $\pi \in [n_x]^{V_x}$ such that $\pi(v) = \alpha(v)$ for all $v \in B_x$, and $\pi(u) < \pi(v)$ whenever $uv \in E_x$. In other words, $\ell_x(\alpha)$ is the number of ways to extend $\alpha$ to a linear extension of the induced poset $(V_x, < \cap (V_x \times V_x))$, where we view a linear extension as a bijection from $V_x$ to $[n_x]$ that satisfies the ordering constraints.

We begin by showing that the values $\ell_x(\alpha)$ are sufficient for computing the number of linear extensions of the poset, that is, they satisfy the listed conditions (i) and (ii). After that we consider the time requirement of computing the values $\ell_x(\alpha)$ for each node of the nice tree decomposition.

Consider first the root node.

► Lemma 6 (Root). We have $\ell(V) = \sum_{\alpha} \ell_r(\alpha)$, where $\alpha$ runs over all injections in $[n_x]^{B_x}$.

**Proof.** Since $V_r = V$, $E_r = E$, and $n_r = n$, we have that

$$ \sum_{\alpha} \ell_r(\alpha) = \sum_{\pi} \prod_{uv \in E} [\pi(u) < \pi(v)] = \ell(V), $$

where $\alpha$ and $\pi$ run over all injections in $[n]^{B_r}$ and $[n]^V$, respectively.

<figure><img src="image_37.png" /></figure>

Next we will show separately for each node type of the nice tree decomposition, how the values $\ell_x(\alpha)$ are determined by the corresponding values for the child node or child nodes of $x$. For all but join nodes the results are immediate, and we omit the proofs.

► Lemma 7 (Leaf). If $x$ is a leaf node, then $\ell_x(\alpha) = 1$ for the unique injection $\alpha$ in $[n_x]^{B_x}$.

For an introduce node, we simply restrict the injection $\alpha$ to the bag in question and check that the ordering constraint holds.

► Lemma 8 (Introduce). If $x$ is an introduce node with child $y$, then

$$ \ell_x(\alpha) = \ell_y(\alpha|_{B_y}) \prod_{u,v \in B_x: uv \in E} [\alpha(u) < \alpha(v)]. $$

For a forget node, we extend the injection $\alpha$ to the larger bag by mapping the new vertex to some value.

► Lemma 9 (Forget). If $x$ is a forget node with child $y$ and $B_x = B_y \setminus \{v\}$, then

$$ \ell_x(\alpha) = \sum_{a=1}^{n_y} \ell_y(\alpha^{v \to a}). $$

To handle a join node, we introduce some convenient notation. Let $\alpha$ be an injection from a $k$-element set $S$ to a range of integers $[m]$. Label the elements of $S$ such that $\alpha(v_1) < \dots < \alpha(v_k)$. For $i = 1, \dots, k-1$, denote by $\alpha_i$ the number of integers between $\alpha(v_i)$ and $\alpha(v_{i+1})$, that is, $\alpha_i := \alpha(v_{i+1}) - \alpha(v_i) - 1$; in addition, denote $\alpha_0 := \alpha(v_1) - 1$ and $\alpha_k := m - \alpha(v_k)$. Observe that $\alpha_0 + \dots + \alpha_k = m - k$. Furthermore, if $\beta$ is another injection from $S'$ to $[m']$, write $\beta \sim \alpha$ if $\beta$ and $\alpha$ specify the same linear order on $S \cap S'$, that is, $\beta(u) < \beta(v)$ if and only if $\alpha(u) < \alpha(v)$ for all $u, v \in S \cap S'$.
5:6 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

The following notation will be useful. Denote by $V_x$ the set of vertices covered by the subtree of $T$ rooted at $x$, that is, $V_x$ is the union of the bags $B_y$ of nodes $y$ to which there is a directed path from $x$. Write $n_x$ for the size $|V_x|$ and $E_x$ for set of edges in the induced graph $G[V_x]$.

Now, for each node $x \in T$ and injection $\alpha \in [n_x]^{B_x}$, define $\ell_x(\alpha)$ as the number of bijections $\pi \in [n_x]^{V_x}$ such that $\pi(v) = \alpha(v)$ for all $v \in B_x$, and $\pi(u) < \pi(v)$ whenever $uv \in E_x$. In other words, $\ell_x(\alpha)$ is the number of ways to extend $\alpha$ to a linear extension of the induced poset $(V_x, \prec \cap (V_x \times V_x))$, where we view a linear extension as a bijection from $V_x$ to $[n_x]$ that satisfies the ordering constraints.

We begin by showing that the values $\ell_x(\alpha)$ are sufficient for computing the number of linear extensions of the poset, that is, they satisfy the listed conditions (i) and (ii). After that we consider the time requirement of computing the values $\ell_x(\alpha)$ for each node of the nice tree decomposition.

Consider first the root node.

► Lemma 6 (Root). We have $\ell(V) = \sum_{\alpha} \ell_r(\alpha)$, where $\alpha$ runs over all injections in $[n_x]^{B_x}$.

**Proof.** Since $V_r = V$, $E_r = E$, and $n_r = n$, we have that

$$ \sum_{\alpha} \ell_r(\alpha) = \sum_{\pi} \prod_{uv \in E} [\pi(u) < \pi(v)] = \ell(V), $$

where $\alpha$ and $\pi$ run over all injections in $[n]^{B_r}$ and $[n]^V$, respectively.

<figure><img src="image_40.png" /></figure>

Next we will show separately for each node type of the nice tree decomposition, how the values $\ell_x(\alpha)$ are determined by the corresponding values for the child node or child nodes of $x$. For all but join nodes the results are immediate, and we omit the proofs.

► Lemma 7 (Leaf). If $x$ is a leaf node, then $\ell_x(\alpha) = 1$ for the unique injection $\alpha$ in $[n_x]^{B_x}$.

For an introduce node, we simply restrict the injection $\alpha$ to the bag in question and check that the ordering constraint holds.

► Lemma 8 (Introduce). If $x$ is an introduce node with child $y$, then

$$ \ell_x(\alpha) = \ell_y(\alpha|_{B_y}) \prod_{u,v \in B_x: uv \in E} [\alpha(u) < \alpha(v)]. $$

For a forget node, we extend the injection $\alpha$ to the larger bag by mapping the new vertex to some value.

► Lemma 9 (Forget). If $x$ is a forget node with child $y$ and $B_x = B_y \setminus \{v\}$, then

$$ \ell_x(\alpha) = \sum_{a=1}^{n_y} \ell_y(\alpha^{v \to a}). $$

To handle a join node, we introduce some convenient notation. Let $\alpha$ be an injection from a $k$-element set $S$ to a range of integers $[m]$. Label the elements of $S$ such that $\alpha(v_1) < \dots < \alpha(v_k)$. For $i = 1, \dots, k-1$, denote by $\alpha_i$ the number of integers between $\alpha(v_i)$ and $\alpha(v_{i+1})$, that is, $\alpha_i := \alpha(v_{i+1}) - \alpha(v_i) - 1$; in addition, denote $\alpha_0 := \alpha(v_1) - 1$ and $\alpha_k := m - \alpha(v_k)$. Observe that $\alpha_0 + \dots + \alpha_k = m - k$. Furthermore, if $\beta$ is another injection from $S'$ to $[m']$, write $\beta \sim \alpha$ if $\beta$ and $\alpha$ specify the same linear order on $S \cap S'$, that is, $\beta(u) < \beta(v)$ if and only if $\alpha(u) < \alpha(v)$ for all $u, v \in S \cap S'$.
► Lemma 10 (Join). If x is a join node with children y and z, then

$$ \ell_x(\alpha) = \sum_{\beta} \sum_{\gamma} [\alpha \sim \beta \sim \gamma] \prod_{i=0}^{|B_x|} [\alpha_i = \beta_i + \gamma_i] \binom{\alpha_i}{\beta_i} \ell_y(\beta) \ell_z(\gamma), $$

where $\beta$ and $\gamma$ run over all injections in $[n_y]^{B_y}$ and $[n_z]^{B_z}$, respectively.

**Proof.** By definition,

$$ \ell_x(\alpha) = \sum_{\pi} \prod_{uv \in E_x} [\pi(u) < \pi(v)], $$

where $\pi$ runs over all bijections from $V_x$ to $[n_x]$ that extend $\alpha$. Observe that by the tree decomposition properties, the sets $V_y \setminus B_x$ and $V_z \setminus B_x$ are disjoint and their union is $V_x \setminus B_x$. Thus we may represent any bijection $\pi: V_x \to [n_x]$ that extends $\alpha$ uniquely by a pair of injections $\beta': V_y \to [n_x]$ and $\gamma': V_z \to [n_x]$ whose restrictions to $B_x$ are equal to $\alpha$ and whose images $\beta'(V_y)$ and $\gamma'(V_z)$ cover $[n_x]$.

$$ \ell_x(\alpha) = \sum_{\beta'} \sum_{\gamma'} [\beta'(V_y) \cup \gamma'(V_z) = [n_x]] \prod_{uv \in E_y} [\beta'(u) < \beta'(v)] \prod_{uv \in E_z} [\gamma'(u) < \gamma'(v)], $$

where $\beta'$ and $\gamma'$ run over all injections that extend $\alpha$ in $[n_x]^{V_y}$ and $[n_x]^{V_z}$, respectively.

Consider then a mapping that “compresses” any such injection $\beta'$ into a bijection $\beta''$: $V_y \to [n_y]$ by letting $\beta''(v) := |\{u \in V_y : \beta'(u) \le \beta'(v)\}|$; let $\gamma''$ denote the bijection obtained similarly from an injection $\gamma'$. Let $\beta$ denote the restriction of $\beta''$ to $B_x$ and $\gamma$ the restriction of $\gamma''$ to $B_x$. We have that $\beta'$ and $\gamma'$ extend $\alpha$ if and only if $\beta \sim \alpha$ and $\gamma \sim \alpha$. Thus we get that

$$ \ell_x(\alpha) = \sum_{\beta'': \beta' \sim \alpha} \sum_{\gamma'': \gamma' \sim \alpha} \prod_{i=0}^{|B_x|} [\alpha_i = \beta_i + \gamma_i] \binom{\alpha_i}{\beta_i} \prod_{uv \in E_y} [\beta''(u) < \beta''(v)] \prod_{uv \in E_z} [\gamma''(u) < \gamma''(v)], $$

where $\beta''$ and $\gamma''$ run over all bijections in $[n_y]^{B_y}$ and $[n_z]^{B_z}$, respectively. The product of the binomial coefficients $\binom{\alpha_i}{\beta_i}$ is the number of pairs $(\beta', \gamma')$ that map to the same pair $(\beta'', \gamma'')$, that is, the number of interleavings of the $\beta_i + \gamma_i$ elements to the range of $\alpha_i$ elements.

To complete the proof, it suffices to write the summation over $\beta''$ as a double-summation: the outer summation being over all injections $\beta: B_y \to [n_y]$ and the inner summation being over all bijections $\beta'': V_y \to [n_y]$ that extend $\beta$; similarly for the summation over $\gamma''$. ◀

► Example 11 (Join in a tree). Consider the example illustrated in Figure 1. The cover graph is a tree with vertex set $V = \{a, b, c, d, e, f, g\}$. In a nice tree decomposition (not shown) the root node $x$ is a join of nodes $y$ and $z$, with $B_y = B_z = B_x = \{c, f\}$. The vertex sets associated with the nodes are $V_x = V$, $V_y = \{a, c, d, e, f\}$, and $V_z = \{b, c, f, g\}$. For the shown injection $\alpha$, the value of $\ell_x(\alpha)$ is obtained by a sum of $\ell_y(\beta) \cdot \ell_z(\gamma)$ over valid pairs $(\beta, \gamma)$, multiplied by the number of possible interleavings, which is given by a product of binomial coefficient. Shown is one pair $(\beta, \gamma)$, for which $\ell_y(\beta) = 1$ and $\ell_z(\gamma) = 1$ and the number of interleavings is equal to $\binom{2}{1}\binom{2}{2}\binom{1}{0} = 4$.

It remains to bound the running time of the algorithm.

► Lemma 12 (Time complexity). Given a width-t nice tree decomposition of the cover graph of an n-element poset, the linear extensions can be counted in $\tilde{O}(n^{t+3})$ bit-operations.
**► Lemma 10 (Join).** If $x$ is a join node with children $y$ and $z$, then

$$ \ell_x(\alpha) = \sum_{\beta} \sum_{\gamma} [\alpha \sim \beta \sim \gamma] \prod_{i=0}^{|B_x|} [\alpha_i = \beta_i + \gamma_i] \binom{\alpha_i}{\beta_i} \ell_y(\beta) \ell_z(\gamma), $$

where $\beta$ and $\gamma$ run over all injections in $[n_y]^{B_y}$ and $[n_z]^{B_z}$, respectively.

**Proof.** By definition,

$$ \ell_x(\alpha) = \sum_{\pi} \prod_{uv \in E_x} [\pi(u) < \pi(v)], $$

where $\pi$ runs over all bijections from $V_x$ to $[n_x]$ that extend $\alpha$. Observe that by the tree decomposition properties, the sets $V_y \setminus B_x$ and $V_z \setminus B_x$ are disjoint and their union is $V_x \setminus B_x$. Thus we may represent any bijection $\pi: V_x \to [n_x]$ that extends $\alpha$ uniquely by a pair of injections $\beta': V_y \to [n_x]$ and $\gamma': V_z \to [n_x]$ whose restrictions to $B_x$ are equal to $\alpha$ and whose images $\beta'(V_y)$ and $\gamma'(V_z)$ cover $[n_x]$.

$$ \ell_x(\alpha) = \sum_{\beta'} \sum_{\gamma'} [\beta'(V_y) \cup \gamma'(V_z) = [n_x]] \prod_{uv \in E_y} [\beta'(u) < \beta'(v)] \prod_{uv \in E_z} [\gamma'(u) < \gamma'(v)], $$

where $\beta'$ and $\gamma'$ run over all injections that extend $\alpha$ in $[n_x]^{V_y}$ and $[n_x]^{V_z}$, respectively.

Consider then a mapping that “compresses” any such injection $\beta'$ into a bijection $\beta''$: $V_y \to [n_y]$ by letting $\beta''(v) := |\{u \in V_y : \beta'(u) \le \beta'(v)\}|$; let $\gamma''$ denote the bijection obtained similarly from an injection $\gamma'$. Let $\beta$ denote the restriction of $\beta''$ to $B_x$ and $\gamma$ the restriction of $\gamma''$ to $B_x$. We have that $\beta'$ and $\gamma'$ extend $\alpha$ if and only if $\beta \sim \alpha$ and $\gamma \sim \alpha$. Thus we get that

$$ \ell_x(\alpha) = \sum_{\beta'':\beta' \sim \alpha} \sum_{\gamma'':\gamma' \sim \alpha} \prod_{i=0}^{|B_x|} [\alpha_i = \beta_i + \gamma_i] \binom{\alpha_i}{\beta_i} \prod_{uv \in E_y} [\beta''(u) < \beta''(v)] \prod_{uv \in E_z} [\gamma''(u) < \gamma''(v)], $$

where $\beta''$ and $\gamma''$ run over all bijections in $[n_y]^{B_y}$ and $[n_z]^{B_z}$, respectively. The product of the binomial coefficients $\binom{\alpha_i}{\beta_i}$ is the number of pairs $(\beta', \gamma')$ that map to the same pair $(\beta'', \gamma'')$, that is, the number of interleavings of the $\beta_i + \gamma_i$ elements to the range of $\alpha_i$ elements.

To complete the proof, it suffices to write the summation over $\beta''$ as a double-summation: the outer summation being over all injections $\beta: B_y \to [n_y]$ and the inner summation being over all bijections $\beta'': V_y \to [n_y]$ that extend $\beta$; similarly for the summation over $\gamma''$. $\blacksquare$

**► Example 11 (Join in a tree).** Consider the example illustrated in Figure 1. The cover graph is a tree with vertex set $V = \{a, b, c, d, e, f, g\}$. In a nice tree decomposition (not shown) the root node $x$ is a join of nodes $y$ and $z$, with $B_y = B_z = B_x = \{c, f\}$. The vertex sets associated with the nodes are $V_x = V$, $V_y = \{a, c, d, e, f\}$, and $V_z = \{b, c, f, g\}$. For the shown injection $\alpha$, the value of $\ell_x(\alpha)$ is obtained by a sum of $\ell_y(\beta) \cdot \ell_z(\gamma)$ over valid pairs $(\beta, \gamma)$, multiplied by the number of possible interleavings, which is given by a product of binomial coefficient. Shown is one pair $(\beta, \gamma)$, for which $\ell_y(\beta) = 1$ and $\ell_z(\gamma) = 1$ and the number of interleavings is equal to $\binom{2}{1}\binom{2}{2}\binom{1}{0} = 4$.

It remains to bound the running time of the algorithm.

**► Lemma 12 (Time complexity).** Given a width-$t$ nice tree decomposition of the cover graph of an $n$-element poset, the linear extensions can be counted in $\tilde{O}(n^{t+3})$ bit-operations.
<figure><img src="image_38.png" /><figcaption>Figure 1 An illustration of the recurrence for a join node; see Example 11 for a description.</figcaption></figure>

**Proof.** Let $x$ be a node in the nice tree decomposition. For brevity, denote $k := |B_x|$. If $x$ is a leaf node, introduce node, or forget node, then the values $\ell_x(\alpha)$ for all injections $\alpha \in [n_x]^{B_x}$ can clearly be computed using $O(kn^k) = O(tn^{t+1})$ basic operations, some of which are additions of two $O(n \log n)$-bit numbers, thus using $\tilde{O}(n^{t+2})$ bit-operations (observe that the factor $t$ is $O(\log n^{t+2})$ and can thus be omitted).

Consider then the remaining case: $x$ is a join node. Let $y$ and $z$ be the two children of $x$. Recall that $B_x = B_y = B_z$.

Represent an injection $\alpha$ in $[n_x]^{B_x}$ as a pair $(\sigma, a)$, where $a = (a_i)_{i=1}^{k+1}$ with $a_i = \alpha_{i-1}$ and $\sigma$ is a bijection from $B_x$ to $[k]$ that captures the specified linear order, that is, $\sigma(u) < \sigma(v)$ if $\alpha(u) < \alpha(v)$. Clearly, the mapping $\alpha \mapsto (\sigma, a)$ is a bijection when we require that $a_i \in \mathbb{N}$ and $|a| = n_x - k$. Using this representation and Lemma 10, write

$$ \ell_x(\sigma, a) = \sum_b \sum_c \prod_{i=0}^{k} [a_i = b_i + c_i] \binom{a_i}{b_i} \ell_y(\sigma, b) \ell_z(\sigma, c), $$

where $b$ and $c$ run over $\mathbb{N}^{k+1}$. By writing $\ell'_x(\sigma, a) := \ell_x(\sigma, a)/a!$, we get the convolution form

$$ \ell'_x(\sigma, a) = \sum_{a=b+c} \ell'_y(\sigma, b) \ell'_z(\sigma, c). $$

To treat this as a multiplication of multivariate polynomials, consider a fixed bijection $\sigma$ and let $P_x(r_1, \dots, r_k)$ be the $k$-variate polynomial where the coefficient of $r_1^{a_1} \cdots r_k^{a_k}$ equals $n! \cdot \ell'_x(\sigma, a)$; we define $P_y$ and $P_z$ similarly. Note that $k$ variables suffice, since $a_{k+1}$ is determined by the fixed $|a|$. Here we multiplied by the factorial $n!$ to get integer coefficients (by Fact 2, since $n \ge |a|, |b|, |c|$). We have that $n! \cdot P_x = P_y P_z$, that is, we obtain $P_x$ by multiplying $P_y$ and $P_z$ and dividing each coefficient of the resulting polynomial by $n!$.

We bound the bit-complexity of the polynomial multiplication using Fact 3. The total degrees of the polynomials are at most $n-k$. Each coefficient of the polynomials is a $\tilde{O}(n)$-bit integer. Thus the multiplication takes $\tilde{O}((n)!)n$ bit-operations.

Multiplying the obtained bound by the number of bijections $\sigma$, we get that all $\ell_x(\sigma, a)$ can be computed using $\tilde{O}(n^{k+1}) = \tilde{O}(n^{t+2})$ bit-operations.

Because there are $O(tn)$ nodes in the nice tree decomposition, $\tilde{O}(n^{t+3})$ bit-operations suffice in total. ▼

## 4 Experiments

This section is devoted to empirical results. We first describe our implementation of the algorithm and the test instances used in the experiments. Then we show how the performance on the algorithm depends on the way we choose the tree decomposition.
<figure><img src="image_41.png" /><figcaption>Figure 1 An illustration of the recurrence for a join node; see Example 11 for a description.</figcaption></figure>

<table><thead><tr><th>Injection</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th></tr></thead><tbody><tr><th>α</th><td>a</td><td>b</td><td>©</td><td>d</td><td>e</td><td>(f)</td><td>g</td></tr><tr><th>β</th><td>a</td><td>©</td><td>d</td><td>e</td><td>(f)</td><td></td><td></td></tr><tr><th>γ</th><td>b</td><td>©</td><td>(f)</td><td>g</td><td></td><td></td><td></td></tr></tbody></table>

**Proof.** Let $x$ be a node in the nice tree decomposition. For brevity, denote $k := |B_x|$. If $x$ is a leaf node, introduce node, or forget node, then the values $\ell_x(\alpha)$ for all injections $\alpha \in [n_x]^{B_x}$ can clearly be computed using $O(kn^k) = O(tn^{t+1})$ basic operations, some of which are additions of two $O(n \log n)$-bit numbers, thus using $\tilde{O}(n^{t+2})$ bit-operations (observe that the factor $t$ is $O(\log n^{t+2})$ and can thus be omitted).

Consider then the remaining case: $x$ is a join node. Let $y$ and $z$ be the two children of $x$. Recall that $B_x = B_y = B_z$.

Represent an injection $\alpha$ in $[n_x]^{B_x}$ as a pair $(\sigma, a)$, where $a = (a_i)_{i=1}^{k+1}$ with $a_i = \alpha_{i-1}$ and $\sigma$ is a bijection from $B_x$ to $[k]$ that captures the specified linear order, that is, $\sigma(u) < \sigma(v)$ if $\alpha(u) < \alpha(v)$. Clearly, the mapping $\alpha \mapsto (\sigma, a)$ is a bijection when we require that $a_i \in \mathbb{N}$ and $|a| = n_x - k$. Using this representation and Lemma 10, write

$$ \ell_x(\sigma, a) = \sum_b \sum_c \prod_{i=0}^{k} [a_i = b_i + c_i] \binom{a_i}{b_i} \ell_y(\sigma, b) \ell_z(\sigma, c), $$

where $b$ and $c$ run over $\mathbb{N}^{k+1}$. By writing $\ell'_x(\sigma, a) := \ell_x(\sigma, a)/a!$, we get the convolution form

$$ \ell'_x(\sigma, a) = \sum_{a=b+c} \ell'_y(\sigma, b) \ell'_z(\sigma, c). $$

To treat this as a multiplication of multivariate polynomials, consider a fixed bijection $\sigma$ and let $P_x(r_1, \dots, r_k)$ be the $k$-variate polynomial where the coefficient of $r_1^{a_1} \cdots r_k^{a_k}$ equals $n! \cdot \ell'_x(\sigma, a)$; we define $P_y$ and $P_z$ similarly. Note that $k$ variables suffice, since $a_{k+1}$ is determined by the fixed $|a|$. Here we multiplied by the factorial $n!$ to get integer coefficients (by Fact 2, since $n \ge |a|, |b|, |c|$). We have that $n! \cdot P_x = P_y P_z$, that is, we obtain $P_x$ by multiplying $P_y$ and $P_z$ and dividing each coefficient of the resulting polynomial by $n!$.

We bound the bit-complexity of the polynomial multiplication using Fact 3. The total degrees of the polynomials are at most $n-k$. Each coefficient of the polynomials is a $\tilde{O}(n)$-bit integer. Thus the multiplication takes $\tilde{O}((n)!)n$ bit-operations.

Multiplying the obtained bound by the number of bijections $\sigma$, we get that all $\ell_x(\sigma, a)$ can be computed using $\tilde{O}(n^{k+1}) = \tilde{O}(n^{t+2})$ bit-operations.

Because there are $O(tn)$ nodes in the nice tree decomposition, $\tilde{O}(n^{t+3})$ bit-operations suffice in total. ◀

## 4 Experiments

This section is devoted to empirical results. We first describe our implementation of the algorithm and the test instances used in the experiments. Then we show how the performance on the algorithm depends on the way we choose the tree decomposition.
## 4.1 Implementation

We have implemented the algorithm described in Section 3 in a C++ program Countle.<fnref n="2" /> For multiplication of polynomials we used a C library FLINT [16]. For finding an optimal tree decomposition we used the C++ library htd [1]. We ran all experiments on machines with Intel Xeon E5540 CPUs; the same machines were used by Kangas et al. [17], which makes their running time measurements directly comparable to the present results.

Two implementation details are worth mentioning. First, for multiplication of multivariate polynomials, we transformed the polynomials into univariate polynomials using an appropriate Kronecker substitution. Specifically, separately for each node $x$ of the tree decomposition and the considered vertex ordering (bijection) $\sigma$, we encode a $k$-variate polynomial in variables $r_1, \dots, r_k$ as a univariate polynomial in variable $s$ by substituting $r_j := s^{d_1+1}\cdots(d_{j-1}+1)$, where each $d_i$ is an upper bound for the degree of $r_i$ in the polynomial. Using knowledge associated with the node $x$ and ordering $\sigma$, we aim at finding a value $d_i$ that is smaller than the trivial upper bound $n_x - k$. To this end, we set $d_i$ to the sum of the largest realized exponents of $r_i$ in the already computed polynomials for the two child nodes of $x$.

Second, we wish to ignore any impossible ordering $\sigma$ at a node $x$ of the tree decomposition, and so save both time and space. The key observation is that, even if the value $\ell_x(\sigma, a)$ is nonzero, we can ignore it if $\sigma$ assigns some two vertices in the bag $B_x$ an order that violates the partial order $\prec$, that is, for some $u, v \in B_x$ we have $u \prec v$ and $\sigma(u) > \sigma(v)$.

## 4.2 Instances

We generated random instances (posets) of different sizes for small values of treewidth $t$. We varied the number of elements $n$ from 10 to 199 ($t=2$), 109 ($t=3$), and 59 ($t=4$). For each pair $(t, n)$ we generated 5 posets; following Kangas et al. [17], we let each poset be a “grid tree,” constructed by randomly joining $t$-by-$t$ grids along the (boundary) edges, orienting the edges so that no directed cycles are introduced, and finally taking the transitive closure.

## 4.3 Results

Because the running time of Countle may be sensitive to the particular (nice) tree decomposition selected, we ran the program on 50 optimal-width tree decompositions, which we generated using htd; we checked that for every encountered instance, htd indeed generated tree decompositions of optimal width. We allowed each individual run to take up to 20 minutes of CPU time and 30 GB of memory.

First we considered the scaling of Countle in terms of the number of elements $n$ and treewidth $t$. We observed that, while the growth of the running time follows the rate suggested by the worst case bound, there is significant variance in the running times for any fixed $(n, t)$, due to differences in the five posets and the 50 tree decompositions per poset (compare median to best in Figure 2). Compared to an implementation of the inclusion-exclusion algorithm by Kangas et al. [17], VEIE, we find that Countle is an order of magnitude faster. For example, Countle can solve a typical (median) poset with a typical (median) tree decomposition in about 20 seconds if $n = 100$ and $t = 2$, or if $n = 50$ and $t = 3$, while VEIE requires about 200 seconds on such instances [17, Fig. 8] (not reproduced here). We have observed that the same pattern also holds for $t = 4$; we omit the detailed results here, as such posets are handled faster by another, exponential time algorithm of Kangas et al. [17, Fig. 8].

<footnote n="2">² Countle is free and publicly available at https://bitbucket.org/samsalo/countledist/.</footnote>
## 4.1 Implementation

We have implemented the algorithm described in Section 3 in a C++ program Countle.<fnref n="2" /> For multiplication of polynomials we used a C library FLINT [16]. For finding an optimal tree decomposition we used the C++ library htd [1]. We ran all experiments on machines with Intel Xeon E5540 CPUs; the same machines were used by Kangas et al. [17], which makes their running time measurements directly comparable to the present results.

Two implementation details are worth mentioning. First, for multiplication of multivariate polynomials, we transformed the polynomials into univariate polynomials using an appropriate Kronecker substitution. Specifically, separately for each node $x$ of the tree decomposition and the considered vertex ordering (bijection) $\sigma$, we encode a $k$-variate polynomial in variables $r_1, \dots, r_k$ as a univariate polynomial in variable $s$ by substituting $r_j := s^{(d_1+1)\cdots(d_{j-1}+1)}$, where each $d_i$ is an upper bound for the degree of $r_i$ in the polynomial. Using knowledge associated with the node $x$ and ordering $\sigma$, we aim at finding a value $d_i$ that is smaller than the trivial upper bound $n_x - k$. To this end, we set $d_i$ to the sum of the largest realized exponents of $r_i$ in the already computed polynomials for the two child nodes of $x$.

Second, we wish to ignore any impossible ordering $\sigma$ at a node $x$ of the tree decomposition, and so save both time and space. The key observation is that, even if the value $\ell_x(\sigma, a)$ is nonzero, we can ignore it if $\sigma$ assigns some two vertices in the bag $B_x$ an order that violates the partial order $\prec$, that is, for some $u, v \in B_x$ we have $u \prec v$ and $\sigma(u) > \sigma(v)$.

## 4.2 Instances

We generated random instances (posets) of different sizes for small values of treewidth $t$. We varied the number of elements $n$ from 10 to 199 ($t = 2$), 109 ($t = 3$), and 59 ($t = 4$). For each pair $(t, n)$ we generated 5 posets; following Kangas et al. [17], we let each poset be a “grid tree,” constructed by randomly joining $t$-by-$t$ grids along the (boundary) edges, orienting the edges so that no directed cycles are introduced, and finally taking the transitive closure.

## 4.3 Results

Because the running time of Countle may be sensitive to the particular (nice) tree decomposition selected, we ran the program on 50 optimal-width tree decompositions, which we generated using htd; we checked that for every encountered instance, htd indeed generated tree decompositions of optimal width. We allowed each individual run to take up to 20 minutes of CPU time and 30 GB of memory.

First we considered the scaling of Countle in terms of the number of elements $n$ and treewidth $t$. We observed that, while the growth of the running time follows the rate suggested by the worst case bound, there is significant variance in the running times for any fixed $(n, t)$, due to differences in the five posets and the 50 tree decompositions per poset (compare median to best in Figure 2). Compared to an implementation of the inclusion-exclusion algorithm by Kangas et al. [17], VEIE, we find that Countle is an order of magnitude faster. For example, Countle can solve a typical (median) poset with a typical (median) tree decomposition in about 20 seconds if $n = 100$ and $t = 2$, or if $n = 50$ and $t = 3$, while VEIE requires about 200 seconds on such instances [17, Fig. 8] (not reproduced here). We have observed that the same pattern also holds for $t = 4$; we omit the detailed results here, as such posets are handled faster by another, exponential time algorithm of Kangas et al. [17, Fig. 8].

<footnote n="2">² Countle is free and publicly available at https://bitbucket.org/samsalo/countledist/.</footnote>
5:10 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

<figure><img src="image_39.png" /><figcaption>■ **Figure 2** The running time of Countle (in seconds) on random “grid tree” posets of treewidth 2 and 3, with a varying number of elements *n*. For each poset, we generated 50 optimal-width tree decompositions and collected the median running time and the running times for the selected and the best tree decomposition. Shown are the medians of these three statistics over five independent posets for each value of *n*.</figcaption></figure>

Then we investigated whether one can efficiently select a near-optimal tree decomposition
from a collection of generated candidates. The observed variance in running times suggests
that, if successful, this could lead to a significant expedition of Countle, by up to one order
of magnitude. To constuct a “selector” we applied the method of Abseher et al. [2] in a
straightforward manner:

C1 We collected a data set of measured running times for multiple pairs of posets and tree decompositions. We used the procedure described in the previous section, except that we used a single poset (instead of five) for each combination of *n* and *t*. If a run was not completed within the 20-minute time limit, we simply discarded the instance (and thus introduced some bias).

C2 We computed for each tree decomposition the values of several features, such as statistics of bag sizes (by node type), node depths (by node type), and distances between join nodes; for a full feature list, see Abseher et al. [2].

C3 We fitted a multivariate linear regression model, separately for each t = 2, 3, 4, with the features as the predictor variables and the logarithm of the running time as the response variable. We used the machine learning software WEKA 3.6.13 [15] with default options. To select a tree decomposition for a given new poset, we first generated 50 candidate tree decompositions for the poset, and then selected the one for which the model predicted the shortest running time.

We observed (Figure 2) that, for *t* = 2, the model is almost always able to select a top-3 tree decomposition, which yields a nearly as good (i.e., short) running time as the best among the 50 tree decompositions. For *t* = 3 the performance degrades: the model is usually able to select a top-10 tree decomposition, which yields a running time that is systematically better than for a typical (median) tree decomposition, yet not quite achieving the performance of the best among the generated candidates. For *t* = 4 the performance degrades further, yet being better than by selecting a random tree decomposition (results not shown). In more quantitative terms, the proportions of tree decompositions (among 50) better than the selected one were 2.5 %, 12 %, 28 % for *t* = 2, 3, 4, respectively; these numbers are medians of averages over 5 test posets (one per fixed *n* and *t*).
5:10 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

<figure><img src="image_42.png" /><figcaption>■ **Figure 2** The running time of Countle (in seconds) on random “grid tree” posets of treewidth 2 and 3, with a varying number of elements *n*. For each poset, we generated 50 optimal-width tree decompositions and collected the median running time and the running times for the selected and the best tree decomposition. Shown are the medians of these three statistics over five independent posets for each value of *n*.</figcaption></figure>

Then we investigated whether one can efficiently select a near-optimal tree decomposition
from a collection of generated candidates. The observed variance in running times suggests
that, if successful, this could lead to a significant expedition of Countle, by up to one order
of magnitude. To construct a “selector” we applied the method of Abseher et al. [2] in a
straightforward manner:

C1 We collected a data set of measured running times for multiple pairs of posets and tree decompositions. We used the procedure described in the previous section, except that we used a single poset (instead of five) for each combination of *n* and *t*. If a run was not completed within the 20-minute time limit, we simply discarded the instance (and thus introduced some bias).

C2 We computed for each tree decomposition the values of several features, such as statistics of bag sizes (by node type), node depths (by node type), and distances between join nodes; for a full feature list, see Abseher et al. [2].

C3 We fitted a multivariate linear regression model, separately for each t = 2, 3, 4, with the features as the predictor variables and the logarithm of the running time as the response variable. We used the machine learning software WEKA 3.6.13 [15] with default options. To select a tree decomposition for a given new poset, we first generated 50 candidate tree decompositions for the poset, and then selected the one for which the model predicted the shortest running time.

We observed (Figure 2) that, for *t* = 2, the model is almost always able to select a top-3 tree decomposition, which yields a nearly as good (i.e., short) running time as the best among the 50 tree decompositions. For *t* = 3 the performance degrades: the model is usually able to select a top-10 tree decomposition, which yields a running time that is systematically better than for a typical (median) tree decomposition, yet not quite achieving the performance of the best among the generated candidates. For *t* = 4 the performance degrades further, yet being better than by selecting a random tree decomposition (results not shown). In more quantitative terms, the proportions of tree decompositions (among 50) better than the selected one were 2.5 %, 12 %, 28 % for *t* = 2, 3, 4, respectively; these numbers are medians of averages over 5 test posets (one per fixed *n* and *t*).
# 5 Concluding remarks

We have presented a new tree-decomposition based algorithm for counting linear extensions. The algorithm relies on fast multiplication of multivariate polynomials, thus differing radically from the inclusion-exclusion approach of Kangas et al. [17]. For any constant treewidth *t* the obtained asymptotic speedup is about linear in the number of elements *n*.

A question not settled here is whether one could save another factor of *n*, that is, solve the problem in time $\tilde{O}(n^{t+2})$. The present authors find this question particularly intriguing for two reasons: One is that for finding an optimal-width tree decomposition, the best known time complexity bound is $\tilde{O}(n^{t+2})$, assuming we let *t* grow at least logarithmically in *n*. The other reason is that for posets whose cover graph is a tree (*t* = 1), Atkinson's [5] algorithm takes - at least seemingly - a different approach and runs in time $\tilde{O}(n^3)$. Furthermore, Atkinson's algorithm is monotonic in the sense that all arithmetic operations are carried out with nonnegative numbers. This is in sharp contrast to both the present algorithm and the inclusion-exclusion algorithm, which crucially rely on a richer algebraic structure.

Our preliminary empirical study confirmed that the improvement in the asymptotic bound consistently transfers to the running times measured in practice. That said, the observed speedup, for *n* around one hundred, was by one order of magnitude rather than two. This “leak” of efficiency can, at least in part, be explained by the present algorithm’s higher sensitivity to the shape of the selected tree decomposition. Indeed, we observed that the best of 50 generated tree decompositions typically yields a 5- to 10-fold speedup in relation to a median tree decomposition. We also showed that there is an efficient way to select the best or close-to-best tree decomposition using a linear regression model that was fitted to a collected data set of instances along with the measured running times, following the method of Abseher et al. [2].

However, we observed that the performance of the regression method rapidly degraded as the treewidth *t* increases. This suggests that the general-purpose method may not suit well for the problem of counting linear extensions. A potential reason for suboptimal performance is that the default set of features [2] does not include perhaps the most informative quantity associated with a node *x* in a tree decomposition, namely the term $n_x^k$ (or some variant of it), which combines the size *k* of the bag of *x* with the number of vertices in the subtree rooted at *x*. This issue could be addressed by extending the feature set accordingly, or, potentially, by using some nonlinear regression model. On the other hand, we did inspect how well a single feature can predict a well-performing tree decomposition. We observed that for *t* = 2 and *t* = 3 the average depth of join nodes alone yielded predictions that were almost as good as the predictions by the full regression model that used all the features. Nevertheless, these observations also encourage looking for a simpler solution: manually constructing a heuristic function that approximates the actual running time by adding up estimated contributions of each tree decomposition node. Note that here the *f*-cost framework [9] is insufficient, as in that framework the contribution of each node can only depend on the size of the bag.

# References

1. Michael Abseher, Nysret Musliu, and Stefan Woltran. htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond. In *Proceedings of the 14th International Conference on Integration of AI and OR Techniques in Constraint Programming*, volume 10335 of *Lecture Notes in Computer Science*, pages 376-386. Springer, 2017.
# 5 Concluding remarks

We have presented a new tree-decomposition based algorithm for counting linear extensions. The algorithm relies on fast multiplication of multivariate polynomials, thus differing radically from the inclusion-exclusion approach of Kangas et al. [17]. For any constant treewidth *t* the obtained asymptotic speedup is about linear in the number of elements *n*.

A question not settled here is whether one could save another factor of *n*, that is, solve the problem in time $\tilde{O}(n^{t+2})$. The present authors find this question particularly intriguing for two reasons: One is that for finding an optimal-width tree decomposition, the best known time complexity bound is $\tilde{O}(n^{t+2})$, assuming we let *t* grow at least logarithmically in *n*. The other reason is that for posets whose cover graph is a tree (*t* = 1), Atkinson's [5] algorithm takes - at least seemingly - a different approach and runs in time $\tilde{O}(n^3)$. Furthermore, Atkinson's algorithm is monotonic in the sense that all arithmetic operations are carried out with nonnegative numbers. This is in sharp contrast to both the present algorithm and the inclusion-exclusion algorithm, which crucially rely on a richer algebraic structure.

Our preliminary empirical study confirmed that the improvement in the asymptotic bound consistently transfers to the running times measured in practice. That said, the observed speedup, for *n* around one hundred, was by one order of magnitude rather than two. This “leak” of efficiency can, at least in part, be explained by the present algorithm’s higher sensitivity to the shape of the selected tree decomposition. Indeed, we observed that the best of 50 generated tree decompositions typically yields a 5- to 10-fold speedup in relation to a median tree decomposition. We also showed that there is an efficient way to select the best or close-to-best tree decomposition using a linear regression model that was fitted to a collected data set of instances along with the measured running times, following the method of Abseher et al. [2].

However, we observed that the performance of the regression method rapidly degraded as the treewidth *t* increases. This suggests that the general-purpose method may not suit well for the problem of counting linear extensions. A potential reason for suboptimal performance is that the default set of features [2] does not include perhaps the most informative quantity associated with a node *x* in a tree decomposition, namely the term $n_x^k$ (or some variant of it), which combines the size *k* of the bag of *x* with the number of vertices in the subtree rooted at *x*. This issue could be addressed by extending the feature set accordingly, or, potentially, by using some nonlinear regression model. On the other hand, we did inspect how well a single feature can predict a well-performing tree decomposition. We observed that for *t* = 2 and *t* = 3 the average depth of join nodes alone yielded predictions that were almost as good as the predictions by the full regression model that used all the features. Nevertheless, these observations also encourage looking for a simpler solution: manually constructing a heuristic function that approximates the actual running time by adding up estimated contributions of each tree decomposition node. Note that here the *f*-cost framework [9] is insufficient, as in that framework the contribution of each node can only depend on the size of the bag.

# References

1. Michael Abseher, Nysret Musliu, and Stefan Woltran. htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond. In *Proceedings of the 14th International Conference on Integration of AI and OR Techniques in Constraint Programming*, volume 10335 of *Lecture Notes in Computer Science*, pages 376-386. Springer, 2017.
5:12 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

2 Michael Abseher, Nysret Musliu, and Stefan Woltran. Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning. *J. Artif. Intell. Res.*, 58:829–858, 2017.

3 Alfred V. Aho, M. R. Garey, and Jeffrey D. Ullman. The Transitive Reduction of a Directed Graph. *SIAM J. Comput.*, 1(2):131–137, 1972.

4 Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of Finding Embeddings in a K-tree. *SIAM J. Algebra. Discr.*, 8(2):277–284, April 1987.

5 Mike D. Atkinson. On computing the number of linear extensions of a tree. *Order*, 7(1):23–25, 1990.

6 Jacqueline Banks, Scott Garrabrant, Mark L. Huber, and Anne Perizzolo. Using TPA to count linear extensions. *arXiv preprint arXiv:1010.4981*, 2017.

7 Umberto Bertelè and Francesco Brioschi. *Nonserial Dynamic Programming*. Academic Press, 1972.

8 Hans L. Bodlaender. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. *SIAM J. Comput.*, 25(6):1305–1317, 1996.

9 Hans L. Bodlaender and Fedor V. Fomin. Tree decompositions with small cost. *Discrete Appl. Math.*, 145(2):143–154, 2005.

10 Hans L. Bodlaender and Ton Kloks. Efficient and Constructive Algorithms for the Path-width and Treewidth of Graphs. *J. Algorithms*, 21(2):358–402, 1996.

11 Graham Brightwell and Peter Winkler. Counting linear extensions. *Order*, 8(3):225–242, 1991.

12 Rina Dechter. Bucket elimination: A unifying framework for reasoning. *Artif. Intell.*, 113(1–2):41–85, 1999.

13 Martin Dyer, Alan Frieze, and Ravi Kannan. A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies. *J. ACM*, 38(1):1–17, 1991.

14 Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak. Counting Linear Extensions: Parameterizations by Treewidth. In *Proceedings of the 24th Annual European Symposium on Algorithms*, volume 57 of *LIPIcs*, pages 39:1–39:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016.

15 Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten. The WEKA Data Mining Software: An Update. *SIGKDD Explor. Newsl.*, 11(1):10–18, November 2009.

16 William B. Hart. Fast Library for Number Theory: An Introduction. In *Proceedings of the Third International Congress on Mathematical Software*, pages 88–91, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://flintlib.org.

17 Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, and Mikko Koivisto. Counting linear extensions of sparse posets. In *Proceedings of the 25th International Joint Conference on Artificial Intelligence*, pages 603–609. IJCAI/AAAI Press, 2016.

18 Richard M. Karp. Dynamic Programming Meets the Principle of Inclusion and Exclusion. *Oper. Res. Lett.*, 1(2):49–51, April 1982.

19 Mikko Koivisto. An $O^*(2^n)$ Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion–Exclusion. In *Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science*, pages 583–590. IEEE Computer Society, 2006.

20 Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham. Empirical hardness models: Methodology and a case study on combinatorial auctions. *J. ACM*, 56(4), 2009.

21 Thomas Lukasiewicz, Maria V. Martinez, and Gerardo I. Simari. Probabilistic Preference Logic Networks. In *Proceedings of the 21st European Conference on Artificial Intelligence*, volume 263 of *Frontiers in Artificial Intelligence and Applications*, pages 561–566. IOS Press, 2014.
5:12 A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions

2 Michael Abseher, Nysret Musliu, and Stefan Woltran. Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning. *J. Artif. Intell. Res.*, 58:829–858, 2017.

3 Alfred V. Aho, M. R. Garey, and Jeffrey D. Ullman. The Transitive Reduction of a Directed Graph. *SIAM J. Comput.*, 1(2):131–137, 1972.

4 Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of Finding Embeddings in a K-tree. *SIAM J. Algebra. Discr.*, 8(2):277–284, April 1987.

5 Mike D. Atkinson. On computing the number of linear extensions of a tree. *Order*, 7(1):23–25, 1990.

6 Jacqueline Banks, Scott Garrabrant, Mark L. Huber, and Anne Perizzolo. Using TPA to count linear extensions. *arXiv preprint arXiv:1010.4981*, 2017.

7 Umberto Bertelè and Francesco Brioschi. *Nonserial Dynamic Programming*. Academic Press, 1972.

8 Hans L. Bodlaender. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. *SIAM J. Comput.*, 25(6):1305–1317, 1996.

9 Hans L. Bodlaender and Fedor V. Fomin. Tree decompositions with small cost. *Discrete Appl. Math.*, 145(2):143–154, 2005.

10 Hans L. Bodlaender and Ton Kloks. Efficient and Constructive Algorithms for the Path-width and Treewidth of Graphs. *J. Algorithms*, 21(2):358–402, 1996.

11 Graham Brightwell and Peter Winkler. Counting linear extensions. *Order*, 8(3):225–242, 1991.

12 Rina Dechter. Bucket elimination: A unifying framework for reasoning. *Artif. Intell.*, 113(1–2):41–85, 1999.

13 Martin Dyer, Alan Frieze, and Ravi Kannan. A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies. *J. ACM*, 38(1):1–17, 1991.

14 Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak. Counting Linear Extensions: Parameterizations by Treewidth. In *Proceedings of the 24th Annual European Symposium on Algorithms*, volume 57 of *LIPIcs*, pages 39:1–39:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016.

15 Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten. The WEKA Data Mining Software: An Update. *SIGKDD Explor. Newsl.*, 11(1):10–18, November 2009.

16 William B. Hart. Fast Library for Number Theory: An Introduction. In *Proceedings of the Third International Congress on Mathematical Software*, pages 88–91, Berlin, Heidelberg, 2010. Springer-Verlag. URL: http://flintlib.org.

17 Kustaa Kangas, Teemu Hankala, Teppo Niinimäki, and Mikko Koivisto. Counting linear extensions of sparse posets. In *Proceedings of the 25th International Joint Conference on Artificial Intelligence*, pages 603–609. IJCAI/AAAI Press, 2016.

18 Richard M. Karp. Dynamic Programming Meets the Principle of Inclusion and Exclusion. *Oper. Res. Lett.*, 1(2):49–51, April 1982.

19 Mikko Koivisto. An $O^*(2^n)$ Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion–Exclusion. In *Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science*, pages 583–590. IEEE Computer Society, 2006.

20 Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham. Empirical hardness models: Methodology and a case study on combinatorial auctions. *J. ACM*, 56(4), 2009.

21 Thomas Lukasiewicz, Maria V. Martinez, and Gerardo I. Simari. Probabilistic Preference Logic Networks. In *Proceedings of the 21st European Conference on Artificial Intelligence*, volume 263 of *Frontiers in Artificial Intelligence and Applications*, pages 561–566. IOS Press, 2014.
22 Heikki Mannila and Christopher Meek. Global Partial Orders from Sequential Data. In *Proceedings of the Sixth International Conference on Knowledge Discovery and Data Mining*, pages 161–168. ACM, 2000.

23 Rolf H. Möhring. Computationally tractable classes of ordered sets. In I. Rival, editor, *Algorithms and Order*, pages 105–193. Kluwer Academic Publishers, 1989.

24 Jason Morton, Lior Pachter, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. Convex Rank Tests and Semigraphoids. *SIAM J. Discrete Math.*, 23(3):1117–1134, 2009.

25 Christian J. Muise, J. Christopher Beck, and Sheila A. McIlraith. Optimal Partial-Order Plan Relaxation via MaxSAT. *J. Artif. Intell. Res.*, 57:113–149, 2016.

26 Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto. Structure Discovery in Bayesian Networks by Sampling Partial Orders. *J. Mach. Learn. Res.*, 17:57:1–57:47, 2016.

27 Marcin Peczarski. New Results in Minimum-Comparison Sorting. *Algorithmica*, 40(2):133–145, 2004.

28 John R. Rice. The algorithm selection problem. *Advances in Computers*, 15:65–118, 1976.

29 Herbert J. Ryser. *Combinatorial Mathematics*, volume 14 of *Carus Mathematical Monographs*. The Mathematical Association of America, 1963.

30 Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto. Counting Linear Extensions in Practice: MCMC versus Exponential Monte Carlo. In *Proceedings of the 32nd AAAI Conference on Artificial Intelligence*, 2018.

31 Joris van der Hoeven and Grégoire Lecerf. On the bit-complexity of sparse polynomial and series multiplication. *J. Symb. Comput.*, 50:227–254, 2013.

32 Chris S. Wallace, Kevin B. Korb, and Honghua Dai. Causal Discovery via MML. In *Proceedings of the 13th International Conference on Machine Learning*, pages 516–524. Morgan Kaufmann, 1996.
22 Heikki Mannila and Christopher Meek. Global Partial Orders from Sequential Data. In *Proceedings of the Sixth International Conference on Knowledge Discovery and Data Mining*, pages 161–168. ACM, 2000.

23 Rolf H. Möhring. Computationally tractable classes of ordered sets. In I. Rival, editor, *Algorithms and Order*, pages 105–193. Kluwer Academic Publishers, 1989.

24 Jason Morton, Lior Pachter, Anne Shiu, Bernd Sturmfels, and Oliver Wienand. Convex Rank Tests and Semigraphoids. *SIAM J. Discrete Math.*, 23(3):1117–1134, 2009.

25 Christian J. Muise, J. Christopher Beck, and Sheila A. McIlraith. Optimal Partial-Order Plan Relaxation via MaxSAT. *J. Artif. Intell. Res.*, 57:113–149, 2016.

26 Teppo Niinimäki, Pekka Parviainen, and Mikko Koivisto. Structure Discovery in Bayesian Networks by Sampling Partial Orders. *J. Mach. Learn. Res.*, 17:57:1–57:47, 2016.

27 Marcin Peczarski. New Results in Minimum-Comparison Sorting. *Algorithmica*, 40(2):133–145, 2004.

28 John R. Rice. The algorithm selection problem. *Advances in Computers*, 15:65–118, 1976.

29 Herbert J. Ryser. *Combinatorial Mathematics*, volume 14 of *Carus Mathematical Monographs*. The Mathematical Association of America, 1963.

30 Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, and Mikko Koivisto. Counting Linear Extensions in Practice: MCMC versus Exponential Monte Carlo. In *Proceedings of the 32nd AAAI Conference on Artificial Intelligence*, 2018.

31 Joris van der Hoeven and Grégoire Lecerf. On the bit-complexity of sparse polynomial and series multiplication. *J. Symb. Comput.*, 50:227–254, 2013.

32 Chris S. Wallace, Kevin B. Korb, and Honghua Dai. Causal Discovery via MML. In *Proceedings of the 13th International Conference on Machine Learning*, pages 516–524. Morgan Kaufmann, 1996.
<figure><img src="image_40.png" /></figure>
<figure><img src="image_43.png" /></figure>
# Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width

## Lars Jaffke<fnref n="1" />

Department of Informatics, University of Bergen, Norway
lars.jaffke@uib.no

https://orcid.org/0000-0003-4856-5863

## O-joung Kwon

Department of Mathematics, Incheon National University, Incheon, South Korea
ojoungkwon@gmail.com

https://orcid.org/0000-0003-1820-1962

## Torstein J. F. Strømme

Department of Informatics, University of Bergen, Norway
torstein.stromme@uib.no

https://orcid.org/0000-0002-3896-3166

## Jan Arne Telle

Department of Informatics, University of Bergen, Norway
jan.arne.telle@uib.no

### Abstract

We generalize the family of $(\sigma, \rho)$-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-$r$ dominating set and distance-$r$ independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as $k$-trapezoid graphs, Dilworth $k$-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, $k$-polygon graphs, circular arc graphs, complements of $d$-degenerate graphs, and $H$-graphs if given an $H$-representation. To supplement these findings, we show that many classes of (distance) $(\sigma, \rho)$-problems are W[1]-hard parameterized by mim-width + solution size.

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** Graph Width Parameters, Graph Classes, Distance Domination Problems, Parameterized Complexity

**Digital Object Identifier** 10.4230/LIPICs.IPEC.2018.6

**Related Version** A full version is available at [12], https://arxiv.org/abs/1803.03514.

## 1 Introduction

Telle and Proskurowski [19] defined the $(\sigma, \rho)$-domination problems, and the more general locally checkable vertex partitioning problems (LCVP). In $(\sigma, \rho)$-domination problems, feasible

<figure><img src="image_41.png" /></figure>

<footnote n="1">¹ Supported by the Bergen Research Foundation (BFS).</footnote>
# Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width

## Lars Jaffke<fnref n="1" />

Department of Informatics, University of Bergen, Norway
lars.jaffke@uib.no

https://orcid.org/0000-0003-4856-5863

## O-joung Kwon

Department of Mathematics, Incheon National University, Incheon, South Korea
ojoungkwon@gmail.com

https://orcid.org/0000-0003-1820-1962

## Torstein J. F. Strømme

Department of Informatics, University of Bergen, Norway
torstein.stromme@uib.no

https://orcid.org/0000-0002-3896-3166

## Jan Arne Telle

Department of Informatics, University of Bergen, Norway
jan.arne.telle@uib.no

### Abstract

We generalize the family of $(\sigma, \rho)$-problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as distance-$r$ dominating set and distance-$r$ independent set. We show that these distance problems are XP parameterized by the structural parameter mim-width, and hence polynomial on graph classes where mim-width is bounded and quickly computable, such as $k$-trapezoid graphs, Dilworth $k$-graphs, (circular) permutation graphs, interval graphs and their complements, convex graphs and their complements, $k$-polygon graphs, circular arc graphs, complements of $d$-degenerate graphs, and $H$-graphs if given an $H$-representation. To supplement these findings, we show that many classes of (distance) $(\sigma, \rho)$-problems are W[1]-hard parameterized by mim-width + solution size.

**2012 ACM Subject Classification** Mathematics of computing → Graph algorithms, Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** Graph Width Parameters, Graph Classes, Distance Domination Problems, Parameterized Complexity

**Digital Object Identifier** 10.4230/LIPICs.IPEC.2018.6

**Related Version** A full version is available at [12], https://arxiv.org/abs/1803.03514.

## 1 Introduction

Telle and Proskurowski [19] defined the $(\sigma, \rho)$-domination problems, and the more general locally checkable vertex partitioning problems (LCVP). In $(\sigma, \rho)$-domination problems, feasible

<figure><img src="image_44.png" /></figure>

<footnote n="1">¹ Supported by the Bergen Research Foundation (BFS).</footnote>
## 6:2 Generalized Distance Domination Problems on mim-width

solutions are vertex sets with constraints on how many neighbours each vertex of the graph has in the set. The framework generalizes important and well-studied problems such as MAXIMUM INDEPENDENT SET and MINIMUM DOMINATING SET, as well as PERFECT CODE, MINIMUM SUBGRAPH WITH MINIMUM DEGREE *d* and a multitude of other problems. See Table 1. Bui-Xuan, Telle and Vatshelle [6] showed that $(\sigma, \rho)$-domination and locally checkable vertex partitioning problems can be solved in time XP parameterized by *mim-width*, if we are given a corresponding decomposition tree. Roughly speaking, the structural parameter mim-width measures how easy it is to decompose a graph along vertex cuts inducing a bipartite graph with small maximum induced matching size [20].

In this paper, we consider distance versions of problems related to independence and domination, like *DISTANCE-*r INDEPENDENT SET and *DISTANCE-*r DOMINATING SET. The *DISTANCE-*r INDEPENDENT SET problem, also studied under the names *r*-SCATTERED SET and *r*-DISPERSION (see e.g. [2] and the references therein), asks to find a set of at least *k* vertices whose vertices have pairwise distance strictly longer than *r*. Agnarsson et al. [1] pointed out that it is identical to the original INDEPENDENT SET problem on the *r*-th power graph *G*^r of the input graph *G*, and also showed that for fixed *r*, it can be solved in linear time for interval graphs, and circular arc graphs. The *DISTANCE-*r DOMINATING SET problem was introduced by Slater [18] and Henning et al. [11]. They also discussed that it is identical to solve the original DOMINATING SET problem on the *r*-th power graph. Slater presented a linear-time algorithm to solve *DISTANCE-*r DOMINATING SET problem on forests.

We generalize all of the $(\sigma, \rho)$-domination and LCVP problems to their distance versions, which naturally captures *DISTANCE-*r INDEPENDENT SET and *DISTANCE-*r DOMINATING SET. Where the original problems put constraints on the size of the immediate neighborhood of a vertex, we consider the constraints to be applied to the ball of radius *r* around it. Consider for instance the MINIMUM SUBGRAPH WITH MINIMUM DEGREE *d* problem; where the original problem is asking for the smallest (number of vertices) subgraph of minimum degree *d*, we are instead looking for the smallest subgraph such that for each vertex there are at least *d* vertices at distance at least 1 and at most *r*. In the PERFECT CODE problem, the target is to choose a subset of vertices such that each vertex has exactly one chosen vertex in its closed neighbourhood. In the distance-*r* version of the problem, we replace the closed neighbourhood by the closed *r*-neighbourhood. This problem is known as PERFECT *r*-CODE, and was introduced by Biggs [4] in 1973. Similarly, for every problem in Table 1 its distance-*r* generalization either introduces a new problem or is already well-known.

We show that all these distance problems are XP parameterized by mim-width if a decomposition tree is given. The main result of the paper is of structural nature, namely that for any positive integer *r* the mim-width of a graph power *G*^r is at most twice the mim-width of *G*. It follows that we can reduce the distance-*r* version of a $(\sigma, \rho)$-domination problem to its non-distance variant by taking the graph power *G*^r, whilst preserving small mim-width.

The downside to showing results using the parameter mim-width, is that we do not know an XP algorithm computing mim-width. Computing a decomposition tree with optimal mim-width is NP-complete in general and W[1]-hard parameterized by itself. Determining the optimal mim-width is not in APX unless NP = ZPP, making it unlikely to have a polynomial-time constant-factor approximation algorithm [17], but saying nothing about an XP algorithm. However, for several graph classes we are able to find a decomposition tree of constant mim-width in polynomial time, using the results of Belmonte and Vatshelle [3]. These include; permutation graphs, convex graphs and their complements, interval graphs and their complements (all of which have linear mim-width 1); (circular *k*-) trapezoid graphs, circular permutation graphs, Dilworth-*k* graphs, *k*-polygon graphs, circular arc graphs and
## 6:2 Generalized Distance Domination Problems on mim-width

solutions are vertex sets with constraints on how many neighbours each vertex of the graph has in the set. The framework generalizes important and well-studied problems such as MAXIMUM INDEPENDENT SET and MINIMUM DOMINATING SET, as well as PERFECT CODE, MINIMUM SUBGRAPH WITH MINIMUM DEGREE *d* and a multitude of other problems. See Table 1. Bui-Xuan, Telle and Vatshelle [6] showed that $(\sigma, \rho)$-domination and locally checkable vertex partitioning problems can be solved in time XP parameterized by *mim-width*, if we are given a corresponding decomposition tree. Roughly speaking, the structural parameter mim-width measures how easy it is to decompose a graph along vertex cuts inducing a bipartite graph with small maximum induced matching size [20].

In this paper, we consider distance versions of problems related to independence and domination, like *DISTANCE-*r INDEPENDENT SET and *DISTANCE-*r DOMINATING SET. The *DISTANCE-*r INDEPENDENT SET problem, also studied under the names *r*-SCATTERED SET and *r*-DISPERSION (see e.g. [2] and the references therein), asks to find a set of at least *k* vertices whose vertices have pairwise distance strictly longer than *r*. Agnarsson et al. [1] pointed out that it is identical to the original INDEPENDENT SET problem on the *r*-th power graph *G*^r of the input graph *G*, and also showed that for fixed *r*, it can be solved in linear time for interval graphs, and circular arc graphs. The *DISTANCE-*r DOMINATING SET problem was introduced by Slater [18] and Henning et al. [11]. They also discussed that it is identical to solve the original DOMINATING SET problem on the *r*-th power graph. Slater presented a linear-time algorithm to solve *DISTANCE-*r DOMINATING SET problem on forests.

We generalize all of the $(\sigma, \rho)$-domination and LCVP problems to their distance versions, which naturally captures *DISTANCE-*r INDEPENDENT SET and *DISTANCE-*r DOMINATING SET. Where the original problems put constraints on the size of the immediate neighborhood of a vertex, we consider the constraints to be applied to the ball of radius *r* around it. Consider for instance the MINIMUM SUBGRAPH WITH MINIMUM DEGREE *d* problem; where the original problem is asking for the smallest (number of vertices) subgraph of minimum degree *d*, we are instead looking for the smallest subgraph such that for each vertex there are at least *d* vertices at distance at least 1 and at most *r*. In the PERFECT CODE problem, the target is to choose a subset of vertices such that each vertex has exactly one chosen vertex in its closed neighbourhood. In the distance-*r* version of the problem, we replace the closed neighbourhood by the closed *r*-neighbourhood. This problem is known as PERFECT *r*-CODE, and was introduced by Biggs [4] in 1973. Similarly, for every problem in Table 1 its distance-*r* generalization either introduces a new problem or is already well-known.

We show that all these distance problems are XP parameterized by mim-width if a decomposition tree is given. The main result of the paper is of structural nature, namely that for any positive integer *r* the mim-width of a graph power *G*^r is at most twice the mim-width of *G*. It follows that we can reduce the distance-*r* version of a $(\sigma, \rho)$-domination problem to its non-distance variant by taking the graph power *G*^r, whilst preserving small mim-width.

The downside to showing results using the parameter mim-width, is that we do not know an XP algorithm computing mim-width. Computing a decomposition tree with optimal mim-width is NP-complete in general and W[1]-hard parameterized by itself. Determining the optimal mim-width is not in APX unless NP = ZPP, making it unlikely to have a polynomial-time constant-factor approximation algorithm [17], but saying nothing about an XP algorithm. However, for several graph classes we are able to find a decomposition tree of constant mim-width in polynomial time, using the results of Belmonte and Vatshelle [3]. These include; permutation graphs, convex graphs and their complements, interval graphs and their complements (all of which have linear mim-width 1); (circular *k*-) trapezoid graphs, circular permutation graphs, Dilworth-*k* graphs, *k*-polygon graphs, circular arc graphs and
complements of $d$-degenerate graphs. Fomin, Golovach and Raymond [10] show that we can find linear decomposition trees of constant mim-width for the very general class of $H$-graphs, see Definition 10, in polynomial time, given<fnref n="2" /> an $H$-representation of the input graph. For all of the above graph classes, our results imply that the distance-$r$ $(\sigma, \rho)$-domination and LCVP problems become polynomial time solvable.

Graphs represented by intersections of objects in some model are often closed under taking powers. For instance, interval graphs, and generally $d$-trapezoid graphs [9, 1], circular arc graphs [16, 1], and leaf power graphs (by definition) are such graphs. We refer to [5, Chapter 10.6] for a survey of such results. For these classes, we already know that the distance-$r$ version of a $(\sigma, \rho)$-domination problem can be solved in polynomial time. However, this closure property does not always hold; for instance, permutation graphs are not closed under taking powers. Our result provides that to obtain such algorithmic results, we do not need to know that these classes are closed under taking powers; it is sufficient to know that classes have bounded mim-width. To the best of our knowledge, for the most well-studied distance-$r$ $(\sigma, \rho)$-domination problem, DISTANCE-$r$ DOMINATING SET, we obtain the first polynomial time algorithms on Dilworth $k$-graphs, convex graphs and their complements, complements of interval graphs, $k$-polygon graphs, $H$-graphs (given an $H$-representation of the input graph), and complements of $d$-degenerate graphs.

The natural question to ask after obtaining an XP algorithm, is whether we can do better, e. g. can we show that for all fixed $r$, the distance-$r$ $(\sigma, \rho)$-domination problems are in FPT? Fomin et al. [10] answered this in the negative by showing that (the standard, i.e. distance-1 variants of) MAXIMUM INDEPENDENT SET, MINIMUM DOMINATING SET and MINIMUM INDEPENDENT DOMINATING SET problems are W[1]-hard parameterized by (linear) mim-width + solution size. We modify their reductions to extend these results to several families of $(\sigma, \rho)$-domination problems, including the maximization variants of INDUCED MATCHING, INDUCED $d$-REGULAR SUBGRAPH and INDUCED SUBGRAPH OF MAX DEGREE $\le d$, the minimization variants of TOTAL DOMINATING SET and $d$-DOMINATING SET and both the maximization and the minimization variant of DOMINATING INDUCED MATCHING.

The remainder of the paper is organized as follows. In Section 2 we introduce the $(\sigma, \rho)$ problems and define their distance-$r$ generalization. In Section 3 we introduce mim-width, and state previously known results. In Section 4 we show that the mim-width of a graph grows by at most a factor 2 when taking (arbitrary large) powers and give algorithmic consequences. We discuss LCVP problems, their distance-$r$ versions and algorithmic consequences regarding them in Section 5 and in Section 6 we present the above mentioned lower bounds. Finally, we give some concluding remarks in Section 7. Proofs of statements marked with ‘★’ are deferred to the full version [12].

## 2 Distance-$r$ $(\sigma, \rho)$-Domination Problems

Let $\sigma$ and $\rho$ be finite or co-finite subsets of the natural numbers $\sigma, \rho \subseteq \mathbb{N}$. Furthermore, for a graph $G$, one of its vertices $v \in V(G)$, and a positive integer $r$, let $N^r(v)$ denote the *ball of radius* $r$ *around* $v$, i. e. $N^r(v) := \{w \in V(G) \setminus \{v\} | \text{DIST}_G(v, w) \le r\}$. A vertex set $S \subseteq V(G)$ is called a *distance-$r$ $(\sigma, \rho)$-dominating set*, if

for each vertex $v \in S$ it holds that $|N^r(v) \cap S| \in \sigma$, and

<footnote n="2">² We would like to remark that it is NP-complete to decide whether a graph is an $H$-graph whenever $H$ is not a cactus [7].</footnote>
complements of $d$-degenerate graphs. Fomin, Golovach and Raymond [10] show that we can find linear decomposition trees of constant mim-width for the very general class of $H$-graphs, see Definition 10, in polynomial time, given<fnref n="2" /> an $H$-representation of the input graph. For all of the above graph classes, our results imply that the distance-$r$ $(\sigma, \rho)$-domination and LCVP problems become polynomial time solvable.

Graphs represented by intersections of objects in some model are often closed under taking powers. For instance, interval graphs, and generally $d$-trapezoid graphs [9, 1], circular arc graphs [16, 1], and leaf power graphs (by definition) are such graphs. We refer to [5, Chapter 10.6] for a survey of such results. For these classes, we already know that the distance-$r$ version of a $(\sigma, \rho)$-domination problem can be solved in polynomial time. However, this closure property does not always hold; for instance, permutation graphs are not closed under taking powers. Our result provides that to obtain such algorithmic results, we do not need to know that these classes are closed under taking powers; it is sufficient to know that classes have bounded mim-width. To the best of our knowledge, for the most well-studied distance-$r$ $(\sigma, \rho)$-domination problem, DISTANCE-$r$ DOMINATING SET, we obtain the first polynomial time algorithms on Dilworth $k$-graphs, convex graphs and their complements, complements of interval graphs, $k$-polygon graphs, $H$-graphs (given an $H$-representation of the input graph), and complements of $d$-degenerate graphs.

The natural question to ask after obtaining an XP algorithm, is whether we can do better, e. g. can we show that for all fixed $r$, the distance-$r$ $(\sigma, \rho)$-domination problems are in FPT? Fomin et al. [10] answered this in the negative by showing that (the standard, i.e. distance-1 variants of) MAXIMUM INDEPENDENT SET, MINIMUM DOMINATING SET and MINIMUM INDEPENDENT DOMINATING SET problems are W[1]-hard parameterized by (linear) mim-width + solution size. We modify their reductions to extend these results to several families of $(\sigma, \rho)$-domination problems, including the maximization variants of INDUCED MATCHING, INDUCED $d$-REGULAR SUBGRAPH and INDUCED SUBGRAPH OF MAX DEGREE $\le d$, the minimization variants of TOTAL DOMINATING SET and $d$-DOMINATING SET and both the maximization and the minimization variant of DOMINATING INDUCED MATCHING.

The remainder of the paper is organized as follows. In Section 2 we introduce the $(\sigma, \rho)$ problems and define their distance-$r$ generalization. In Section 3 we introduce mim-width, and state previously known results. In Section 4 we show that the mim-width of a graph grows by at most a factor 2 when taking (arbitrary large) powers and give algorithmic consequences. We discuss LCVP problems, their distance-$r$ versions and algorithmic consequences regarding them in Section 5 and in Section 6 we present the above mentioned lower bounds. Finally, we give some concluding remarks in Section 7. Proofs of statements marked with ‘★’ are deferred to the full version [12].

## 2 Distance-$r$ $(\sigma, \rho)$-Domination Problems

Let $\sigma$ and $\rho$ be finite or co-finite subsets of the natural numbers $\sigma, \rho \subseteq \mathbb{N}$. Furthermore, for a graph $G$, one of its vertices $v \in V(G)$, and a positive integer $r$, let $N^r(v)$ denote the *ball of radius* $r$ *around* $v$, i. e. $N^r(v) := \{w \in V(G) \setminus \{v\} | \text{DIST}_G(v, w) \le r\}$. A vertex set $S \subseteq V(G)$ is called a *distance-$r$ $(\sigma, \rho)$-dominating set*, if

for each vertex $v \in S$ it holds that $|N^r(v) \cap S| \in \sigma$, and

<footnote n="2">² We would like to remark that it is NP-complete to decide whether a graph is an $H$-graph whenever $H$ is not a cactus [7].</footnote>
6:4 Generalized Distance Domination Problems on mim-width

<table><caption>**Table 1** Some vertex subset properties expressible as $(\sigma, \rho)$ sets, with $N = \{0, 1, ...\}$ and $N^+ = \{1, 2, ...\}$. Column *d* shows $d = \max(d(\sigma), d(\rho))$. For each problem, at least one of the minimization, the maximization and the existence problem is NP-complete. For problems marked with $\star$ (resp., $\star\star$), W[1]-hardness of the maximization (resp., minimization) problem parameterized by mim-width + solution size is shown in the present paper. For problems marked with $*$ (resp., $\star\star$) the W[1]-hardness of maximization (resp., minimization) in the same parameterization was shown by Fomin et al. [10].</caption><thead><tr><th>σ</th><th>ρ</th><th>d</th><th>Standard name</th></tr></thead><tbody><tr><td>{0}</td><td>N</td><td>1</td><td>Independent set *</td></tr><tr><td>N</td><td>N<sup>+</sup></td><td>1</td><td>Dominating set **</td></tr><tr><td>{0}</td><td>N<sup>+</sup></td><td>1</td><td>Maximal Independent set **</td></tr><tr><td>N<sup>+</sup></td><td>N<sup>+</sup></td><td>1</td><td>Total Dominating set **</td></tr><tr><td>{0}</td><td>{0, 1}</td><td>2</td><td>Strong Stable set or 2-Packing</td></tr><tr><td>{0}</td><td>{1}</td><td>2</td><td>Perfect Code or Efficient Dom. set</td></tr><tr><td>{0, 1}</td><td>{0, 1}</td><td>2</td><td>Total Nearly Perfect set</td></tr><tr><td>{0, 1}</td><td>{1}</td><td>2</td><td>Weakly Perfect Dominating set</td></tr><tr><td>{1}</td><td>{1}</td><td>2</td><td>Total Perfect Dominating set</td></tr><tr><td>{1}</td><td>N</td><td>2</td><td>Induced Matching *</td></tr><tr><td>{1}</td><td>N<sup>+</sup></td><td>2</td><td>Dominating Induced Matching *, **</td></tr><tr><td>N</td><td>{1}</td><td>2</td><td>Perfect Dominating set</td></tr><tr><td>N</td><td>{d, d + 1, ...}</td><td>d</td><td>d-Dominating set **</td></tr><tr><td>{d}</td><td>N</td><td>d + 1</td><td>Induced d-Regular Subgraph *</td></tr><tr><td>{d, d + 1, ...}</td><td>N</td><td>d</td><td>Subgraph of Min Degree ≥ d</td></tr><tr><td>{0, 1, ..., d}</td><td>N</td><td>d + 1</td><td>Induced Subg. of Max Degree ≤ d *</td></tr></tbody></table>

for each vertex $v \in V(G) \setminus S$ it holds that $|N^r(v) \cap S| \in \rho$.

For the special case of $r = 1$, we call a distance-1 $(\sigma, \rho)$-dominating set simply a $(\sigma, \rho)$-dominating set or $(\sigma, \rho)$ set. This recovers many well-studied naturally defined vertex sets of graphs. For instance, a $(\{0\}, N)$ set is an independent set as there are no edges inside of the set, and we do not care about adjacencies between $S$ and $V(G) \setminus S$; and a $(N, N^+)$ set is a dominating set since each vertex in $V(G) \setminus S$ has to have at least one neighbor in $S$.

There are three types of distance-$r$ $(\sigma, \rho)$-domination problems: minimization, maximization, and existence. For $r = 1$, we denote the problem of finding a minimum (maximum) $(\sigma, \rho)$ set as the $\text{MIN-}(\sigma, \rho)$ ($\text{MAX-}(\sigma, \rho)$) problem, see Table 1 for examples.

The *d-value* of a distance-$r$ $(\sigma, \rho)$ problem is a constant which will ultimately affect the runtime of the algorithm. For a set $\mu \subseteq N$, the value $d(\mu)$ should be understood as the highest value in $N$ we need to enumerate in order to describe $\mu$. Hence, if $\mu$ is finite, it is simply the maximum value in $\mu$, and if $\mu$ is co-finite, it is the maximum natural number not in $\mu$ (1 is added for technical reasons).

**Definition 1 (d-value).** Let $d(N) = 0$. For every non-empty finite or co-finite set $\mu \subseteq N$, let $d(\mu) = 1 + \min(\max\{x \mid x \in \mu\}, \max\{x \mid x \in N \setminus \mu\})$.

For a given distance-$r$ $(\sigma, \rho)$ problem $\Pi_{\sigma,\rho}$, its *d-value* is defined as $d(\Pi_{\sigma,\rho}) := \max\{d(\sigma), d(\rho)\}$, see column *d* in Table 1.

3 Mim-width and Applications

*Maximum induced matching width*, or *mim-width* for short, was introduced in the Ph.D. thesis of Vatshelle [20], used implicitly by Belmonte and Vatshelle [3], and is a structural
## 6:4 Generalized Distance Domination Problems on mim-width

<table><caption>**Table 1** Some vertex subset properties expressible as $(\sigma, \rho)$ sets, with $\mathbb{N} = \{0, 1, ...\}$ and $\mathbb{N}^+ = \{1, 2, ...\}$. Column *d* shows $d = \max(d(\sigma), d(\rho))$. For each problem, at least one of the minimization, the maximization and the existence problem is NP-complete. For problems marked with $\star$ (resp., $\star\star$), W[1]-hardness of the maximization (resp., minimization) problem parameterized by mim-width + solution size is shown in the present paper. For problems marked with $*$ (resp., $\star\star$) the W[1]-hardness of maximization (resp., minimization) in the same parameterization was shown by Fomin et al. [10].</caption><thead><tr><th>σ</th><th>ρ</th><th>d</th><th>Standard name</th></tr></thead><tbody><tr><td>{0}</td><td>ℝ</td><td>1</td><td>Independent set *</td></tr><tr><td>ℝ</td><td>ℝ<sup>+</sup></td><td>1</td><td>Dominating set **</td></tr><tr><td>{0}</td><td>ℝ<sup>+</sup></td><td>1</td><td>Maximal Independent set **</td></tr><tr><td>ℝ<sup>+</sup></td><td>ℝ<sup>+</sup></td><td>1</td><td>Total Dominating set **</td></tr><tr><td>{0}</td><td>{0, 1}</td><td>2</td><td>Strong Stable set or 2-Packing</td></tr><tr><td>{0}</td><td>{1}</td><td>2</td><td>Perfect Code or Efficient Dom. set</td></tr><tr><td>{0, 1}</td><td>{0, 1}</td><td>2</td><td>Total Nearly Perfect set</td></tr><tr><td>{0, 1}</td><td>{1}</td><td>2</td><td>Weakly Perfect Dominating set</td></tr><tr><td>{1}</td><td>{1}</td><td>2</td><td>Total Perfect Dominating set</td></tr><tr><td>{1}</td><td>ℝ</td><td>2</td><td>Induced Matching ⋆</td></tr><tr><td>{1}</td><td>ℝ<sup>+</sup></td><td>2</td><td>Dominating Induced Matching ⋆, **</td></tr><tr><td>ℝ</td><td>{1}</td><td>2</td><td>Perfect Dominating set</td></tr><tr><td>ℝ</td><td>{d, d + 1, ...}</td><td>d</td><td>d-Dominating set **</td></tr><tr><td>{d}</td><td>ℝ</td><td>d + 1</td><td>Induced d-Regular Subgraph ⋆</td></tr><tr><td>{d, d + 1, ...}</td><td>ℝ</td><td>d</td><td>Subgraph of Min Degree ≥ d</td></tr><tr><td>{0, 1, ..., d}</td><td>ℝ</td><td>d + 1</td><td>Induced Subg. of Max Degree ≤ d ⋆</td></tr></tbody></table>

for each vertex $v \in V(G) \setminus S$ it holds that $|N^r(v) \cap S| \in \rho$.

For the special case of $r = 1$, we call a distance-1 $(\sigma, \rho)$-dominating set simply a $(\sigma, \rho)$-dominating set or $(\sigma, \rho)$ set. This recovers many well-studied naturally defined vertex sets of graphs. For instance, a $(\{0\}, \mathbb{N})$ set is an independent set as there are no edges inside of the set, and we do not care about adjacencies between $S$ and $V(G) \setminus S$; and a $(\mathbb{N}, \mathbb{N}^+)$ set is a dominating set since each vertex in $V(G) \setminus S$ has to have at least one neighbor in $S$.

There are three types of distance-$r$ $(\sigma, \rho)$-domination problems: minimization, maximization, and existence. For $r = 1$, we denote the problem of finding a minimum (maximum) $(\sigma, \rho)$ set as the $\text{MIN-}(\sigma, \rho)$ ($\text{MAX-}(\sigma, \rho)$) problem, see Table 1 for examples.

The *d-value* of a distance-$r$ $(\sigma, \rho)$ problem is a constant which will ultimately affect the runtime of the algorithm. For a set $\mu \subseteq \mathbb{N}$, the value $d(\mu)$ should be understood as the highest value in $\mathbb{N}$ we need to enumerate in order to describe $\mu$. Hence, if $\mu$ is finite, it is simply the maximum value in $\mu$, and if $\mu$ is co-finite, it is the maximum natural number not in $\mu$ (1 is added for technical reasons).

**Definition 1 (d-value).** Let $d(\mathbb{N}) = 0$. For every non-empty finite or co-finite set $\mu \subseteq \mathbb{N}$, let $d(\mu) = 1 + \min(\max\{x \mid x \in \mu\}, \max\{x \mid x \in \mathbb{N} \setminus \mu\})$.

For a given distance-$r$ $(\sigma, \rho)$ problem $\Pi_{\sigma, \rho}$, its *d-value* is defined as $d(\Pi_{\sigma, \rho}) := \max\{d(\sigma), d(\rho)\}$, see column *d* in Table 1.

## 3 Mim-width and Applications

*Maximum induced matching width*, or *mim-width* for short, was introduced in the Ph.D. thesis of Vatshelle [20], used implicitly by Belmonte and Vatshelle [3], and is a structural
graph parameter described over decomposition trees (sometimes called branch decompositions), similar to graph parameters such as rank-width and module-width. Decomposition trees naturally appear in divide and conquer style algorithms where one recursively partitions the pieces of a problem into two parts. When the algorithm is at the point where it combines solutions of its subproblems to form a full solution, the structure of the cuts are (unsurprisingly) important to the runtime; this is especially true of dynamic programming when one needs to store multiple sub-solutions at each intermediate node. We will briefly introduce the necessary machinery here, but for a more comprehensive introduction we refer the reader to [20].

A graph of maximum degree at most 3 is called subcubic. A decomposition tree for a graph G is a pair $(T, \delta)$ where T is a subcubic tree and $\delta: V(G) \to L(T)$ is a bijection between the vertices of G and the leaves of T. Each edge $e \in E(T)$ naturally splits the leaves of the tree in two groups depending on their connected component when e is removed. In this way, each edge $e \in E(T)$ also represent a partition of V(G) into two partition classes $A_e$ and $\bar{A}_e$. One way to measure the cut structure is by the maximum induced matching across a cut of $(T, \delta)$. A set of edges M is called an induced matching if no pair of edges in M shares an endpoint and if the subgraph induced by the endpoints of M does not contain any additional edges.

**► Definition 2 (mim-width).** Let G be a graph, and let $(T, \delta)$ be a decomposition tree for G. For each edge $e \in E(T)$ and corresponding partition of the vertices $A_e, \bar{A}_e$, we let $cutmim_G(A_e, \bar{A}_e)$ denote the size of a maximum induced matching of the bipartite graph on the edges crossing the cut. Let the mim-width of the decomposition tree be

$$mimw_G(T, \delta) = \max_{e \in E(T)} \{cutmim(A_e, \bar{A}_e)\}$$

The mim-width of the graph G, denoted $mimw(G)$, is the minimum value of $mimw_G(T, \delta)$ over all possible decompositions trees $(T, \delta)$. The linear mim-width of the graph G is the minimum value of $mimw_G(T, \delta)$ over all possible decompositions trees $(T, \delta)$ where T is a caterpillar.

In previous work, Bui-Xuan et al. [6] and Belmonte and Vatshelle [3] showed that all $(\sigma, \rho)$ problems can be solved in time $n^{O(w)}$ where w denotes the mim-width of a decomposition tree that is provided as part of the input. More precisely, they show the following.<fnref n="3" />

**► Proposition 3 ([3, 6]).** There is an algorithm that given a graph G and a decomposition tree $(T, \delta)$ of G with $w := mimw_G(T, \delta)$ solves each $(\sigma, \rho)$ problem $\Pi$ with $d := d(\Pi)$

(i) in time $O(n^{4+2d \cdot w})$, if T is a caterpillar, and

(ii) in time $O(n^{4+3d \cdot w})$, otherwise.

# 4 Mim-width on Graph Powers

**► Definition 4 (Graph power).** Let $G = (V, E)$ be a graph. Then the k-th power of G, denoted $G^k$, is a graph on the same vertex set where there is an edge between two vertices if and only if the distance between them is at most k in G. Formally, $V(G^k) = V(G)$ and $E(G^k) = \{uv | \text{DIST}_G(u, v) \le k\}$.

<footnote n="3">³ We would like to remark that the original results in [6] are stated in terms of the number of d-neighborhood equivalence classes across the cuts in the decomposition tree ($nec_d(T, \delta)$) giving a runtime of $n^4 \cdot nec_d(T, \delta)^c$ (where c = 2 if the given decomposition is a caterpillar and c = 3 otherwise). In [3, Lemma 2], Belmonte and Vatshelle show that $nec_d(T, \delta) \le n^{d \cdot mimw_G(T, \delta)}$.</footnote>
graph parameter described over decomposition trees (sometimes called branch decompositions), similar to graph parameters such as rank-width and module-width. Decomposition trees naturally appear in divide and conquer style algorithms where one recursively partitions the pieces of a problem into two parts. When the algorithm is at the point where it combines solutions of its subproblems to form a full solution, the structure of the cuts are (unsurprisingly) important to the runtime; this is especially true of dynamic programming when one needs to store multiple sub-solutions at each intermediate node. We will briefly introduce the necessary machinery here, but for a more comprehensive introduction we refer the reader to [20].

A graph of maximum degree at most 3 is called subcubic. A decomposition tree for a graph G is a pair $(T, \delta)$ where T is a subcubic tree and $\delta: V(G) \to L(T)$ is a bijection between the vertices of G and the leaves of T. Each edge $e \in E(T)$ naturally splits the leaves of the tree in two groups depending on their connected component when e is removed. In this way, each edge $e \in E(T)$ also represent a partition of V(G) into two partition classes $A_e$ and $\bar{A}_e$. One way to measure the cut structure is by the maximum induced matching across a cut of $(T, \delta)$. A set of edges M is called an induced matching if no pair of edges in M shares an endpoint and if the subgraph induced by the endpoints of M does not contain any additional edges.

**► Definition 2 (mim-width).** Let G be a graph, and let $(T, \delta)$ be a decomposition tree for G. For each edge $e \in E(T)$ and corresponding partition of the vertices $A_e, \bar{A}_e$, we let $cutmim_G(A_e, \bar{A}_e)$ denote the size of a maximum induced matching of the bipartite graph on the edges crossing the cut. Let the mim-width of the decomposition tree be

$$mimw_G(T, \delta) = \max_{e \in E(T)} \{cutmim(A_e, \bar{A}_e)\}$$

The mim-width of the graph G, denoted $mimw(G)$, is the minimum value of $mimw_G(T, \delta)$ over all possible decompositions trees $(T, \delta)$. The linear mim-width of the graph G is the minimum value of $mimw_G(T, \delta)$ over all possible decompositions trees $(T, \delta)$ where T is a caterpillar.

In previous work, Bui-Xuan et al. [6] and Belmonte and Vatshelle [3] showed that all $(\sigma, \rho)$ problems can be solved in time $n^{O(w)}$ where w denotes the mim-width of a decomposition tree that is provided as part of the input. More precisely, they show the following.<fnref n="3" />

**► Proposition 3 ([3, 6]).** There is an algorithm that given a graph G and a decomposition tree $(T, \delta)$ of G with $w := mimw_G(T, \delta)$ solves each $(\sigma, \rho)$ problem $\Pi$ with $d := d(\Pi)$

(i) in time $O(n^{4+2d \cdot w})$, if T is a caterpillar, and

(ii) in time $O(n^{4+3d \cdot w})$, otherwise.

# 4 Mim-width on Graph Powers

**► Definition 4 (Graph power).** Let $G = (V, E)$ be a graph. Then the k-th power of G, denoted $G^k$, is a graph on the same vertex set where there is an edge between two vertices if and only if the distance between them is at most k in G. Formally, $V(G^k) = V(G)$ and $E(G^k) = \{uv | \text{DIST}_G(u, v) \le k\}$.

<footnote n="3">³ We would like to remark that the original results in [6] are stated in terms of the number of d-neighborhood equivalence classes across the cuts in the decomposition tree ($nec_d(T, \delta)$) giving a runtime of $n^4 \cdot nec_d(T, \delta)^c$ (where c = 2 if the given decomposition is a caterpillar and c = 3 otherwise). In [3, Lemma 2], Belmonte and Vatshelle show that $nec_d(T, \delta) \le n^{d \cdot mimw_G(T, \delta)}$.</footnote>
6:6 Generalized Distance Domination Problems on mim-width

<figure><img src="image_42.png" /><figcaption>Figure 1 Structure of two paths P<sub>uv</sub> and P<sub>wx</sub> when the edge u'<sub>i</sub>x' exists in G. Dashed edges appear in G<sup>k</sup>, solid edges appear in G, squiggly lines are (shortest) paths existing in G (possibly of length 0, and possibly crossing back and forth across the cut).</figcaption></figure>

Theorem 5. For any graph G and positive integer k, mimw(G<sup>k</sup>) ≤ 2 · mimw(G).

**Proof.** Assume that there is a decomposition tree of mim-width w for the graph G. We show that the same decomposition tree has mim-width at most 2w for G<sup>k</sup>.

We consider a cut A, Ā of the decomposition tree. Let M be a maximum induced matching across the cut for G<sup>k</sup>. To prove our claim, it suffices to construct an induced matching across the cut M' in G such that |M'| ≥ |M|/2.

We begin by noticing that for an edge uv ∈ M, the distance between u and v is at most k in G. For each such edge uv ∈ M, we let P<sub>uv</sub> denote some shortest path between u and v in G (including the endpoints u and v).

**Claim 5.1.** Let uv, wx ∈ M be two distinct edges of the matching. Then P<sub>uv</sub> and P<sub>wx</sub> are vertex disjoint.

**Proof.** We may assume that u, w ∈ A and v, x ∈ Ā. Now assume for the sake of contradiction there exists a vertex y ∈ P<sub>uv</sub> ∩ P<sub>wx</sub>. Because both paths have length at most k, we have that DIST<sub>G</sub>(u, y) + DIST<sub>G</sub>(y, v) ≤ k, and DIST<sub>G</sub>(w, y) + DIST<sub>G</sub>(y, x) ≤ k. Adding these together, we get

$$DIST_G(u, y) + DIST_G(y, v) + DIST_G(w, y) + DIST_G(y, x) \leq 2k.$$

Since uv and wx are both in M, there can not exist edges ux and wv in G<sup>k</sup>. Hence, their distance in G is strictly greater than k, i.e. DIST<sub>G</sub>(u, y) + DIST<sub>G</sub>(y, x) ≥ DIST<sub>G</sub>(u, x) > k, and DIST<sub>G</sub>(w, y) + DIST<sub>G</sub>(y, v) > k. Putting these together, we obtain our contradiction:

$$DIST_G(u, y) + DIST_G(y, x) + DIST_G(w, y) + DIST_G(y, v) > 2k$$

This concludes the proof of the claim.

<figure><img src="image_43.png" /></figure>

Our next observation is that for each uv ∈ M, the path P<sub>uv</sub> starts (without loss of generality) in A, and ends in Ā. There must hence exist at least one point at which the path cross from A to Ā. For each uv ∈ M, we can thus safely let u'<sub>i</sub>v' ∈ E(P<sub>uv</sub>) denote an edge in G such that u' ∈ A and v' ∈ Ā.

We plan to construct our matching M' by picking a subset of such edges. However, we can not simply take all of them, since some pairs may be incompatible in the sense that they will not form an induced matching across the cut A, Ā. We examine the structures that arise when two such edges u'<sub>i</sub>v' and w'<sub>i</sub>x' are incompatible, and can not both be included in the same induced matching across the cut. For easier readability, we let α<sub>d</sub> be a shorthand notation for DIST<sub>G</sub>(α, α') for α ∈ {u, v, w, x}.
6:6 Generalized Distance Domination Problems on mim-width

<figure><img src="image_45.png" /><figcaption>Figure 1 Structure of two paths P$_{uv}$ and P$_{wx}$ when the edge u'x' exists in G. Dashed edges appear in G$^k$, solid edges appear in G, squiggly lines are (shortest) paths existing in G (possibly of length 0, and possibly crossing back and forth across the cut).</figcaption></figure>

Theorem 5. For any graph G and positive integer k, mimw(G$^k$) ≤ 2 · mimw(G).

**Proof.** Assume that there is a decomposition tree of mim-width w for the graph G. We show that the same decomposition tree has mim-width at most 2w for G$^k$.

We consider a cut A, $\bar{A}$ of the decomposition tree. Let M be a maximum induced matching across the cut for G$^k$. To prove our claim, it suffices to construct an induced matching across the cut M' in G such that |M'| ≥ |M|/2.

We begin by noticing that for an edge uv ∈ M, the distance between u and v is at most k in G. For each such edge uv ∈ M, we let P$_{uv}$ denote some shortest path between u and v in G (including the endpoints u and v).

**Claim 5.1.** Let uv, wx ∈ M be two distinct edges of the matching. Then P$_{uv}$ and P$_{wx}$ are vertex disjoint.

**Proof.** We may assume that u, w ∈ A and v, x ∈ $\bar{A}$. Now assume for the sake of contradiction there exists a vertex y ∈ P$_{uv} \cap P_{wx}$. Because both paths have length at most k, we have that $DIST_G(u, y) + DIST_G(y, v) \le k$, and $DIST_G(w, y) + DIST_G(y, x) \le k$. Adding these together, we get

$$DIST_G(u, y) + DIST_G(y, v) + DIST_G(w, y) + DIST_G(y, x) \le 2k.$$

Since uv and wx are both in M, there can not exist edges ux and wv in G$^k$. Hence, their distance in G is strictly greater than k, i.e. $DIST_G(u, y) + DIST_G(y, x) \ge DIST_G(u, x) > k$, and $DIST_G(w, y) + DIST_G(y, v) > k$. Putting these together, we obtain our contradiction:

$$DIST_G(u, y) + DIST_G(y, x) + DIST_G(w, y) + DIST_G(y, v) > 2k$$

This concludes the proof of the claim.

<figure><img src="image_46.png" /></figure>

Our next observation is that for each uv ∈ M, the path P$_{uv}$ starts (without loss of generality) in A, and ends in $\bar{A}$. There must hence exist at least one point at which the path cross from A to $\bar{A}$. For each uv ∈ M, we can thus safely let $u'v' \in E(P_{uv})$ denote an edge in G such that $u' \in A$ and $v' \in \bar{A}$.

We plan to construct our matching M' by picking a subset of such edges. However, we can not simply take all of them, since some pairs may be incompatible in the sense that they will not form an induced matching across the cut A, $\bar{A}$. We examine the structures that arise when two such edges $u'v'$ and $w'x'$ are incompatible, and can not both be included in the same induced matching across the cut. For easier readability, we let $\alpha_d$ be a shorthand notation for $DIST_G(\alpha, \alpha')$ for $\alpha \in \{u, v, w, x\}$.
**► Claim 5.2.** Let $uv, wx \in M$ be two distinct edges of $M$ and let $u'v'$ and $w'x'$ be edges on the shortest paths as defined above. If there is an edge $u'x' \in E(G)$, then all of the following hold. See Figure 1.

(a) $u_d + x_d = k$

(b) $u_d + v_d = w_d + x_d = k - 1$

(c) $w_d = u_d - 1$

**Proof.** (a) Since $ux$ is not an edge in $G^k$, the distance between $u$ and $x$ must be at least $k+1$ in $G$, and so $u_d + x_d$ must be at least $k$. It remains to show that $u_d + x_d \le k$ for equality to hold. Similarly to the proof of Claim 5.1, we know that $P_{uv}$ and $P_{wx}$ both are of length at most $k$. We get

$$u_d + v_d + w_d + x_d \le 2k - 2 \qquad (1)$$

The $-2$ at the end is because we do not include the length contributed by edges $u'v'$ and $w'x'$ in our sum. Now assume for the sake of contradiction that $u_d + x_d \ge k + 1$. Then we get that

$$v_d + w_d \le 2k - 2 - k - 1 = k - 3$$

Because $\text{DIST}_G(v', w') \le 3$ (follow the edges $u'v' \to u'x' \to w'x'$), this implies that $\text{DIST}_G(v, w) \le k$, and the edge $vw$ would hence exist in $G^k$. This contradicts that $uv$ and $wx$ were both in the same induced matching $M$.

(b) Assume for the sake of contradiction that $u_d + v_d \le k - 2$. Then, rather than Equation 1, we get the following bound

$$u_d + v_d + w_d + x_d \le 2k - 3$$

By (a) we know that $u_d+x_d = k$, so by a similar argument as above we get that $v_d+x_d \le k-3$, obtaining a contradiction. An analogous argument holds for $w_d+x_d$.

(c) This follows immediately by substituting (a) into (b).

We will now construct our induced matching $M'$. We construct two candidates for $M'$, and we will pick the biggest one. First, we construct $M'_0$ by including $u'v'$ for each edge $uv \in M$ where $\text{DIST}_G(u, u')$ is even. Symetrically, $M'_1$ is constructed by including $u'v'$ if $\text{DIST}_G(u, u')$ is odd. Clearly, at least one of $M'_0, M'_1$ contains $\ge \frac{|M|}{2}$ edges. It remains to show that $M'$ indeed forms an induced matching across the cut $A, \bar{A}$ in $G$.

Consider two distinct edges $u'v'$ and $w'x'$ from $M'$. By Claim 5.1, the two edges are vertex disjoint. If there is an edge violating that $u'v'$ and $w'x'$ are both in the same induced matching, it must be either $u'x'$ or $v'w'$. Without loss of generality we may assume it is an edge of the type $u'x'$. By Claim 5.2 (c), we then have that the parities of $\text{DIST}_G(u, u')$ and $\text{DIST}_G(w, w')$ are different. But by how $M'$ was constructed, this is not possible. This concludes the proof. ▼

**► Observation 6.** For a positive integer $r$, a graph $G$ and a vertex $u \in V(G)$, the $r$-neighbourhood of $u$ is equal to the neighbourhood of $u$ in $G^r$, i.e. $N_G^r(u) = N_{G^r}(u)$.

The observation above shows that solving a distance-$r$ $(\sigma, \rho)$ problem on $G$ is the same as solving the same standard distance-1 variation of the problem on $G^r$. Hence, we may reduce our problem to the standard version by simply computing the graph power. Combining Theorem 5 with the algorithms provided in Proposition 3, we have the following consequence.
**► Claim 5.2.** Let $uv, wx \in M$ be two distinct edges of $M$ and let $u'v'$ and $w'x'$ be edges on the shortest paths as defined above. If there is an edge $u'x' \in E(G)$, then all of the following hold. See Figure 1.

(a) $u_d + x_d = k$

(b) $u_d + v_d = w_d + x_d = k - 1$

(c) $w_d = u_d - 1$

**Proof.** (a) Since $ux$ is not an edge in $G^k$, the distance between $u$ and $x$ must be at least $k + 1$ in $G$, and so $u_d + x_d$ must be at least $k$. It remains to show that $u_d + x_d \le k$ for equality to hold. Similarly to the proof of Claim 5.1, we know that $P_{uv}$ and $P_{wx}$ both are of length at most $k$. We get

$$u_d + v_d + w_d + x_d \le 2k - 2 \qquad (1)$$

The $-2$ at the end is because we do not include the length contributed by edges $u'v'$ and $w'x'$ in our sum. Now assume for the sake of contradiction that $u_d + x_d \ge k + 1$. Then we get that

$$v_d + w_d \le 2k - 2 - k - 1 = k - 3$$

Because $\text{DIST}_G(v', w') \le 3$ (follow the edges $u'v' \to u'x' \to w'x'$), this implies that $\text{DIST}_G(v, w) \le k$, and the edge $vw$ would hence exist in $G^k$. This contradicts that $uv$ and $wx$ were both in the same induced matching $M$.

(b) Assume for the sake of contradiction that $u_d + v_d \le k - 2$. Then, rather than Equation 1, we get the following bound

$$u_d + v_d + w_d + x_d \le 2k - 3$$

By (a) we know that $u_d + x_d = k$, so by a similar argument as above we get that $v_d + x_d \le k - 3$, obtaining a contradiction. An analogous argument holds for $w_d + x_d$.

(c) This follows immediately by substituting (a) into (b).

We will now construct our induced matching $M'$. We construct two candidates for $M'$, and we will pick the biggest one. First, we construct $M'_0$ by including $u'v'$ for each edge $uv \in M$ where $\text{DIST}_G(u, u')$ is even. Symetrically, $M'_1$ is constructed by including $u'v'$ if $\text{DIST}_G(u, u')$ is odd. Clearly, at least one of $M'_0, M'_1$ contains $\ge \frac{|M|}{2}$ edges. It remains to show that $M'$ indeed forms an induced matching across the cut $A, \bar{A}$ in $G$.

Consider two distinct edges $u'v'$ and $w'x'$ from $M'$. By Claim 5.1, the two edges are vertex disjoint. If there is an edge violating that $u'v'$ and $w'x'$ are both in the same induced matching, it must be either $u'x'$ or $v'w'$. Without loss of generality we may assume it is an edge of the type $u'x'$. By Claim 5.2 (c), we then have that the parities of $\text{DIST}_G(u, u')$ and $\text{DIST}_G(w, w')$ are different. But by how $M'$ was constructed, this is not possible. This concludes the proof. ▼

**► Observation 6.** For a positive integer $r$, a graph $G$ and a vertex $u \in V(G)$, the $r$-neighbourhood of $u$ is equal to the neighbourhood of $u$ in $G^r$, i.e. $N_G^r(u) = N_{G^r}(u)$.

The observation above shows that solving a distance-$r$ $(\sigma, \rho)$ problem on $G$ is the same as solving the same standard distance-1 variation of the problem on $G^r$. Hence, we may reduce our problem to the standard version by simply computing the graph power. Combining Theorem 5 with the algorithms provided in Proposition 3, we have the following consequence.
6:8 Generalized Distance Domination Problems on mim-width

**Corollary 7 (★)**. There is an algorithm that for all $r \in \mathbb{N}$, given a graph $G$ and a decomposition tree $(T, \delta)$ of $G$ with $w := \text{mimw}_G(T, \delta)$ solves each distance-$r$ $(\sigma, \rho)$ problem $\Pi$ with $d := d(\Pi)$

(i) in time $O(n^{4+4d \cdot w})$, if $T$ is a caterpillar, and

(ii) in time $O(n^{4+6d \cdot w})$, otherwise.

5 LCVP Problems

A generalization of $(\sigma, \rho)$ problems are the locally checkable vertex partitioning (LCVP) problems. A degree constraint matrix $D$ is a $q \times q$ matrix where each entry is a finite or co-finite subset of $\mathbb{N}$. For a graph $G$ and a partition of its vertices $\mathcal{V} = \{V_1, V_2, \dots, V_q\}$, we say that it is a $D$-partition if and only if, for each $i, j \in [q]$ and each vertex $v \in V_i$, it holds that $|N(v) \cap V_j| \in D[i, j]$. Empty partition classes are allowed.

For instance, if a graph can be partitioned according to the $3 \times 3$ matrix whose diagonal entries are $\{0\}$ and the non-diagonal ones are $\mathbb{N}$, then the graph is 3-colorable. Typically, the natural algorithmic questions associated with LCVP properties are existential.<fnref n="4" /> Interesting problems which can be phrased in such terms include the *H-COVERING* and *GRAPH H-HOMOMORPHISM* problems where *H* is fixed, as well as *q-COLORING*, *PERFECT MATCHING CUT* and more. We refer to [19] for an overview.

We generalize LCVP properties to their distance-$r$ version, by considering the ball of radius $r$ around each vertex rather than just the immediate neighbourhood.

**Definition 8 (Distance-$r$ neighbourhood constraint matrix).** A distance-$r$ neighbourhood constraint matrix $D$ is a $q \times q$ matrix where each entry is a finite or co-finite subset of $\mathbb{N}$. For a graph $G$ and a partition of its vertices $\mathcal{V} = \{V_1, V_2, \dots, V_q\}$, we say that it is a $D$-distance-$r$-partition if and only if, for each $i, j \in [q]$ and each vertex $v \in V_i$, it holds that $|N^r(v) \cap V_j| \in D[i, j]$. Empty partition classes are allowed.

We say that an algorithmic problem is a *distance-$r$ LCVP problem* if the property in question can be described by a distance-$r$ neighbourhood constraint matrix. For example, the distance-$r$ version of a problem such as *q-COLORING* can be interpreted as an assignment of at most *q* colours to vertices of a graph such that no two vertices are assigned the same colour if they are at distance *r* or closer.

For a given distance-$r$ LCVP problem $\Pi$, its $d$-value $d(\Pi)$ is the maximum $d$-value over all the sets in the corresponding neighbourhood constraint matrix.

As in the case of $(\sigma, \rho)$ problems, combining Theorem 5 with Observation 6 and the works [3, 6] we have the following result.

**Corollary 9.** There is an algorithm that for all $r \in \mathbb{N}$, given a graph $G$ and a decomposition tree $(T, \delta)$ of $G$ with $w := \text{mimw}_G(T, \delta)$ solves each distance-$r$ LCVP problem $\Pi$ with $d := d(\Pi)$

(i) in time $O(n^{4+4qd \cdot w})$, if $T$ is a caterpillar, and

(ii) in time $O(n^{4+6qd \cdot w})$, otherwise.

<footnote n="4">⁴ Note however that each $(\sigma, \rho)$ problem can be stated as an LCVP problem via the matrix $D_{(\sigma, \rho)} = \begin{bmatrix} \sigma & \mathbb{N} \\ \rho & \mathbb{N} \end{bmatrix}$, so maximization or minimization of some block of the partition can be natural as well.</footnote>
6:8 Generalized Distance Domination Problems on mim-width

**Corollary 7 (★)**. There is an algorithm that for all $r \in \mathbb{N}$, given a graph $G$ and a decomposition tree $(T, \delta)$ of $G$ with $w := mimw_G(T, \delta)$ solves each distance-$r$ $(\sigma, \rho)$ problem $\Pi$ with $d := d(\Pi)$

(i) in time $O(n^{4+4d \cdot w})$, if $T$ is a caterpillar, and

(ii) in time $O(n^{4+6d \cdot w})$, otherwise.

5 LCVP Problems

A generalization of $(\sigma, \rho)$ problems are the locally checkable vertex partitioning (LCVP) problems. A degree constraint matrix $D$ is a $q \times q$ matrix where each entry is a finite or co-finite subset of $\mathbb{N}$. For a graph $G$ and a partition of its vertices $\mathcal{V} = \{V_1, V_2, \dots, V_q\}$, we say that it is a $D$-partition if and only if, for each $i, j \in [q]$ and each vertex $v \in V_i$, it holds that $|N(v) \cap V_j| \in D[i, j]$. Empty partition classes are allowed.

For instance, if a graph can be partitioned according to the $3 \times 3$ matrix whose diagonal entries are $\{0\}$ and the non-diagonal ones are $\mathbb{N}$, then the graph is 3-colorable. Typically, the natural algorithmic questions associated with LCVP properties are existential.<fnref n="4" /> Interesting problems which can be phrased in such terms include the *H-COVERING* and *GRAPH H-HOMOMORPHISM* problems where *H* is fixed, as well as *q-COLORING*, *PERFECT MATCHING CUT* and more. We refer to [19] for an overview.

We generalize LCVP properties to their distance-$r$ version, by considering the ball of radius $r$ around each vertex rather than just the immediate neighbourhood.

**Definition 8 (Distance-$r$ neighbourhood constraint matrix).** A distance-$r$ neighbourhood constraint matrix $D$ is a $q \times q$ matrix where each entry is a finite or co-finite subset of $\mathbb{N}$. For a graph $G$ and a partition of its vertices $\mathcal{V} = \{V_1, V_2, \dots, V_q\}$, we say that it is a $D$-distance-$r$-partition if and only if, for each $i, j \in [q]$ and each vertex $v \in V_i$, it holds that $|N^r(v) \cap V_j| \in D[i, j]$. Empty partition classes are allowed.

We say that an algorithmic problem is a *distance-$r$ LCVP problem* if the property in question can be described by a distance-$r$ neighbourhood constraint matrix. For example, the distance-$r$ version of a problem such as *q-COLORING* can be interpreted as an assignment of at most *q* colours to vertices of a graph such that no two vertices are assigned the same colour if they are at distance *r* or closer.

For a given distance-$r$ LCVP problem $\Pi$, its $d$-value $d(\Pi)$ is the maximum $d$-value over all the sets in the corresponding neighbourhood constraint matrix.

As in the case of $(\sigma, \rho)$ problems, combining Theorem 5 with Observation 6 and the works [3, 6] we have the following result.

**Corollary 9.** There is an algorithm that for all $r \in \mathbb{N}$, given a graph $G$ and a decomposition tree $(T, \delta)$ of $G$ with $w := mimw_G(T, \delta)$ solves each distance-$r$ LCVP problem $\Pi$ with $d := d(\Pi)$

(i) in time $O(n^{4+4qd \cdot w})$, if $T$ is a caterpillar, and

(ii) in time $O(n^{4+6qd \cdot w})$, otherwise.

<footnote n="4">⁴ Note however that each $(\sigma, \rho)$ problem can be stated as an LCVP problem via the matrix $D_{(\sigma, \rho)} = \begin{bmatrix} \sigma & \mathbb{N} \\ \rho & \mathbb{N} \end{bmatrix}$, so maximization or minimization of some block of the partition can be natural as well.</footnote>
# 6 Lower Bounds

We show that several $(\sigma, \rho)$-problems are W[1]-hard parameterized by linear mim-width plus solution size. Our reductions are based on two recent reductions due to Fomin, Golovach and Raymond [10] who showed that INDEPENDENT SET and DOMINATING SET are W[1]-hard parameterized by linear mim-width plus solution size. In fact they show hardness for the above mentioned problems on H-graphs (the parameter being the number of edges in H plus solution size) which we now define formally.

**► Definition 10 (H-Graph).** Let $X$ be a set and $S$ a family of subsets of $X$. The intersection graph of $S$ is a graph with vertex set $S$ such that $S, T \in S$ are adjacent if and only if $S \cap T \neq \emptyset$. Let $H$ be a (multi-) graph. We say that $G$ is an $H$-graph if there is a subdivision $H'$ of $H$ and a family of subsets $\mathcal{M} := \{M_v\}_{v \in V(G)}$ (called an $H$-representation) of $V(H')$ where $H'[M_v]$ is connected for all $v \in V(G)$, such that $G$ is isomorphic to the intersection graph of $\mathcal{M}$.

All of the hardness results presented in this section are obtained via reductions to the respective problems on *H*-graphs, and the hardness for linear mim-width follows from the following proposition.

**► Proposition 11 (Theorem 2 in [10]).** Let $G$ be an $H$-graph. Then, $G$ has linear mim-width at most $2 \cdot \|H\|$ and a corresponding decomposition tree can be computed in polynomial time given an $H$-representation of $G$.

The first lower bound concerns several maximization problems that can be expressed in the $(\sigma, \rho)$ framework. Recall that the INDEPENDENT SET problem can be formulated as $\text{MAX-}\{(0, \mathbb{N})\}$. The following result states that a class of problems that generalize the INDEPENDENT SET problem where each vertex in the solution is allowed to have at most some fixed number of $d$ neighbors of the solution, and several variants thereof, is W[1]-hard on $H$-graphs parameterized by $\|H\|$ plus solution size.

**► Theorem 12.** For any fixed $d \in \mathbb{N}$ and $x \le d+1$, the following holds. Let $\sigma^* \subseteq \mathbb{N}_{\le d}$ with $d \in \sigma^*$. Then, $\text{MAX-}(\sigma^*, \mathbb{N}_{\ge x})$ DOMINATION is W[1]-hard on $H$-graphs parameterized by the number of edges in $H$ plus solution size, and the hardness holds even if an $H$-representation of the input graph is given.

**Proof.** To prove the theorem, we provide a reduction from MULTICOLORED CLIQUE where given a graph $G$ and a partition $V_1, \dots, V_k$ of $V(G)$, the question is whether $G$ contains a clique of size $k$ using precisely one vertex from each $V_i$ ($i \in [k]$). This problem is known to be W[1]-complete [8, 14].

Let $(G, V_1, \dots, V_k)$ be an instance of MULTICOLORED CLIQUE. We can assume that $k \ge 2$ and that $|V_i| = p$ for $i \in [k]$. If the second assumption does not hold, let $p := \max_{i \in [k]} |V_i|$ and add $p - |V_i|$ isolated vertices to $V_i$, for each $i \in [k]$. (Note that adding isolated vertices does not change the answer to the problem.) For $i \in [k]$, we denote by $v_1^i, \dots, v_p^i$ the vertices of $V_i$. We first describe the reduction of Fomin et al. [10] and then explain how to modify it to prove the theorem.

**The Construction of Fomin, Golovach and Raymond [10].** The graph $H$ is obtained as follows.

1. Construct $k$ nodes $u_1, \dots, u_k$.
# 6 Lower Bounds

We show that several $(\sigma, \rho)$-problems are W[1]-hard parameterized by linear mim-width plus solution size. Our reductions are based on two recent reductions due to Fomin, Golovach and Raymond [10] who showed that INDEPENDENT SET and DOMINATING SET are W[1]-hard parameterized by linear mim-width plus solution size. In fact they show hardness for the above mentioned problems on H-graphs (the parameter being the number of edges in H plus solution size) which we now define formally.

**► Definition 10 (H-Graph).** Let $X$ be a set and $S$ a family of subsets of $X$. The intersection graph of $S$ is a graph with vertex set $S$ such that $S, T \in S$ are adjacent if and only if $S \cap T \neq \emptyset$. Let $H$ be a (multi-) graph. We say that $G$ is an $H$-graph if there is a subdivision $H'$ of $H$ and a family of subsets $\mathcal{M} := \{M_v\}_{v \in V(G)}$ (called an $H$-representation) of $V(H')$ where $H'[M_v]$ is connected for all $v \in V(G)$, such that $G$ is isomorphic to the intersection graph of $\mathcal{M}$.

All of the hardness results presented in this section are obtained via reductions to the respective problems on $H$-graphs, and the hardness for linear mim-width follows from the following proposition.

**► Proposition 11 (Theorem 2 in [10]).** Let $G$ be an $H$-graph. Then, $G$ has linear mim-width at most $2 \cdot \|H\|$ and a corresponding decomposition tree can be computed in polynomial time given an $H$-representation of $G$.

The first lower bound concerns several maximization problems that can be expressed in the $(\sigma, \rho)$ framework. Recall that the INDEPENDENT SET problem can be formulated as $\text{MAX-}\{(0, \mathbb{N})\}$. The following result states that a class of problems that generalize the INDEPENDENT SET problem where each vertex in the solution is allowed to have at most some fixed number of $d$ neighbors of the solution, and several variants thereof, is W[1]-hard on $H$-graphs parameterized by $\|H\|$ plus solution size.

**► Theorem 12.** For any fixed $d \in \mathbb{N}$ and $x \le d+1$, the following holds. Let $\sigma^* \subseteq \mathbb{N}_{\le d}$ with $d \in \sigma^*$. Then, $\text{MAX-}(\sigma^*, \mathbb{N}_{\ge x})$ DOMINATION is W[1]-hard on $H$-graphs parameterized by the number of edges in $H$ plus solution size, and the hardness holds even if an $H$-representation of the input graph is given.

**Proof.** To prove the theorem, we provide a reduction from MULTICOLORED CLIQUE where given a graph $G$ and a partition $V_1, \dots, V_k$ of $V(G)$, the question is whether $G$ contains a clique of size $k$ using precisely one vertex from each $V_i$ ($i \in [k]$). This problem is known to be W[1]-complete [8, 14].

Let $(G, V_1, \dots, V_k)$ be an instance of MULTICOLORED CLIQUE. We can assume that $k \ge 2$ and that $|V_i| = p$ for $i \in [k]$. If the second assumption does not hold, let $p := \max_{i \in [k]} |V_i|$ and add $p - |V_i|$ isolated vertices to $V_i$, for each $i \in [k]$. (Note that adding isolated vertices does not change the answer to the problem.) For $i \in [k]$, we denote by $v_1^i, \dots, v_p^i$ the vertices of $V_i$. We first describe the reduction of Fomin et al. [10] and then explain how to modify it to prove the theorem.

**The Construction of Fomin, Golovach and Raymond [10].** The graph $H$ is obtained as follows.

1. Construct $k$ nodes $u_1, \dots, u_k$.