24:10 Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness

**Corollary 11.** Let $\Phi$ be a graph property and let $\mathcal{K} = \{k \in \mathbb{N} \mid \sum_{A \in \mathcal{E}_k^*} (-1)^{\#A} \neq 0\}$. If $\mathcal{K}$ is infinite, then $\#\mathrm{IndSub}(\Phi)$ is $\#\mathrm{W}[1]$-hard. If additionally $\mathcal{K}$ is dense, $\#\mathrm{IndSub}(\Phi)$ can not be solved in time $f(k) \cdot \#V(G)^{o(k)}$ for any computable function $f$, unless ETH fails.

Due to space constraints the proof is deferred to the related version of the paper. However, let us give the rough idea: By Theorem 9 and Theorem 10 there exists a (tight) reduction from the problem $\#\mathrm{Clique}(\mathcal{K})$ of counting cliques of size $k$ where $k \in \mathcal{K}$ is promised.

As $\mathcal{K}$ is infinite we can apply a standard technique using colors and the inclusion-exclusion principle to reduce $\#\mathrm{Clique}$ to $\#\mathrm{Clique}(\mathcal{K})$, the former of which is $\#\mathrm{W}[1]$-complete and, assuming ETH, cannot be solved in time $f(k) \cdot n^{o(k)}$ for any computable function $f$ [5, 6]. This immediately yields $\#\mathrm{W}[1]$-hardness of $\#\mathrm{Clique}(\mathcal{K})$ and hence $\#\mathrm{IndSub}(\Phi)$. If additionally $\mathcal{K}$ is dense, the reduction is tight and the lower bound under ETH transfers as well.

4 Monotone properties

Recall that monotone graph properties are closed under the removal of edges. In what follows we assume every monotone graph property to hold on the independent set, i.e., the graph containing no edges, because otherwise the property would be trivially false. For technical reasons we say that a property is *non-trivial* if it is false on $K_k$ for all but finitely many $k \in \mathbb{N}$.<fnref n="9" /> Due to space constraints we might omit or only sketch proofs and defer the details to the related version of the paper. We start by refining Theorem 10 for monotone properties.

**Lemma 12.** Let $\Phi$ be a monotone graph property and let $k$ be a non-zero natural number. Then it holds that $\sum_{A \in \mathcal{E}_k^*} (-1)^{\#A} = \hat{\chi}(\Delta(\Phi_k))$.

**Corollary 13 (Corollary 2 restated).** Let $\Phi$ be a monotone graph property and let

$$ \mathcal{K} = \{k \in \mathbb{N} \mid \hat{\chi}(\Delta(\Phi_k)) \neq 0\}. $$

If $\mathcal{K}$ is infinite, then $\#\mathrm{IndSub}(\Phi)$ is $\#\mathrm{W}[1]$-hard. If additionally $\mathcal{K}$ is dense, $\#\mathrm{IndSub}(\Phi)$ can not be solved in time $f(k) \cdot \#V(G)^{o(k)}$ for any computable function $f$, unless ETH fails.

**Proof.** Follows immediately from Lemma 12 and Corollary 11. ▼

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

The above criterion yields hardness of $\#\mathrm{IndSub}(\Phi)$ for every monotone graph property $\Phi$ whose graph complex is well-understood with respect to the (reduced) Euler characteristic. The thesis of Jonsson (see Chapt. 10.5 in [17]) provides a large list of graph complexes including e.g. disconnectivity, colorability and coverability, only to name a few, whose reduced Euler characteristics are non-zero infinitely often and to which Corollary 13 is hence applicable. We would also like to point out the work of Chakrabarti, Khot and Shi [4] who proved the reduced Euler characteristic of a large family of graph complexes to be odd. Their result will be used to prove the fourth condition of Theorem 4 and reads as follows — we state it in terms of homomorphisms.

**Lemma 14 ([4]).** Let $F$ be a graph and let $\Phi^{[F]}$ be the graph property that holds true on a graph $G$ if and only if $\mathrm{Hom}(F, G) = \emptyset$, i.e., there is no homomorphism from $F$ to $G$. Furthermore let $T_F := \min\{2^{2^t} - 1 \mid 2^{2^t} \ge \#V(F)\}$ and let $k \in \mathbb{N}$ such that $k \equiv 1 \mod T_F$. Then it holds that $\chi(\Phi_k^{[F]}) \equiv 0 \mod 2$ and hence $\hat{\chi}(\Phi_k^{[F]}) \equiv 1 \mod 2$.

<footnote n="9">⁹ This is required to exclude properties like $\Phi(G) = 0 \Leftrightarrow \#V(G) \equiv 1 \mod 2$ which indeed is monotone as it is closed under the removal of edges.</footnote>
<figure><img src="image_123.png" /><figcaption>■ **Figure 1** Non-empty unions of orbits on the operation of $Z_7$ on the edge set of the labeled graph with 7 vertices. If $\Phi$ is trivially true then $\Delta^{Z_7}(\Phi_7)$ contains all of the above subsets of orbits. If $\Phi$ holds only for bipartite graphs then none of the above subsets is contained in $\Delta^{Z_7}(\Phi_7)$. If $\Phi$ is planarity then $\Delta^{Z_7}(\Phi_7) = \{O_1, O_2, O_3\}$. More exotically, if $\Phi$ is the property of not being 5-edge-connected then $\Delta^{Z_7}(\Phi_7)$ contains every subset of orbits except for $O_1 \cup O_2 \cup O_3$.</figcaption></figure>

Unfortunately, as the proof of the above lemma shows, it is often quite tedious to argue about the (reduced) Euler characteristic of the graph complex induced by a more complicated property $\Phi$ and hence proving hardness of $\#\mathrm{IndSub}(\Phi)$. In the remainder of this section we will therefore demonstrate that Corollary 13 together with Theorem 7 yields a fruitful topological approach to prove $\#\mathrm{W}[1]$-hardness and conditional lower bounds for $\#\mathrm{IndSub}(\Phi)$, given that $\Phi$ is a monotone graph property. We outline the approach in the following lemma.

**Lemma 15.** Let $\Phi$ be a monotone graph property, let $\mathcal{K}$ be an infinite subset of $\mathbb{N}$ and let $\Gamma = \{\Gamma_k \mid k \in \mathcal{K}\}$ be a set of permutation groups such that for every $k \in \mathcal{K}$ the group $\Gamma_k$ is a $p_k$-power group for some prime $p_k$. If $\hat{\chi}(\Delta^{\Gamma}(\Phi_k)) \neq 0 \bmod{p_k}$ holds for every $k \in \mathcal{K}$ then $\#\mathrm{IndSub}(\Phi)$ is $\#\mathrm{W}[1]$-hard. If additionally $\mathcal{K}$ is dense, $\#\mathrm{IndSub}(\Phi)$ can not be solved in time $f(k) \cdot \#\mathrm{V}(G)^{o(k)}$ for any computable function $f$, unless ETH fails.

**Proof.** Follows immediately from Corollary 13 and Theorem 7. ▼

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

Intuitively, Lemma 15 states that instead of analyzing $\hat{\chi}(\Delta(\Phi_k))$ which might be tedious, it suffices to prove that the reduced Euler characteristic of the fixed-point complex of $\Delta(\Phi_k)$ with respect to a $p$-power group is not 0 modulo $p$. For our purposes it will suffice to use the groups $Z_p$ for prime numbers $p$, explained as follows. Recall that the ground set of $\Delta(\Phi_p)$ is the set of all edges of the labeled complete graph on $p$ vertices. Now $b \in Z_p$ is interpreted as a relabeling $x \mapsto x+b$ of the vertices$^{10}$, which induces an operation on the edges by mapping the edge $\{x, y\}$ to the edge $\{x+b, y+b\}$. We remark that this group was also used in an intermediate step in [18]. It can easily be verified that this mapping is a group operation. Furthermore $\Delta(\Phi_p)$ is a $Z_p$-simplicial complex with respect to this operation as $\Phi$ is invariant under relabeling of vertices. Hence the fixed-point complex $\Delta^{Z_p}(\Phi_p)$ is defined. Furthermore observe that every orbit of the group operation is an Hamilton cycle. We illustrate $\Delta^{Z_7}(\Phi_7)$ for some properties $\Phi$ in Figure 1.

Note that, given a prime $p > 2$, the ground set of $\Delta^{Z_p}(\Phi_p)$ consists of exactly $\frac{1}{2}(p-1)$ elements. In particular those are the Hamiltonian cycles $H_1 = (0, 1, 2, \dots)$, $H_2 = (0, 2, 4, \dots)$, $H_3 = (0, 3, 6, \dots)$, ..., $H_{\frac{1}{2}(p-1)} = (0, \frac{1}{2}(p-1), p-1, \dots)$. Equivalently, $H_i$ is the orbit of the (labeled) edge $\{0, i\}$ under the operation of $Z_p$ for $i \in \{1, \dots, \frac{1}{2}(p-1)\}$ and it can easily be verified that those are all orbits of the group operation. In what follows, given a non-empty set $P \subseteq \{1, \dots, \frac{1}{2}(p-1)\}$, we write $H_P$ for the graph with vertices (labeled with) $\{0, \dots, p-1\}$ and edges $\bigcup_{i \in P} H_i$.

**Fact 16.** Let $P$ be non-empty subset of $\{1, \dots, \frac{1}{2}(p-1)\}$. Then $P \in \Delta^{Z_P}(\Phi_P) \Leftrightarrow H_P \in \Phi_P$.

<footnote n="10">10 Here + is addition modulo $p$.</footnote>
<figure><img src="image_124.png" /><figcaption>■ **Figure 1** Non-empty unions of orbits on the operation of $Z_7$ on the edge set of the labeled graph with 7 vertices. If $\Phi$ is trivially true then $\Delta^{Z_7}(\Phi_7)$ contains all of the above subsets of orbits. If $\Phi$ holds only for bipartite graphs then none of the above subsets is contained in $\Delta^{Z_7}(\Phi_7)$. If $\Phi$ is planarity then $\Delta^{Z_7}(\Phi_7) = \{O_1, O_2, O_3\}$. More exotically, if $\Phi$ is the property of not being 5-edge-connected then $\Delta^{Z_7}(\Phi_7)$ contains every subset of orbits except for $O_1 \cup O_2 \cup O_3$.</figcaption></figure>

Unfortunately, as the proof of the above lemma shows, it is often quite tedious to argue about the (reduced) Euler characteristic of the graph complex induced by a more complicated property $\Phi$ and hence proving hardness of $\#\mathrm{IndSub}(\Phi)$. In the remainder of this section we will therefore demonstrate that Corollary 13 together with Theorem 7 yields a fruitful topological approach to prove $\#\mathrm{W}[1]$-hardness and conditional lower bounds for $\#\mathrm{IndSub}(\Phi)$, given that $\Phi$ is a monotone graph property. We outline the approach in the following lemma.

**Lemma 15.** Let $\Phi$ be a monotone graph property, let $\mathcal{K}$ be an infinite subset of $\mathbb{N}$ and let $\Gamma = \{\Gamma_k \mid k \in \mathcal{K}\}$ be a set of permutation groups such that for every $k \in \mathcal{K}$ the group $\Gamma_k$ is a $p_k$-power group for some prime $p_k$. If $\hat{\chi}(\Delta^{\Gamma}(\Phi_k)) \neq 0 \bmod{p_k}$ holds for every $k \in \mathcal{K}$ then $\#\mathrm{IndSub}(\Phi)$ is $\#\mathrm{W}[1]$-hard. If additionally $\mathcal{K}$ is dense, $\#\mathrm{IndSub}(\Phi)$ can not be solved in time $f(k) \cdot \#\mathrm{V}(G)^{o(k)}$ for any computable function $f$, unless ETH fails.

**Proof.** Follows immediately from Corollary 13 and Theorem 7. ▼

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

Intuitively, Lemma 15 states that instead of analyzing $\hat{\chi}(\Delta(\Phi_k))$ which might be tedious, it suffices to prove that the reduced Euler characteristic of the fixed-point complex of $\Delta(\Phi_k)$ with respect to a $p$-power group is not 0 modulo $p$. For our purposes it will suffice to use the groups $Z_p$ for prime numbers $p$, explained as follows. Recall that the ground set of $\Delta(\Phi_p)$ is the set of all edges of the labeled complete graph on $p$ vertices. Now $b \in Z_p$ is interpreted as a relabeling $x \mapsto x+b$ of the vertices$^{10}$, which induces an operation on the edges by mapping the edge $\{x, y\}$ to the edge $\{x+b, y+b\}$. We remark that this group was also used in an intermediate step in [18]. It can easily be verified that this mapping is a group operation. Furthermore $\Delta(\Phi_p)$ is a $Z_p$-simplicial complex with respect to this operation as $\Phi$ is invariant under relabeling of vertices. Hence the fixed-point complex $\Delta^{Z_p}(\Phi_p)$ is defined. Furthermore observe that every orbit of the group operation is an Hamilton cycle. We illustrate $\Delta^{Z_7}(\Phi_7)$ for some properties $\Phi$ in Figure 1.

Note that, given a prime $p > 2$, the ground set of $\Delta^{Z_p}(\Phi_p)$ consists of exactly $\frac{1}{2}(p-1)$ elements. In particular those are the Hamiltonian cycles $H_1 = (0, 1, 2, \dots)$, $H_2 = (0, 2, 4, \dots)$, $H_3 = (0, 3, 6, \dots)$, ..., $H_{\frac{1}{2}(p-1)} = (0, \frac{1}{2}(p-1), p-1, \dots)$. Equivalently, $H_i$ is the orbit of the (labeled) edge $\{0, i\}$ under the operation of $Z_p$ for $i \in \{1, \dots, \frac{1}{2}(p-1)\}$ and it can easily be verified that those are all orbits of the group operation. In what follows, given a non-empty set $P \subseteq \{1, \dots, \frac{1}{2}(p-1)\}$, we write $H_P$ for the graph with vertices (labeled with) $\{0, \dots, p-1\}$ and edges $\bigcup_{i \in P} H_i$.

**Fact 16.** Let $P$ be non-empty subset of $\{1, \dots, \frac{1}{2}(p-1)\}$. Then $P \in \Delta^{Z_P}(\Phi_P) \Leftrightarrow H_P \in \Phi_P$.

<footnote n="10">10 Here + is addition modulo $p$.</footnote>
Now we have everything we need to prove our main result. We start with monotone properties that are false on odd cycles or true on odd antiholes.

**Lemma 17.** Let $\Phi$ be a non-trivial monotone graph property. If $\Phi$ does not hold on odd cycles or if $\Phi$ holds on odd anti-holes then there exists a constant $N \in \mathbb{N}$ such that $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) \neq 0 \mod p$ for every prime $p > N$.

**Proof sketch.** If $\Phi$ does not hold on odd cycles then $\Delta^{Z_p}(\Phi_p) = \emptyset$ and hence we have that $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) = 1 - \chi(\Delta^{Z_p}(\Phi_p)) = 1 - 0 = 1 \neq 0 \mod p$. As $\Phi$ is non-trivial there exists $N \in \mathbb{N}$ such that $\Phi(K_k) = 0$ for all $k > N$. Now if $\Phi$ holds on odd anti-holes then $\Delta^{Z_p}(\Phi_p) = \{P \mid \emptyset \subsetneq P \subsetneq \{1, \dots, \frac{1}{2}(p-1)\}\}$ for all $p > N$ since $\Phi$ is monotone and $H_P$ is an anti-hole if and only if $\#P = \frac{p-1}{2} - 1$. Furthermore, $\Phi$ does not hold on $H_{\{1, \dots, \frac{1}{2}(p-1)\}} \cong K_p$ as $p > N$. Now it can be easily verified that $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) = (-1)^{\frac{1}{2}(p-1)+1} \neq 0 \mod p$. $\quad$

We continue with one more exotic property which illustrates the utility of the topological approach by exploiting the simple structure of $\Delta^{Z_p}(\Phi_p)$.

**Lemma 18.** Let $c \in \mathbb{N}$ be an arbitrary constant and let $\Phi$ be the graph property of being not $(c+1)$-edge-connected. Then $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) \neq 0 \mod p$ for every prime $p > c + 3$.

**Proof sketch.** We rely on the observation that the graph $H_P$ is $(c+1)$-edge-connected if and only if $\#P > \lfloor \frac{c}{2} \rfloor$. Hence $\Delta^{Z_p}(\Phi_p) = \{P \subseteq \{1, \dots, \frac{1}{2}(p-1) \mid P \neq \emptyset \wedge \#P \leq \lfloor \frac{c}{2} \rfloor\}\}$. Now it can be easily verified that $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) = (-1)^{\lfloor \frac{c}{2} \rfloor} \cdot (\frac{1}{2}^{(p-1)-1}) \neq 0 \mod p$. $\quad$

Finally, Theorem 4 follows from Lemma 15, 14, 17 and 18. Details are given in the related version of the paper.

# 5 Non-monotone properties

In this section, we present #W[1]-hardness results for two non-monotone properties. For the first one, we generalize [16] where hardness was established for counting induced subgraphs with an even (or odd) number of edges. It turns out that any non-trivial modularity constraint with respect to a prime induces #W[1]-hardness. To this end let $q$ be a prime and $\mathcal{Q}$ be a subset of $\{0, \dots, q-1\}$. Then the property $\text{Mod}[q, \mathcal{Q}]$ holds on a graph $H$ if and only if $(\#E(H) \mod q) \in \mathcal{Q}$. For the second property, let $F$ be a connected graph. Then the property $\text{Iso}[F]$ holds on a graph $H$ if and only if $H$ contains an isolated subgraph that is isomorphic to $F$. Due to space constraints the proof of the following theorem is deferred to the related version of the paper.

**Theorem 19.** For all primes $q$, non-trivial subsets $\mathcal{Q}$ of $\{0, \dots, q-1\}$ and connected graphs $F$, the problems $\text{IndSub}(\text{Mod}[q, \mathcal{Q}])$ and $\text{IndSub}(\text{Iso}[F])$ are #W[1]-hard and can not be solved in time $f(k) \cdot n^{o(k)}$ for any computable function $f$, unless ETH fails.

# 6 Conclusion and future work

We used the framework of graph motif parameters to provide a sufficient criterion for #W[1]-hardness of $\text{IndSub}(\Phi)$. For monotone properties $\Phi$ this amounts to the reduced Euler characteristic of the associated graph complex to be non-zero infinitely often. In particular, our results provide a fine-grained reduction from the problem of counting cliques of size $k$ to counting induced subgraphs of size $k$ with property $\Phi$ whenever $\Phi$ is monotone and $\hat{\chi}(\Delta(\Phi_k)) \neq 0$. Using a topological approach, we established hardness for a large class of
Now we have everything we need to prove our main result. We start with monotone properties that are false on odd cycles or true on odd antiholes.

**Lemma 17.** Let $\Phi$ be a non-trivial monotone graph property. If $\Phi$ does not hold on odd cycles or if $\Phi$ holds on odd anti-holes then there exists a constant $N \in \mathbb{N}$ such that $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) \neq 0 \mod p$ for every prime $p > N$.

**Proof sketch.** If $\Phi$ does not hold on odd cycles then $\Delta^{Z_p}(\Phi_p) = \emptyset$ and hence we have that $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) = 1 - \chi(\Delta^{Z_p}(\Phi_p)) = 1 - 0 = 1 \neq 0 \mod p$. As $\Phi$ is non-trivial there exists $N \in \mathbb{N}$ such that $\Phi(K_k) = 0$ for all $k > N$. Now if $\Phi$ holds on odd anti-holes then $\Delta^{Z_p}(\Phi_p) = \{P \mid \emptyset \subsetneq P \subsetneq \{1, \dots, \frac{1}{2}(p-1)\}\}$ for all $p > N$ since $\Phi$ is monotone and $H_P$ is an anti-hole if and only if $\#P = \frac{p-1}{2} - 1$. Furthermore, $\Phi$ does not hold on $H_{\{1, \dots, \frac{1}{2}(p-1)\}} \cong K_p$ as $p > N$. Now it can be easily verified that $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) = (-1)^{\frac{1}{2}(p-1)+1} \neq 0 \mod p$. $\quad$

We continue with one more exotic property which illustrates the utility of the topological approach by exploiting the simple structure of $\Delta^{Z_p}(\Phi_p)$.

**Lemma 18.** Let $c \in \mathbb{N}$ be an arbitrary constant and let $\Phi$ be the graph property of being not $(c+1)$-edge-connected. Then $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) \neq 0 \mod p$ for every prime $p > c + 3$.

**Proof sketch.** We rely on the observation that the graph $H_P$ is $(c+1)$-edge-connected if and only if $\#P > \lfloor \frac{c}{2} \rfloor$. Hence $\Delta^{Z_p}(\Phi_p) = \{P \subseteq \{1, \dots, \frac{1}{2}(p-1) \mid P \neq \emptyset \wedge \#P \leq \lfloor \frac{c}{2} \rfloor\}\}$. Now it can be easily verified that $\hat{\chi}(\Delta^{Z_p}(\Phi_p)) = (-1)^{\lfloor \frac{c}{2} \rfloor} \cdot (\frac{1}{2}^{(p-1)-1}) \neq 0 \mod p$. $\quad$

Finally, Theorem 4 follows from Lemma 15, 14, 17 and 18. Details are given in the related version of the paper.

# 5 Non-monotone properties

In this section, we present #W[1]-hardness results for two non-monotone properties. For the first one, we generalize [16] where hardness was established for counting induced subgraphs with an even (or odd) number of edges. It turns out that any non-trivial modularity constraint with respect to a prime induces #W[1]-hardness. To this end let $q$ be a prime and $\mathcal{Q}$ be a subset of $\{0, \dots, q-1\}$. Then the property Mod[$q$, $\mathcal{Q}$] holds on a graph $H$ if and only if ($\#E(H) \mod q \in \mathcal{Q}$). For the second property, let $F$ be a connected graph. Then the property Iso[$F$] holds on a graph $H$ if and only if $H$ contains an isolated subgraph that is isomorphic to $F$. Due to space constraints the proof of the following theorem is deferred to the related version of the paper.

**Theorem 19.** For all primes $q$, non-trivial subsets $\mathcal{Q}$ of $\{0, \dots, q-1\}$ and connected graphs $F$, the problems #IndSub(Mod[$q$, $\mathcal{Q}$]) and #IndSub(Iso[$F$]) are #W[1]-hard and can not be solved in time $f(k) \cdot n^{o(k)}$ for any computable function $f$, unless ETH fails.

# 6 Conclusion and future work

We used the framework of graph motif parameters to provide a sufficient criterion for #W[1]-hardness of #IndSub($\Phi$). For monotone properties $\Phi$ this amounts to the reduced Euler characteristic of the associated graph complex to be non-zero infinitely often. In particular, our results provide a fine-grained reduction from the problem of counting cliques of size $k$ to counting induced subgraphs of size $k$ with property $\Phi$ whenever $\Phi$ is monotone and $\hat{\chi}(\Delta(\Phi_k)) \neq 0$. Using a topological approach, we established hardness for a large class of
non-trivial monotone graph properties. The obvious next question, whose answer would settle the parameterized complexity of #IndSub($\Phi$) for monotone properties completely, is whether for every non-trivial monotone property $\Phi$ the set of $k$ such that $\hat{\chi}(\Delta(\Phi_k)) \neq 0$ is infinite.

References

1. OEIS Foundation Inc. (2018). The On-Line Encyclopedia of Integer Sequences. URL: http://oeis.org.

2. Karl R. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-Parameter Inductability II (Extended Abstract). In *STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993, Proceedings*, pages 374–385, 1993. doi:10.1007/3-540-56503-5_38.

3. Glen E Bredon. *Introduction to compact transformation groups*, volume 46. Academic press, 1972.

4. Amit Chakrabarti, Subhash Khot, and Yaoyun Shi. Evasiveness of Subgraph Containment and Related Properties. *SIAM J. Comput.*, 31(3):866–875, 2001. doi:10.1137/S0097539700382005.

5. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. *Inf. Comput.*, 201(2):216–231, 2005. doi:10.1016/j.ic.2005.05.001.

6. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. *J. Comput. Syst. Sci.*, 72(8):1346–1367, 2006. doi:10.1016/j.jcss.2006.04.007.

7. Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. In *Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games*, pages 587–596, 2008. doi:10.1007/978-3-540-70575-8_48.

8. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In *Proceedings of the 49th ACM Symposium on Theory of Computing, STOC*, pages 210–223, 2017. doi:10.1145/3055399.3055502.

9. Radu Curticapean and Dániel Marx. Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. In *Proceedings of the 55th Annual Symposium on Foundations of Computer Science, FOCS*, pages 130–139, 2014. doi:10.1109/FOCS.2014.22.

10. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. *Theoretical Computer Science*, 329(1):315–323, 2004.

11. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. *SIAM J. Comput.*, 33(4):892–922, 2004. doi:10.1137/S0097539703427203.

12. Jörg Flum and Martin Grohe. *Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)*. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.

13. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. *Journal of the ACM (JACM)*, 54(1):1, 2007.

14. Mark Jerrum and Kitty Meeks. Some Hard Families of Parameterized Counting Problems. *TOCT*, 7(3):11:1–11:18, 2015. doi:10.1145/2786017.

15. Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. *J. Comput. Syst. Sci.*, 81(4):702–716, 2015. doi:10.1016/j.jcss.2014.11.015.
non-trivial monotone graph properties. The obvious next question, whose answer would settle the parameterized complexity of #IndSub($\Phi$) for monotone properties completely, is whether for every non-trivial monotone property $\Phi$ the set of $k$ such that $\hat{\chi}(\Delta(\Phi_k)) \neq 0$ is infinite.

References

1. OEIS Foundation Inc. (2018). The On-Line Encyclopedia of Integer Sequences. URL: http://oeis.org.

2. Karl R. Abrahamson, Rodney G. Downey, and Michael R. Fellows. Fixed-Parameter Inductability II (Extended Abstract). In *STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993, Proceedings*, pages 374–385, 1993. doi:10.1007/3-540-56503-5_38.

3. Glen E Bredon. *Introduction to compact transformation groups*, volume 46. Academic press, 1972.

4. Amit Chakrabarti, Subhash Khot, and Yaoyun Shi. Evasiveness of Subgraph Containment and Related Properties. *SIAM J. Comput.*, 31(3):866–875, 2001. doi:10.1137/S0097539700382005.

5. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. *Inf. Comput.*, 201(2):216–231, 2005. doi:10.1016/j.ic.2005.05.001.

6. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. Strong computational lower bounds via parameterized complexity. *J. Comput. Syst. Sci.*, 72(8):1346–1367, 2006. doi:10.1016/j.jcss.2006.04.007.

7. Yijia Chen, Marc Thurley, and Mark Weyer. Understanding the Complexity of Induced Subgraph Isomorphisms. In *Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games*, pages 587–596, 2008. doi:10.1007/978-3-540-70575-8_48.

8. Radu Curticapean, Holger Dell, and Dániel Marx. Homomorphisms are a good basis for counting small subgraphs. In *Proceedings of the 49th ACM Symposium on Theory of Computing, STOC*, pages 210–223, 2017. doi:10.1145/3055399.3055502.

9. Radu Curticapean and Dániel Marx. Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. In *Proceedings of the 55th Annual Symposium on Foundations of Computer Science, FOCS*, pages 130–139, 2014. doi:10.1109/FOCS.2014.22.

10. Víctor Dalmau and Peter Jonsson. The complexity of counting homomorphisms seen from the other side. *Theoretical Computer Science*, 329(1):315–323, 2004.

11. Jörg Flum and Martin Grohe. The Parameterized Complexity of Counting Problems. *SIAM J. Comput.*, 33(4):892–922, 2004. doi:10.1137/S0097539703427203.

12. Jörg Flum and Martin Grohe. *Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)*. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.

13. Martin Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. *Journal of the ACM (JACM)*, 54(1):1, 2007.

14. Mark Jerrum and Kitty Meeks. Some Hard Families of Parameterized Counting Problems. *TOCT*, 7(3):11:1–11:18, 2015. doi:10.1145/2786017.

15. Mark Jerrum and Kitty Meeks. The parameterised complexity of counting connected subgraphs and graph motifs. *J. Comput. Syst. Sci.*, 81(4):702–716, 2015. doi:10.1016/j.jcss.2014.11.015.
16 Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. *Combinatorica*, 37(5):965-990, 2017. doi:10.1007/s00493-016-3338-5.

17 Jakob Jonsson. *Simplicial complexes of graphs*, volume 1928 of *Lecture Notes in Mathematics*. Springer-Verlag, Berlin, 2008. doi:10.1007/978-3-540-75859-4.

18 Jeff Kahn, Michael E. Saks, and Dean Sturtevant. A Topological Approach to Evasiveness. In *24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983*, pages 31-33, 1983. doi:10.1109/SFCS.1983.4.

19 Richard E. Ladner. On the Structure of Polynomial Time Reducibility. *J. ACM*, 22(1):155-171, 1975. doi:10.1145/321864.321877.

20 László Lovász. *Large networks and graph limits*, volume 60. American Mathematical Society Providence, 2012.

21 Frank H. Lutz. Some Results Related to the Evasiveness Conjecture. *J. Comb. Theory, Ser. B*, 81(1):110-124, 2001. doi:10.1006/jctb.2000.2000.

22 Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. *Discrete Applied Mathematics*, 198:170-194, 2016. doi:10.1016/j.dam.2015.06.019.

23 Carl A. Miller. Evasiveness of Graph Properties and Topological Fixed-Point Theorems. *Foundations and Trends in Theoretical Computer Science*, 7(4):337-415, 2013. doi:10.1561/0400000055.

24 Robert Oliver. Fixed-point sets of group actions on finite acyclic complexes. *Commentarii Mathematici Helvetici*, 50(1):155-177, 1975.

25 Ronald L. Rivest and Jean Vuillemin. On Recognizing Graph Properties from Adjacency Matrices. *Theor. Comput. Sci.*, 3(3):371-384, 1976. doi:10.1016/0304-3975(76)90053-0.

26 Marc Roth. Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices. In *25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria*, pages 63:1-63:14, 2017. doi:10.4230/LIPIcs.ESA.2017.63.

27 PA Smith. Fixed-point theorems for periodic transformations. *American Journal of Mathematics*, 63(1):1-8, 1941.

28 Leslie G. Valiant. The Complexity of Computing the Permanent. *Theor. Comput. Sci.*, 8:189-201, 1979. doi:10.1016/0304-3975(79)90044-6.
16 Mark Jerrum and Kitty Meeks. The parameterised complexity of counting even and odd induced subgraphs. *Combinatorica*, 37(5):965-990, 2017. doi:10.1007/s00493-016-3338-5.

17 Jakob Jonsson. *Simplicial complexes of graphs*, volume 1928 of *Lecture Notes in Mathematics*. Springer-Verlag, Berlin, 2008. doi:10.1007/978-3-540-75859-4.

18 Jeff Kahn, Michael E. Saks, and Dean Sturtevant. A Topological Approach to Evasiveness. In *24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983*, pages 31-33, 1983. doi:10.1109/SFCS.1983.4.

19 Richard E. Ladner. On the Structure of Polynomial Time Reducibility. *J. ACM*, 22(1):155-171, 1975. doi:10.1145/321864.321877.

20 László Lovász. *Large networks and graph limits*, volume 60. American Mathematical Society Providence, 2012.

21 Frank H. Lutz. Some Results Related to the Evasiveness Conjecture. *J. Comb. Theory, Ser. B*, 81(1):110-124, 2001. doi:10.1006/jctb.2000.2000.

22 Kitty Meeks. The challenges of unbounded treewidth in parameterised subgraph counting problems. *Discrete Applied Mathematics*, 198:170-194, 2016. doi:10.1016/j.dam.2015.06.019.

23 Carl A. Miller. Evasiveness of Graph Properties and Topological Fixed-Point Theorems. *Foundations and Trends in Theoretical Computer Science*, 7(4):337-415, 2013. doi:10.1561/0400000055.

24 Robert Oliver. Fixed-point sets of group actions on finite acyclic complexes. *Commentarii Mathematici Helvetici*, 50(1):155-177, 1975.

25 Ronald L. Rivest and Jean Vuillemin. On Recognizing Graph Properties from Adjacency Matrices. *Theor. Comput. Sci.*, 3(3):371-384, 1976. doi:10.1016/0304-3975(76)90053-0.

26 Marc Roth. Counting Restricted Homomorphisms via Möbius Inversion over Matroid Lattices. In *25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria*, pages 63:1-63:14, 2017. doi:10.4230/LIPIcs.ESA.2017.63.

27 PA Smith. Fixed-point theorems for periodic transformations. *American Journal of Mathematics*, 63(1):1-8, 1941.

28 Leslie G. Valiant. The Complexity of Computing the Permanent. *Theor. Comput. Sci.*, 8:189-201, 1979. doi:10.1016/0304-3975(79)90044-6.
# A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem

## Daniel Lokshtanov<fnref n="1" />

Department of Informatics - University of Bergen, Bergen, Norway
daniel.lokshtanov@uib.no

## Mateus de Oliveira Oliveira<fnref n="2" />

Department of Informatics - University of Bergen, Bergen, Norway
mateus.oliveira@uib.no

## Saket Saurabh<fnref n="3" />

Department of Informatics - University of Bergen, Bergen, Norway
saket.saurabh@uib.no

### Abstract

In the EMBEDDED PLANAR DIAMETER IMPROVEMENT problem (EPDI) we are given a graph $G$ embedded in the plane and a positive integer $d$. The goal is to determine whether one can add edges to the planar embedding of $G$ in such a way that planarity is preserved and in such a way that the resulting graph has diameter at most $d$. Using non-constructive techniques derived from Robertson and Seymour's graph minor theory, together with the effectivization by self-reduction technique introduced by Fellows and Langston, one can show that EPDI can be solved in time $f(d) \cdot |V(G)|^{O(1)}$ for some function $f(d)$. The caveat is that this algorithm is *not* strongly uniform in the sense that the function $f(d)$ is not known to be computable. On the other hand, even the problem of determining whether EPDI can be solved in time $f_1(d) \cdot |V(G)|^{f_2(d)}$ for *computable* functions $f_1$ and $f_2$ has been open for more than two decades [Cohen et. al. Journal of Computer and System Sciences, 2017]. In this work we settle this later problem by showing that EPDI can be solved in time $f(d) \cdot |V(G)|^{O(d)}$ for some computable function $f$. Our techniques can also be used to show that the EMBEDDED $k$-OUTERPLANAR DIAMETER IMPROVEMENT problem ($k$-EOPDI), a variant of EPDI where the resulting graph is required to be $k$-outerplanar instead of planar, can be solved in time $f(d) \cdot |V(G)|^{O(k)}$ for some computable function $f$. This shows that for each fixed $k$, the problem $k$-EOPDI is strongly uniformly fixed parameter tractable with respect to the diameter parameter $d$.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and
exact algorithms

**Keywords and phrases** Embedded Planar Diameter Improvement, Constructive Algorithms, Nooses

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

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

<footnote n="1">¹ Daniel Lokshtanov acknowledges support from the ERC grant agreement no. 715744.</footnote>

<footnote n="2">² Mateus de Oliveira Oliveira acknowledges support from the Bergen Research Foundation.</footnote>

<footnote n="3">³ Saket Saurabh acknowledges support from the ERC grant agreement no. 306992.</footnote>
# A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem

## Daniel Lokshtanov<fnref n="1" />

Department of Informatics - University of Bergen, Bergen, Norway
daniel.lokshtanov@uib.no

## Mateus de Oliveira Oliveira<fnref n="2" />

Department of Informatics - University of Bergen, Bergen, Norway
mateus.oliveira@uib.no

## Saket Saurabh<fnref n="3" />

Department of Informatics - University of Bergen, Bergen, Norway
saket.saurabh@uib.no

### Abstract

In the EMBEDDED PLANAR DIAMETER IMPROVEMENT problem (EPDI) we are given a graph $G$ embedded in the plane and a positive integer $d$. The goal is to determine whether one can add edges to the planar embedding of $G$ in such a way that planarity is preserved and in such a way that the resulting graph has diameter at most $d$. Using non-constructive techniques derived from Robertson and Seymour's graph minor theory, together with the effectivization by self-reduction technique introduced by Fellows and Langston, one can show that EPDI can be solved in time $f(d) \cdot |V(G)|^{O(1)}$ for some function $f(d)$. The caveat is that this algorithm is *not* strongly uniform in the sense that the function $f(d)$ is not known to be computable. On the other hand, even the problem of determining whether EPDI can be solved in time $f_1(d) \cdot |V(G)|^{f_2(d)}$ for *computable* functions $f_1$ and $f_2$ has been open for more than two decades [Cohen et. al. Journal of Computer and System Sciences, 2017]. In this work we settle this later problem by showing that EPDI can be solved in time $f(d) \cdot |V(G)|^{O(d)}$ for some computable function $f$. Our techniques can also be used to show that the EMBEDDED $k$-OUTERPLANAR DIAMETER IMPROVEMENT problem ($k$-EOPDI), a variant of EPDI where the resulting graph is required to be $k$-outerplanar instead of planar, can be solved in time $f(d) \cdot |V(G)|^{O(k)}$ for some computable function $f$. This shows that for each fixed $k$, the problem $k$-EOPDI is strongly uniformly fixed parameter tractable with respect to the diameter parameter $d$.

**2012 ACM Subject Classification** Theory of computation → Parameterized complexity and exact algorithms

**Keywords and phrases** Embedded Planar Diameter Improvement, Constructive Algorithms, Nooses

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

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

<footnote n="1">¹ Daniel Lokshtanov acknowledges support from the ERC grant agreement no. 715744.</footnote>

<footnote n="2">² Mateus de Oliveira Oliveira acknowledges support from the Bergen Research Foundation.</footnote>

<footnote n="3">³ Saket Saurabh acknowledges support from the ERC grant agreement no. 306992.</footnote>
# 1 Introduction

In this work, a *plane graph* is a pair $G^g = (G, g)$ consisting of a planar graph $G$ together with a planar embedding $g$ of $G^4$. In the EMBEDDED PLANAR DIAMETER IMPROVEMENT problem (EPDI), we are given a plane graph $G^g$ and a positive integer $d$, and the goal is to determine whether $G^g$ has a plane supergraph $H^h$ of diameter at most $d$. The set of YES instances of EPDI is closed under minors. In other words, if $G^g$ has a plane supergraph of diameter at most $d$, then any minor of $G^g$ also has such a supergraph. Therefore, using non-constructive arguments from Robertson and Seymour's graph minor theory [14, 15] in conjunction with the fact that planar graphs of constant diameter have constant treewidth, one can show that for each fixed $d$, there exists an algorithm $\mathfrak{A}_d$ which determines in linear time whether a given plane graph $G^g$ has a plane supergraph of diameter at most $d$. The caveat is that the non-constructive techniques mentioned above provide us with no clue about what the algorithm $\mathfrak{A}_d$ actually is. This problem can be partially remedied using a technique called effectivization by self-reduction introduced by Fellows and Langston [10, 8]. Using this technique one can show that for some function $f: \mathbb{N} \to \mathbb{N}$, there exists a single algorithm $\mathfrak{A}$ which takes a plane graph $G^g$ and a positive integer $d$ as input, and determines in time $f(d) \cdot |V(G)|^{O(1)}$ whether $G^g$ has a plane supergraph of diameter at most $d$. Nevertheless, the function $f: \mathbb{N} \to \mathbb{N}$ bounding the influence of the parameter $d$ in the running time of the algorithm mentioned above is not known to be computable. The problem of determining whether EPDI admits an algorithm running in time $f(d) \cdot |V(G)|^{O(1)}$ for some *computable* function $f$ is a notorious and long-standing open problem in parameterized complexity theory [8, 9, 5]. Interestingly even the problem of determining whether EPDI can be solved in time $f_1(d) \cdot |V(G)|^{f_2(d)}$ for *computable* functions $f_1$ and $f_2$ has remained open until now [4]. In this work we settle this latter problem by showing that EPDI can be solved in time $2^{d^{O(d)}} \cdot |V(G)|^{O(d)}$. The problem of determining whether EPDI can be solved in time $f(d) \cdot |V(G)|^{O(1)}$ for some *computable* function $f: \mathbb{N} \to \mathbb{N}$ remains widely open.

**▶ Theorem 1.** There is an algorithm $\mathfrak{A}$ that takes as input, a positive integer $d$, and a plane graph $G^g$, and determines in time $2^{d^{O(d)}} \cdot |V(G)|^{O(d)}$ whether $G^g$ has a plane supergraph $H^h$ of diameter at most $d$.

A graph is 1-outerplanar if it can be embedded in the plane in such a way that every vertex lies in the outer face of the embedding. A graph is *k*-outerplanar if it can be embedded in the plane in such a way that after deleting all vertices in the outer face, the remaining graph is (*k* − 1)-outerplanar. In [4] Cohen et al. have considered the *k*-OUTERPLANAR DIAMETER IMPROVEMENT problem (*k*-OPDI), a variant of the PDI problem in which the target supergraph is required to be *k*-outerplanar instead of planar. In particular, they have shown that the 1-OPDI problem can be solved in polynomial time. The complexity of the *k*-OPDI problem with respect to explicit algorithms was left as an open problem for *k* ≥ 2. By adapting our algorithm for the EPDI problem we are able to show that when the input graph is given together with an embedding that must be preserved, then the resulting problem, the *k*-EOPDI problem, can be solved in time $2^{d^{O(d)}} \cdot |V(G)|^{O(k)}$ for each fixed $k$. In other words, this problem is strongly uniformly fixed parameter tractable with respect to the diameter parameter for each fixed value of outerplanarity.

<footnote n="4">⁴ See Section 2 for formal definitions.</footnote>
# 1 Introduction

In this work, a *plane graph* is a pair $G^g = (G, g)$ consisting of a planar graph $G$ together with a planar embedding $g$ of $G^g$. In the EMBEDDED PLANAR DIAMETER IMPROVEMENT problem (EPDI), we are given a plane graph $G^g$ and a positive integer $d$, and the goal is to determine whether $G^g$ has a plane supergraph $H^h$ of diameter at most $d$. The set of YES instances of EPDI is closed under minors. In other words, if $G^g$ has a plane supergraph of diameter at most $d$, then any minor of $G^g$ also has such a supergraph. Therefore, using non-constructive arguments from Robertson and Seymour's graph minor theory [14, 15] in conjunction with the fact that planar graphs of constant diameter have constant treewidth, one can show that for each fixed $d$, there exists an algorithm $\mathfrak{A}_d$ which determines in linear time whether a given plane graph $G^g$ has a plane supergraph of diameter at most $d$. The caveat is that the non-constructive techniques mentioned above provide us with no clue about what the algorithm $\mathfrak{A}_d$ actually is. This problem can be partially remedied using a technique called effectivization by self-reduction introduced by Fellows and Langston [10, 8]. Using this technique one can show that for some function $f: \mathbb{N} \to \mathbb{N}$, there exists a single algorithm $\mathfrak{A}$ which takes a plane graph $G^g$ and a positive integer $d$ as input, and determines in time $f(d) \cdot |V(G)|^{O(1)}$ whether $G^g$ has a plane supergraph of diameter at most $d$. Nevertheless, the function $f: \mathbb{N} \to \mathbb{N}$ bounding the influence of the parameter $d$ in the running time of the algorithm mentioned above is not known to be computable. The problem of determining whether EPDI admits an algorithm running in time $f(d) \cdot |V(G)|^{O(1)}$ for some *computable* function $f$ is a notorious and long-standing open problem in parameterized complexity theory [8, 9, 5]. Interestingly even the problem of determining whether EPDI can be solved in time $f_1(d) \cdot |V(G)|^{f_2(d)}$ for *computable* functions $f_1$ and $f_2$ has remained open until now [4]. In this work we settle this latter problem by showing that EPDI can be solved in time $2^{d^{O(d)}} \cdot |V(G)|^{O(d)}$. The problem of determining whether EPDI can be solved in time $f(d) \cdot |V(G)|^{O(1)}$ for some *computable* function $f: \mathbb{N} \to \mathbb{N}$ remains widely open.

**▶ Theorem 1.** There is an algorithm $\mathfrak{A}$ that takes as input, a positive integer $d$, and a plane graph $G^g$, and determines in time $2^{d^{O(d)}} \cdot |V(G)|^{O(d)}$ whether $G^g$ has a plane supergraph $H^h$ of diameter at most $d$.

A graph is 1-outerplanar if it can be embedded in the plane in such a way that every vertex lies in the outer face of the embedding. A graph is $k$-outerplanar if it can be embedded in the plane in such a way that after deleting all vertices in the outer face, the remaining graph is $(k-1)$-outerplanar. In [4] Cohen et al. have considered the $k$-OUTERPLANAR DIAMETER IMPROVEMENT problem ($k$-OPDI), a variant of the PDI problem in which the target supergraph is required to be $k$-outerplanar instead of planar. In particular, they have shown that the 1-OPDI problem can be solved in polynomial time. The complexity of the $k$-OPDI problem with respect to explicit algorithms was left as an open problem for $k \ge 2$. By adapting our algorithm for the EPDI problem we are able to show that when the input graph is given together with an embedding that must be preserved, then the resulting problem, the $k$-EOPDI problem, can be solved in time $2^{d^{O(d)}} \cdot |V(G)|^{O(k)}$ for each fixed $k$. In other words, this problem is strongly uniformly fixed parameter tractable with respect to the diameter parameter for each fixed value of outerplanarity.

<footnote n="4">⁴ See Section 2 for formal definitions.</footnote>
**► Theorem 2.** There is an algorithm $\mathfrak{A}$ that takes as input, positive integers $d, k$, and a plane graph $G^g$, and determines in time $2^{d^{O(d)}} \cdot |V(G)|^{O(k)}$ whether $G^g$ has a $k$-outerplanar plane supergraph $H^h$ of diameter at most $d$.

**Related Work.** In the *planar diameter improvement problem* (PDI), the input consists of a planar graph $G$ and a positive integer $d$ and the goal is to determine whether one can add edges to $G$ in such a way that the resulting graph is planar and has diameter at most $d$. Note that the difference between EPDI and PDI is that in the former we are given an embedding that must be preserved, while in the latter no embedding is given at the input. Recently, using automata theoretic techniques, the second author was able to provide strongly uniform FPT and XP algorithms for many graph completion problems where the parameter to be improved is definable in counting monadic second order logic [6]. In particular, when specialized to the PDI problem, the techniques in [6] yield a strongly uniform algorithm that solves PDI in time $f(d) \cdot 2^{O(\Delta \cdot d)} \cdot |V(G)|^{O(d)}$, where $f$ is a computable function and $\Delta$ is the maximum degree of the input graph $G$. Nevertheless, the problem of determining whether PDI admits a strongly uniform algorithm running in time $f_1(d) \cdot |V(G)|^{f_2(d)}$ for computable functions $f_1$ and $f_2$ is still open if no bound is imposed on the degree of the input graph. We note that currently it is not known either whether PDI is reducible to EPDI or whether EPDI is reducible to PDI in XP time. Therefore it is not clear if our algorithm for EPDI can be used to provide a strongly uniform XP algorithm for PDI. It is worth noting that no hardness results for either PDI or EPDI are known. Indeed, determining whether either of these problems is NP-hard is also a long-standing open problem.

While the techniques employed in [6] to tackle the PDI problem on graphs of bounded degree are automata theoretic, the techniques employed in the present work to tackle the EPDI problem on general graphs are based on dynamic programming. In particular, our main algorithm carefully exploits the view of separators in plane graphs as *nooses* - simple closed curves in the plane that touch the graph only in the vertices (see e.g. [2]). The terminology *noose* for such curves comes from the graph minors project of Robertson and Seymour [13]. Our algorithm processes nooses in a way reminiscent of the dynamic programming algorithm of Bouchitte and Todinca over potential maximal cliques [3]. Although this method has found numerous applications in the field of graph algorithms [7, 12, 11], this work is the first which apply these techniques in the context of completion problems.

For each fixed $d$, let $G_d$ be the *subgraph-closure*<fnref n="5" /> of the class of planar graphs of diameter at most $d$. Then clearly a graph $G$ is a yes instance of PDI if and only if $G \in G_d$. When considering the task of constructing strongly uniform algorithms for PDI, two general approaches come to mind. The first follows by observing that graphs in $G_d$ have treewidth at most $O(d)$, and that for each fixed $d \in \mathbb{N}$, $G_d$ is MSO definable. Therefore, one could try to devise an algorithm $\mathfrak{A}$ that takes an integer $d$ as input and constructs an MSO formula $\varphi_d$ defining $G_d$. With such a formula $\varphi_d$ in hands, one could apply Courcelle's model checking theorem to determine whether a given graph $G$ is a yes instance of PDI. The existence of such an algorithm $\mathfrak{A}$ is however an open problem. We note that one can easily define by induction on $d$ an MSO sentence $\phi_d$ which is true on a graph $G$ if and only if $G$ is planar and has diameter at most $d$. Nevertheless, it is not clear how to use $\phi_d$ to construct $\varphi_d$. It is worth noting that there is no algorithm that takes an MSO sentence $\varphi$ as input and constructs a sentence $\varphi'$ defining the subgraph closure of the models of $\varphi$. For instance, let

<footnote n="5">⁵ Note that the class of planar graphs of diameter at most $d$ is closed under contractions but not under subgraphs, since removing edges may increase the diameter.</footnote>
**► Theorem 2.** *There is an algorithm $\mathcal{A}$ that takes as input, positive integers $d, k$, and a plane graph $G^g$, and determines in time $2^{d^{O(d)}} \cdot |V(G)|^{O(k)}$ whether $G^g$ has a k-outerplanar plane supergraph $H^h$ of diameter at most $d$.*

**Related Work.** In the *planar diameter improvement problem* (PDI), the input consists of a planar graph $G$ and a positive integer $d$ and the goal is to determine whether one can add edges to $G$ in such a way that the resulting graph is planar and has diameter at most $d$. Note that the difference between EPDI and PDI is that in the former we are given an embedding that must be preserved, while in the latter no embedding is given at the input. Recently, using automata theoretic techniques, the second author was able to provide strongly uniform FPT and XP algorithms for many graph completion problems where the parameter to be improved is definable in counting monadic second order logic [6]. In particular, when specialized to the PDI problem, the techniques in [6] yield a strongly uniform algorithm that solves PDI in time $f(d) \cdot 2^{O(\Delta \cdot d)} \cdot |V(G)|^{O(d)}$, where $f$ is a computable function and $\Delta$ is the maximum degree of the input graph $G$. Nevertheless, the problem of determining whether PDI admits a strongly uniform algorithm running in time $f_1(d) \cdot |V(G)|^{f_2(d)}$ for computable functions $f_1$ and $f_2$ is still open if no bound is imposed on the degree of the input graph. We note that currently it is not known either whether PDI is reducible to EPDI or whether EPDI is reducible to PDI in XP time. Therefore it is not clear if our algorithm for EPDI can be used to provide a strongly uniform XP algorithm for PDI. It is worth noting that no hardness results for either PDI or EPDI are known. Indeed, determining whether either of these problems is NP-hard is also a long-standing open problem.

While the techniques employed in [6] to tackle the PDI problem on graphs of bounded degree are automata theoretic, the techniques employed in the present work to tackle the EPDI problem on general graphs are based on dynamic programming. In particular, our main algorithm carefully exploits the view of separators in plane graphs as *nooses* - simple closed curves in the plane that touch the graph only in the vertices (see e.g. [2]). The terminology *noose* for such curves comes from the graph minors project of Robertson and Seymour [13]. Our algorithm processes nooses in a way reminiscent of the dynamic programming algorithm of Bouchitte and Todinca over potential maximal cliques [3]. Although this method has found numerous applications in the field of graph algorithms [7, 12, 11], this work is the first which apply these techniques in the context of completion problems.

For each fixed $d$, let $\mathcal{G}_d$ be the *subgraph-closure*<fnref n="5" /> of the class of planar graphs of diameter at most $d$. Then clearly a graph $G$ is a yes instance of PDI if and only if $G \in \mathcal{G}_d$. When considering the task of constructing strongly uniform algorithms for PDI, two general approaches come to mind. The first follows by observing that graphs in $\mathcal{G}_d$ have treewidth at most $O(d)$, and that for each fixed $d \in \mathbb{N}$, $\mathcal{G}_d$ is MSO definable. Therefore, one could try to devise an algorithm $\mathcal{A}$ that takes an integer $d$ as input and constructs an MSO formula $\varphi_d$ defining $\mathcal{G}_d$. With such a formula $\varphi_d$ in hands, one could apply Courcelle's model checking theorem to determine whether a given graph $G$ is a yes instance of PDI. The existence of such an algorithm $\mathcal{A}$ is however an open problem. We note that one can easily define by induction on $d$ an MSO sentence $\phi_d$ which is true on a graph $G$ if and only if $G$ is planar and has diameter at most $d$. Nevertheless, it is not clear how to use $\phi_d$ to construct $\varphi_d$. It is worth noting that there is no algorithm that takes an MSO sentence $\varphi$ as input and constructs a sentence $\varphi'$ defining the subgraph closure of the models of $\varphi$. For instance, let

<footnote n="5">⁵ Note that the class of planar graphs of diameter at most $d$ is closed under contractions but *not* under subgraphs, since removing edges may increase the diameter.</footnote>
$\mathcal{L} = \{L_n\}_{n \in \mathbb{N}}$ be the family of ladder graphs, where $L_n$ is the ladder with $n$ steps. It is easy to see that $\mathcal{L}$ is MSO definable and every graph in $\mathcal{L}$ has treewidth at most 2. Nevertheless, the subgraph closure of $\mathcal{L}$ does not have finite index. Therefore, such subgraph closure is not MSO definable, since Courcelle's theorem implies that MSO-definable families of graphs of bounded treewidth have finite index.

The second approach is based on the fact that for each fixed $d \in \mathbb{N}$, the set of graphs $G_d$ is minor closed. In particular, this implies that the class $G_d$ can be characterized by a finite set $M_d$ of forbidden minors. Therefore, one could try to devise an effective algorithm that takes an integer $d \in \mathbb{N}$ as input and gives as output the list of all forbidden minors in $M_d$. By using the fact that minor-freeness can be tested in time FPT in the size of the minors, such an algorithm $\mathfrak{A}$ would solve PDI in time FPT in $d$. We observe however that the problem of listing the elements of $M_d$ may be much more difficult than the problem of solving PDI in time FPT in $d$. It is worth noting that Adler, Kreutzer and Grohe have shown that if a minor-free graph property $\mathcal{P}$ is MSO definable and has constant treewidth, then one can effectively enumerate the set of forbidden minors for $\mathcal{P}$ [1]. Nevertheless, the problem with this approach is that, as discussed in the previous paragraph, it is not clear how to construct an MSO sentence $\varphi_d$ defining $G_d$.

## 2 Preliminaries

**Graphs.** For each $n \in \mathbb{N}$ we let $[n] = \{1, ..., n\}$. For each finite set $S$ we let $\mathcal{P}(S, 2) = \{\{u, v\} \subseteq S \mid u \neq v\}$ be the set of unordered pairs of elements from $S$. In this work, a graph is a pair $G = (V(G), E(G))$ where $V(G)$ is a finite set of vertices and $E(G) \subseteq \mathcal{P}([n], 2)$ is a set of undirected edges. A path of length $m$ in $G$ is a sequence $p = v_0v_1...v_m$ of distinct vertices where for each $i \in \{0, ..., m-1\}$, $\{v_i, v_{i+1}\} \in E(G)$. We say that $v_0$ and $v_m$ are the endpoints of $p$. The distance $dist(u, v)$ between vertices $u$ and $v$ is defined as the length of the shortest path with endpoints $u$ and $v$. The diameter of $G$, is defined as $d(G) = \max_{u,v} dist(u, v)$.

**Embeddings.** A simple arc in $\mathbb{R}^2$ is a subset $\alpha \subseteq \mathbb{R}^2$ that is a homeomorphic image of the closed real interval $[0, 1]$. We let $endpts(\alpha)$ be the endpoints of $\alpha$, and $Int(\alpha) = \alpha \setminus endpts(\alpha)$ be the interior of $\alpha$. We let $\mathcal{A}$ be the set of simple arcs in $\mathbb{R}^2$. A planar embedding of $G$ is a map $g: V(G) \cup E(G) \to \mathbb{R}^2 \cup \mathcal{A}$ that assigns a point $g(v) \in \mathbb{R}^2$ to each vertex $v \in V(G)$ and a simple arc $g(\{u, v\}) \in \mathcal{A}$ with each edge $\{u, v\}$ in such a way that the following conditions are satisfied.

1. For each $u, v \in V(G)$, $g(u) \neq g(v)$.

2. For each $\{u, v\} \in E(G)$, $g(u), g(v) \in \mathcal{G}$ are the endpoints of the simple arc $g(\{u, v\})$.

3. For each $\{u, v\} \in E(G)$, and each $w \in V(G)$ such that $w \neq u$ and $w \neq v$, $g(w) \notin g(\{u, v\})$.

4. For each $\{u, v\}, \{u', v'\} \in E(G)$, $\mathrm{Int}(g(\{u, v\})) \cap \mathrm{Int}(g(\{u', v'\})) = \emptyset$.

Intuitively, a planar embedding of a graph $G$ is a drawing of $G$ on the plane where each vertex $v$ is represented by a point and each edge $e$ is represented by a non self-intersecting curve that connects the points corresponding to the endpoints of $e$, and no crossings are allowed. A *plane graph* is a pair $G^g = (G, g)$ where $G$ is a graph and $g$ is a planar embedding of $G$. For technical reasons, in this work we assume that the origin $(0,0) \in \mathbb{R}^2$ is distinct from $g(v)$ for each $v \in V(G)$ and does not belong to $g(e)$ for each edge $e \in E(G)$.

**Plane Completion.** Let $G$ and $H$ be graphs. We say that $G$ is a subgraph of $H$ if $V(G) \subseteq V(H)$ and $E(G) \subseteq E(H)$. If $G^g$ and $H^h$ are plane graphs, then we say that $G^g$ is a plane
$\mathcal{L} = \{L_n\}_{n \in \mathbb{N}}$ be the family of ladder graphs, where $L_n$ is the ladder with $n$ steps. It is easy to see that $\mathcal{L}$ is MSO definable and every graph in $\mathcal{L}$ has treewidth at most 2. Nevertheless, the subgraph closure of $\mathcal{L}$ does not have finite index. Therefore, such subgraph closure is not MSO definable, since Courcelle's theorem implies that MSO-definable families of graphs of bounded treewidth have finite index.

The second approach is based on the fact that for each fixed $d \in \mathbb{N}$, the set of graphs $G_d$ is minor closed. In particular, this implies that the class $G_d$ can be characterized by a finite set $M_d$ of forbidden minors. Therefore, one could try to devise an effective algorithm that takes an integer $d \in \mathbb{N}$ as input and gives as output the list of all forbidden minors in $M_d$. By using the fact that minor-freeness can be tested in time FPT in the size of the minors, such an algorithm $\mathfrak{A}$ would solve PDI in time FPT in $d$. We observe however that the problem of listing the elements of $M_d$ may be much more difficult than the problem of solving PDI in time FPT in $d$. It is worth noting that Adler, Kreutzer and Grohe have shown that if a minor-free graph property $\mathcal{P}$ is MSO definable and has constant treewidth, then one can effectively enumerate the set of forbidden minors for $\mathcal{P}$ [1]. Nevertheless, the problem with this approach is that, as discussed in the previous paragraph, it is not clear how to construct an MSO sentence $\varphi_d$ defining $G_d$.

## 2 Preliminaries

**Graphs.** For each $n \in \mathbb{N}$ we let $[n] = \{1, ..., n\}$. For each finite set $S$ we let $\mathcal{P}(S, 2) = \{\{u, v\} \subseteq S \mid u \neq v\}$ be the set of unordered pairs of elements from $S$. In this work, a graph is a pair $G = (V(G), E(G))$ where $V(G)$ is a finite set of vertices and $E(G) \subseteq \mathcal{P}([n], 2)$ is a set of undirected edges. A path of length $m$ in $G$ is a sequence $p = v_0v_1...v_m$ of distinct vertices where for each $i \in \{0, ..., m-1\}$, $\{v_i, v_{i+1}\} \in E(G)$. We say that $v_0$ and $v_m$ are the endpoints of $p$. The distance $dist(u, v)$ between vertices $u$ and $v$ is defined as the length of the shortest path with endpoints $u$ and $v$. The diameter of $G$, is defined as $d(G) = \max_{u,v} dist(u, v)$.

**Embeddings.** A simple arc in $\mathbb{R}^2$ is a subset $\alpha \subseteq \mathbb{R}^2$ that is a homeomorphic image of the closed real interval $[0, 1]$. We let $endpts(\alpha)$ be the endpoints of $\alpha$, and $Int(\alpha) = \alpha \setminus endpts(\alpha)$ be the interior of $\alpha$. We let $\mathcal{A}$ be the set of simple arcs in $\mathbb{R}^2$. A planar embedding of $G$ is a map $g: V(G) \cup E(G) \rightarrow \mathbb{R}^2 \cup \mathcal{A}$ that assigns a point $g(v) \in \mathbb{R}^2$ to each vertex $v \in V(G)$ and a simple arc $g(\{u, v\}) \in \mathcal{A}$ with each edge $\{u, v\}$ in such a way that the following conditions are satisfied.

1. For each $u, v \in V(G)$, $g(u) \neq g(v)$.

2. For each $\{u, v\} \in E(G)$, $g(u), g(v) \in \mathcal{G}$ are the endpoints of the simple arc $g(\{u, v\})$.

3. For each $\{u, v\} \in E(G)$, and each $w \in V(G)$ such that $w \neq u$ and $w \neq v$, $g(w) \notin g(\{u, v\})$.

4. For each $\{u, v\}, \{u', v'\} \in E(G)$, $\mathrm{Int}(g(\{u, v\})) \cap \mathrm{Int}(g(\{u', v'\})) = \emptyset$.

Intuitively, a planar embedding of a graph $G$ is a drawing of $G$ on the plane where each vertex $v$ is represented by a point and each edge $e$ is represented by a non self-intersecting curve that connects the points corresponding to the endpoints of $e$, and no crossings are allowed. A *plane graph* is a pair $G^g = (G, g)$ where $G$ is a graph and $g$ is a planar embedding of $G$. For technical reasons, in this work we assume that the origin $(0,0) \in \mathbb{R}^2$ is distinct from $g(v)$ for each $v \in V(G)$ and does not belong to $g(e)$ for each edge $e \in E(G)$.

**Plane Completion.** Let $G$ and $H$ be graphs. We say that $G$ is a *subgraph* of $H$ if $V(G) \subseteq V(H)$ and $E(G) \subseteq E(H)$. If $G^g$ and $H^h$ are plane graphs, then we say that $G^g$ is a *plane*
<figure><img src="image_126.png" /><figcaption>■ **Figure 1** Left: a plane graph $G$ of diameter 3. Right: a plane completion of $G$ of diameter 2.</figcaption></figure>

subgraph of $H^h$ if $G$ is a subgraph of $H$, $g|_{V(G)} = h|_{V(G)}$ and $g_{E(G)} = h|_{E(G)}$ $^6$. Alternatively, we say that $H^h$ is a *plane completion* of $G^h$ (Figure 1). We say that such a completion $H^h$ is triangulated if each face of $H^h$ has three vertices.

**Combinatorial face.** Let $G^g$ be a plane graph. We say that a point $p \in \mathbb{R}^2$ is *independent* of $G^g$ if $p \neq g(v)$ for every $v \in V(G)$ and $p \notin g(e)$ for every $e \in E(G)$. We say that an independent point $p$ *reaches* a point $p' \in \mathbb{R}^2$ if there is a simple arc $\alpha$ with endpoints $p$ and $p'$ that does not contain any vertex in $g(V)\setminus\{p, p'\}$ and does not intersect the interior of any arc in $g(E)$. If $p$ is an independent point then we let $\mathcal{F}(G^g, p)$ be the subgraph of $G$ whose vertex set is $V(\mathcal{F}(G^g, p)) = \{v \in V(G) \mid p$ reaches $g(v)\}$ and whose edge set is $E(\mathcal{F}(G^g, p)) = \{e \in E(G) \mid p$ reaches each point in $g(e)\}$.

We let $b(p)$ be a boolean value that is 0 if the origin $(0,0)$ is reachable from $p$, and 1 otherwise. We say that a pair $F = (X, b)$, where $X$ is a subgraph of $G$ and $b \in \{0,1\}$, is a *combinatorial face* if there exists a $p \in \mathbb{R}^2$ such that $X = \mathcal{F}(G^g, p)$ and $b = b(p)$. For instance, if $G^g$ is a plane graph where $G$ is a tree, then the unique combinatorial face of $G^g$ is the pair $F = (G, 1)$. On the other hand, if $G$ is a cycle, then $G^g$ has two faces: $F_1 = (G, 0)$ and $F_2 = (G, 1)$. We write $F(G^g)$ to denote the set of all faces of $G^g$. We note that $F(G^g)$ has $O(|V(G)|)$ faces. If $F = (X, b)$ is a combinatorial face, then we define $V(F) = V(X)$ and $E(F) = E(X)$.

We say that two embedded versions $G^g$ and $G^{g'}$ of a graph $G$ are equivalent if $F(G^g) = F(G^{g'})$. We write $G^g \equiv G^{g'}$ to denote that $G^g$ and $G^{g'}$ are equivalent.

## 3 Nooses

► **Definition 3.** Let $G^g$ be a plane graph. A $G^g$-noose is a subset $\eta \subseteq \mathbb{R}^2$ homeomorphic to the unit circle $S_1$ such that $\eta \cap \text{Int}(g(uv)) = \emptyset$ for every edge $uv \in E(G)$.

We note that if $\eta$ is a $G^g$-noose, the intersection $\eta \cap g(V(G))$ may be non-empty. We let $V(\eta) = \{v \in V(G) \mid g(v) \in \eta\}$ be the set of vertices of $G$ whose image lies in the noose $\eta$. The size of $\eta$ is defined as $|\eta| = |V(\eta)|$.

<figure><img src="image_127.png" /><figcaption>■ **Figure 2** Left: a plane graph $G$ and one of its nooses $\eta$. Right: the graph $G_{\eta}^{g_{\eta}}$ that lies in the interior of $\eta$.</figcaption></figure>

<footnote>$^6$ Where $g|_{V(G)}$ and $g|_{E(G)}$ denote the restrictions of $g$ to $V(G)$ and to $E(G)$ respectively.</footnote>
<figure><img src="image_127.png" /><figcaption>■ **Figure 1** Left: a plane graph $G$ of diameter 3. Right: a plane completion of $G$ of diameter 2.</figcaption></figure>

subgraph of $H^h$ if $G$ is a subgraph of $H$, $g|_{V(G)} = h|_{V(G)}$ and $g_{E(G)} = h|_{E(G)}$ $^6$. Alternatively, we say that $H^h$ is a *plane completion* of $G^h$ (Figure 1). We say that such a completion $H^h$ is triangulated if each face of $H^h$ has three vertices.

**Combinatorial face.** Let $G^g$ be a plane graph. We say that a point $p \in \mathbb{R}^2$ is *independent* of $G^g$ if $p \neq g(v)$ for every $v \in V(G)$ and $p \notin g(e)$ for every $e \in E(G)$. We say that an independent point $p$ *reaches* a point $p' \in \mathbb{R}^2$ if there is a simple arc $\alpha$ with endpoints $p$ and $p'$ that does not contain any vertex in $g(V)\setminus\{p, p'\}$ and does not intersect the interior of any arc in $g(E)$. If $p$ is an independent point then we let $\mathcal{F}(G^g, p)$ be the subgraph of $G$ whose vertex set is $V(\mathcal{F}(G^g, p)) = \{v \in V(G) \mid p$ reaches $g(v)\}$ and whose edge set is $E(\mathcal{F}(G^g, p)) = \{e \in E(G) \mid p$ reaches each point in $g(e)\}$.

We let $b(p)$ be a boolean value that is 0 if the origin $(0,0)$ is reachable from $p$, and 1 otherwise. We say that a pair $F = (X, b)$, where $X$ is a subgraph of $G$ and $b \in \{0,1\}$, is a *combinatorial face* if there exists a $p \in \mathbb{R}^2$ such that $X = \mathcal{F}(G^g, p)$ and $b = b(p)$. For instance, if $G^g$ is a plane graph where $G$ is a tree, then the unique combinatorial face of $G^g$ is the pair $F = (G, 1)$. On the other hand, if $G$ is a cycle, then $G^g$ has two faces: $F_1 = (G, 0)$ and $F_2 = (G, 1)$. We write $F(G^g)$ to denote the set of all faces of $G^g$. We note that $F(G^g)$ has $O(|V(G)|)$ faces. If $F = (X, b)$ is a combinatorial face, then we define $V(F) = V(X)$ and $E(F) = E(X)$.

We say that two embedded versions $G^g$ and $G^{g'}$ of a graph $G$ are equivalent if $F(G^g) = F(G^{g'})$. We write $G^g \equiv G^{g'}$ to denote that $G^g$ and $G^{g'}$ are equivalent.

## 3 Nooses

► **Definition 3.** Let $G^g$ be a plane graph. A $G^g$-noose is a subset $\eta \subseteq \mathbb{R}^2$ homeomorphic to the unit circle $S_1$ such that $\eta \cap \text{Int}(g(uv)) = \emptyset$ for every edge $uv \in E(G)$.

We note that if $\eta$ is a $G^g$-noose, the intersection $\eta \cap g(V(G))$ may be non-empty. We let $V(\eta) = \{v \in V(G) \mid g(v) \in \eta\}$ be the set of vertices of $G$ whose image lies in the noose $\eta$. The size of $\eta$ is defined as $|\eta| = |V(\eta)|$.

<figure><img src="image_128.png" /><figcaption>■ **Figure 2** Left: a plane graph $G$ and one of its nooses $\eta$. Right: the graph $G_{\eta}^{g_{\eta}}$ that lies in the interior of $\eta$.</figcaption></figure>

<footnote>$^6$ Where $g|_{V(G)}$ and $g|_{E(G)}$ denote the restrictions of $g$ to $V(G)$ and to $E(G)$ respectively.</footnote>
**Combinatorial cycle.** Let $\Sigma$ be a finite set. We let $\Sigma^k$ be the set of sequences of length $k$ over $\Sigma$. If $a_0a_1...a_{k-1}$ is a sequence in $\Sigma^k$, then we let

$$[a_0a_1...a_{k-1}] = \{a_{j_0}a_{j_1}...a_{j_{k-1}} \mid \exists l \in \{0, ..., k-1\} \forall i \in \{0, ..., k-1\}, j_i = i + l \mod k\}.$$

be the set of all cyclic shifts of the string $a_0a_1...a_{k-1}$. We say that the set $[a_0a_1...a_{k-1}]$ is a *combinatorial cycle* over $\Sigma$.

**Noose Type.** Let $G^g$ be a plane graph and $\Sigma(G) = V(G) \cup F(G)$. A $G^g$-noose type is a cycle $\tau = [v_0F_0v_1F_1...v_{r-1}F_{r-1}]$ over $\Sigma(G)$ where $\{v_0, ..., v_{r-1}\} \subseteq V(G)$, $\{F_0, ..., F_{r-1}\} \subseteq F(G^g)$, and $\{v_i, v_{i+1 \mod r}\} \subseteq V(F_i)$ for each $i \in \{0, 1, ..., r-1\}$. We say that a $G^g$ noose $\eta$ is compatible with $\tau$ if there exist simple arcs $\ell_0, ..., \ell_{r-1}$ satisfying the following properties.

1. $\eta = \bigcup_{i \in \{0, ..., r-1\}} \ell_i$.

2. For each $i \in \{0, ..., r-1\}$, $endpts(\ell_i) = \{g(v_i), g(v_{i+1 \mod r})\}$.

3. For each $i \in \{0, ..., r-1\}$, $\ell_i \cap \ell_{i+1 \mod r} = v_{i+1 \mod r}$.

We say that two $G^g$-nooses $\eta_1$ and $\eta_2$ are equivalent if there exists a $G^g$-noose type $\tau$ such that both $\eta_1$ and $\eta_2$ are compatible with $\tau$. We note that uncountably many $G^g$-nooses may be compatible with a given $G^g$-noose type $\tau$.

<figure><img src="image_128.png" /><figcaption>■ **Figure 3** The type of the noose type $\eta$ is the cycle $[v_1F_2v_3F_1v_6F_1v_4F_3]$. Note that the segment of $\eta$ between $v_1$ and $v_3$ lies in the area delimited by the face $F_2$, the segment between $v_3$ and $v_6$ lies in the area delimited by face $F_1$ and so on.</figcaption></figure>

Let $\gamma$ be a subset of $\mathbb{R}^2$ homeomorphic to the unit circle $S_1$. We say that a point $p \in \mathbb{R}^2$ belongs to the closed interior of $\gamma$ if $\alpha \cap \gamma \neq \emptyset$ for every simple arc $\alpha$ with $endpts(\alpha) = \{(0, 0), p\}$. We let $\hat{\gamma}$ be the set of points in the closed interior of $\gamma$. If $G^g = (G, g)$ is a plane graph and $\eta$ is a $G^g$-noose, then we let $G_{\eta}^{g\eta} = (G_{\eta}, g_{\eta})$ be the plane graph where

1. $V(G_{\eta}) = \{v \in V(G) \mid g(v) \in \hat{\eta}\}$,

2. $E(G_{\eta}) = \{uv \in E(G) \mid g(uv) \subset \hat{\eta}\}$,

3. $g_{\eta}: V(G_{\eta}) \cup E(G_{\eta}) \to \mathbb{R}_2 \cup A$ with $g_{\eta}|_{V(G_{\eta})} = g|_{V(G_{\eta})}$ and $g_{\eta}|_{E(G_{\eta})} = g|_{E(G_{\eta})}$.

Intuitively, the graph $G_{\eta}^{g\eta}$ is the plane subgraph of $G^g$ that lies in the closed interior of $\eta$.

► **Observation 1.** Let $G^g$ be a plane graph and $\eta_1$ and $\eta_2$ be equivalent $G^g$-nooses. Then $G_{\eta_1}^{g\eta_1} = G_{\eta_2}^{g\eta_2}$.

► **Definition 4.** Let $G^g$ be a plane graph and $\tau$ be a $G^g$-noose type. We say that a plane completion $H^h$ of $G^g$ is $\tau$-respecting if there is a $G^g$-noose $\eta$ of type $\tau$ which is also a $H^h$-noose.

We note that in Definition 4, although the $G^g$-noose type of $\eta$ is $\tau$, the $H^h$-noose type of $\eta$ is not necessarily $\tau$ since $H^h$ may have more faces than $G^g$.
**Combinatorial cycle.** Let $\Sigma$ be a finite set. We let $\Sigma^k$ be the set of sequences of length $k$ over $\Sigma$. If $a_0a_1...a_{k-1}$ is a sequence in $\Sigma^k$, then we let

$$[a_0a_1...a_{k-1}] = \{a_{j_0}a_{j_1}...a_{j_{k-1}} \mid \exists l \in \{0, ..., k-1\} \forall i \in \{0, ..., k-1\}, j_i = i + l \mod k\}.$$

be the set of all cyclic shifts of the string $a_0a_1...a_{k-1}$. We say that the set $[a_0a_1...a_{k-1}]$ is a *combinatorial cycle* over $\Sigma$.

**Noose Type.** Let $G^g$ be a plane graph and $\Sigma(G) = V(G) \cup F(G)$. A $G^g$-noose type is a cycle $\tau = [v_0F_0v_1F_1...v_{r-1}F_{r-1}]$ over $\Sigma(G)$ where $\{v_0, ..., v_{r-1}\} \subseteq V(G)$, $\{F_0, ..., F_{r-1}\} \subseteq F(G^g)$, and $\{v_i, v_{i+1 \mod r}\} \subseteq V(F_i)$ for each $i \in \{0, 1, ..., r-1\}$. We say that a $G^g$ noose $\eta$ is compatible with $\tau$ if there exist simple arcs $\ell_0, ..., \ell_{r-1}$ satisfying the following properties.

1. $\eta = \bigcup_{i \in \{0, ..., r-1\}} \ell_i$.

2. For each $i \in \{0, ..., r-1\}$, $endpts(\ell_i) = \{g(v_i), g(v_{i+1 \mod r})\}$.

3. For each $i \in \{0, ..., r-1\}$, $\ell_i \cap \ell_{i+1 \mod r} = v_{i+1 \mod r}$.

We say that two $G^g$-nooses $\eta_1$ and $\eta_2$ are equivalent if there exists a $G^g$-noose type $\tau$ such that both $\eta_1$ and $\eta_2$ are compatible with $\tau$. We note that uncountably many $G^g$-nooses may be compatible with a given $G^g$-noose type $\tau$.

<figure><img src="image_129.png" /><figcaption>■ **Figure 3** The type of the noose type $\eta$ is the cycle $[v_1F_2v_3F_1v_6F_1v_4F_3]$. Note that the segment of $\eta$ between $v_1$ and $v_3$ lies in the area delimited by the face $F_2$, the segment between $v_3$ and $v_6$ lies in the area delimited by face $F_1$ and so on.</figcaption></figure>

Let $\gamma$ be a subset of $\mathbb{R}^2$ homeomorphic to the unit circle $S_1$. We say that a point $p \in \mathbb{R}^2$ belongs to the closed interior of $\gamma$ if $\alpha \cap \gamma \neq \emptyset$ for every simple arc $\alpha$ with $endpts(\alpha) = \{(0, 0), p\}$. We let $\hat{\gamma}$ be the set of points in the closed interior of $\gamma$. If $G^g = (G, g)$ is a plane graph and $\eta$ is a $G^g$-noose, then we let $G_{\eta}^{g\eta} = (G_{\eta}, g_{\eta})$ be the plane graph where

1. $V(G_{\eta}) = \{v \in V(G) \mid g(v) \in \hat{\eta}\}$,

2. $E(G_{\eta}) = \{uv \in E(G) \mid g(uv) \subset \hat{\eta}\}$,

3. $g_{\eta}: V(G_{\eta}) \cup E(G_{\eta}) \to \mathbb{R}_2 \cup A$ with $g_{\eta}|_{V(G_{\eta})} = g|_{V(G_{\eta})}$ and $g_{\eta}|_{E(G_{\eta})} = g|_{E(G_{\eta})}$.

Intuitively, the graph $G_{\eta}^{g\eta}$ is the plane subgraph of $G^g$ that lies in the closed interior of $\eta$.

► **Observation 1.** Let $G^g$ be a plane graph and $\eta_1$ and $\eta_2$ be equivalent $G^g$-nooses. Then $G_{\eta_1}^{g\eta_1} = G_{\eta_2}^{g\eta_2}$.

► **Definition 4.** Let $G^g$ be a plane graph and $\tau$ be a $G^g$-noose type. We say that a plane completion $H^h$ of $G^g$ is $\tau$-respecting if there is a $G^g$-noose $\eta$ of type $\tau$ which is also a $H^h$-noose.

We note that in Definition 4, although the $G^g$-noose type of $\eta$ is $\tau$, the $H^h$-noose type of $\eta$ is not necessarily $\tau$ since $H^h$ may have more faces than $G^g$.
# 4 Representative Sets

Let $G^g$ be a plane graph and $\eta$ be a $G^g$-noose. We say that a plane completion $H^h$ of $G^g$ is $\eta$-respecting if $\eta$ is also an $H^h$-noose. We say that a plane graph $X^x$ is a $(G^g, \eta)$-completion if the following conditions are satisfied.

1. $\eta$ is a $X^x$-noose.

2. $X^x = X_{\eta}^{x_{\eta}}$.

3. $X^x$ is a plane completion of $G_{\eta}^{g_{\eta}}$.

Intuitively, a $(G^h, \eta)$-completion is a plane completion $X^x$ of $G_{\eta}^{h_{\eta}}$ where all vertices and edges are drawn inside $\eta$.

**Proposition 1.** If $H^h$ is an $\eta$-respecting plane completion of $G^g$, then $H_{\eta}^{g_{\eta}}$ is a $(G^g, \eta)$-completion.

If $G^g$ is a plane graph and $H^h$ is a plane subgraph of $G^g$ then we let $G^g - H^h$ be the plane graph $Y^y$ where $V(Y) = V(G)$, $E(Y) = E(G) \setminus E(H)$ and $y = g|_{V(Y)}$. In other words, $G^g - H^h$ is the graph obtained by deleting from $G$ the edges which are shared with $H$. On the other hand, let $G^g$ and $H^h$ be plane graphs such that $V(H) \subseteq V(G)$, $\text{Int}(h(e)) \cap g(e') = \emptyset$ for every $e \in E(H) \setminus E(G)$ and every $e' \in E(G)$, and such that $h(e) = g(e)$ for every $e \in E(G) \cap E(H)$. We let $G^g + H^h$ be the plane graph $Y^y$ with vertex set $V(Y) = V(G)$, edge set $E(Y) = E(G) \cup E(H)$, and embedding $y$ such that $y|_{V(G)} = g|_{V(G)}$, $y|_{E(G)} = g|_{E(G)}$ and $y|_{E(H) \setminus E(G)} = h|_{E(H) \setminus E(G)}$. In other words, $G^g + H^h$ is the graph obtained by adding all edges in $E(H) \setminus E(G)$ to $G$ and by drawing these edges in the plane according to $h$.

We say that $H^h$ is a $\eta$-respecting diameter-$d$ plane completion of $G^g$ if $H^h$ is a $\eta$-respecting plane completion of $G^g$ of diameter at most $d$.

**Definition 5.** Let $G^g$ be a plane graph and $\eta$ be a $G^g$-noose. Let $A$ and $B$ be sets of $(G^g, \eta)$-completions. We say that $A$ represents $B$ if for every diameter-$d$ $\eta$-respecting plane completion $H^h$ of $G^g$, such that $H_{\eta}^{h_{\eta}} \in B$, there exists some $X^x \in A$ such that $(H^h - H_{\eta}^{h_{\eta}}) + X^x$ is also a diameter-$d$ plane completion of $G^g$.

Let $G^g$ be a plane graph and $\eta$ be a $G^g$-noose. We let $V(\eta) = \{v \in V(G) | g(v) \in \eta\}$ be the set of vertices of $G$ whose image under $g$ lies on $\eta$, and $\hat{V}(\eta)$ be the set of vertices of $G$ that lie in the closed interior of $\eta$.

Let $X^x$ be a $(G^g, \eta)$-completion. The truncated distance between any two vertices $v, v'$ of $\hat{V}(\eta)$, denoted by $d(X^x, v, v')$ is defined as the distance between $v$ and $v'$ in $X^x$ if this distance is at most $d$, and $\infty$ otherwise. We let $D(X^x) = [d(X^x, v, v')]_{v,v' \in V(\eta)}$, be the matrix of truncated distances between any two vertices in $V(\eta)$. For any vertex $v$ in $\hat{V}(\eta)$, we let $D(X^x, v) = [d(X^x, v, v')]_{v' \in V(\eta)}$ be the vector of distances between $v$ and the vertices whose image lie in the noose $\eta$. We say that two vertices $u$ and $u'$ in $\hat{V}(\eta)$ are unresolved if their distance in $X^x$ is greater than $d$. For each pair of unresolved vertices we let $D(X^x, u, u') = (D(X^x, u), D(X^x, u'))$ be the pair of distance vectors from $u$ to $V(\eta)$ and from $u'$ to $V(\eta)$ respectively. We let

$$ \mathbb{D}(X^x) = \{D(X^x, u, u') | (u, u') \text{ is an unresolved pair}\}. $$

The signature of $X^x$ is defined as follows.

$$ S(X^x) = (D(X^x), \mathbb{D}(X^x)). \qquad (1) $$

**Proposition 2.** Let $|V(\eta)| \le 8d$. Then there exist at most $2^{dO(d)}$ distinct signatures.
## 4 Representative Sets

Let $G^g$ be a plane graph and $\eta$ be a $G^g$-noose. We say that a plane completion $H^h$ of $G^g$ is $\eta$-respecting if $\eta$ is also an $H^h$-noose. We say that a plane graph $X^x$ is a $(G^g, \eta)$-completion if the following conditions are satisfied.

1. $\eta$ is a $X^x$-noose.

2. $X^x = X_{\eta}^{x_{\eta}}$.

3. $X^x$ is a plane completion of $G_{\eta}^{g_{\eta}}$.

Intuitively, a $(G^h, \eta)$-completion is a plane completion $X^x$ of $G_{\eta}^{h_{\eta}}$ where all vertices and edges are drawn inside $\eta$.

**Proposition 1.** If $H^h$ is an $\eta$-respecting plane completion of $G^g$, then $H_{\eta}^{g_{\eta}}$ is a $(G^g, \eta)$-completion.

If $G^g$ is a plane graph and $H^h$ is a plane subgraph of $G^g$ then we let $G^g - H^h$ be the plane graph $Y^y$ where $V(Y) = V(G)$, $E(Y) = E(G) \setminus E(H)$ and $y = g|_{V(Y)}$. In other words, $G^g - H^h$ is the graph obtained by deleting from $G$ the edges which are shared with $H$. On the other hand, let $G^g$ and $H^h$ be plane graphs such that $V(H) \subseteq V(G)$, $\mathrm{Int}(h(e)) \cap g(e') = \emptyset$ for every $e \in E(H) \setminus E(G)$ and every $e' \in E(G)$, and such that $h(e) = g(e)$ for every $e \in E(G) \cap E(H)$. We let $G^g + H^h$ be the plane graph $Y^y$ with vertex set $V(Y) = V(G)$, edge set $E(Y) = E(G) \cup E(H)$, and embedding $y$ such that $y|_{V(G)} = g|_{V(G)}$, $y|_{E(G)} = g|_{E(G)}$ and $y|_{E(H) \setminus E(G)} = h|_{E(H) \setminus E(G)}$. In other words, $G^g + H^h$ is the graph obtained by adding all edges in $E(H) \setminus E(G)$ to $G$ and by drawing these edges in the plane according to $h$.

We say that $H^h$ is a $\eta$-respecting diameter-$d$ plane completion of $G^g$ if $H^h$ is a $\eta$-respecting plane completion of $G^g$ of diameter at most $d$.

**Definition 5.** Let $G^g$ be a plane graph and $\eta$ be a $G^g$-noose. Let $A$ and $B$ be sets of $(G^g, \eta)$-completions. We say that $A$ represents $B$ if for every diameter-$d$ $\eta$-respecting plane completion $H^h$ of $G^g$, such that $H_{\eta}^{h_{\eta}} \in B$, there exists some $X^x \in A$ such that $(H^h - H_{\eta}^{h_{\eta}}) + X^x$ is also a diameter-$d$ plane completion of $G^g$.

Let $G^g$ be a plane graph and $\eta$ be a $G^g$-noose. We let $V(\eta) = \{v \in V(G) | g(v) \in \eta\}$ be the set of vertices of $G$ whose image under $g$ lies on $\eta$, and $\hat{V}(\eta)$ be the set of vertices of $G$ that lie in the closed interior of $\eta$.

Let $X^x$ be a $(G^g, \eta)$-completion. The truncated distance between any two vertices $v, v'$ of $\hat{V}(\eta)$, denoted by $d(X^x, v, v')$ is defined as the distance between $v$ and $v'$ in $X^x$ if this distance is at most $d$, and $\infty$ otherwise. We let $D(X^x) = [d(X^x, v, v')]_{v,v' \in V(\eta)}$, be the matrix of truncated distances between any two vertices in $V(\eta)$. For any vertex $v$ in $\hat{V}(\eta)$, we let $D(X^x, v) = [d(X^x, v, v')]_{v' \in V(\eta)}$ be the vector of distances between $v$ and the vertices whose image lie in the noose $\eta$. We say that two vertices $u$ and $u'$ in $\hat{V}(\eta)$ are unresolved if their distance in $X^x$ is greater than $d$. For each pair of unresolved vertices we let $D(X^x, u, u') = (D(X^x, u), D(X^x, u'))$ be the pair of distance vectors from $u$ to $V(\eta)$ and from $u'$ to $V(\eta)$ respectively. We let

$$ \mathbb{D}(X^x) = \{D(X^x, u, u') | (u, u') \text{ is an unresolved pair}\}. $$

The signature of $X^x$ is defined as follows.

$$ S(X^x) = (D(X^x), \mathbb{D}(X^x)). \qquad (1) $$

**Proposition 2.** Let $|V(\eta)| \le 8d$. Then there exist at most $2^{d^O(d)}$ distinct signatures.
**Lemma 6.** Let $H^h$ be a plane completion of $G^g$ of diameter at most $d$ and let $X^x$ be a $(G^g, \eta)$-completion such that $S(H_{\eta}^{h_{\eta}}, \eta) = S(X^x, \eta)$. Then if $H^g$ has diameter at most $d$, $(H^h - H_{\eta}^{h_{\eta}}) + X^x$ has diameter at most $d$.

**Lemma 7.** Let $G^g$ be a plane graph, $\eta$ be a $G^g$-noose and $B$ be a set of $(G^g, \tau)$-completions. Then one can construct in time $2^{d^{O(d)}} \cdot |B|$ a set $\text{Trunc}(B)$ of $(G^g, h)$-completions such that $|\text{Trunc}(B)| \le d^{O(d)}$ and $\text{Trunc}(B)$ represents $B$.

**Proof.** Let $B$ be a set of $(G^g, \eta)$ completions. For each signature $S$, let $B(S)$ be the set of all graphs $H^h$ in $B$ with $S(H^h, \eta) = S$. Finally, let $\text{Trunc}(B)$ be the set obtained by selecting a unique graph $H_S^h$ from set $B(S)$ whenever $B(S)$ is non-empty. Then by Lemma 6, $\text{Trunc}(B)$ represents $B$. ▼

**5 Algorithm for Embedded Planar Diameter Improvement**

In this section we will devise an algorithm that takes a plane graph $G^g$ and a positive integer $d$ as input and determines in time $|V(G)|^{O(d)}$ whether $G^g$ has a diameter-$d$ plane completion $H^h$. In the remainder of this section we assume that the input plane graph $G^g$ and the input positive integer $d$ are fixed.

**Definition 8.** Let $\eta$ be a $G^g$-noose. We define the following set.

$$ \mathcal{F}_{\eta} = \{H_{\eta}^{h_{\eta}} | H^h \text{ is a diameter-}d \text{ plane completion of } G^g\}. $$

Intuitively, $\mathcal{F}_{\eta}$ is the set of all plane completions of the graph $G_{\eta}^{g_{\eta}}$ that can be extended to some diameter-$d$ plane completion of the graph $G^g$. For each $G^g$-noose $\eta$ we will define a family $\tilde{\mathcal{F}}_{\eta} \subseteq \mathcal{F}_{\eta}$ of $(G^g, \eta)$-completions such that $\tilde{\mathcal{F}}_{\eta}$ represents $\mathcal{F}_{\eta}$ and $|\tilde{\mathcal{F}}_{\eta}| \le 2^{d^{O(d)}}$.

We will define a partial order on nooses as follows. First, for each noose $\eta$, we consider the following triple.

$$ \phi(\eta) = [|V(G_{\eta}^{g_{\eta}})|, |E(G_{\eta}^{g_{\eta}})|, -|\eta|]. $$

We set $\eta < \eta'$ if and only if $\phi(\eta) < \phi(\eta')$. In other words, a noose $\eta$ is smaller than a noose $\eta'$ if the closed interior of $\eta$ has less vertices than the closed interior of $\eta'$, or if these interiors have the same number of vertices, but the first has less edges, or if both interiors have the same number of edges and vertices and the first noose has more vertices than the latter noose. Note that there is an inversion in the third coordinate, since the larger the noose-size, the lesser is the order.

We will compute $\tilde{\mathcal{F}}_{\eta}$ under the assumption that $\tilde{\mathcal{F}}_{\eta'}$ has been computed for every $\eta'$ such that $\phi(\eta') < \phi(\eta)$. There are three cases to be considered. In all cases the size of the involved nooses will be at most $8d$. In the first case, assuming that the size of $\eta$ is at most $8d$, we will show how to compute $\tilde{\mathcal{F}}_{\eta}$ under the assumption that $\tilde{\mathcal{F}}_{\eta'}$ has been computed for every noose $\eta'$ whose closed interior has fewer edges than the one of $\eta$. The second case concerns nooses of size strictly less than $8d$. In this case, we will show how to compute $\tilde{\mathcal{F}}_{\eta}$ assuming that we have computed $\tilde{\mathcal{F}}_{\eta'}$ for every noose $\eta'$ of size $|\eta| + 1$ whose closed interior is identical to the one of $\eta$. Note that due to the negative sign in the definition of $\phi(\eta)$, if two nooses $\eta$ and $\eta'$ have identical closed interior and $|\eta'| > |\eta|$, then $\phi(\eta') < \phi(\eta)$. Finally, the most important case is the third, in which nooses have size exactly $8d$. In this case we show how to compute $\tilde{\mathcal{F}}_{\eta}$ assuming we have computed $\tilde{\mathcal{F}}_{\eta'}$ for every noose of size $8d$ whose closed interior is strictly contained in the closed interior of $\eta$. We note that we only need to consider one noose $\eta_{\tau}$ for each noose-type $\tau$. Therefore, the number of nooses to be considered will be upper bounded by $n^{O(d)}$.
**Lemma 6.** Let $H^h$ be a plane completion of $G^g$ of diameter at most $d$ and let $X^x$ be a $(G^g, \eta)$-completion such that $S(H_{\eta}^{h_{\eta}}, \eta) = S(X^x, \eta)$. Then if $H^g$ has diameter at most $d$, $(H^h - H_{\eta}^{h_{\eta}}) + X^x$ has diameter at most $d$.

**Lemma 7.** Let $G^g$ be a plane graph, $\eta$ be a $G^g$-noose and $B$ be a set of $(G^g, \tau)$-completions. Then one can construct in time $2^{d^{O(d)}} \cdot |B|$ a set $\text{Trunc}(B)$ of $(G^g, h)$-completions such that $|\text{Trunc}(B)| \le d^{O(d)}$ and $\text{Trunc}(B)$ represents $B$.

**Proof.** Let $B$ be a set of $(G^g, \eta)$ completions. For each signature $S$, let $B(S)$ be the set of all graphs $H^h$ in $B$ with $S(H^h, \eta) = S$. Finally, let $\text{Trunc}(B)$ be the set obtained by selecting a unique graph $H_S^h$ from set $B(S)$ whenever $B(S)$ is non-empty. Then by Lemma 6, $\text{Trunc}(B)$ represents $B$. ▼

**5 Algorithm for Embedded Planar Diameter Improvement**

In this section we will devise an algorithm that takes a plane graph $G^g$ and a positive integer $d$ as input and determines in time $|V(G)|^{O(d)}$ whether $G^g$ has a diameter-$d$ plane completion $H^h$. In the remainder of this section we assume that the input plane graph $G^g$ and the input positive integer $d$ are fixed.

**Definition 8.** Let $\eta$ be a $G^g$-noose. We define the following set.

$$ \mathcal{F}_{\eta} = \{H_{\eta}^{h_{\eta}} | H^h \text{ is a diameter-}d \text{ plane completion of } G^g\}. $$

Intuitively, $\mathcal{F}_{\eta}$ is the set of all plane completions of the graph $G_{\eta}^{g_{\eta}}$ that can be extended to some diameter-$d$ plane completion of the graph $G^g$. For each $G^g$-noose $\eta$ we will define a family $\tilde{\mathcal{F}}_{\eta} \subseteq \mathcal{F}_{\eta}$ of $(G^g, \eta)$-completions such that $\tilde{\mathcal{F}}_{\eta}$ represents $\mathcal{F}_{\eta}$ and $|\tilde{\mathcal{F}}_{\eta}| \le 2^{d^{O(d)}}$.

We will define a partial order on nooses as follows. First, for each noose $\eta$, we consider the following triple.

$$ \phi(\eta) = [|V(G_{\eta}^{g_{\eta}})|, |E(G_{\eta}^{g_{\eta}})|, -|\eta|]. $$

We set $\eta < \eta'$ if and only if $\phi(\eta) < \phi(\eta')$. In other words, a noose $\eta$ is smaller than a noose $\eta'$ if the closed interior of $\eta$ has less vertices than the closed interior of $\eta'$, or if these interiors have the same number of vertices, but the first has less edges, or if both interiors have the same number of edges and vertices and the first noose has more vertices than the latter noose. Note that there is an inversion in the third coordinate, since the larger the noose-size, the lesser is the order.

We will compute $\tilde{\mathcal{F}}_{\eta}$ under the assumption that $\tilde{\mathcal{F}}_{\eta'}$ has been computed for every $\eta'$ such that $\phi(\eta') < \phi(\eta)$. There are three cases to be considered. In all cases the size of the involved nooses will be at most $8d$. In the first case, assuming that the size of $\eta$ is at most $8d$, we will show how to compute $\tilde{\mathcal{F}}_{\eta}$ under the assumption that $\tilde{\mathcal{F}}_{\eta'}$ has been computed for every noose $\eta'$ whose closed interior has fewer edges than the one of $\eta$. The second case concerns nooses of size strictly less than $8d$. In this case, we will show how to compute $\tilde{\mathcal{F}}_{\eta}$ assuming that we have computed $\tilde{\mathcal{F}}_{\eta'}$ for every noose $\eta'$ of size $|\eta| + 1$ whose closed interior is identical to the one of $\eta$. Note that due to the negative sign in the definition of $\phi(\eta)$, if two nooses $\eta$ and $\eta'$ have identical closed interior and $|\eta'| > |\eta|$, then $\phi(\eta') < \phi(\eta)$. Finally, the most important case is the third, in which nooses have size exactly $8d$. In this case we show how to compute $\tilde{\mathcal{F}}_{\eta}$ assuming we have computed $\tilde{\mathcal{F}}_{\eta'}$ for every noose of size $8d$ whose closed interior is strictly contained in the closed interior of $\eta$. We note that we only need to consider one noose $\eta_{\tau}$ for each noose-type $\tau$. Therefore, the number of nooses to be considered will be upper bounded by $n^{O(d)}$.
**Case One.** Let $G^g$ be a plane graph and $\eta$ be a $G^g$-noose with $|\eta| < 8d$. We say that an edge $uv \in E(G)$ is parallel to $\eta$ if there exists a simple arc $\ell \in \mathcal{A}$ such that the following conditions are satisfied.

1. $\ell \subseteq \eta$.

2. endpts($\ell$) = {$g(u), g(v)$}.

3. Let $\alpha = \ell \cup g(uv)$ and let $\hat{\alpha}$ be the closed interior of $\alpha$.

a. $\hat{\alpha} \cap g(V(G)) = \{g(u), g(v)\}$.

b. $\hat{\alpha} \cap g(u'v') \subseteq \{g(u), g(v)\}$ for each $u'v' \in E(G)$.

In other words, $uv$ is parallel to $\eta$ if there is a simple arc $\ell \subset \eta$ with endpoints $\{g(u), g(v)\}$ such that the closed interior of the curve $\ell \cup g(uv)$ only intersects the drawing of $G$ in the points of $g(u, v)$ (Figure 4).

We say that an edge $uv \in E(G)$ is *internally* (resp. *externally*) parallel to $\eta$ if $uv$ is parallel to $\eta$ and $g(uv) \subset \hat{\eta}$ (resp. $g(uv) \cap \hat{\eta} = \{g(u), g(v)\}$). We note that if an edge $uv$ is parallel to $\eta$, then $uv$ is either internally or externally parallel to $\eta$. Let $G^g$ be a plane graph and $uv \in E(G)$. We let $G^g - uv$ be the plane graph which is obtained by deleting the edge $uv$ from $E(G)$ and by restricting the mapping $g$ to the remaining edges.

**Proposition 3.** Let $\eta$ be a $G^g$-noose, and let $uv$ be an edge in $E(G)$ such that $uv$ is internally parallel to $\eta$. Then there exists a $G^g$-noose $\eta'$ such that $V(\eta) = V(\eta')$, $uv$ is externally parallel to $\eta'$ and $G_{\eta'}^{g\eta'} = G_{\eta}^{g\eta} - uv$. (See Figure 4).

<figure><img src="image_129.png" /><figcaption>Figure 4 The edge $uv$ is internally parallel to $\eta$ and externally parallel to $\eta'$. Note that the graph $G_{\eta'}^{g\eta'}$ is equal to the graph $G_{\eta}^{g\eta}$ minus the edge $uv$. Intuitively, the noose $\eta'$ is obtained from $\eta$ by deleting the arc $\ell$ and by gluing the arc $\ell'$ in its place.</figcaption></figure>

**Lemma 9.** Let $uv$ be an edge in $E(G)$, and let $\eta$ be a $G^g$-noose such that $uv$ is internally parallel to $\eta$. Let $\eta'$ be a $G^g$-noose such that $V(\eta) = V(\eta')$, $G_{\eta'}^{g\eta'} = G_{\eta}^{g\eta} - uv$ and $uv$ is externally parallel to $\eta'$. Note that such a noose $\eta'$ exists by Proposition 3. Suppose that $X^x \in \mathcal{F}_{\eta}$. Then there exists $Y^y \in \mathcal{F}_{\eta'}$ such that $Y^y = X^x - uv$.

Let $Y^y$ be a $(G^g, \eta)$-completion and $uv$ be an edge in $E(G) \setminus E(Y)$ such that $u, v \in V(\eta)$. We let $Y^y + uv$ be the plane graph $X^x$ where $V(X) = V(Y)$, $E(X) = E(Y)$, $x|_{V(G) \cup E(G)} = y$ and $x(uv) = g(uv)$.

**Lemma 10.** Let $uv$ be an edge in $E(G)$, and let $\eta$ and $\eta'$ be $G^g$-nooses such that $V(\eta) = V(\eta')$ and $G_{\eta}^{g} = G_{\eta'}^{g} + uv$. Assume that $\tilde{\mathcal{F}}_{\eta'}$ represents $\mathcal{F}_{\eta'}$. Then $\tilde{\mathcal{F}}_{\eta} = \tilde{\mathcal{F}}_{\eta'} + uv$ represents $\mathcal{F}_{\eta}$.

**Case Two.** Let $k < 8d$ and let $\eta$ be a $G^g$-noose of type $\tau = [v_0F_0v_1F_1\dots v_{k-1}F_{k-1}]$. A trivial extension of $\eta$ is a noose $G^g$-noose $\eta'$ of type

$$ \tau = [v_0F_0v_1F_1\dots v_jF_juF_jv_{j+1}\dots v_{k-1}F_{k-1}] $$
**Case One.** Let $G^g$ be a plane graph and $\eta$ be a $G^g$-noose with $|\eta| < 8d$. We say that an edge $uv \in E(G)$ is parallel to $\eta$ if there exists a simple arc $\ell \in \mathcal{A}$ such that the following conditions are satisfied.

1. $\ell \subseteq \eta$.

2. endpts($\ell$) = {$g(u), g(v)$}.

3. Let $\alpha = \ell \cup g(uv)$ and let $\hat{\alpha}$ be the closed interior of $\alpha$.

a. $\hat{\alpha} \cap g(V(G)) = \{g(u), g(v)\}$.

b. $\hat{\alpha} \cap g(u'v') \subseteq \{g(u), g(v)\}$ for each $u'v' \in E(G)$.

In other words, $uv$ is parallel to $\eta$ if there is a simple arc $\ell \subset \eta$ with endpoints $\{g(u), g(v)\}$ such that the closed interior of the curve $\ell \cup g(uv)$ only intersects the drawing of $G$ in the points of $g(u, v)$ (Figure 4).

We say that an edge $uv \in E(G)$ is *internally* (resp. *externally*) parallel to $\eta$ if $uv$ is parallel to $\eta$ and $g(uv) \subset \hat{\eta}$ (resp. $g(uv) \cap \hat{\eta} = \{g(u), g(v)\}$). We note that if an edge $uv$ is parallel to $\eta$, then $uv$ is either internally or externally parallel to $\eta$. Let $G^g$ be a plane graph and $uv \in E(G)$. We let $G^g - uv$ be the plane graph which is obtained by deleting the edge $uv$ from $E(G)$ and by restricting the mapping $g$ to the remaining edges.

**Proposition 3.** Let $\eta$ be a $G^g$-noose, and let $uv$ be an edge in $E(G)$ such that $uv$ is internally parallel to $\eta$. Then there exists a $G^g$-noose $\eta'$ such that $V(\eta) = V(\eta')$, $uv$ is externally parallel to $\eta'$ and $G_{\eta'}^{g\eta'} = G_{\eta}^{g\eta} - uv$. (See Figure 4).

<figure><img src="image_130.png" /><figcaption>Figure 4 The edge $uv$ is internally parallel to $\eta$ and externally parallel to $\eta'$. Note that the graph $G_{\eta'}^{g\eta'}$ is equal to the graph $G_{\eta}^{g\eta}$ minus the edge $uv$. Intuitively, the noose $\eta'$ is obtained from $\eta$ by deleting the arc $\ell$ and by gluing the arc $\ell'$ in its place.</figcaption></figure>

**Lemma 9.** Let $uv$ be an edge in $E(G)$, and let $\eta$ be a $G^g$-noose such that $uv$ is internally parallel to $\eta$. Let $\eta'$ be a $G^g$-noose such that $V(\eta) = V(\eta')$, $G_{\eta'}^{g\eta'} = G_{\eta}^{g\eta} - uv$ and $uv$ is externally parallel to $\eta'$. Note that such a noose $\eta'$ exists by Proposition 3. Suppose that $X^x \in \mathcal{F}_{\eta}$. Then there exists $Y^y \in \mathcal{F}_{\eta'}$ such that $Y^y = X^x - uv$.

Let $Y^y$ be a $(G^g, \eta)$-completion and $uv$ be an edge in $E(G) \setminus E(Y)$ such that $u, v \in V(\eta)$. We let $Y^y + uv$ be the plane graph $X^x$ where $V(X) = V(Y)$, $E(X) = E(Y)$, $x|_{V(G) \cup E(G)} = y$ and $x(uv) = g(uv)$.

**Lemma 10.** Let $uv$ be an edge in $E(G)$, and let $\eta$ and $\eta'$ be $G^g$-nooses such that $V(\eta) = V(\eta')$ and $G_{\eta}^{g} = G_{\eta'}^{g} + uv$. Assume that $\tilde{\mathcal{F}}_{\eta'}$ represents $\mathcal{F}_{\eta'}$. Then $\tilde{\mathcal{F}}_{\eta} = \tilde{\mathcal{F}}_{\eta'} + uv$ represents $\mathcal{F}_{\eta}$.

**Case Two.** Let $k < 8d$ and let $\eta$ be a $G^g$-noose of type $\tau = [v_0F_0v_1F_1\dots v_{k-1}F_{k-1}]$. A trivial extension of $\eta$ is a noose $G^g$-noose $\eta'$ of type

$$ \tau = [v_0F_0v_1F_1\dots v_jF_juF_jv_{j+1}\dots v_{k-1}F_{k-1}] $$
<figure><img src="image_130.png" /><figcaption>■ **Figure 5** The nooses $\eta'$ and $\eta''$ are trivial extensions of $\eta$. The red dashed region indicates where a new vertex was added. Note that $G_{\eta}^g = G_{\eta'}^g = G_{\eta''}^g$.</figcaption></figure>

for some $j \in \{0, ..., k-1\}$ and some $u$ which belongs to face $F_j$ and to the closed interior of $\eta$. Note that if $\eta'$ is a trivial extension of $\eta$, then $\eta$ and $\eta'$ have identical closed interiors. In Figure 5 we depict two trivial extensions $\eta'$ and $\eta''$ of a noose $\eta$.

We say that a noose $\eta$ is extensible if $|V(\eta)| < 8d$ and if $\eta$ has at least one trivial extension. We let $\text{Ext}(\eta)$ be the set of (equivalence classes of) trivial extensions of $\eta$. It is immediate that for each extensible noose $\eta$, $\mathcal{F}_{\eta} = \bigcup_{\eta' \in \text{Ext}(\eta)} \mathcal{F}_{\eta'}$. Based on this equality, for each extensible noose $\eta$, we define the set $\hat{\mathcal{F}}_{\eta} = \bigcup_{\eta' \in \text{Ext}(\eta)} \tilde{\mathcal{F}}_{\eta'}$.

**Lemma 11.** Let $\eta$ be an extensible noose. Suppose that $\tilde{\mathcal{F}}_{\eta'}$ represents $\mathcal{F}_{\eta'}$ for every $\eta' \in \text{Ext}(\eta)$. Then $\tilde{\mathcal{F}}_{\eta}$ represents $\mathcal{F}_{\eta}$.

Note that the number of extensions of a noose $\eta$ may be linear in $|V(G)|$. Therefore, the number of plane graphs in $\hat{\mathcal{F}}_{\eta}$ may be linear in $|V(G)|$. To decrease the size of this family, we apply the *Trunc* operator introduced in Section 4.

**Lemma 12.** Let $\eta$ be an extensible noose and let $\tilde{\mathcal{F}}_{\eta} = \text{Trunc}(\hat{\mathcal{F}}_{\eta})$. Then $\tilde{\mathcal{F}}_{\eta}$ represents $\mathcal{F}_{\eta}$.

**Case Three.** In this section we will deal with the case in which $|\eta| = 8d$. Let $G^g$ be a plane graph. A face-vertex sequence is a sequence $X = F_1v_1F_2...v_{r-1}F_r$ where $r \ge 1$, $\{v_1, ..., v_{r-1}\} \subseteq V(G)$, $\{F_1, ..., F_r\} \subseteq F(G)$, and for each $i \in \{1, ..., r-2\}$, $v_i$ and $v_{i+1}$ are in $F_i$. We note that any noose type $\tau = [v_0F_0v_1...v_mF_m]$ where $m \ge 1$ can be written as $\tau = [v_0Xv_rY]$ where $X = F_1v_1F_2...v_{r-1}F_{r-1}$ and $Y = FRIA$ are face-vertex sequences.

The reverse of a face-vertex sequence $X = F_1v_1F_2...v_{r-1}F_r$ is the face-vertex sequence $X^R = FRIA...F_2v_1F_1$. Let $\tau_1$ and $\tau_2$ be noose types. We say that $\tau_1$ and $\tau_2$ are summable if there is a unique maximal$^7$ face-vertex sequence $X = X(\tau_1, \tau_2)$ with the property that there exist vertices $v, v'$ and face-vertex sequences $Y$ and $Z$ such that $\tau_1 = [vYv'X]$ and $\tau_2 = [v'ZvX^R]$. If this is the case, the sum of $\tau_1$ with $\tau_2$ is defined as $\tau_1 \oplus \tau_2 = [vYv'Z]$. We let $V(X(\tau_1, \tau_2))$ denote the vertices which lie in the face vertex sequence $X(\tau_1, \tau_2)$.

We note that a noose $\eta$ has type $\tau_1 \oplus \tau_2$ if and only if there exist vertices $v, v'$ and simple arcs $l_1, l'_1, l_2, l'_2$ with endpoints $\{v, v'\}$ satisfying the following properties.

1. $l_1 \cap l'_1 = l_2 \cap l'_2 = l_1 \cap l_2 = \{v, v'\}$.

2. $g(V(X(\tau_1, \tau_2))) \subseteq l'_1 \cap l'_2$.

3. $\eta = l_1 \cup l_2$.

4. $\eta_1 = l_1 \cup l'_1$ is a noose of type $\tau_1$.

5. $\eta_2 = l_2 \cup l'_2$ is a noose of type $\tau_2$.

Intuitively, $\eta$ is obtained from $\eta_1$ and $\eta_2$ by the following process. First, we delete the interior of $l'_1$ from $\eta_1$ to obtain the segment $l_1$, and we delete the interior of $l'_2$ from $\eta_2$ to

<footnote>$^7$ Maximal with respect to length.</footnote>
<figure><img src="image_131.png" /><figcaption>■ **Figure 5** The nooses $\eta'$ and $\eta''$ are trivial extensions of $\eta$. The red dashed region indicates where a new vertex was added. Note that $G_{\eta}^g = G_{\eta'}^g = G_{\eta''}^g$.</figcaption></figure>

for some $j \in \{0, ..., k-1\}$ and some $u$ which belongs to face $F_j$ and to the closed interior of $\eta$. Note that if $\eta'$ is a trivial extension of $\eta$, then $\eta$ and $\eta'$ have identical closed interiors. In Figure 5 we depict two trivial extensions $\eta'$ and $\eta''$ of a noose $\eta$.

We say that a noose $\eta$ is extensible if $|V(\eta)| < 8d$ and if $\eta$ has at least one trivial extension. We let $\text{Ext}(\eta)$ be the set of (equivalence classes of) trivial extensions of $\eta$. It is immediate that for each extensible noose $\eta$, $\mathcal{F}_{\eta} = \bigcup_{\eta' \in \text{Ext}(\eta)} \mathcal{F}_{\eta'}$. Based on this equality, for each extensible noose $\eta$, we define the set $\hat{\mathcal{F}}_{\eta} = \bigcup_{\eta' \in \text{Ext}(\eta)} \tilde{\mathcal{F}}_{\eta'}$.

**Lemma 11.** Let $\eta$ be an extensible noose. Suppose that $\tilde{\mathcal{F}}_{\eta'}$ represents $\mathcal{F}_{\eta'}$ for every $\eta' \in \text{Ext}(\eta)$. Then $\tilde{\mathcal{F}}_{\eta}$ represents $\mathcal{F}_{\eta}$.

Note that the number of extensions of a noose $\eta$ may be linear in $|V(G)|$. Therefore, the number of plane graphs in $\hat{\mathcal{F}}_{\eta}$ may be linear in $|V(G)|$. To decrease the size of this family, we apply the *Trunc* operator introduced in Section 4.

**Lemma 12.** Let $\eta$ be an extensible noose and let $\tilde{\mathcal{F}}_{\eta} = \text{Trunc}(\hat{\mathcal{F}}_{\eta})$. Then $\tilde{\mathcal{F}}_{\eta}$ represents $\mathcal{F}_{\eta}$.

**Case Three.** In this section we will deal with the case in which $|\eta| = 8d$. Let $G^g$ be a plane graph. A face-vertex sequence is a sequence $X = F_1v_1F_2...v_{r-1}F_r$ where $r \ge 1$, $\{v_1, ..., v_{r-1}\} \subseteq V(G)$, $\{F_1, ..., F_r\} \subseteq F(G)$, and for each $i \in \{1, ..., r-2\}$, $v_i$ and $v_{i+1}$ are in $F_i$. We note that any noose type $\tau = [v_0F_0v_1...v_mF_m]$ where $m \ge 1$ can be written as $\tau = [v_0Xv_rY]$ where $X = F_1v_1F_2...v_{r-1}F_{r-1}$ and $Y = FRIA$ are face-vertex sequences.

The reverse of a face-vertex sequence $X = F_1v_1F_2...v_{r-1}F_r$ is the face-vertex sequence $X^R = FRIA...F_2v_1F_1$. Let $\tau_1$ and $\tau_2$ be noose types. We say that $\tau_1$ and $\tau_2$ are summable if there is a unique maximal$^7$ face-vertex sequence $X = X(\tau_1, \tau_2)$ with the property that there exist vertices $v, v'$ and face-vertex sequences $Y$ and $Z$ such that $\tau_1 = [vYv'X]$ and $\tau_2 = [v'ZvX^R]$. If this is the case, the sum of $\tau_1$ with $\tau_2$ is defined as $\tau_1 \oplus \tau_2 = [vYv'Z]$. We let $V(X(\tau_1, \tau_2))$ denote the vertices which lie in the face vertex sequence $X(\tau_1, \tau_2)$.

We note that a noose $\eta$ has type $\tau_1 \oplus \tau_2$ if and only if there exist vertices $v, v'$ and simple arcs $l_1, l'_1, l_2, l'_2$ with endpoints $\{v, v'\}$ satisfying the following properties.

1. $l_1 \cap l'_1 = l_2 \cap l'_2 = l_1 \cap l_2 = \{v, v'\}$.

2. $g(V(X(\tau_1, \tau_2))) \subseteq l'_1 \cap l'_2$.

3. $\eta = l_1 \cup l_2$.

4. $\eta_1 = l_1 \cup l'_1$ is a noose of type $\tau_1$.

5. $\eta_2 = l_2 \cup l'_2$ is a noose of type $\tau_2$.

Intuitively, $\eta$ is obtained from $\eta_1$ and $\eta_2$ by the following process. First, we delete the interior of $l'_1$ from $\eta_1$ to obtain the segment $l_1$, and we delete the interior of $l'_2$ from $\eta_2$ to

<footnote>$^7$ Maximal with respect to length.</footnote>
obtain the segment $l_2$. Subsequently, we glue $l_1$ with $l_2$ along their common endpoints in order to obtain the noose $\eta$. We note that if $\eta = \eta_1 \oplus \eta_2$ then $G_{\eta}^{g_{\eta}} = G_{\eta_1}^{g_{\eta_1}} \cup G_{\eta_2}^{g_{\eta_2}}$.

Let $\eta$ be a $G^g$-noose with $|\eta| = 8d$ and let $H^h$ be a triangulated $\eta$-respecting diameter-d plane completion of $G^g$. Let $V_1 \cup V_2 \cup V_3 \cup V_4$ be a partition of $V(\eta)$ where for each $i \in \{1, 2, 3, 4\}$, $V_i$ has $d$ consecutive vertices. Let $\hat{V}_1 \cup \hat{V}_2 \cup \hat{V}_3 \cup \hat{V}_4$ be a partition of the vertex set of $H_{\eta}^{h_{\eta}}$ where for each $v \in V(H_{\eta}^{h_{\eta}})$,

$$v \in \hat{V}_i \Leftrightarrow \left[ \text{dist}(v, V_i) < \min_{j<i} \text{dist}(v, V_j) \wedge \text{dist}(v, V_i) \le \min_{j>i} \text{dist}(v, V_j) \right].$$

Intuitively, the set of vertices incident with the noose $\eta$ is partitioned into four consecutive sections of size $d$: north ($V_1$), east ($V_2$), south ($V_3$) and west ($V_4$). Subsequently, each vertex $v \in V(G_{\eta}^g)$ is classified as being north ($\hat{V}_1$), east ($\hat{V}_2$), south ($\hat{V}_3$) or west ($\hat{V}_4$) according to whether $v$ is closer to a northern, eastern, southern or western vertex from the noose. In the case in which a vertex $v$ is as close to $V_i$ as it is to $V_j$, for some $i \neq j$, ties are broken by considering that north is smaller than east, which is smaller than south, which is smaller than west. We note that the way in which we have decided to break ties is completely arbitrary.

**Lemma 13.** There is an edge $uv \in E(H_{\eta}^{h_{\eta}})$ such that either $u \in \hat{V}_1$ and $v \in \hat{V}_3$, or $u \in \hat{V}_2$ and $v \in \hat{V}_4$.

**Lemma 14.** At least one of the following statements must be satisfied.

1. There is a path of length at most $2d + 1$ between a vertex in $V_1$ to a vertex in $V_3$.

2. There is a path of length at most $2d + 1$ between a vertex in $V_2$ and a vertex in $V_4$.

<figure><img src="image_131.png" /><figcaption>**Figure 6** Left: A noose $\eta$ with $8d$ vertices, and the sets $V_i$ and $\hat{V}_i$. Either there is an edge from a maximal element of $\hat{V}_1$ to a maximal element of $\hat{V}_3$, or an edge between a maximal element of $\hat{V}_2$ and a maximal element of $\hat{V}_4$. Middle: A path from $V_1$ to $V_3$ is depicted. Right: the path from $V_1$ to $V_3$ can be used to show that $\eta = \eta_1 \oplus \eta_2$ for nooses $\eta_1$ and $\eta_2$ where can be split into nooses $\eta_1 \oplus \eta_2$.</figcaption></figure>

**Lemma 15.** Let $H^h$ be a $\eta$-respecting diameter-d plane triangulated completion of $G^g$. Then there exist $G^g$-nooses $\eta_1$ and $\eta_2$ satisfying the following properties.

1. $|V(\eta_1)| \le 8d$ and $|V(\eta_2)| \le 8d$.

2. $\eta = \eta_1 \oplus \eta_2$.

3. $H^h$ is both $\eta_1$-respecting and $\eta_2$-respecting.

4. $H_{\eta}^{h_{\eta}} = H_{\eta_1}^{h_{\eta_1}} \cup H_{\eta_2}^{h_{\eta_2}}$.

Let $\eta, \eta_1$ and $\eta_2$ be $G^g$ nooses such that $\eta = \eta_1 \oplus \eta_2$. Then we define the following set: $\mathcal{F}_{\eta_1} \oplus \mathcal{F}_{\eta_2} = \{X^x \cup Y^y | X^x \in \mathcal{F}_{\eta_1}, Y^y \in \mathcal{F}_{\eta_2}\}$. Then, Lemma 15 implies that whenever $|\eta| = 8d$, $\mathcal{F}_{\eta} = \bigcup_{\eta=\eta_1 \oplus \eta_2} \mathcal{F}_{\eta_1} \oplus \mathcal{F}_{\eta_2}$.
obtain the segment $l_2$. Subsequently, we glue $l_1$ with $l_2$ along their common endpoints in order to obtain the noose $\eta$. We note that if $\eta = \eta_1 \oplus \eta_2$ then $G_{\eta}^{g_{\eta}} = G_{\eta_1}^{g_{\eta_1}} \cup G_{\eta_2}^{g_{\eta_2}}$.

Let $\eta$ be a $G^g$-noose with $|\eta| = 8d$ and let $H^h$ be a triangulated $\eta$-respecting diameter-d plane completion of $G^g$. Let $V_1 \cup V_2 \cup V_3 \cup V_4$ be a partition of $V(\eta)$ where for each $i \in \{1, 2, 3, 4\}$, $V_i$ has $d$ consecutive vertices. Let $\hat{V}_1 \cup \hat{V}_2 \cup \hat{V}_3 \cup \hat{V}_4$ be a partition of the vertex set of $H_{\eta}^{h_{\eta}}$ where for each $v \in V(H_{\eta}^{h_{\eta}})$,

$$v \in \hat{V}_i \Leftrightarrow \left[ \text{dist}(v, V_i) < \min_{j<i} \text{dist}(v, V_j) \wedge \text{dist}(v, V_i) \le \min_{j>i} \text{dist}(v, V_j) \right].$$

Intuitively, the set of vertices incident with the noose $\eta$ is partitioned into four consecutive sections of size $d$: north ($V_1$), east ($V_2$), south ($V_3$) and west ($V_4$). Subsequently, each vertex $v \in V(G_{\eta}^g)$ is classified as being north ($\hat{V}_1$), east ($\hat{V}_2$), south ($\hat{V}_3$) or west ($\hat{V}_4$) according to whether $v$ is closer to a northern, eastern, southern or western vertex from the noose. In the case in which a vertex $v$ is as close to $V_i$ as it is to $V_j$, for some $i \neq j$, ties are broken by considering that north is smaller than east, which is smaller than south, which is smaller than west. We note that the way in which we have decided to break ties is completely arbitrary.

**Lemma 13.** There is an edge $uv \in E(H_{\eta}^{h_{\eta}})$ such that either $u \in \hat{V}_1$ and $v \in \hat{V}_3$, or $u \in \hat{V}_2$ and $v \in \hat{V}_4$.

**Lemma 14.** At least one of the following statements must be satisfied.

1. There is a path of length at most $2d + 1$ between a vertex in $V_1$ to a vertex in $V_3$.

2. There is a path of length at most $2d + 1$ between a vertex in $v_2$ and a vertex in $v_4$.

<figure><img src="image_132.png" /><figcaption>Figure 6 Left: A noose $\eta$ with $8d$ vertices, and the sets $V_i$ and $\hat{V}_i$. Either there is an edge from a maximal element of $\hat{V}_1$ to a maximal element of $\hat{V}_3$, or an edge between a maximal element of $\hat{V}_2$ and a maximal element of $\hat{V}_4$. Middle: A path from $V_1$ to $V_3$ is depicted. Right: the path from $V_1$ to $V_3$ can be used to show that $\eta = \eta_1 \oplus \eta_2$ for nooses $\eta_1$ and $\eta_2$ where can be split into nooses $\eta_1 \oplus \eta_2$.</figcaption></figure>

**Lemma 15.** Let $H^h$ be a $\eta$-respecting diameter-d plane triangulated completion of $G^g$. Then there exist $G^g$-nooses $\eta_1$ and $\eta_2$ satisfying the following properties.

1. $|V(\eta_1)| \le 8d$ and $|V(\eta_2)| \le 8d$.

2. $\eta = \eta_1 \oplus \eta_2$.

3. $H^h$ is both $\eta_1$-respecting and $\eta_2$-respecting.

4. $H_{\eta}^{h_{\eta}} = H_{\eta_1}^{h_{\eta_1}} \cup H_{\eta_2}^{h_{\eta_2}}$.

Let $\eta, \eta_1$ and $\eta_2$ be $G^g$ nooses such that $\eta = \eta_1 \oplus \eta_2$. Then we define the following set: $\mathcal{F}_{\eta_1} \oplus \mathcal{F}_{\eta_2} = \{X^x \cup Y^y \mid X^x \in \mathcal{F}_{\eta_1}, Y^y \in \mathcal{F}_{\eta_2}\}$. Then, Lemma 15 implies that whenever $|\eta| = 8d$, $\mathcal{F}_{\eta} = \bigcup_{\eta=\eta_1 \oplus \eta_2} \mathcal{F}_{\eta_1} \oplus \mathcal{F}_{\eta_2}$.
**► Lemma 16.** Let $\eta$ be a $G^g$-noose with $|\eta| = 8d$, and assume that for every two $G^g$-nooses $\eta_1$ and $\eta_2$ such that $\eta = \eta_1 \oplus \eta_2$ we have that $\tilde{\mathcal{F}}_{\eta_1}$ represents $\mathcal{F}_{\eta_1}$ and $\tilde{\mathcal{F}}_{\eta_2}$ represents $\mathcal{F}_{\eta_2}$. Then $\mathcal{F}_{\eta}$ is represented by the following set.

$$ \tilde{\mathcal{F}}_{\eta} = \text{Trunc} \left( \bigcup_{\eta=\eta_1 \oplus \eta_2} \tilde{\mathcal{F}}_{\eta_1} \oplus \tilde{\mathcal{F}}_{\eta_2} \right) = \text{Trunc} \left( \bigcup_{\eta=\eta_1 \oplus \eta_2} \{X^x \cup Y^y \mid X^x \in \tilde{\mathcal{F}}_{\eta_1}, Y^y \in \tilde{\mathcal{F}}_{\eta_2}\} \right) \quad (2) $$

**Algorithm.** Now we summarize our algorithm for determining whether a given plane graph $G^g$ admits a plane completion of diameter at most $d$. We assume that the graph has at least $d$ vertices, since otherwise the graph has trivially a completion of diameter at most $d$. As a first step we enumerate all combinatorial faces of $G^g$, constructing in this way the set $F(G^g)$. We note that there exists at most $O(|V(G)|)$ such faces, and the set $F(G^g)$ can clearly be constructed in time $|V(G)|^{O(1)}$. As a second step, we enumerate all noose types containing at most $8d$ vertices. In other words, we enumerate all cycles $\tau = [v_0F_1v_1...v_{r-1}F_r]$ where $r-1 \le 8d$, and verify if $\tau$ is a valid noose type. Since there are at most $O(|V(G)|)$ combinatorial faces, there are at most $|V(G)|^{O(d)}$ possible noose types with at most $8d$ vertices. Let $\mathcal{T}$ be the set of all such noose types. Now, for each noose type $\tau \in \mathcal{T}$, we select an arbitrary noose $\eta_{\tau}$ of type $\tau$. We say that $\eta_{\tau}$ is a representative for $\tau$. Let $\mathcal{N} = \{\eta_{\tau}\}_{\tau \in \mathcal{T}}$ be the set of all such nooses.

For each noose $\eta \in \mathcal{N}$, we will compute a set $\tilde{\mathcal{F}}_{\eta}$ containing at most $2^{d^{O(d)}}$ triangulated plane completions of the graph $G_{\eta}^{g_{\eta}}$. In particular the set $\tilde{\mathcal{F}}_{\eta}$ represents the set $\mathcal{F}_{\eta}$. The sets $\tilde{\mathcal{F}}_{\eta}$ are computed by dynamic programming.

In the base case, let $\mathcal{N}^0 \subseteq \mathcal{N}$ be the minimal elements of $\mathcal{N}$ with respect to the noose ordering defined in the beginning of Section 5. For each such minimal noose $\eta^0$, we have that $|V(\eta^0)| = 3$, and the graph $G_{\eta}^{g_{\eta}}$ has no edges. Therefore the set $\tilde{\mathcal{F}}_{\eta}$ can be constructed in constant time in this case.

Now assume that we are dealing with a non-minimal noose $\eta \in \mathcal{N}$ and that $\tilde{\mathcal{F}}_{\eta'}$ has been constructed for every $\eta' < \eta$. We will show how to construct $\tilde{\mathcal{F}}_{\eta}$. There are three cases to be considered.

1. If there is some edge $uv \in E(G)$ which is externally parallel to $\eta$, then we consider a noose $\eta'$ such that $G_{\eta'}^{g_{\eta'}} = G_{\eta}^{g_{\eta}} - uv$. Then we set $\tilde{\mathcal{F}}_{\eta} = \tilde{\mathcal{F}}_{\eta'} + uv$.

2. If $\eta$ is trivially extensible, then we let $\tilde{\mathcal{F}}_{\eta} = \text{Trunc} \left( \bigcup_{\eta' \in \text{Ext}(\eta)} \tilde{\mathcal{F}}(\eta') \right)$.

3. If $|\eta| = 8d$, then we let $\tilde{\mathcal{F}}_{\eta} = \text{Trunc} \left( \bigcup_{\eta=\eta_1 \oplus \eta_2} \tilde{\mathcal{F}}_{\eta_1} \oplus \tilde{\mathcal{F}}_{\eta_2} \right)$

Now let $\eta$ be a maximal noose in $\mathcal{N}$. Then we have that $|\eta| = 3$ and that the graph $G_{\eta}^{g_{\eta}} = G^g$. Therefore, we have that $G^g$ admits a diameter-$d$ plane completion if and only if the set $\tilde{\mathcal{F}}_{\eta}$ is non-empty. Additionally, if this is the case, then any graph in $\tilde{\mathcal{F}}_{\eta}$ is a diameter-$d$ plane completion of $G^g$.

Note that in any of the three cases above the time necessary to construct the set $\tilde{\mathcal{F}}_{\eta}$ from previously computed $\tilde{\mathcal{F}}_{\eta'}$ is at most $2^{d^{O(d)}} \cdot |V(G)|^{O(d)}$, since there are at most $|V(G)|^{O(d)}$ nooses in $\mathcal{N}$ and each $\tilde{\mathcal{F}}_{\eta'}$ has at most $2^{d^{O(d)}}$ elements. This implies that the computation of $\tilde{\mathcal{F}}_{\eta}$ for every $\eta \in \mathcal{N}$ also takes time at most $2^{d^{O(d)}} \cdot |V(G)|^{O(d)}$, as stated in Theorem 1.

**k-Outerplanar Plane Diameter Improvement.** The algorithm for solving the embedded k-outerplanar diameter improvement problem is almost identical to the one to solve the embedded planar diameter improvement problem. The only difference is that, since the input graph is k-outerplanar, we only need to consider nooses of size at most $8k$, instead of $8d$ as in the previous algorithm.
**► Lemma 16.** Let $\eta$ be a $G^g$-noose with $|\eta| = 8d$, and assume that for every two $G^g$-nooses $\eta_1$ and $\eta_2$ such that $\eta = \eta_1 \oplus \eta_2$ we have that $\tilde{\mathcal{F}}_{\eta_1}$ represents $\mathcal{F}_{\eta_1}$ and $\tilde{\mathcal{F}}_{\eta_2}$ represents $\mathcal{F}_{\eta_2}$. Then $\mathcal{F}_{\eta}$ is represented by the following set.

$$ \tilde{\mathcal{F}}_{\eta} = \text{Trunc} \left( \bigcup_{\eta=\eta_1 \oplus \eta_2} \tilde{\mathcal{F}}_{\eta_1} \oplus \tilde{\mathcal{F}}_{\eta_2} \right) = \text{Trunc} \left( \bigcup_{\eta=\eta_1 \oplus \eta_2} \{X^x \cup Y^y \mid X^x \in \tilde{\mathcal{F}}_{\eta_1}, Y^y \in \tilde{\mathcal{F}}_{\eta_2}\} \right) \quad (2) $$

**Algorithm.** Now we summarize our algorithm for determining whether a given plane graph $G^g$ admits a plane completion of diameter at most $d$. We assume that the graph has at least $d$ vertices, since otherwise the graph has trivially a completion of diameter at most $d$. As a first step we enumerate all combinatorial faces of $G^g$, constructing in this way the set $F(G^g)$. We note that there exists at most $O(|V(G)|)$ such faces, and the set $F(G^g)$ can clearly be constructed in time $|V(G)|^{O(1)}$. As a second step, we enumerate all noose types containing at most $8d$ vertices. In other words, we enumerate all cycles $\tau = [v_0F_1v_1...v_{r-1}F_r]$ where $r-1 \le 8d$, and verify if $\tau$ is a valid noose type. Since there are at most $O(|V(G)|)$ combinatorial faces, there are at most $|V(G)|^{O(d)}$ possible noose types with at most $8d$ vertices. Let $\mathcal{T}$ be the set of all such noose types. Now, for each noose type $\tau \in \mathcal{T}$, we select an arbitrary noose $\eta_{\tau}$ of type $\tau$. We say that $\eta_{\tau}$ is a representative for $\tau$. Let $\mathcal{N} = \{\eta_{\tau}\}_{\tau \in \mathcal{T}}$ be the set of all such nooses.

For each noose $\eta \in \mathcal{N}$, we will compute a set $\tilde{\mathcal{F}}_{\eta}$ containing at most $2^{d^{O(d)}}$ triangulated plane completions of the graph $G_{\eta}^{g_{\eta}}$. In particular the set $\tilde{\mathcal{F}}_{\eta}$ represents the set $\mathcal{F}_{\eta}$. The sets $\tilde{\mathcal{F}}_{\eta}$ are computed by dynamic programming.

In the base case, let $\mathcal{N}^0 \subseteq \mathcal{N}$ be the minimal elements of $\mathcal{N}$ with respect to the noose ordering defined in the beginning of Section 5. For each such minimal noose $\eta^0$, we have that $|V(\eta^0)| = 3$, and the graph $G_{\eta}^{g_{\eta}}$ has no edges. Therefore the set $\tilde{\mathcal{F}}_{\eta}$ can be constructed in constant time in this case.

Now assume that we are dealing with a non-minimal noose $\eta \in \mathcal{N}$ and that $\tilde{\mathcal{F}}_{\eta'}$ has been constructed for every $\eta' < \eta$. We will show how to construct $\tilde{\mathcal{F}}_{\eta}$. There are three cases to be considered.

1. If there is some edge $uv \in E(G)$ which is externally parallel to $\eta$, then we consider a noose $\eta'$ such that $G_{\eta'}^{g_{\eta'}} = G_{\eta}^{g_{\eta}} - uv$. Then we set $\tilde{\mathcal{F}}_{\eta} = \tilde{\mathcal{F}}_{\eta'} + uv$.

2. If $\eta$ is trivially extensible, then we let $\tilde{\mathcal{F}}_{\eta} = \text{Trunc} \left( \bigcup_{\eta' \in \text{Ext}(\eta)} \tilde{\mathcal{F}}(\eta') \right)$.

3. If $|\eta| = 8d$, then we let $\tilde{\mathcal{F}}_{\eta} = \text{Trunc} \left( \bigcup_{\eta=\eta_1 \oplus \eta_2} \tilde{\mathcal{F}}_{\eta_1} \oplus \tilde{\mathcal{F}}_{\eta_2} \right)$

Now let $\eta$ be a maximal noose in $\mathcal{N}$. Then we have that $|\eta| = 3$ and that the graph $G_{\eta}^{g_{\eta}} = G^g$. Therefore, we have that $G^g$ admits a diameter-$d$ plane completion if and only if the set $\tilde{\mathcal{F}}_{\eta}$ is non-empty. Additionally, if this is the case, then any graph in $\tilde{\mathcal{F}}_{\eta}$ is a diameter-$d$ plane completion of $G^g$.

Note that in any of the three cases above the time necessary to construct the set $\tilde{\mathcal{F}}_{\eta}$ from previously computed $\tilde{\mathcal{F}}_{\eta'}$ is at most $2^{d^{O(d)}} \cdot |V(G)|^{O(d)}$, since there are at most $|V(G)|^{O(d)}$ nooses in $\mathcal{N}$ and each $\tilde{\mathcal{F}}_{\eta'}$ has at most $2^{d^{O(d)}}$ elements. This implies that the computation of $\tilde{\mathcal{F}}_{\eta}$ for every $\eta \in \mathcal{N}$ also takes time at most $2^{d^{O(d)}} \cdot |V(G)|^{O(d)}$, as stated in Theorem 1.

**k-Outerplanar Plane Diameter Improvement.** The algorithm for solving the embedded k-outerplanar diameter improvement problem is almost identical to the one to solve the embedded planar diameter improvement problem. The only difference is that, since the input graph is k-outerplanar, we only need to consider nooses of size at most $8k$, instead of $8d$ as in the previous algorithm.
In particular, the proof of Lemma 14 may be adapted in such a way that if we split the set $V(\eta)$ into sets $V_1, V_2, V_3, V_4$ as done previously, then there is either a path of length at most $2k$ between some vertex in $V_1$ and some vertex in $V_3$, or a path of length at most $2k$ between some vertex in $V_3$ and some vertex in $V_4$. As a consequence, the value $8d$ in Lemma 15 may be replaced with $8k$ when considering $k$-outerplanar graphs. With these adaptations our algorithm for the embedded $k$-outerplanar diameter improvement problem is guaranteed to run in time $2^{d^O(d)} \cdot |V(G)|^{O(k)}$ as stated in Theorem 2.

References

1 Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. In Proc. of SODA 2008, pages 641–650. SIAM, 2008.

2 Vincent Bouchitté, Frédéric Mazoit, and Ioan Todinca. Chordal embeddings of planar graphs. Discrete Mathematics, 273(1):85–102, 2003.

3 Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing, 31(1):212–232, 2001.

4 Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M Thilikos, and Mathias Weller. A polynomial-time algorithm for outerplanar diameter improvement. Journal of Computer and System Sciences, 2017.

5 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.

6 Mateus de Oliveira Oliveira. On Supergraphs satisfying CMSO properties. In Proc. of the 26th Conference on Computer Science Logic (CSL 2017). To appear., volume 82 of LIPIcs, 2017.

7 Frederic Dorn, Eelko Penninkx, Hans L Bodlaender, and Fedor V Fomin. Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica, 58(3):790–810, 2010.

8 Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999.

9 Michael R. Fellows and Rodney G. Downey. Parameterized Computational Feasibility. Feasible Mathematics II, 13:219–244, 1995.

10 Michael R Fellows and Michael A Langston. On search decision and the efficiency of polynomial-time algorithms. In Proc. of STOC 1989, pages 501–512. ACM, 1989.

11 Fedor V Fomin and Dimitrios M Thilikos. A simple and fast approach for solving problems on planar graphs. In STACS, volume 2996, pages 56–67. Springer, 2004.

12 Fedor V Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54–87, 2015.

13 Neil Robertson and Paul D Seymour. Graph minors. XI. Circuits on a surface. Journal of Combinatorial Theory, Series B, 60(1):72–106, 1994.

14 Neil Robertson and Paul D Seymour. Graph minors. XIII. The disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65–110, 1995.

15 Neil Robertson and Paul D Seymour. Graph minors. XX. Wagner's conjecture. Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004.
In particular, the proof of Lemma 14 may be adapted in such a way that if we split the set $V(\eta)$ into sets $V_1, V_2, V_3, V_4$ as done previously, then there is either a path of length at most $2k$ between some vertex in $V_1$ and some vertex in $V_3$, or a path of length at most $2k$ between some vertex in $V_3$ and some vertex in $V_4$. As a consequence, the value $8d$ in Lemma 15 may be replaced with $8k$ when considering $k$-outerplanar graphs. With these adaptations our algorithm for the embedded $k$-outerplanar diameter improvement problem is guaranteed to run in time $2^{d^O(d)} \cdot |V(G)|^{O(k)}$ as stated in Theorem 2.

References

1 Isolde Adler, Martin Grohe, and Stephan Kreutzer. Computing excluded minors. In Proc. of SODA 2008, pages 641–650. SIAM, 2008.

2 Vincent Bouchitté, Frédéric Mazoit, and Ioan Todinca. Chordal embeddings of planar graphs. Discrete Mathematics, 273(1):85–102, 2003.

3 Vincent Bouchitté and Ioan Todinca. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM Journal on Computing, 31(1):212–232, 2001.

4 Nathann Cohen, Daniel Gonçalves, Eun Jung Kim, Christophe Paul, Ignasi Sau, Dimitrios M Thilikos, and Mathias Weller. A polynomial-time algorithm for outerplanar diameter improvement. Journal of Computer and System Sciences, 2017.

5 Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.

6 Mateus de Oliveira Oliveira. On Supergraphs satisfying CMSO properties. In Proc. of the 26th Conference on Computer Science Logic (CSL 2017). To appear., volume 82 of LIPIcs, 2017.

7 Frederic Dorn, Eelko Penninkx, Hans L Bodlaender, and Fedor V Fomin. Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions. Algorithmica, 58(3):790–810, 2010.

8 Rodney G. Downey and Michael R. Fellows. Parameterized Complexity. Monographs in Computer Science. Springer, 1999.

9 Michael R. Fellows and Rodney G. Downey. Parameterized Computational Feasibility. Feasible Mathematics II, 13:219–244, 1995.

10 Michael R Fellows and Michael A Langston. On search decision and the efficiency of polynomial-time algorithms. In Proc. of STOC 1989, pages 501–512. ACM, 1989.

11 Fedor V Fomin and Dimitrios M Thilikos. A simple and fast approach for solving problems on planar graphs. In STACS, volume 2996, pages 56–67. Springer, 2004.

12 Fedor V Fomin, Ioan Todinca, and Yngve Villanger. Large induced subgraphs via triangulations and CMSO. SIAM Journal on Computing, 44(1):54–87, 2015.

13 Neil Robertson and Paul D Seymour. Graph minors. XI. Circuits on a surface. Journal of Combinatorial Theory, Series B, 60(1):72–106, 1994.

14 Neil Robertson and Paul D Seymour. Graph minors. XIII. The disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65–110, 1995.

15 Neil Robertson and Paul D Seymour. Graph minors. XX. Wagner's conjecture. Journal of Combinatorial Theory, Series B, 92(2):325–357, 2004.
<figure><img src="image_132.png" /></figure>
<figure><img src="image_133.png" /></figure>
# The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration

## Édouard Bonnet

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
edouard.bonnet@dauphine.fr

## Florian Sikora

Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016, Paris, France
florian.sikora@dauphine.fr

## Abstract

The Program Committee of the Third Parameterized Algorithms and Computational Experiments challenge (PACE 2018) reports on the third iteration of the PACE challenge. This year, all three tracks were dedicated to solve the STEINER TREE problem, in which, given an edge-weighted graph and a subset of its vertices called terminals, one has to find a minimum-weight subgraph which spans all the terminals. In Track A, the number of terminals was limited. In Track B, a tree-decomposition of the graph was provided in the input, and the treewidth was limited. Finally, Track C welcomed heuristics. Over 80 participants on 40 teams from 16 countries submitted their implementations to the competition.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability

**Keywords and phrases** Steiner tree problem, contest, implementation challenge, FPT

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

**Funding** Partially supported by the LABEX MILYON (ANR-10- LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR) and project "ESIGMA" (ANR-17-CE23-0010).

**Acknowledgements** The PACE challenge was supported by Networks [35], an NWO Gravitation project of the University of Amsterdam, Eindhoven University of Technology, Leiden University, and the Center for Mathematics and Computer Science (CWI), by data-experts.de, and by Freunde der Saarbrücker Informatik (FdSI). The prize money (3750 €) and travel grants (1000 € for Daniel Rehfeldt who presented SCIP-Jack during the award ceremony) were given through the generosity of Networks [35] and data-experts.de. We are grateful to Szymon Wasik and Jan Badura for the fruitful collaboration and for hosting the competition at optil.io.

## 1 Introduction

The Parameterized Algorithms and Computational Experiments Challenge (PACE) was conceived in Fall 2015 to deepen the relationship between parameterized algorithms and practice. It aims to:

1. Bridge the divide between the theory of algorithm design and analysis, and the practice of algorithm engineering.

2. Inspire new theoretical developments.

3. Investigate in how far theoretical algorithms from parameterized complexity and related fields are competitive in practice.

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

© Édouard Bonnet and Florian Sikora;
licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 26; pp. 26:1–26:15

Leibniz International Proceedings in Informatics

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

LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
# The PACE 2018 Parameterized Algorithms and Computational Experiments Challenge: The Third Iteration

## Édouard Bonnet

Univ Lyon, CNRS, ENS de Lyon, Université Claude Bernard Lyon 1, LIP UMR5668, France
edouard.bonnet@dauphine.fr

## Florian Sikora

Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016, Paris, France
florian.sikora@dauphine.fr

## Abstract

The Program Committee of the Third Parameterized Algorithms and Computational Experiments challenge (PACE 2018) reports on the third iteration of the PACE challenge. This year, all three tracks were dedicated to solve the STEINER TREE problem, in which, given an edge-weighted graph and a subset of its vertices called terminals, one has to find a minimum-weight subgraph which spans all the terminals. In Track A, the number of terminals was limited. In Track B, a tree-decomposition of the graph was provided in the input, and the treewidth was limited. Finally, Track C welcomed heuristics. Over 80 participants on 40 teams from 16 countries submitted their implementations to the competition.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability

**Keywords and phrases** Steiner tree problem, contest, implementation challenge, FPT

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

**Funding** Partially supported by the LABEX MILYON (ANR-10- LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR) and project "ESIGMA" (ANR-17-CE23-0010).

**Acknowledgements** The PACE challenge was supported by Networks [35], an NWO Gravitation project of the University of Amsterdam, Eindhoven University of Technology, Leiden University, and the Center for Mathematics and Computer Science (CWI), by data-experts.de, and by *Freunde der Saarbrücker Informatik (FdSI)*. The prize money (3750 €) and travel grants (1000 € for Daniel Rehfeldt who presented SCIP-Jack during the award ceremony) were given through the generosity of Networks [35] and data-experts.de. We are grateful to Szymon Wasik and Jan Badura for the fruitful collaboration and for hosting the competition at optil.io.

# 1 Introduction

The Parameterized Algorithms and Computational Experiments Challenge (PACE) was conceived in Fall 2015 to deepen the relationship between parameterized algorithms and practice. It aims to:

1. Bridge the divide between the theory of algorithm design and analysis, and the practice of algorithm engineering.

2. Inspire new theoretical developments.

3. Investigate in how far theoretical algorithms from parameterized complexity and related fields are competitive in practice.

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

© Édouard Bonnet and Florian Sikora;
licensed under Creative Commons License CC-BY

13th International Symposium on Parameterized and Exact Computation (IPEC 2018).

Editors: Christophe Paul and Michal Pilipczuk; Article No. 26; pp. 26:1–26:15

Leibniz International Proceedings in Informatics

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

LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
4. Produce universally accessible libraries of implementations and repositories of benchmark instances.

5. Encourage the dissemination of these findings in scientific papers.

The first iteration of PACE was held at IPEC 2016 [13]. Since then, PACE has been mentioned as an inspiration in many papers [1, 3, 21, 22, 25, 31, 33, 41, 42]. Hisao Tamaki's companion theory paper to his winning implementations of PACE 2017 [14] won the best paper award at ESA 2017 [40]. Very recent works acknowledging PACE or inspired by the challenge include the following papers [5, 7, 32, 20, 4, 17]. At this year's ESA, it was shown that parallelized dynamic programming (DP) on tree decompositions is a competitive approach to SAT solving [23]. According to the paper, this was made possible by the excellent programs developed for the treewidth tracks of PACE 2016 and 2017. At the same conference, Bannach and Brendt provided an efficient and simple interface to DP on tree decompositions [2].

In this article, we report on the third iteration of PACE. The PACE 2018 challenge was announced on November 14, 2017. The final version of the submissions was due on May 12, 2018. We informed the participants of the result on May 14, and announced them to the public on August 22nd, during the award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2018) in Helsinki.

## 2 The Steiner Tree Problem: Theory and Practice

There are many different variants of the Steiner Tree problem. They all involve the task to interconnect objects called terminals by using minimum-length wires. Here, we focus on the main variant in graphs. For a subset of edges $F$ of an undirected graph, let $V(F)$ denote the set of vertices that are endpoints of those edges. A formal definition of the STEINER TREE problem can be stated as follows.

**Input:** An undirected graph $G$ with a non-negative weight function on its edges $w: E(G) \to \mathbb{R}^{+}$, and a set of terminals $T \subseteq V(G)$.

**Output:** A subset of edges $F \subseteq E(G)$ minimizing $\sum_{e \in F} w(e)$ such that: $T \subseteq V(F)$ holds and $(V(F), F)$ is a connected graph.

We will interchangeably regard $F$ and $(V(F), F)$ as the solution. In words, given an edge-weighted graph and a subset of its vertices (the terminals) the task is to find a minimum-weight subgraph that spans all terminals. As the weights are non-negative, any edge of a cycle in a feasible solution can be removed to obtain a solution that is still feasible but has a smaller or equal total weight. Hence, there is always a tree among the optimum solutions, which explains the second word, *Tree*, in the problem name. The first word, *Steiner*, refers to the 19th-century geometer Jakob Steiner.

We chose STEINER TREE to be the problem of PACE 2018 since it has a wide spectrum of real-life applications, including the design of VLSI, optical or wireless communication systems, and transportation networks [30]. Furthermore, as a result of the 11th DIMACS implementation challenge, there are established benchmarks for STEINER TREE and its variants. Finally, as we will see in the next section, this problem has interesting FPT algorithms.

### 2.1 Parameterized algorithms

In what follows, we denote the number of edges of an input graph $G$ by $n$, its number of edges by $m$, its number of terminals by $t$, and its treewidth by $w$. Steiner vertices are the non-terminal vertices touched by a solution $F \subseteq E(G)$, and we denote their number by $s$,
4. Produce universally accessible libraries of implementations and repositories of benchmark instances.

5. Encourage the dissemination of these findings in scientific papers.

The first iteration of PACE was held at IPEC 2016 [13]. Since then, PACE has been mentioned as an inspiration in many papers [1, 3, 21, 22, 25, 31, 33, 41, 42]. Hisao Tamaki's companion theory paper to his winning implementations of PACE 2017 [14] won the best paper award at ESA 2017 [40]. Very recent works acknowledging PACE or inspired by the challenge include the following papers [5, 7, 32, 20, 4, 17]. At this year's ESA, it was shown that parallelized dynamic programming (DP) on tree decompositions is a competitive approach to SAT solving [23]. According to the paper, this was made possible by the excellent programs developed for the treewidth tracks of PACE 2016 and 2017. At the same conference, Bannach and Brendt provided an efficient and simple interface to DP on tree decompositions [2].

In this article, we report on the third iteration of PACE. The PACE 2018 challenge was announced on November 14, 2017. The final version of the submissions was due on May 12, 2018. We informed the participants of the result on May 14, and announced them to the public on August 22nd, during the award ceremony at the International Symposium on Parameterized and Exact Computation (IPEC 2018) in Helsinki.

## 2 The Steiner Tree Problem: Theory and Practice

There are many different variants of the Steiner Tree problem. They all involve the task to interconnect objects called terminals by using minimum-length wires. Here, we focus on the main variant in graphs. For a subset of edges $F$ of an undirected graph, let $V(F)$ denote the set of vertices that are endpoints of those edges. A formal definition of the STEINER TREE problem can be stated as follows.

**Input:** An undirected graph $G$ with a non-negative weight function on its edges $w: E(G) \to \mathbb{R}^+$, and a set of terminals $T \subseteq V(G)$.

**Output:** A subset of edges $F \subseteq E(G)$ minimizing $\sum_{e \in F} w(e)$ such that: $T \subseteq V(F)$ holds and $(V(F), F)$ is a connected graph.

We will interchangeably regard $F$ and $(V(F), F)$ as the solution. In words, given an edge-weighted graph and a subset of its vertices (the terminals) the task is to find a minimum-weight subgraph that spans all terminals. As the weights are non-negative, any edge of a cycle in a feasible solution can be removed to obtain a solution that is still feasible but has a smaller or equal total weight. Hence, there is always a tree among the optimum solutions, which explains the second word, *Tree*, in the problem name. The first word, *Steiner*, refers to the 19th-century geometer Jakob Steiner.

We chose STEINER TREE to be the problem of PACE 2018 since it has a wide spectrum of real-life applications, including the design of VLSI, optical or wireless communication systems, and transportation networks [30]. Furthermore, as a result of the 11th DIMACS implementation challenge, there are established benchmarks for STEINER TREE and its variants. Finally, as we will see in the next section, this problem has interesting FPT algorithms.

### 2.1 Parameterized algorithms

In what follows, we denote the number of edges of an input graph $G$ by $n$, its number of edges by $m$, its number of terminals by $t$, and its treewidth by $w$. Steiner vertices are the non-terminal vertices touched by a solution $F \subseteq E(G)$, and we denote their number by $s$,
that is, we have $s = |V(F) \setminus T|$. As we will see, there are FPT algorithms for STEINER TREE with $t$ as a parameter and with $w$ as a parameter, that is, algorithms running in time $f(t)n^{O(1)}$ and $g(w)n^{O(1)}$ for some computable functions $f$ and $g$.

## The Dreyfus-Wagner algorithm

There is a classical algorithm from the 70s designed by Dreyfus and Wagner [16] (henceforth DW) with running time $O(3^t n + 2^t n^2 + n(n \log n + m))$. This was later improved to $O(3^t n + 2^t(n \log n + m))$ by Erickson, Monma, and Veinott [19] (henceforth EMV). It works by dynamic programming on pairs of disjoint subsets of the set of terminals $T$. To keep it simple, in a solution $(V(F), F)$, there is a vertex with degree at least 3 whose removal would disconnect two disjoint sets of terminals $T_1, T_2 \subset T$. One can store a lightest way of connecting $T_1$ and $T_2$ for all the pairs $T_1, T_2$ in a bottom-up manner. The number of pairs of disjoint sets in a universe of $t$ elements is $3^t$, which explains part of the running time of DM and EMV.

One can wonder if the exponential basis of 3 can be decreased. There has been quite a bit of work done in that direction, leading to a series of improvements going from 3 to 2. However, no submission to this year's PACE challenge have made use of these improvements, for good reason: They tend to come with a nasty blow-up in the polynomial factors. For instance, there are $O(2.5^t n^{15})$ and $O(2.1^t n^{58})$ time algorithms [24]. If the weights are bounded by some constant (and in the variant where the vertices, not the edges, are weighted), there is an algorithm with running time roughly $O(2^t n^2 + nm)$, based on the so-called fast subset convolution [6].

## Treewidth-based algorithms

Given a tree-decomposition $(\mathcal{T}, \{V_u\}_{u \in V(\mathcal{T})})$ of width $w$ of the input graph $G$ (with $\mathcal{T}$, a rooted tree and $\{V_u\}$, a family of subsets of $V(G)$ indexed by the nodes of $\mathcal{T}$), one can solve STEINER TREE in time $O^*(w^w)$ by bottom-up dynamic programming on the nodes of $\mathcal{T}$. Indeed, once the subtree of $\mathcal{T}$ at $u \in V(\mathcal{T})$ is processed, the information to remember, besides the invested budget, is the subset of vertices of $V_u$ touched by a partial solution and how these vertices are connected in the partial solution. This information can be represented by a partition of a subset of $V_u$. The number of such objects is bounded by $O(w^w)$ since $|V_u| \le w+1$, hence the size of the DP table and the running time.

For some time it was an open question if STEINER TREE and similar problems with a connectivity constraint can be solved in time $2^{O(w)} n^{O(1)}$ instead of $2^{O(w \log w)} n^{O(1)}$. This was finally resolved in 2011 with the Cut&Count technique of Cygan et al. [12]. In a nutshell, the Cut&Count technique starts by addressing the parity version of the problem: how many sets of $\ell$ connected edges span $T$, modulo 2? For this, one counts the number $p$ of pairs $(D, C)$ where $D$ is a set of at most $\ell$ edges spanning $T$ (and $D$ is not required to be connected) and $C$ is a cut such that every connected component of $D$ is fully contained in one side of $C$. If we restrict a designated terminal to always be on the left side of $C$, the number of possible $C$ for a given $D$ is $2^{cc(D)-1}$, where $cc(D)$ is the number of connected components of $D$. This number is 1 if $D$ is connected and even otherwise. So, the parity of $p$ is the answer to our question. Since computing $p$ does not exhibit a (global) connectivity constraint, it can be done in time $2^{O(w)} n^{O(1)}$ by standard dynamic programming. Finally, one can distinguish the case zero solutions from the case non-zero even number of solutions by using the Isolation Lemma. This lemma implies that by giving uniformly random integer weights between 1 and $100\ell m$ to edges, there will be, with high probability, exactly one solution of minimum total
that is, we have $s = |V(F) \setminus T|$. As we will see, there are FPT algorithms for STEINER TREE with $t$ as a parameter and with $w$ as a parameter, that is, algorithms running in time $f(t)n^{O(1)}$ and $g(w)n^{O(1)}$ for some computable functions $f$ and $g$.

## The Dreyfus-Wagner algorithm

There is a classical algorithm from the 70s designed by Dreyfus and Wagner [16] (henceforth DW) with running time $O(3^t n + 2^t n^2 + n(n \log n + m))$. This was later improved to $O(3^t n + 2^t(n \log n + m))$ by Erickson, Monma, and Veinott [19] (henceforth EMV). It works by dynamic programming on pairs of disjoint subsets of the set of terminals $T$. To keep it simple, in a solution $(V(F), F)$, there is a vertex with degree at least 3 whose removal would disconnect two disjoint sets of terminals $T_1, T_2 \subset T$. One can store a lightest way of connecting $T_1$ and $T_2$ for all the pairs $T_1, T_2$ in a bottom-up manner. The number of pairs of disjoint sets in a universe of $t$ elements is $3^t$, which explains part of the running time of DM and EMV.

One can wonder if the exponential basis of 3 can be decreased. There has been quite a bit of work done in that direction, leading to a series of improvements going from 3 to 2. However, no submission to this year's PACE challenge have made use of these improvements, for good reason: They tend to come with a nasty blow-up in the polynomial factors. For instance, there are $O(2.5^t n^{15})$ and $O(2.1^t n^{58})$ time algorithms [24]. If the weights are bounded by some constant (and in the variant where the vertices, not the edges, are weighted), there is an algorithm with running time roughly $O(2^t n^2 + nm)$, based on the so-called fast subset convolution [6].

## Treewidth-based algorithms

Given a tree-decomposition $(\mathcal{T}, \{V_u\}_{u \in V(\mathcal{T})})$ of width $w$ of the input graph $G$ (with $\mathcal{T}$, a rooted tree and $\{V_u\}$, a family of subsets of $V(G)$ indexed by the nodes of $\mathcal{T}$), one can solve STEINER TREE in time $O^*(w^w)$ by bottom-up dynamic programming on the nodes of $\mathcal{T}$. Indeed, once the subtree of $\mathcal{T}$ at $u \in V(\mathcal{T})$ is processed, the information to remember, besides the invested budget, is the subset of vertices of $V_u$ touched by a partial solution and how these vertices are connected in the partial solution. This information can be represented by a partition of a subset of $V_u$. The number of such objects is bounded by $O(w^w)$ since $|V_u| \le w+1$, hence the size of the DP table and the running time.

For some time it was an open question if STEINER TREE and similar problems with a connectivity constraint can be solved in time $2^{O(w)} n^{O(1)}$ instead of $2^{O(w \log w)} n^{O(1)}$. This was finally resolved in 2011 with the Cut&Count technique of Cygan et al. [12]. In a nutshell, the Cut&Count technique starts by addressing the parity version of the problem: how many sets of $\ell$ connected edges span $T$, modulo 2? For this, one counts the number $p$ of pairs $(D, C)$ where $D$ is a set of at most $\ell$ edges spanning $T$ (and $D$ is not required to be connected) and $C$ is a cut such that every connected component of $D$ is fully contained in one side of $C$. If we restrict a designated terminal to always be on the left side of $C$, the number of possible $C$ for a given $D$ is $2^{cc(D)-1}$, where $cc(D)$ is the number of connected components of $D$. This number is 1 if $D$ is connected and even otherwise. So, the parity of $p$ is the answer to our question. Since computing $p$ does not exhibit a (global) connectivity constraint, it can be done in time $2^{O(w)} n^{O(1)}$ by standard dynamic programming. Finally, one can distinguish the case zero solutions from the case non-zero even number of solutions by using the Isolation Lemma. This lemma implies that by giving uniformly random integer weights between 1 and $100\ell m$ to edges, there will be, with high probability, exactly one solution of minimum total
weight (provided, of course, that there was a solution to begin with). For this total weight, we will therefore find an odd number of solutions, and may confidently report it.

One might then ask for a deterministic $2^{O(w)}n^{O(1)}$ time algorithm, which could handle weighted instances. The rank-based approach of Bodlaender et al. [8] does exactly that. The main idea is that when performing the standard $O^*(w^k)$ DP, one does not need to keep every partition of a bag. Instead, one can prune the partitions in the following way. If $S$ is the set of partitions of a bag achievable by partial solutions of a certain cost, then one can safely restrict attention to a subset $S' \subseteq S$, such that: if there is a $\Pi_1 \in S$ compatible with a partition $\Pi^*$ generated by a partial solution in the rest of the graph, then there should be at least one $\Pi_2 \in S'$ also compatible with $\Pi^*$. By compatible, we mean that the two partitions would fully connect the common subset of the bag touched by the partial solutions. If one represents compatibility by a square matrix in $F_2$ whose rows and columns are indexed by the partitions (with a 1 in the entries corresponding to compatible partitions, and a 0 otherwise), then it can be observed that any single row/column of a linearly dependent family of rows/columns can be safely removed. Indeed, for every index of the deleted vector containing a 1, there has to be another vector of the family also containing a 1 at this position. Then it is proved that the rank of the matrix with all the partitions is $2^{O(w)}$, and that Gaussian elimination can be done in the same time without having to explicitly store or compute all $O^*(w^k)$ permutations. This three-act story is told with the exact balance of details and conciseness in the book on parameterized complexity by Cygan et al. [11].

## Known theoretical obstacles

The STEINER TREE problem parameterized by the number $s$ of Steiner vertices is $W[2]$-hard [34]. Furthermore it is unlikely that there is an algorithm running in time $O(n^{s-\epsilon})$, for any $\epsilon > 0$. Such an algorithm would indeed give, by a simple reduction, an algorithm in $n^{k-\epsilon}$ for $k$-DOMINATING SET, contradicting the Strong Exponential Time Hypothesis [39]. Theory also says that one cannot expect very efficient preprocessing: there is no polynomial kernel in $s+t$ (the total number of vertices in $V(F)$) unless the polynomial-time hierarchy collapses [15]. Although, in practice, there are dozens of listed reductions rules which can sometimes completely solve large real-world instances.

## Approximations

We hastily touch the approximability status of STEINER TREE as it might be relevant to heuristics. A minimum spanning tree in the subgraph induced by the terminals of the metric closure yields an approximation ratio of 2 [27]. There is a 1.39-approximation based on a scheme called *iterative randomized rounding* of an LP-formulation [9], and a combinatorial 1.55-approximation [38]. However, STEINER TREE is APX-hard: there is no 1.01-approximation unless P=NP [10].

## 2.2 DIMACS challenge

In 2014, the 11th (and latest) DIMACS implementation challenge was also dedicated to solving Steiner Tree problems, and extensive libraries of instances existed prior to our challenge. As we will detail later, we mainly selected our instances from the Steinlib sets. Furthermore, there were already very efficient programs solving Steiner Tree and its variants. One successful program during the DIMACS competition, SCIP-Jack, also participated in our challenge. SCIP-Jack is a branch-and-cut algorithm based on the free MIP-solver SCIP. As such, it provides a natural baseline and comparison for the FPT approaches.
weight (provided, of course, that there was a solution to begin with). For this total weight,
we will therefore find an odd number of solutions, and may confidently report it.

One might then ask for a deterministic $2^{O(w)}n^{O(1)}$ time algorithm, which could handle
weighted instances. The rank-based approach of Bodlaender et al. [8] does exactly that. The
main idea is that when performing the standard $O^*(w^w)$ DP, one does not need to keep
every partition of a bag. Instead, one can prune the partitions in the following way. If $S$ is
the set of partitions of a bag achievable by partial solutions of a certain cost, then one can
safely restrict attention to a subset $S' \subseteq S$, such that: if there is a $\Pi_1 \in S$ compatible with
a partition $\Pi^*$ generated by a partial solution in the rest of the graph, then there should
be at least one $\Pi_2 \in S'$ also compatible with $\Pi^*$. By compatible, we mean that the two
partitions would fully connect the common subset of the bag touched by the partial solutions.
If one represents compatibility by a square matrix in $\mathbb{F}_2$ whose rows and columns are indexed
by the partitions (with a 1 in the entries corresponding to compatible partitions, and a
0 otherwise), then it can be observed that any single row/column of a linearly dependent
family of rows/columns can be safely removed. Indeed, for every index of the deleted vector
containing a 1, there has to be another vector of the family also containing a 1 at this
position. Then it is proved that the rank of the matrix with all the partitions is $2^{O(w)}$, and
that Gaussian elimination can be done in the same time without having to explicitly store or
compute all $O^*(w^w)$ permutations. This three-act story is told with the exact balance of
details and conciseness in the book on parameterized complexity by Cygan et al. [11].

## Known theoretical obstacles

The STEINER TREE problem parameterized by the number *s* of Steiner vertices is W[2]-hard [34]. Furthermore it is unlikely that there is an algorithm running in time *O*(n*s*⁻¹), for any *ε* > 0. Such an algorithm would indeed give, by a simple reduction, an algorithm in n*k*⁻¹ for *k*-DOMINATING SET, contradicting the Strong Exponential Time Hypothesis [39]. Theory also says that one cannot expect very efficient preprocessing: there is no polynomial kernel in *s* + *t* (the total number of vertices in V(F)) unless the polynomial-time hierarchy collapses [15]. Although, in practice, there are dozens of listed reductions rules which can sometimes completely solve large real-world instances.

## Approximations

We hastily touch the approximability status of STEINER TREE as it might be relevant
to heuristics. A minimum spanning tree in the subgraph induced by the terminals of
the metric closure yields an approximation ratio of 2 [27]. There is a 1.39-approximation
based on a scheme called *iterative randomized rounding* of an LP-formulation [9], and a
combinatorial 1.55-approximation [38]. However, STEINER TREE is APX-hard: there is no
1.01-approximation unless P=NP [10].

## 2.2 DIMACS challenge

In 2014, the 11th (and latest) DIMACS implementation challenge was also dedicated to
solving Steiner Tree problems, and extensive libraries of instances existed prior to our
challenge. As we will detail later, we mainly selected our instances from the Steinlib sets.
Furthermore, there were already very efficient programs solving Steiner Tree and its variants.
One successful program during the DIMACS competition, SCIP-Jack, also participated in
our challenge. SCIP-Jack is a branch-and-cut algorithm based on the free MIP-solver SCIP.
As such, it provides a natural baseline and comparison for the FPT approaches.
<figure><img src="image_135.png" /><figcaption>Figure 1 The distribution (#edges, #terminals) of the public (left) and private (right) instances of Track A in log-log plot.</figcaption></figure>

## 3 Selection of the instances and rules

Before we selected the instances, we first defined the precise goals of each track. In light of the efficient parameterized algorithms described in the previous paragraphs and the objectives of PACE, it will not come as a surprise that we decided that Track A would have instances where the number *t* of terminals is relatively small, while in Track B the treewidth *w* of the graphs would be relatively small.

Generating artificial instances for which a careful optimization of the Dreyfus-Wagner algorithm (for Track A) or of the rank-based approach for dynamic programming on tree decompositions (for Track B) would get a decisive advantage compared to a generic solver (ILP, SAT) was not our goal. So, we selected our instances among established benchmarks (mainly Steinlib, PUC, GAP, Vienna), which were also used four years ago in the DIMACS challenge on Steiner Tree.

### 3.1 Track A

For this track, we picked quite a lot of instances with a VLSI application. They are grid graphs with rectangular holes and Manhattan distance weights (in the ALUE, ALUT, DIW, DMXA, GAP, MSM, TAQ, and LIN sets). We used randomly generated sparse instances meant to be resistant to preprocessing (in the E, I160, I640, PUC sets). We also included industrial instances stemming from wire routing problems (in the WRP3 and WRP4 sets), and real geographical networks in the form of complete graphs with Euclidean distances (X set).

Among these instance sets, we selected 200 instances: 100 public (given to the contestants) and 100 private (used for the evaluation), with 4 to 136 terminals. The median number of terminals is 16 and its mean is 19.4, while 1480 is the mean number of vertices, and 8515, the mean number of edges (see Figure 1). On more than 20 of those instances, top implementations of the DIMACS challenge, such as Staynerd, take tens of minutes. We sorted the instances by increasing (*t*, *m*) in the lexicographic order.

The main rule for Track A and B was that the algorithm (deterministic or randomized) should be exact. A sub-optimal output (in the public or private instances) would therefore mean disqualification. The final score is the number of private instances solved on the optil.io platform with 30 minutes per instance.
<figure><img src="image_136.png" /><figcaption>Figure 1 The distribution (#edges, #terminals) of the public (left) and private (right) instances of Track A in log-log plot.</figcaption></figure>

# 3 Selection of the instances and rules

Before we selected the instances, we first defined the precise goals of each track. In light of the efficient parameterized algorithms described in the previous paragraphs and the objectives of PACE, it will not come as a surprise that we decided that Track A would have instances where the number *t* of terminals is relatively small, while in Track B the treewidth *w* of the graphs would be relatively small.

Generating artificial instances for which a careful optimization of the Dreyfus-Wagner algorithm (for Track A) or of the rank-based approach for dynamic programming on tree decompositions (for Track B) would get a decisive advantage compared to a generic solver (ILP, SAT) was not our goal. So, we selected our instances among established benchmarks (mainly Steinlib, PUC, GAP, Vienna), which were also used four years ago in the DIMACS challenge on Steiner Tree.

## 3.1 Track A

For this track, we picked quite a lot of instances with a VLSI application. They are grid graphs with rectangular holes and Manhattan distance weights (in the ALUE, ALUT, DIW, DMXA, GAP, MSM, TAQ, and LIN sets). We used randomly generated sparse instances meant to be resistant to preprocessing (in the E, I160, I640, PUC sets). We also included industrial instances stemming from wire routing problems (in the WRP3 and WRP4 sets), and real geographical networks in the form of complete graphs with Euclidean distances (X set).

Among these instance sets, we selected 200 instances: 100 public (given to the contestants) and 100 private (used for the evaluation), with 4 to 136 terminals. The median number of terminals is 16 and its mean is 19.4, while 1480 is the mean number of vertices, and 8515, the mean number of edges (see Figure 1). On more than 20 of those instances, top implementations of the DIMACS challenge, such as Staynerd, take tens of minutes. We sorted the instances by increasing (*t*, *m*) in the lexicographic order.

The main rule for Track A and B was that the algorithm (deterministic or randomized) should be exact. A sub-optimal output (in the public or private instances) would therefore mean disqualification. The final score is the number of private instances solved on the optil.io platform with 30 minutes per instance.
<figure><img src="image_136.png" /><figcaption>■ **Figure 2** The distribution (#edges,treewidth) of the public (left) and private (right) instances of Track B in lin-log plot.</figcaption></figure>

## 3.2 Track B

For this track, we used a lot of rectilinear instances with a low treewidth but a high number of terminals (in the ES100FST, ES500FST, ES1000FST sets, where the number between ES and FST corresponds to the number of terminals). We also used many instances from WRP3 and WRP4 with an intermediate number of terminals (≈50). A tree decomposition of almost always minimum width was given with the input. We computed these decompositions using the winning implementations of the treewidth track of PACE 2017 by Strasser and by Tamaki and his team [14].

On the 200 instances that we picked, the average number of vertices is 1490, the average number of edges is 2847, the average number of terminals is 606, and its median is 100. Furthermore the width of the given tree decompositions range from 6 to 47 with a median of 19.5 (see Figure 2). We sorted the instances by increasing (w, m). The rules were the same as in Track A.

## 3.3 Track C

Finally in Track C, dedicated to heuristics, we chose large and difficult instances with many terminals and high treewidth. To this end, we used the hardest instances of Steinlib. We also added a lot of instances from the Vienna set. These instances were generated from real-world telecommunication networks by Ivana Ljubic's group at the University of Vienna. A majority of the selected instances cannot be solved within one hour by the state-of-the-art program. In several cases, the actual optimum is unknown.

The average number of vertices is 27K, the average number of edges is 48K, and the average number of terminals is 1114, with a median at 360.5 (see Figure 3). Finally the best treewidth upper bound (obtained with the heuristics of previous PACE) on these instances is almost always above 40. We sorted the instances by increasing (t, m).

In track C, the final score to maximize is the sum over all the private instances of the ratio opt/sol where opt is the optimum (if known) or the best known upper bound (otherwise) and sol is the value of the proposed output. Outputting a non-feasible solution would not disqualify the submission, but would give a score of 0 on that particular instance.
<figure><img src="image_137.png" /><figcaption>■ **Figure 2** The distribution (#edges,treewidth) of the public (left) and private (right) instances of Track B in lin-log plot.</figcaption></figure>

## 3.2 Track B

For this track, we used a lot of rectilinear instances with a low treewidth but a high number of terminals (in the ES100FST, ES500FST, ES1000FST sets, where the number between ES and FST corresponds to the number of terminals). We also used many instances from WRP3 and WRP4 with an intermediate number of terminals (≈50). A tree decomposition of almost always minimum width was given with the input. We computed these decompositions using the winning implementations of the treewidth track of PACE 2017 by Strasser and by Tamaki and his team [14].

On the 200 instances that we picked, the average number of vertices is 1490, the average number of edges is 2847, the average number of terminals is 606, and its median is 100. Furthermore the width of the given tree decompositions range from 6 to 47 with a median of 19.5 (see Figure 2). We sorted the instances by increasing (w, m). The rules were the same as in Track A.

## 3.3 Track C

Finally in Track C, dedicated to heuristics, we chose large and difficult instances with many terminals and high treewidth. To this end, we used the hardest instances of Steinlib. We also added a lot of instances from the Vienna set. These instances were generated from real-world telecommunication networks by Ivana Ljubic's group at the University of Vienna. A majority of the selected instances cannot be solved within one hour by the state-of-the-art program. In several cases, the actual optimum is unknown.

The average number of vertices is 27K, the average number of edges is 48K, and the average number of terminals is 1114, with a median at 360.5 (see Figure 3). Finally the best treewidth upper bound (obtained with the heuristics of previous PACE) on these instances is almost always above 40. We sorted the instances by increasing (t, m).

In track C, the final score to maximize is the sum over all the private instances of the ratio opt/sol where opt is the optimum (if known) or the best known upper bound (otherwise) and sol is the value of the proposed output. Outputting a non-feasible solution would not disqualify the submission, but would give a score of 0 on that particular instance.
<figure><img src="image_137.png" /><figcaption>Figure 3 The distribution (#edges, #terminals) of the public (left) and private (right) instances of Track C in log-log plot.</figcaption></figure>

<table><caption>Table 1 Participation per country (based on the initial registration form; more teams and participants uploaded their code on optil.io afterwards).</caption><thead><tr><th>Country</th><th>Teams</th><th>Participants</th></tr></thead><tbody><tr><td>Austria</td><td>2</td><td>4</td></tr><tr><td>Brazil</td><td>1</td><td>3</td></tr><tr><td>Canada</td><td>1</td><td>1</td></tr><tr><td>Czechia</td><td>2</td><td>4</td></tr><tr><td>Denmark</td><td>1</td><td>1</td></tr><tr><td>England</td><td>1</td><td>1</td></tr><tr><td>Finland</td><td>1</td><td>1</td></tr><tr><td>France</td><td>4</td><td>7</td></tr><tr><td>Germany</td><td>4</td><td>5</td></tr><tr><td>India</td><td>6</td><td>12</td></tr><tr><td>Japan</td><td>4</td><td>8</td></tr><tr><td>Mexico</td><td>1</td><td>4</td></tr><tr><td>Netherlands</td><td>2</td><td>6</td></tr><tr><td>Norway</td><td>2</td><td>4</td></tr><tr><td>Poland</td><td>2</td><td>11</td></tr><tr><td>Romania</td><td>1</td><td>3</td></tr></tbody><tfoot><tr><td>Total</td><td>35</td><td>75</td></tr></tfoot></table>

## 4 Participation and results

This year, we had over 40 teams and 80 participants coming from 16 countries and four continents: including Austria, Brazil, Canada, Czechia, Denmark, England, Finland, France, Germany, India, Japan, Mexico, the Netherlands, Norway, Poland, and Romania.

The number of teams and participants both doubled compared to PACE 2017. To be precise, the above numbers correspond to teams and participants who sent a final implementation to at least one track. If we also count people who uploaded some code on the optil.io platform but dropped out of the competition, the number of teams exceeds 50 and the number of participants exceeds 100. If we count the teams with their multiplicity (that is, the number of tracks in which they participated), this number exceeds 75.
<figure><img src="image_138.png" /><figcaption>Figure 3 The distribution (#edges, #terminals) of the public (left) and private (right) instances of Track C in log-log plot.</figcaption></figure>

<table><caption>Table 1 Participation per country (based on the initial registration form; more teams and participants uploaded their code on optil.io afterwards).</caption><thead><tr><th>Country</th><th>Teams</th><th>Participants</th></tr></thead><tbody><tr><td>Austria</td><td>2</td><td>4</td></tr><tr><td>Brazil</td><td>1</td><td>3</td></tr><tr><td>Canada</td><td>1</td><td>1</td></tr><tr><td>Czechia</td><td>2</td><td>4</td></tr><tr><td>Denmark</td><td>1</td><td>1</td></tr><tr><td>England</td><td>1</td><td>1</td></tr><tr><td>Finland</td><td>1</td><td>1</td></tr><tr><td>France</td><td>4</td><td>7</td></tr><tr><td>Germany</td><td>4</td><td>5</td></tr><tr><td>India</td><td>6</td><td>12</td></tr><tr><td>Japan</td><td>4</td><td>8</td></tr><tr><td>Mexico</td><td>1</td><td>4</td></tr><tr><td>Netherlands</td><td>2</td><td>6</td></tr><tr><td>Norway</td><td>2</td><td>4</td></tr><tr><td>Poland</td><td>2</td><td>11</td></tr><tr><td>Romania</td><td>1</td><td>3</td></tr><tr><td>Total</td><td>35</td><td>75</td></tr></tbody></table>

# 4 Participation and results

This year, we had over 40 teams and 80 participants coming from 16 countries and four continents: including Austria, Brazil, Canada, Czechia, Denmark, England, Finland, France, Germany, India, Japan, Mexico, the Netherlands, Norway, Poland, and Romania.

The number of teams and participants both doubled compared to PACE 2017. To be precise, the above numbers correspond to teams and participants who sent a final implementation to at least one track. If we also count people who uploaded some code on the optil.io platform but dropped out of the competition, the number of teams exceeds 50 and the number of participants exceeds 100. If we count the teams with their multiplicity (that is, the number of tracks in which they participated), this number exceeds 75.
## 4.1 Track A

Yoichi Iwata and Takuto Shigemura won this track by solving 95 private instances. Their algorithm builds upon the dynamic programming of Erickson-Monma-Veinott (EMV). A technical lemma permitted them to prune a lot of entries in the DP table. This happens to also solve instances with small treewidth even when the number of terminals is relatively large.

Krzysztof Mziarz and Adam Polak got the second place by preprocessing and improving Dreyfus-Wagner (DW) with the heuristic ideas presented by Hougardy et al. [29]. The latter consists of running a shortest path algorithm (Dijkstra, A*, etc.) in the partial solutions in order to prune the search space.

Koch and Rehfeldt took the third place with their program SCIP-Jack which has three main components. First, known and new reduction methods simplify the instance. Secondly, a set of heuristics provides upper and lower bounds. Finally, a reduction (of many variants) to the directed Steiner tree problem is performed and the core of the algorithm is a branch-and-cut approach using the MIP-solver SCIP (developed by a superset of this team).

At the fourth place, albeit still very close to the first place, solving 92 instances, Andre Schidler, Johannes Fichte, and Markus Hecher used reduction rules presented by Rehfeldt [37], including the so-called *dual ascent* and the improved DW by Hougardy et al. [29]. All the other teams implemented some refinements of DW or EMV.

- **1st place, 450 €:** Yoichi Iwata and Takuto Shigemura (team wata&sigma; from Japanese National Institute of Informatics and University of Tokyo) solved 95 out of 100 instances github.com/wata-orz/steiner_tree

- **2nd place, 350 €:** Krzysztof Mziarz and Adam Polak (team Jagiellonian from Jagielłonian University) solved 94 out of 100 instances https://bitbucket.org/krismaz/pace2018

- **3rd place, 300 €:** Thorsten Koch and Daniel Rehfeldt (team reko from Zuse Institute Berlin and TU Berlin) solved 93 out of 100 instances github.com/dRehfeldt/scipjack/

- **4th place, 225 €:** Andre Schidler, Johannes Fichte, and Markus Hecher (team TUW from TU Vienna) solved 92 out of 100 instances github.com/ASchidler/pace17/

- **5th place:** Krzysztof Kiljan, Dominik Klemba, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Mateusz Radecki, and Michał Ziobro (team UWarsaw from University of Warsaw and Jagiellonian University) solved 67 out of 100 instances https://bitbucket.org/marcin_pilipczuk/pace2018-steiner-tree

- **6th place:** Suhas Thejaswi (team Noname from Aalto University) solved 66 out of 100 instances github.com/suhastheju/pace-2018-exact

- **6th place:** Peter Mitura and Ondřej Suchý (team FIT CTU in Prague from the Czech Technical University) solved 66 out of 100 instances github.com/PMitura/pace2018

- **6th place:** Johannes Varga (team johannes from TU Vienna) solved 66 out of 100 instances github.com/josshy/st-tree

- **9th place:** Saket Saurabh, P. S. Srinivasan, and Prafullkumar Tale (team SSPSPT from the Institute Of Mathematical Sciences, HBNI, Chennai and the International Institute of Information Technology, Bangalore) solved 48 out of 100 instances github.com/pptale/PACE18
## 4.1 Track A

Yoichi Iwata and Takuto Shigemura won this track by solving 95 private instances. Their algorithm builds upon the dynamic programming of Erickson-Monma-Veinott (EMV). A technical lemma permitted them to prune a lot of entries in the DP table. This happens to also solve instances with small treewidth even when the number of terminals is relatively large.

Krzysztof Mziarz and Adam Polak got the second place by preprocessing and improving Dreyfus-Wagner (DW) with the heuristic ideas presented by Hougardy et al. [29]. The latter consists of running a shortest path algorithm (Dijkstra, A*, etc.) in the partial solutions in order to prune the search space.

Koch and Rehfeldt took the third place with their program SCIP-Jack which has three main components. First, known and new reduction methods simplify the instance. Secondly, a set of heuristics provides upper and lower bounds. Finally, a reduction (of many variants) to the directed Steiner tree problem is performed and the core of the algorithm is a branch-and-cut approach using the MIP-solver SCIP (developed by a superset of this team).

At the fourth place, albeit still very close to the first place, solving 92 instances, Andre Schidler, Johannes Fichte, and Markus Hecher used reduction rules presented by Rehfeldt [37], including the so-called dual ascent and the improved DW by Hougardy et al. [29].

All the other teams implemented some refinements of DW or EMV.

- **1st place, 450 €:** Yoichi Iwata and Takuto Shigemura (team wata&sigma; from Japanese National Institute of Informatics and University of Tokyo) solved 95 out of 100 instances
  github.com/wata-orz/steiner_tree

- **2nd place, 350 €:** Krzysztof Mziarz and Adam Polak (team Jagiellonian from Jagielłonian University) solved 94 out of 100 instances
  https://bitbucket.org/krismaz/pace2018

- **3rd place, 300 €:** Thorsten Koch and Daniel Rehfeldt (team reko from Zuse Institute Berlin and TU Berlin) solved 93 out of 100 instances
  github.com/dRehfeldt/scipjack/

- **4th place, 225 €:** Andre Schidler, Johannes Fichte, and Markus Hecher (team TUW from TU Vienna) solved 92 out of 100 instances
  github.com/ASchidler/pace17/

- **5th place:** Krzysztof Kiljan, Dominik Klemba, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Mateusz Radecki, and Michał Ziobro (team UWarsaw from University of Warsaw and Jagiellonian University) solved 67 out of 100 instances
  https://bitbucket.org/marcin_pilipczuk/pace2018-steiner-tree

- **6th place:** Suhas Thejaswi (team Noname from Aalto University) solved 66 out of 100 instances
  github.com/suhastheju/pace-2018-exact

- **6th place:** Peter Mitura and Ondřej Suchý (team FIT CTU in Prague from the Czech Technical University) solved 66 out of 100 instances
  github.com/PMitura/pace2018

- **6th place:** Johannes Varga (team johannes from TU Vienna) solved 66 out of 100 instances
  github.com/josshy/st-tree

- **9th place:** Saket Saurabh, P. S. Srinivasan, and Prafullkumar Tale (team SSPSPT from the Institute Of Mathematical Sciences, HBNI, Chennai and the International Institute of Information Technology, Bangalore) solved 48 out of 100 instances
  github.com/pptale/PACE18
- **10th place:** Sharat Ibrahimpur (team the65thbit from University of Waterloo) solved 69 out of 100 instances but was incorrect on 1 instance
  github.com/sharat1105/PACE2018

- **11th place:** S. Vaishali and Rathna Subramanian (team PCCoders from PSG College of Technology, Coimbatore) solved 14 out of 100 instances but was incorrect on several instances
  github.com/ammuv/PACE-2018-

- **12th place:** R. Vijayaragunathan, N. S. Narayanaswamy, and Rajesh Pandian M. (team Resilience from TCS Lab, Indian Institute of Technology, Madras) solved 9 instances but was incorrect on several instances
  github.com/mrprajesh/pace2018

One can see two well-defined clusters (90-95 and 65-70). The implementation at 10th place would have led the second cluster, if not for a small bug that showed only on one private instance.

## 4.2 Track B

In this track with low treewidth, the developers of SCIP-Jack, Thorsten Koch and Daniel Rehfeldt, took the first place by solving 92 of the 100 instances in the private set. They do not directly exploit the tree-decomposition given in input, but it is likely that the low treewidth indirectly translates into higher efficiency of their preprocessing, heuristics, and/or branch-and-cut. Otherwise, it is hard to explain how the same program, discarding the tree-decomposition, won Track B by solving 15 more instances than the winner of Track A (where they finished third).

At the second place, Yoichi Iwata and Takuto Shigemura implemented the standard $O*(w^w)$ dynamic programming on the tree-decomposition. When the treewidth becomes too large, they switch to their improved EMV algorithm. They observe that their algorithm for Track A performs well when the treewidth is low since the existence of small separators prunes a lot of entries in the DP table.

Completing the podium, Tom van der Zanden added to the rank-based approach a handful of nice observations, crediting some of them to Luuk van der Graaff's master thesis [28]. This results in the only program of the competition solving all the instances with treewidth at most 15. In particular, this implementation is the only one to solve instance 39 of the private set, which has 5K+ vertices, 20K+ edges, 2.4K+ terminals, and treewidth 11.

- **1st place, 450 €:** Thorsten Koch and Daniel Rehfeldt (team reko from Zuse Institute Berlin and TU Berlin) solved 92 out of 100 instances
  github.com/dRehfeldt/scipjack/

- **2nd place, 350 €:** Yoichi Iwata and Takuto Shigemura (team wata&sigma; from the Japanese National Institute of Informatics and the University of Tokyo) solved 77 out of 100 instances
  github.com/wata-orz/steiner_tree

- **3rd place, 300 €:** Tom van der Zanden (team Tom from Utrecht University) solved 58 out of 100 instances
  github.com/TomvdZanden/SteinerTreeTW

- **4th place:** Peter Mitura and Ondřej Suchý (team FIT CTU in Prague from the Czech Technical University) solved 52 out of 100 instances
  github.com/PMitura/pace2018
- **10th place:** Sharat Ibrahimpur (team the65thbit from University of Waterloo) solved 69 out of 100 instances but was incorrect on 1 instance
  github.com/sharat1105/PACE2018

- **11th place:** S. Vaishali and Rathna Subramanian (team PCCoders from PSG College of Technology, Coimbatore) solved 14 out of 100 instances but was incorrect on several instances
  github.com/ammuv/PACE-2018-

- **12th place:** R. Vijayaragunathan, N. S. Narayanaswamy, and Rajesh Pandian M. (team Resilience from TCS Lab, Indian Institute of Technology, Madras) solved 9 instances but was incorrect on several instances
  github.com/mrprajesh/pace2018

One can see two well-defined clusters (90-95 and 65-70). The implementation at 10th place would have led the second cluster, if not for a small bug that showed only on one private instance.

## 4.2 Track B

In this track with low treewidth, the developers of SCIP-Jack, Thorsten Koch and Daniel Rehfeldt, took the first place by solving 92 of the 100 instances in the private set. They do not directly exploit the tree-decomposition given in input, but it is likely that the low treewidth indirectly translates into higher efficiency of their preprocessing, heuristics, and/or branch-and-cut. Otherwise, it is hard to explain how the same program, discarding the tree-decomposition, won Track B by solving 15 more instances than the winner of Track A (where they finished third).

At the second place, Yoichi Iwata and Takuto Shigemura implemented the standard $O*(w^w)$ dynamic programming on the tree-decomposition. When the treewidth becomes too large, they switch to their improved EMV algorithm. They observe that their algorithm for Track A performs well when the treewidth is low since the existence of small separators prunes a lot of entries in the DP table.

Completing the podium, Tom van der Zanden added to the rank-based approach a handful of nice observations, crediting some of them to Luuk van der Graaff's master thesis [28]. This results in the only program of the competition solving all the instances with treewidth at most 15. In particular, this implementation is the only one to solve instance 39 of the private set, which has 5K+ vertices, 20K+ edges, 2.4K+ terminals, and treewidth 11.

- **1st place, 450€:** Thorsten Koch and Daniel Rehfeldt (team reko from Zuse Institute Berlin and TU Berlin) solved 92 out of 100 instances
  github.com/dRehfeldt/scipjack/

- **2nd place, 350€:** Yoichi Iwata and Takuto Shigemura (team wata&sigma; from the Japanese National Institute of Informatics and the University of Tokyo) solved 77 out of 100 instances
  github.com/wata-orz/steiner_tree

- **3rd place, 300€:** Tom van der Zanden (team Tom from Utrecht University) solved 58 out of 100 instances
  github.com/TomvdZanden/SteinerTreeTW

- **4th place:** Peter Mitura and Ondřej Suchý (team FIT CTU in Prague from the Czech Technical University) solved 52 out of 100 instances
  github.com/PMitura/pace2018
■ **Table 2** For each team: *score* is the number of private instances solved, *treewidth approach*, the treewidth-based algorithm used, if any, *first unsolved*, the number of the first unsolved private instance (we recall that the instances of Track B were sorted lexicographically by increasing (*w*, *e*)) and the corresponding value of the treewidth, *switching to DW-like*, if the treewidth approach is substituted to a terminal-based algorithm (DW = Dreyfus-Wagner algorithm, EMV = Erickson-Monma-Veinott algorithm), and *criterion to switch* what is the test to switch to such an algorithm.

<table><thead><tr><th>Team</th><th>score</th><th>treewidth approach</th><th>first unsolved</th><th>switching to DW-like</th><th>criterion to switch</th></tr></thead><tbody><tr><td>reko</td><td><b>92</b></td><td>no</td><td>26, w = 9</td><td>no</td><td>-</td></tr><tr><td>wata_sigma</td><td>77</td><td>w<sup>w</sup> DP</td><td>26, w = 9</td><td>EMV</td><td>w > 10 or (w > 8 and t < 300)</td></tr><tr><td>Tom</td><td>58</td><td>2<sup>O(w)</sup> rank-based</td><td><b>54</b>, w = 16</td><td>EMV</td><td>3<sup>t</sup> < 5<sup>w</sup></td></tr><tr><td>FIT CTU in Prague</td><td>52</td><td>2<sup>O(w)</sup> rank-based</td><td>39, w = 11</td><td>no</td><td>-</td></tr><tr><td>yasu</td><td>52</td><td>2<sup>O(w)</sup> rank-based</td><td>13, w = 7</td><td>DW</td><td>w > 15</td></tr><tr><td>fujiyoshi</td><td>49</td><td>2<sup>O(w)</sup> rank-based</td><td>39, w = 11</td><td>no</td><td>-</td></tr><tr><td>UWarsaw</td><td>33</td><td>2<sup>O(w)</sup> rank-based</td><td>32, w = 10</td><td>no</td><td>-</td></tr><tr><td>lapo</td><td>33</td><td>2<sup>O(w)</sup> rank-based</td><td>13, w = 7</td><td>no</td><td>-</td></tr></tbody></table>

- **4th place:** Yasuaki Kobayashi (team Yasu from Kyoto University) solved 52 out of 100 instances
  https://bitbucket.org/yasu0207/steiner_tree

- **6th place:** Akio Fujiyoshi (team CBGfinder from Ibaraki University) solved 49 out of 100 instances
  github.com/akio-fujiyoshi/CBGfinder_for_steiner_treeProblem

- **7th place:** Krzysztof Kiljan, Dominik Klemba, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Mateusz Radecki, and Michał Ziobro (team UWarsaw from University of Warsaw and Jagiellonian University) solved 33 out of 100 instances
  https://bitbucket.org/marcin_pilipczuk/pace2018-steiner-tree

- **7th place:** Dilson Guimarães, Guilherme Gomes, João Gonçalves, and Vinícius dos Santos (team lapo from LAPO-UFMG) solved 33 out of 100 instances
  github.com/dilsonguim/pace2018

The rest of the teams implemented the rank-based approach of Bodlaender et al. [8] as the main or secondary component. At the shared fourth place, Peter Mitura and Ondřej Suchý (FIT CTU in Prague)'s implementation is the fastest of the competition on average, while Yasuaki Kobayashi's program also switches to a terminal-based approach when the treewidth becomes too large. Table 2 summarizes the approach used by all the teams.

Since the instances were edge-weighted, no submission tried to use the Cut&Count technique. It would be interesting to compare the speed of the rank-based and the Cut&Count techniques on unweighted instances of relatively low treewidth. Another direction would be to make Cut&Count work on edge-weighted instances, in practice and/or in theory.

## 4.3 Track C

This track attracted the most participants. Regarding the instance sizes, it should be observed that a naive implementation (without preprocessing) of the 2-approximation algorithm does not finish within the time limit. The contributions use either meta-heuristics (an evolutionary algorithm for the winning team, iterated local-search with noising for the third team, simulated annealing, etc.), or start from some solution (a spanning tree, an arbitrary feasible solution, or a 2-approximation) and then improve it with local search. Radek Hušek and teammates (Team Tarken) used a parameterized approximation approach [18].
**Table 2** For each team: *score* is the number of private instances solved, *treewidth approach*, the treewidth-based algorithm used, if any, *first unsolved*, the number of the first unsolved private instance (we recall that the instances of Track B were sorted lexicographically by increasing (*w*, *e*)) and the corresponding value of the treewidth, *switching to DW-like*, if the treewidth approach is substituted to a terminal-based algorithm (DW = Dreyfus-Wagner algorithm, EMV = Erickson-Monma-Veinott algorithm), and *criterion to switch* what is the test to switch to such an algorithm.

<table><thead><tr><th>Team</th><th>score</th><th>treewidth approach</th><th>first unsolved</th><th>switching to DW-like</th><th>criterion to switch</th></tr></thead><tbody><tr><td>reko</td><td><b>92</b></td><td>no</td><td>26, w = 9</td><td>no</td><td>-</td></tr><tr><td>wata_sigma</td><td>77</td><td>w<sup>w</sup> DP</td><td>26, w = 9</td><td>EMV</td><td>w > 10 or (w > 8 and t < 300)</td></tr><tr><td>Tom</td><td>58</td><td>2<sup>O(w)</sup> rank-based</td><td><b>54</b>, w = 16</td><td>EMV</td><td>3<sup>t</sup> < 5<sup>w</sup></td></tr><tr><td>FIT CTU in Prague</td><td>52</td><td>2<sup>O(w)</sup> rank-based</td><td>39, w = 11</td><td>no</td><td>-</td></tr><tr><td>yasu</td><td>52</td><td>2<sup>O(w)</sup> rank-based</td><td>13, w = 7</td><td>DW</td><td>w > 15</td></tr><tr><td>fujiyoshi</td><td>49</td><td>2<sup>O(w)</sup> rank-based</td><td>39, w = 11</td><td>no</td><td>-</td></tr><tr><td>UWarsaw</td><td>33</td><td>2<sup>O(w)</sup> rank-based</td><td>32, w = 10</td><td>no</td><td>-</td></tr><tr><td>lapo</td><td>33</td><td>2<sup>O(w)</sup> rank-based</td><td>13, w = 7</td><td>no</td><td>-</td></tr></tbody></table>

- **4th place:** Yasuaki Kobayashi (team Yasu from Kyoto University) solved 52 out of 100 instances
  https://bitbucket.org/yasu0207/steiner_tree

- **6th place:** Akio Fujiyoshi (team CBGfinder from Ibaraki University) solved 49 out of 100 instances
  github.com/akio-fujiyoshi/CBGfinder_for_steiner_treeProblem

- **7th place:** Krzysztof Kiljan, Dominik Klemba, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Mateusz Radecki, and Michał Ziobro (team UWarsaw from University of Warsaw and Jagiellonian University) solved 33 out of 100 instances
  https://bitbucket.org/marcin_pilipczuk/pace2018-steiner-tree

- **7th place:** Dilson Guimarães, Guilherme Gomes, João Gonçalves, and Vinícius dos Santos (team lapo from LAPO-UFMG) solved 33 out of 100 instances
  github.com/dilsonguim/pace2018

The rest of the teams implemented the rank-based approach of Bodlaender et al. [8] as the main or secondary component. At the shared fourth place, Peter Mitura and Ondřej Suchý (FIT CTU in Prague)'s implementation is the fastest of the competition on average, while Yasuaki Kobayashi's program also switches to a terminal-based approach when the treewidth becomes too large. Table 2 summarizes the approach used by all the teams.

Since the instances were edge-weighted, no submission tried to use the Cut&Count technique. It would be interesting to compare the speed of the rank-based and the Cut&Count techniques on unweighted instances of relatively low treewidth. Another direction would be to make Cut&Count work on edge-weighted instances, in practice and/or in theory.

## 4.3 Track C

This track attracted the most participants. Regarding the instance sizes, it should be observed that a naive implementation (without preprocessing) of the 2-approximation algorithm does not finish within the time limit. The contributions use either meta-heuristics (an evolutionary algorithm for the winning team, iterated local-search with noising for the third team, simulated annealing, etc.), or start from some solution (a spanning tree, an arbitrary feasible solution, or a 2-approximation) and then improve it with local search. Radek Hušek and teammates (Team Tarken) used a parameterized approximation approach [18].
- **1st place, 450 €:** Emmanuel Romero Ruiz, Emmanuel Antonio Cuevas, Irwin Enrique Villalobos López, and Carlos Segura González (CIMAT Team from the Center for Research in Mathematics, Guanajuato) got an average ratio of 99.93/100
  github.com/HeathcliffAC/SteinerTreeProblem

- **2nd place, 350 €:** Thorsten Koch and Daniel Rehfeldt (team reko from Zuse Institute Berlin and TU Berlin) got an average ratio of 99.85/100
  github.com/dRehfeldt/scipjack/

- **3rd place, 300 €:** Martin Josef Geiger (team MJG from HSU Hamburg) [26] got an average ratio of 99.80/100
  https://data.mendeley.com/datasets/yf9vpkgwdr/1

- **4th place, 225 €:** Radek Hušek, Tomáš Toufar, Dušan Knop, Tomáš Masařík, and Eduard Eiben (team CUiB from Charles University, Prague and University of Bergen) got an average ratio of 99.72/100
  github.com/goderik01/PACE2018

- **5th place:** Emmanuel Arrighi and Mateus de Oliveira Oliveira (team Gardeners from ENS Cachan and University of Bergen) got an average ratio of 98.93/100
  github.com/SteinerGardeners/TrackC-Version1

- **6th place:** Krzysztof Kiljan, Dominik Klemba, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Mateusz Radecki, and Michał Ziobro (team UWarsaw from University of Warsaw and Jagiellonian University) got an average ratio of 98.27/100
  https://bitbucket.org/marcin_pilipczuk/pace2018-steiner-tree

- **7th place:** Stéphane Grandcolas (team SGLS from LIS Marseille) got an average ratio of 97.54/100
  http://www.dil.univ-mrs.fr/~gcolas/sgls.c

- **8th place:** Max Hort, Marciano Geijselaers, Joshua Scheidt, Pit Schneider, and Tahmina Begum (team JMMPT from the Department of Data Science and Knowledge Engineering, Maastricht University) got an average ratio of 97.15/100
  github.com/maxhort/Pacechallenge-TrackC/

- **9th place:** Dimitri Watel and Marc-Antoine Weisser (team DoubleDoubleU from SAMOVAR-ENSIHE and LRI-Centrale-Supelec) got an average ratio of 96.92/100
  github.com/mouton5000/PACE2018/

- **10th place:** R. Vijayaragunathan, N. S. Narayanaswamy, and Rajesh Pandian M. (team Resilience from TCS Lab and the Indian Institute of Technology Madras) got an average ratio of 94.57/100
  github.com/mrprajesh/pace2018

- **11th place:** Sharat Ibrahimpur (team the65thbit from University of Waterloo) got an average ratio of 94.37/100
  github.com/sharat1105/PACE2018

- **12th place:** Saket Saurabh, P. S. Srinivasan, and Prafullkumar Tale (team SSPSPT from the Institute Of Mathematical Sciences, HBNI, Chennai and the International Institute of Information Technology, Bangalore) got an average ratio of 82.61/100
  github.com/pptale/PACE18

- **13th place:** Harumi Haraguchi, Hiroshi Arai, Shiyougo Akiyama, and Masaki Kubonoya (team Haraguchi laboratory from Ibaraki University) got an average ratio of 80.73/100
  github.com/Harulabo/pace2018

Eleven more teams participated in this track but did not finalize their submission by sharing a link to their code. Table 3 shows that the second team (reko) was more often the one reporting a best solution. However, the first team (CIMAT Team) was more consistently very close to those best solutions.
- **1st place, 450 €:** Emmanuel Romero Ruiz, Emmanuel Antonio Cuevas, Irwin Enrique Villalobos López, and Carlos Segura González (CIMAT Team from the Center for Research in Mathematics, Guanajuato) got an average ratio of 99.93/100
  github.com/HeathcliffAC/SteinerTreeProblem

- **2nd place, 350 €:** Thorsten Koch and Daniel Rehfeldt (team reko from Zuse Institute Berlin and TU Berlin) got an average ratio of 99.85/100
  github.com/dRehfeldt/scipjack/

- **3rd place, 300 €:** Martin Josef Geiger (team MJG from HSU Hamburg) [26] got an average ratio of 99.80/100
  https://data.mendeley.com/datasets/yf9vpkgwdr/1

- **4th place, 225 €:** Radek Hušek, Tomáš Toufar, Dušan Knop, Tomáš Masařík, and Eduard Eiben (team CUiB from Charles University, Prague and University of Bergen) got an average ratio of 99.72/100
  github.com/goderik01/PACE2018

- **5th place:** Emmanuel Arrighi and Mateus de Oliveira Oliveira (team Gardeners from ENS Cachan and University of Bergen) got an average ratio of 98.93/100
  github.com/SteinerGardeners/TrackC-Version1

- **6th place:** Krzysztof Kiljan, Dominik Klemba, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Mateusz Radecki, and Michał Ziobro (team UWarsaw from University of Warsaw and Jagiellonian University) got an average ratio of 98.27/100
  https://bitbucket.org/marcin_pilipczuk/pace2018-steiner-tree

- **7th place:** Stéphane Grandcolas (team SGLS from LIS Marseille) got an average ratio of 97.54/100
  http://www.dil.univ-mrs.fr/~gcolas/sgls.c

- **8th place:** Max Hort, Marciano Geijselaers, Joshua Scheidt, Pit Schneider, and Tahmina Begum (team JMMPT from the Department of Data Science and Knowledge Engineering, Maastricht University) got an average ratio of 97.15/100
  github.com/maxhort/Pacechallenge-TrackC/

- **9th place:** Dimitri Watel and Marc-Antoine Weisser (team DoubleDoubleU from SAMOVAR-ENSIHE and LRI-Centrale-Supelec) got an average ratio of 96.92/100
  github.com/mouton5000/PACE2018/

- **10th place:** R. Vijayaragunathan, N. S. Narayanaswamy, and Rajesh Pandian M. (team Resilience from TCS Lab and the Indian Institute of Technology Madras) got an average ratio of 94.57/100
  github.com/mrprajesh/pace2018

- **11th place:** Sharat Ibrahimpur (team the65thbit from University of Waterloo) got an average ratio of 94.37/100
  github.com/sharat1105/PACE2018

- **12th place:** Saket Saurabh, P. S. Srinivasan, and Prafullkumar Tale (team SSPSPT from the Institute Of Mathematical Sciences, HBNI, Chennai and the International Institute of Information Technology, Bangalore) got an average ratio of 82.61/100
  github.com/pptale/PACE18

- **13th place:** Harumi Haraguchi, Hiroshi Arai, Shiyougo Akiyama, and Masaki Kubonoya (team Haraguchi laboratory from Ibaraki University) got an average ratio of 80.73/100
  github.com/Harulabo/pace2018

Eleven more teams participated in this track but did not finalize their submission by sharing a link to their code. Table 3 shows that the second team (reko) was more often the one reporting a best solution. However, the first team (CIMAT Team) was more consistently very close to those best solutions.
<table><caption>**Table 3** For the first four teams: their final score, how many times they computed the best solution, and how many times their solution is *x%* close to the best solution, on the private set.</caption><thead><tr><th>Team name</th><th>Cumul. ratio</th><th># Best</th><th># ≤ 0.1%</th><th># ≤ 0.5%</th><th># ≤ 1%</th><th># ≤ 2%</th><th># ≤ 3%</th></tr></thead><tbody><tr><td>CIMAT Team</td><td>99.93</td><td>34</td><td>49</td><td>95</td><td>100</td><td>100</td><td>100</td></tr><tr><td>reko</td><td>99.85</td><td>78</td><td>81</td><td>88</td><td>93</td><td>99</td><td>100</td></tr><tr><td>MJG</td><td>99.80</td><td>24</td><td>58</td><td>87</td><td>95</td><td>98</td><td>100</td></tr><tr><td>CUiB</td><td>99.72</td><td>19</td><td>48</td><td>82</td><td>89</td><td>97</td><td>100</td></tr></tbody></table>

# 5 PACE organization

In September 2018, the PACE 2018 Program Committee transferred to the Steering Committee. The Steering Committee and the PACE 2018 Program Committee are as follows.

<table><tbody><tr><td rowspan="10">Steering committee:</td><td>Édouard Bonnet</td><td>ENS Lyon</td></tr><tr><td>Holger Dell</td><td>Saarland Informatics Campus</td></tr><tr><td>Thore Husfeldt</td><td>ITU Copenhagen & Lund University</td></tr><tr><td>Bart M. P. Jansen (chair)</td><td>Eindhoven University of Technology</td></tr><tr><td>Petteri Kaski</td><td>Aalto University</td></tr><tr><td>Christian Komusiewicz</td><td>Philipps-Universität Marburg</td></tr><tr><td>Frances A. Rosamond</td><td>University of Bergen</td></tr><tr><td>Florian Sikora</td><td>Paris-Dauphine University</td></tr><tr><td rowspan="2">Track A, B, C:</td><td>Édouard Bonnet</td><td>ENS Lyon</td></tr><tr><td>Florian Sikora</td><td>Paris-Dauphine University</td></tr></tbody></table>

The Program Committee of PACE 2019 will be chaired by Johannes Fichte (TU Dresden) and Markus Hecher (TU Vienna).

# 6 Conclusion

We thank all the participants for their enthusiasm and look forward to the next PACE. We are particularly happy that this edition attracted many people outside the parameterized complexity community, and wish that this will continue for the future editions.

We welcome anyone who is interested to add their name to the mailing list on the website [36] to receive PACE updates and join the discussion. In particular, plans for PACE 2019 will be posted there.

# References

1 Michael Abseher, Nysret Musliu, and Stefan Woltran. htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond. In Domenico Salvagnin and Michele Lombardi, editors, *Proceedings of the 14th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR '17)*, volume 10335 of *Lecture Notes in Computer Science*, pages 376-386. Springer, 2017. doi:10.1007/978-3-319-59776-8_30.

2 Max Bannach and Sebastian Berndt. Practical Access to Dynamic Programming on Tree Decompositions. In *26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland*, pages 6:1-6:13, 2018. doi:10.4230/LIPIcs.ESA.2018.6.