A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II

We sketch the reduction for distance to path from the $𝖶[\mathrm{𝟣}]$-hard Multicolored Clique Problem (MCP) [25, 44]. In MCP the input is a graph $G$ whose vertex set is partitioned into $k$ color classes $V_1,\mathrm{\dots },V_k$ with $V_i:=\{v_1^i,\mathrm{\dots },v_q^i\}$ for all $i\in [k]$. MCP asks whether there is a clique in $G$ containing exactly one vertex per color class. Given an instance of MCP, we construct a graph $G^{\prime }$ using the following gadgets (see Figure 2):

Selection Gadget

For every color class $i\in [k]$, we have a selection gadget consisting of a vertex ${\widehat{t}}^i$ and a path $X^i$ that contains for every $v_p^i\in V_i$ a vertex $x_p^i$. These vertices are ordered by their index $p$ and after every vertex $x_p^i$ (and, thus, before $x_{p+1}^i$) there is a vertex ${\widehat{x}}_p^i$ in that path. The vertex ${\widehat{t}}^i$ is adjacent to all vertices in the path $X^i$.

Verification Gadget

For each pair $i,j\in [k]$ with , we have a verification gadget consisting of a vertex ${\widehat{d}}^{i,j}$ and a path $W^{i,j}$ containing for every edge $v_p^i{v}_r^j\in E(G)$ a vertex $w_{p,r}^{i,j}$ in arbitrary order. The vertex ${\widehat{d}}^{i,j}$ is adjacent to all vertices in the path $W^{i,j}$.

We order the subpaths described in the selection and verification gadgets as follows:

The last vertex of one of the paths is adjacent to the first vertex of the succeeding path and, thus, they form one large path $\mathrm{\Psi }$ in $G^{\prime }$. Furthermore, $G^{\prime }$ contains vertices $s^1$ and ${\widehat{s}}^1$ that are adjacent to all vertices in $X^1$. For every $i\in [k]$ with $i>1$, $G^{\prime }$ contains vertices $s^i$ and ${\widehat{s}}^i$ that are adjacent to all vertices in $X^i$ and $X^{i-1}$. For all $i,j\in [k]$ with , the graph contains vertices $c^{i,j}$ and ${\widehat{c}}^{i,j}$ that are adjacent to all vertices in $W^{i,j}$ and to all vertices in the path preceding $W^{i,j}$ in the ordering described above. Finally, $G$ contains a vertex $z$ that is adjacent to all vertices in $W^{k-1,k}$ and to ${\widehat{s}}^1$. As there are $𝒪(k^2)$ vertices in $G^{\prime }$ that are not part of the path $\mathrm{\Psi }$, the distance to path of $G^{\prime }$ is $𝒪(k^2)$.

We define $Y$ as the set containing all the vertices defined above that have a hat in their name, i.e., . The partial order $\pi$ is the reflexive and transitive closure of the following constraints:

1. (P1)

   $s^1\prec v$ for all $v\in V(G^{\prime })\setminus \{s^1\}$,

2. (P2)

   $z\prec y$ for all $y\in Y$,

3. (P3)

   $x_p^i\prec w_{p,r}^{i,j}$ for all $i,j\in [k]$ with and all $p,r\in [q]$ with $v_p^i{v}_r^j\in E(G)$

4. (P4)

   $x_r^j\prec w_{p,r}^{i,j}$ for all $i,j\in [k]$ with and all $p,r\in [q]$ with $v_p^i{v}_r^j\in E(G)$

Every $\pi$-extending Hamiltonian path has to visit exactly one vertex in each $X^i$ and $W^{i,j}$ on its way from $s^1$ to $z$ as all the vertices with hats cannot be visited before $z$. Due to the constrains (P3) and (P4), a vertex of $W^{i,j}$ corresponding to an edge $v_p^i{v}_r^j$ can only be visited if both $x_p^i$ and $x_r^j$ have already been visited. Therefore, we only can reach $z$ if the visited vertices of the selection gadgets form a a multicolored clique of $G$.

Conversely, a multicolored clique implies that we can reach $z$ from $s^1$ using such a path. We can visit the remaining vertices by traversing the path $\mathrm{\Psi }$ and using ${\widehat{c}}^{i,j},{\widehat{d}}^{i,j},{\widehat{s}}^i$ and ${\widehat{t}}^i$ outside of $\mathrm{\Psi }$ to jump over vertices that have already been visited. For details see the full version [6]. For distance to linear forest modules we can adapt the construction by deleting the edges between consecutive gadgets since these edges have not been used in the proof. The resulting graph has distance to linear forest modules $𝒪(k^2)$. $◀$

We only sketch the idea of the algorithm as it is a quite straightforward adaption of Algorithm 2 in [7]. For details, we refer to that publication. First note that an induced subgraph does not have more inner vertices for a fixed embedding. Hence, it suffices to deal with 2-connected graphs (Theorem 5.1 in [7]). Let $C=(v_0,\mathrm{\dots },v_{\mathrm{\ell }})$ be the outer face of the planar embedding and let $W$ be the set of vertices that are not on the outer face. Since $G$ is 2-connected, the face $C$ forms a cycle. Furthermore, let $c$ be the cost function on the edges of $G$.

The idea of Algorithm 2 in [7] is to use a dynamic programming approach. To this end, the authors consider tuples $(a,b,\omega )$, which represent prefixes of Hamiltonian paths. Here, $a$ and $b$ are the indices of the endpoints of the interval on $C$ associated with that prefix (see Lemma 5.2 in [7]) and $\omega$ is either 1 or 2 depending on whether the prefix ends in $v_a$ or $v_b$. For the problem considered here, we simply need to adjust these to tuples of the form $(a,b,X,t)$, where $a$ and $b$ again represent the indices of the endpoints of the interval on $C$ associated with the prefix, $X\subseteq W$ is the set of inner vertices in the prefix and $t$ forms the endpoint of the prefix. There are at most $n^2$ intervals and at most $2^k$ subsets of $W$. The endpoint $t$ either has to be a vertex of $X$ or one of the vertices $v_a$ and $v_b$. Therefore, there are at most $(k+2)$ endpoints and the total number of tuples is bounded by $2^k(k+2)n^2$. Similar as in Algorithm 2 of [7], we compute for every tuple $(a,b,X,t)$ the minimal cost $M(a,b,X,t)$ of an ordered path $𝒫$ of $G$ fulfilling the following properties (or $\mathrm{\infty }$ if no such path exists):

1. (i)

   $𝒫$ consists of the vertices in the interval between $v_a$ and $v_b$ of $C$ and in the set $X$,

2. (ii)

   $𝒫$ is a prefix of a linear extension of $\pi$,

3. (iii)

   $𝒫$ ends in $t$.

This is done inductively by the size of $𝒫$. Let $a^{\prime }$, $b^{\prime }$, and $X^{\prime }$ be the updated values if $t$ is removed from the potential prefix. We first have to check whether $t$ is minimal in $\pi$ if all the vertices of $[a^{\prime },b^{\prime }]$ and $X^{\prime }$ have been visited. This costs $𝒪(n)$ time. If this is not the case, we set the $M$-value to $\mathrm{\infty }$. Otherwise, we check the $M$-values for all possible vertices $t^{\prime }$ that are before $t$ in the prefix. Note that $t^{\prime }$ can only be an element of $X^{\prime }$ or one of the two vertices $v_{a^{\prime }}$ and $v_{b^{\prime }}$, due to Lemma 5.2 in [7]. For each choice of $t^{\prime }$ we compute the value $M(a^{\prime },b^{\prime },X^{\prime },t^{\prime })+c(t{t}^{\prime })$ and set the $M$-value of $(a,b,X,t)$ to the minimum of these values. Note that this can be done in $𝒪(k)\subseteq 𝒪(n)$ time using an adjacency matrix.

Summing up, for each of the $𝒪(2^{k}k{n}^2)$ tuples we need $𝒪(n)$ time which leads to the overall running time of $𝒪(2^{k}k{n}^3)$. The proof of the correctness of the algorithm follows along the lines of the proof of Theorem 5.3 in [7]. $◀$

The idea of that algorithm can also be used to give an $\mathrm{𝖷𝖯}$ algorithm for distance to outerplanar. The crucial difference in the complexity is based on the fact that there is not only one interval of the outer face used by a prefix of a Hamiltonian path but at most $k+1$. To prove this, we need the following definitions.

Let $C$ be a closed walk of a plane graph $G$. A subgraph $H$ lies inside of $C$ if all vertices and edges of $H$ are elements of $C$ or are placed in a bounded region of ${ℝ}^2\setminus C$. The subgraph $H$ lies strictly inside of $C$ if it lies inside of $C$ and does not contain a vertex of $C$. A subgraph $H$ lies outside of $C$ if all vertices and edges of $H$ are elements of $C$ or are placed in the unbounded region of ${ℝ}^2\setminus C$.

We use induction over the number of vertices of $G$. For one vertex the statement is trivial. Assume that the statement holds for all graphs with less than $n$ vertices. Let $G$ be a graph with $n$ vertices and a set $W\subseteq V(G)$ of size $k$ such that $G-W$ is planar. Let $C$ be a face of a planar embedding of $G-W$. Note that $C$ could be a closed walk with repeating vertices, for example, the outer face of a graph that is not 2-connected. To simplify the notation, we assume that $C$ does not repeat vertices. By tweaking the definitions, the other case can be proven analogously.

Let $P$ be a prefix of a Hamiltonian path $𝒫$ of $G$ that does not contain all vertices of $𝒫$. Let $𝒮$ be the smallest partition of $V(C)\cap V(P)$ into intervals of $C$, i.e., the intervals are inclusion-maximal. See Figure 3 for an illustration. Let $|𝒮|=\mathrm{\ell }$. If we remove the elements of $C$ from $P$, we get pairwise disjoint subpaths of $P$ and the endpoints of these subpaths have neighbors on $P$ that lie on $C$. We ignore the subpath that contains all vertices before the first vertex of $C$ on $P$ if it exists and the subpath containing all vertices after the last vertex of $C$ on $P$ if it exists. We also ignore all subpaths where the neighbor of the first and the last vertex lie on the same interval of $𝒮$. Thus, we only consider subpaths that connect two intervals of $𝒮$. As all intervals of $𝒮$ have to be connected via such paths, there are at least $\mathrm{\ell }-1$ of these subpaths. If each of these subpaths contains a vertex of $W$, then $\mathrm{\ell }\le k+1$ and we are done. Otherwise, consider a subpath $P_{\text{sub}}$ that does not contain vertices of $W$. We define the crest induced by $P_{\text{sub}}$ as the subpath of $P$ containing $P_{\text{sub}}$ and the $P$-neighbors of its endpoints. Let $Q$ be such a crest. Let $v_i$ be the first vertex and $v_j$ be the last vertex of $Q$ with regard to the ordering of $P$. By definition, both $v_i$ and $v_j$ lie on $C$. We define $C[v_i,v_j]$ as the part of $C$ between $v_i$ and $v_j$ in the cyclic ordering and $C[v_j,v_i]$ as the part of $C$ between $v_j$ and $v_i$ in the cyclic ordering. Further note that $v_i$ and $v_j$ lie in different intervals of $𝒮$. Therefore, there are vertices not in $P$, both in $C[v_i,v_j]$ and in $C[v_j,v_i]$. Let $t$ be the end vertex of $P$ or, in case this end vertex is $v_j$, let $t$ be the successor of $v_j$ in the Hamiltonian path $𝒫$. Note that $t$ exists as $P$ does not contain all vertices of $𝒫$. W.l.o.g. we may assume that $t$ lies outside of $\tilde{Q}=Q\cup C[v_i,v_j]$. If this is not the case, then we define one face inside of $\tilde{Q}$ as outer face without changing the faces of the embedding. Then, we can consider $Q\cup C[v_j,v_i]$ as $\tilde{Q}$.

Let $R$ be a minimal crest inside of $\tilde{Q}$, i.e., there is no crest that lies inside of $\tilde{R}=R\cup C[x,y]$, where $x$ and $y$ are the endpoints of $R$ and $C[x,y]$ is the part of $C$ between $x$ and $y$ that is inside of $\tilde{Q}$. Note that $C[x,y]$ contains vertices that are not part of $P$ as the crest $R$ connects two intervals, say $S_x$ and $S_y$ where $x\in S_x$ and $y\in S_y$.

We will now show that we can always find either a vertex to delete or an edge to contract in order to apply the induction hypothesis.

Assume that there is an edge $ab\in E(P)$ such that w.l.o.g. $b$ is strictly inside of $\tilde{R}$. We contract the edge $ab$ in $G$ and $P$. The resulting graph $G^{\prime }$ and resulting path $P^{\prime }$ fulfill the induction hypothesis, i.e., $W\subseteq V(G^{\prime })$, $P^{\prime }$ is a prefix of a Hamiltonian path of $G^{\prime }$ and $C$ is a face of an embedding of $G^{\prime }$. Therefore, we can partition $V(C)\cap V(P^{\prime })$ into at most $k+1$ intervals of $C$. These intervals map bijectively to intervals of $V(C)\cap V(P)$. Hence, we can assume that $P$ does not contain any vertices strictly inside of $\tilde{R}$.

Suppose there is an interval $S\in 𝒮$ that is contained completely in $C[x,y]-\{x,y\}$. As $\tilde{R}$ separates $S$ from the vertices outside of $\tilde{R}$ and no vertices in $P$ are strictly inside of $\tilde{R}$, all $P$-neighbors of vertices of $S$ are either in $S$ or in $W$. As $t$ lies outside of $\tilde{R}$, the interval $S$ has at least one $P$-neighbor in $W$. If $S$ has exactly one $P$-neighbor $w\in W$ – i.e. $P$ starts with $S$ – then we delete $w$ and the whole interval $S$ and connect the neighbors of $S$ on $C$ with an edge. This gives a graph $G^{\prime }$ with one less vertex in $W$ and one less interval. The suffix of $P$ that starts at the successor of $w$ is a prefix of a Hamiltonian path in $G^{\prime }$. The statement follows by induction.

Suppose $S$ has more than one $P$-neighbor in $W$. We connect these neighbors to form a clique. Furthermore, we sort them by their appearance in $P$ and contract the last and the penultimate vertex of these neighbors. As $t$ lies outside of $\tilde{R}$, the last neighbor of $S$ cannot be used to enter $\tilde{R}$. Therefore, all vertices visited in $P$ between these two neighbors lie in $S$. We now delete $S$ and connect its neighbors on $C$ with an edge. We can transform $P$ into $P^{\prime }$ by replacing a sequence of $S$-vertices between two $P$-neighbors of $S$ by one of the clique edges. The statement follows by induction as there is one vertex less in $W$ and one interval less, see Figure 4.

If there is no interval that is contained completely in $C[x,y]-\{x,y\}$, then all vertices on $C[x,y]$ are either in $S_x$, $S_y$ or not in $P$. In this case, we can apply similar arguments to contract the vertices that are not in $P$ and, thus, join $S_x$ and $S_y$ to reduce the number of intervals. The details can be found in the full version [6]. $◀$

Using this lemma, we can adapt the algorithm given in Theorem 3.3 such that it solves the MinPOHPP in $\mathrm{𝖷𝖯}$ time for distance to outerplanar. This adaption is rather straightforward. In the dynamic program, we replace the vertices representing the single interval on $C$ by a set of at most $k+1$ intervals. It is not difficult to observe that the number of those sets is bounded by $n^{𝒪(k)}$. This leads to the following running time bound.

We reduce from a special case of the Alternating Linear Extension Problem that was introduced and shown to be $\mathrm{𝖭𝖯}$-complete in [7]. In this case of the problem, we are given two non-empty disjoint sets $A$ and $B$ with $|A|=|B|$ and a partial order $\pi \subseteq A\times B$ and we ask for a linear extension of $\pi$ that alternates between elements of $A$ and $B$ starting in some vertex of $A$.

Let $(A,B,\pi )$ be an instance of this problem with $A=\{a_1,\mathrm{\dots },a_n\}$ and $B=\{b_1,\mathrm{\dots },b_n\}$. We build a graph $G$ as follows (see Figure 5 for an illustration). The vertex set of $G$ is the disjoint union of $A$, $B$, $X=\{x_1,\mathrm{\dots },x_n\}$, $Y=\{y_1,\mathrm{\dots },y_n\}$, and $Z=\{z_1,\mathrm{\dots },z_n\}$. The graph $G$ contains all edges except for those between $X$ and $B$, between $X$ and $Y$ as well as those between $Y$ and $A$. In other words, the edges of $G$ can be covered by the three cliques $C_1=A\cup X\cup Z$, $C_2=A\cup B\cup Z$, and $C_3=B\cup Y\cup Z$.

The partial order ${\pi }^{\prime }$ contains all tuples of $\pi$. Additionally, it fixes $x_1$ as start vertex and contains the following chain of constraints: $x_1\prec y_1\prec z_1\prec x_2\prec y_2\prec z_2\mathrm{\cdots }\prec x_n\prec y_n\prec z_n$.

Assume the instance $(A,B,\pi )$ has an alternating linear extension $\sigma$. W.l.o.g. we may assume that $\sigma =(a_1,b_1,a_2,b_2,\mathrm{\dots },a_n,b_n)$. Inserting $x_i$ before $a_i$ and $(y_i,z_i)$ after $b_i$ leads to a ${\pi }^{\prime }$-extending Hamiltonian path and cycle of $G$.

Conversely, assume we have a ${\pi }^{\prime }$-extending Hamiltonian path $𝒫$ in $G$. We observe that $𝒫$ uses one vertex of $A$ and one vertex of $B$ between $x_i$ and $y_i$ as all vertices $z_j$ with are to the left of $x_i$ and all vertices $z_j$ with $j\ge i$ are to the right of $y_i$. Since $X$ and $Y$ have the same size as $A$ and $B$, we have to use exactly one vertex of $A$ and one of $B$ between every $x_i$ and $y_i$. Thus, $𝒫$ contains an alternating linear extension of $\pi$. $◀$

We have to leave open the case of edge clique cover number 2. However, we can observe that the graph $G$ constructed in the proof of Theorem 4.1 has clique cover number 2 since the cliques $C_1$ and $C_3$ cover all vertices. This implies the following result.

Note that for graphs of clique cover number 1 (i.e., cliques), POHPP and POHCP are trivial as every linear extension of $\pi$ induces a Hamiltonian cycle.

It follows from Theorem 3.1 that POHPP and POHCP are $𝖶[\mathrm{𝟣}]$-hard when parameterized by distance to block. Here, we extend this result to distance to clique.

As for Theorem 3.1, we use a reduction from Multicolored Clique to POHPP and then use Observation 2.1 to derive $𝖶[\mathrm{𝟣}]$-hardness also for POHCP. Let $G$ be an instance of MCP with color classes $V_1,\mathrm{\dots },V_k$ where $V_i=\{v_1^i,\mathrm{\dots },v_q^i\}$. The construction works similar as for Theorem 3.1. The main difference is how we encode the selection of a vertex from a color class. While in the proof of Theorem 3.1 the representative of the selected vertex was visited, here we visit all representatives except from the one of the selected vertex.

We construct a graph $G^{\prime }$ using the following gadgets:

Selection Gadget

For every color class $i\in [k]$, we have a clique $X^i$ that contains for every $v_p^i\in V_i$ a vertex $x_p^i$.

Verification Gadget

For each pair $i,j\in [k]$ with , we have a clique $W^{i,j}$ containing for every edge $v_p^i{v}_r^j\in E(G)$ a vertex $w_{p,r}^{i,j}$.

Next we describe how these gadgets are connected to each other (see Figure 6). The union of the selection gadgets and the verification gadgets forms one large clique. We order the subcliques described in the selection and verification gadgets as follows:

We have the following additional vertices in $G^{\prime }$. First, we have $s^1$, ${\widehat{s}}^1$, and ${\widehat{t}}^1$ that are adjacent to all vertices in $X^1$. For every $i$ with $2\le i\le k-1$, we have vertices $s^i$, ${\widehat{s}}^i$ and ${\widehat{t}}^i$. For $i=k$, we have only $s^i$ and ${\widehat{s}}^i$. Vertex $s^i$ is adjacent to all vertices in $X^i$ and $X^{i-1}$ and the vertices ${\widehat{s}}^i$ and ${\widehat{t}}^i$ are adjacent to all vertices in $X^i$. Furthermore, ${\widehat{s}}^i$ is adjacent to ${\widehat{t}}^{i-1}$. For all $i,j\in [k]$ with , there are vertices $c^{i,j}$ and ${\widehat{c}}^{i,j}$ that are adjacent to all vertices in $W^{i,j}$ and to all vertices in the clique to left of $W^{i,j}$ in the ordering described above. Finally, we have vertices $z$ and $\widehat{z}$ that are adjacent to all vertices in $W^{k-1,k}$. Furthermore, $z$ is adjacent to ${\widehat{s}}^1$. Observe that the graph $G^{\prime }$ without the selection and verification gadgets contains $3k+2\left(\genfrac{}{}{0pt}{}{k}{2}\right)+2$ vertices. Therefore, the distance to clique of $G^{\prime }$ is $𝒪(k^2)$.

The partial order $\pi$ is the reflexive and transitive closure of the following constraints.

1. (P1)

   $s^1\prec v$ for all $v\in V(G^{\prime })\setminus \{s^1\}$,

2. (P2)

   $v\prec \widehat{z}$ for all $v\in V(G^{\prime })\setminus \{\widehat{z}\}$,

3. (P3)

   $s^1\prec s^2\prec \mathrm{\cdots }\prec s^k$,

4. (P4)

   $z\prec {\widehat{s}}^1\prec {\widehat{t}}^1\prec {\widehat{s}}^2\prec {\widehat{t}}^2\prec \mathrm{\cdots }\prec {\widehat{s}}^k$,

5. (P5)

   $c^{i,j}\prec c^{i^{\prime },j^{\prime }}$ for all $i,j,i^{\prime },j^{\prime }\in [k]$ with or $i=i^{\prime }$ and ,

6. (P6)

   $c^{k-1,k}\prec z$,

7. (P7)

   $c^{i,j}\prec w_{p,r}^{i,j}$ for all $i,j\in [k]$ with and all $w_{p,r}^{i,j}\in W^{i,j}$,

8. (P8)

   $x_p^i\prec w_{r,s}^{i,j}$ for all $i,j\in [k]$ with and all $w_{r,s}^{i,j}\in W^{i,j}$ with $p\ne r$,

9. (P9)

   $x_p^j\prec w_{r,s}^{i,j}$ for all $i,j\in [k]$ with and all $w_{r,s}^{i,j}\in W^{i,j}$ with $p\ne s$.

First assume that there is a multicolored clique $\{v_{p_1}^1,\mathrm{\dots },v_{p_k}^k\}$ in $G$. Then we claim that there is $\pi$-extending Hamiltonian path in $G^{\prime }$. We start our path in $s^1$ and then we visit all the vertices in $X^1$ except for the vertex $x_{p_1}^1$. Then we visit $s^2$. We repeat this for all $i\in [k]$. Next we visit $c^{1,2}$. Now we visit $w_{p_1,p_2}^{1,2}$. Note that this is possible since all the vertices that have to be to the left of $w_{p_1,p_2}^{1,2}$ by (P8) and (P9) are already visited. Next we visit $c^{1,3}$ and afterwards $w_{p_1,p_3}^{1,3}$ which is possible for the same reason as mentioned above. We repeat this procedure until we reach $w_{p_1,p_k}^{1,k}$. Next, we visit $c^{2,3}$. The same procedure works until we reach $w_{p_{k-1},p_k}^{k-1,k}$. Next we visit $z$. Now, starting with $i=1$, we visit for all $i\in [k]$ the vertices ${\widehat{s}}^i$, followed by $x_{p_i}^i$ and ${\widehat{t}}^i$ until we reach $x_{p_k}^k$. Then, we visit ${\widehat{c}}^{1,2}$ followed by all remaining vertices $w_{p,r}^{1,2}\in W^{1,2}$ which is possible as all the left vertices in the constraints (P8) and (P9) have already been visited. We repeat this for all $i,j$ with in the lexicographic order and eventually we have visited all vertices in $W^{k-1,k}$. Finally, we visit $\widehat{z}$. It is easy to check that this Hamiltonian paths fulfills all constraints of $\pi$.

Now assume that there is a $\pi$-extending Hamiltonian path $𝒫$ in $G^{\prime }$. Let $i\in [k]$ be arbitrary. By (P4), ${\widehat{s}}^i$ is to the right of $z$. By (P2), ${\widehat{s}}^i$ is not the last vertex of $𝒫$ and, thus, it has two neighbors in $𝒫$. One of these two neighbors has to be in $X^i$. Therefore, for each $i\in [k]$, there is at least one vertex in $X^i$ that is to the right of $z$ in $𝒫$.

Using the constraints (P8) and (P9), we can observe that there can be at most one vertex of $W^{i,j}$ to the left of $z$ for every choice of $i$ and $j$ with . Otherwise, all vertices of $X^i$ and $X^j$ would be to the left of $z$ contradicting our observation above. This also implies that there is exactly one vertex of $W^{i,j}$ to the left of $z$ since $c^{i,j}$ has two neighbors in $𝒫$ and one of these neighbors has to be an element of $W^{i,j}$. The constraints (P8) and (P9) imply now that there can be at most one vertex of every $X^i$ to the right of $z$. Combining this with the existence of such a vertex shown above, we see that in every $X^i$ there is exactly one vertex $x_{p_i}^i$ to the right of $z$. Since there is a vertex of every $W^{i,j}$ to the left of $z$, it is not difficult to see that the set $\{v_{p_1}^1,\mathrm{\dots },v_{p_k}^k\}$ forms a multicolored clique in $G$.

The arguments above show that the graph $(G^{\prime },\pi )$ is a valid reduction. Since the distance to clique of $G^{\prime }$ is $𝒪(k^2)$ it also a proper $\mathrm{𝖥𝖯𝖳}$ reduction from MCP to POHPP parameterized by the distance to clique.

Similar as in Theorem 3.1, we can adapt the construction to show that POHPP is also $𝖶[\mathrm{𝟣}]$-hard for distance to cluster modules. To this end, we delete all the edges in $G^{\prime }$ between different gadgets. This works since these edges have not been used in the proof and since the resulting graph has distance to cluster modules $𝒪(k^2)$. $◀$

We consider all possible options for the start vertex of the Hamiltonian path and how the path traverses through the edges of $F$, i.e., we fix the set of edges $\widehat{F}\subseteq F$ that are used and also fix in which direction and in which order they are used. There are at most $k\cdot k!\cdot 2^k\cdot n$ many of these options. Let $\widehat{W}$ be the set of vertices incident to edges of $\widehat{F}$. Note that we only continue if every vertex in $\widehat{W}$ has at most two incident edges in $\widehat{F}$. Furthermore, the ordering on $\widehat{F}$ implies a vertex ordering $\sigma$ on $\widehat{W}$.

First, we check whether $\sigma$ is valid for $\pi$. If so, in the rest of the procedure for that option, we try to fill in all the other vertices of $G$. Whenever there are two consecutive vertices $x$ and $y$ in $\sigma$ that are not adjacent via an edge of $\widehat{F}$, we have to use edges of $G-F$. Since the path between the blocks of these vertices in the block-cut tree of $G-F$ is unique, we know which cut vertices have to be used on that path and we reserve these cut vertices for that path. The algorithm now traverses the ordering $\sigma$ and, if necessary, uses paths in $G-F$. These paths visit all vertices of a block that are possible due to $\pi$ except those that are reserved for later paths. The details can be found in the full version [6]. $◀$

Note that Dumas et al. [20] present a quadratic kernel for deciding whether the edge distance to block of a graph $G$ is at most $k$. This implies an $\mathrm{𝖥𝖯𝖳}$ algorithm with running time $k^{𝒪(k)}\cdot n^{𝒪(1)}$ that decides whether the edge distance to block is at most $k$. Calling this algorithm $𝒪(m)$ times, we can also construct the respective set $F$. This implies the following.

Next we give an $\mathrm{𝖷𝖯}$ algorithm for the (vertex) distance to block $k$. We can compute a set $W$ of size $\le k$ such that $G-W$ is a block graph in $n^{𝒪(k)}$ time. For each vertex of $W$, the algorithm fixes its predecessor and successor in a potential Hamiltonian path. This choice can be transferred to an instance of POHPP with edge distance to block $\le k$ with a fixed edge choice $\widehat{F}$. Then, it is sufficient to apply the subroutine of Theorem 4.4.

As we have seen in Theorem 4.3, there is no $\mathrm{𝖥𝖯𝖳}$ algorithm for distance to cluster modules unless $𝖶[\mathrm{𝟣}]=\mathrm{𝖥𝖯𝖳}$. However, we can give such an algorithm for distance to clique module.

Let $W\subseteq V(G)$ be a set of size $k$ such that $G-W$ is a clique module of $G$. Note that such a set can be computed in polynomial time since the largest clique module is equivalent to the largest set of vertices with the same closed neighborhood. We now consider every ordering $\sigma =(w_1,\mathrm{\dots },w_k)$ of the vertices in $W$ that fulfills the constraints of $\pi$. To decide whether $\sigma$ is an eligible choice, we have to check whether we can insert the vertices of $G-W$ into $\sigma$ in such a way that the result is a $\pi$-extending Hamiltonian path. Some of the vertices of $W$ may be secluded, i.e., they are not adjacent to any vertices in $G-W$. As secluded vertices have to induce subpaths in $\sigma$, we can contract them and only consider non-secluded vertices of $W$ in the following. By adapting the partial order, we prevent that some vertex of $G-W$ is added between the vertices of the edge that results from that contraction.

We try to insert vertices of $G-W$ into the ordering $\sigma$ as rightmost as possible, i.e., we try to only insert such a vertex into the gap between $w_{i-1}$ and $w_i$ if it is a predecessor of $w_i$ in $\pi$. However, it might be that $w_{i-1}$ and $w_i$ are not adjacent and all predecessors of $w_i$ in $G-W$ are already visited. Then we have to take some other vertex from $G-W$ between $w_{i-1}$ and $w_i$. For all $x\in V(G-W)$, we define $r(x)$ as the minimum index $j$ such that $x$ is to the left of $w_j$ in the partial order. Among all remaining vertices of $G-W$ that are allowed to be to the left of $w_i$, we take a vertex with minimal $r(x)$ value. The details of the algorithm and the proof of correctness can be found in the full version [6]. $◀$