Proof sketch. We only prove hardness of \((0,2)\)-3-\(\mathsf{SAT}\) to give an example of the application of [thm:dichotomy]. The other cases are proved similarly. The problem \((0,2)\)-3-\(\mathsf{SAT}\) is equivalent to \(\mathsf{SAT}(S)\) where \(S=\{R_0,R_1,R_2,R_3\}\) and \[\begin{align} R_0=\{(x,y,z)\in\{0,1\}^3: x+y+z\leq 2\} & R_1=\{(x,y,z)\in\{0,1\}^3: x+y-z\leq 1\}\\ R_2=\{(x,y,z)\in\{0,1\}^3: x-y-z\leq 0\} & R_3=\{(x,y,z)\in\{0,1\}^3: x+y+z\geq 1\}. \end{align}\] The relation \(R_i\) corresponds to a clause where exactly \(i\) variables are negated. In the following, functions are applied coordinate-wise as in the definition of polymorphisms. As \((0,0,0)\notin R_3\) and \((1,1,1)\notin R_0\), conditions  of [thm:dichotomy] are violated. As \({r_1=(1,0,0)\in R_3}\) and \(r_2=(0,1,0)\in R_3\), but \({f_\land(r_1,r_2)=(0,0,0)\notin R_3}\), condition  is violated. As \({r_3=(1,1,0)}\) and \({r_4=(0,1,1)}\) are in \(R_0\), but \({f_\lor(r_3,r_4)=(1,1,1)\notin R_0}\), condition  is violated. As the tuples \({r_5=(1,0,0)}\), \({r_6=(0,1,0)}\) and \(r_7=(0,0,1)\) are in \(R_3\), but \({\mathsf{majority}(r_5,r_6,r_7)=(0,0,0)}\) is not, condition  is violated. Finally, \({r_8=(0,1,1)}\), \({r_9=(1,0,1)}\) and \({r_{10}=(1,1,0)}\) are in \(R_0\), but \(\mathsf{minority}(r_8,r_9,r_{10})=(0,0,0)\) is not, so condition  is violated. By [thm:dichotomy], the problem \((0,2)\)-3-\(\mathsf{SAT}\) is \(\mathsf{NP}\)-complete. ◻

Proof.

The algorithm proceeds by iteratively replacing literals or clauses. In each step, the algorithm applies one of the rules displayed in 1 to simplify the current formula, replacing a clause with a smaller one or removing it entirely while assigning values to variables. Here, \(A\) and \(B\) denote different literals, \(C\) denotes a constant and \(X\) and \(Y\) are arbitrary literals or constants. The rules are only given up to permutation of their elements, i.e. \(A\lor\overline{A}\lor A\) is treated like \(A\lor A\lor \overline{A}\). The operation \(A/X\) replaces the literal \(A\) by \(X\) and the negated literal \(\overline{A}\) by \(\overline{X}\). The operation \(C/A\) is defined to be \(A/C\). Both \(1/1\) and \(0/0\) induce no operation and the operations \(1/0\) and \(0/1\) cause the algorithm to output unsatisfiable. Similarly, the operation \(A/\overline{A}\) causes the algorithm to output unsatisfiable.

The correctness of the presented rules is immediate. The first five rules exhaustively treat clauses of length three. The remaining rules treat the clause with length at most two. In each step, a clause is removed or a literal is removed from a clause, so the algorithm runs in polynomial time with respect to \(|\varphi|\). If the resulting formula is empty, the algorithm outputs satisfiable. Otherwise, it outputs the resulting formula. ◻

Proof.

2 gives a list of reduction rules that are the first phase of the algorithm. The notation is as in the proof of 1. If the resulting formula is empty, the algorithm outputs satisfiable. Otherwise, if it has not already been found that \(\varphi\) is not \((2,3)\)-satisfiable, the resulting formula contains the constant 1 at most once in every clause. The algorithm then replaces every occurrence of the constant 1 with a new variable \(Z\) to obtain \(\psi\). ◻

Proof. The witness-characterization of \(\mathsf{NP}\) implies membership of \((a,b,\alpha)\text{-}\mathsf{CCP}\) in \(\mathsf{NP}\). The reductions presented here are based on the constructions from [5], [6]. A notable difference is that the instances constructed here satisfy \(|C|=3\) for all \(C\in\mathcal{C}(D)\) whereas the instances of [5], [6] have color classes of arbitrary size. Our constructed graphs will only satisfy \(\alpha(D)\leq3\) at first, so there may initially be smaller color classes. However, this is not a problem: by iteratively adding vertices which are not reachable from \(s\), i.e. vertices with no incoming arcs, all color classes can be padded to size 3. Denote the result of padding the digraph \(D\) by \(D^+\).

The key elements of the reductions are the B-gadget [6] and the W-gadget [5], which correspond to the cases \(b\leq 2\) and \(b=3\), respectively. These gadgets have the property that any \((s,t)\)-path can contain at most one of two subpaths of a certain kind while satisfying the size constraints of \((a,b,3)\text{-}\mathsf{CCP}\). This allows the modeling of truth assignments by identifying one path with 0 and the other with 1 while introducing one gadget for each variable. First, fix \((a,b)\) with \(0\leq a\leq b\leq2\) and \(b\geq1\).

The B-gadget \(B[s,t,n_1,n_2]\) has vertex set \(V=\{s,t,y_0,\dots,y_{n_1},z_1,\dots,z_{n_2+1}\}\) and the following arcs: \(sy_0\dots y_{n_1}t\) and \(sz_1\dots z_{n_2+1}t\) are paths such that every vertex on the path dominates all vertices preceding it except for its direct predecessor and \(\{{y_0,\dots, y_{n_1}\}\rightarrow\{z_1,\dots,z_{n_2+1}}\}\). The vertices of the gadgets will be partitioned differently depending on \((a,b)\), so some of the arcs will be removed later. As an example, the B-gadget \(B[s,t,1,2]\) is visualized in 3.

We now specify the reduction. Let \(\varphi\) be a formula in 3-CNF. Apply 1 to determine if \(\varphi\) is \((a,b)\)-satisfiable or obtain the formula \(\psi\). In the first case, map \(\varphi\) to some fixed yes-instance or no-instance depending on whether it is satisfiable or not. Otherwise, let \(X_1,\dots,X_n\) be the variables of \(\psi\) and \(C_1,\dots,C_m\) be the clauses of \(\psi\). Let \(X_i\) occur \(p_i\) times as a literal and \(q_i\) times as a negated literal. For all \(i\) such that \(1\leq i\leq n\), we associate with \(X_i\) the B-gadget \(B^i\mathrel{\vcenter{:}}= B[s^i,t^i,p_i,q_i]\) and give each vertex in this gadget the superscript \(i\) to uniquely identify all vertices. The \(j\)-th occurrence of \(X_i\) as a positive (resp. negative) literal corresponds to \(y_j^i\) (resp. \(z_j^i\)). Denote by \(V_i\) the set of vertices associated with the literals of the clause \(C_i\). Identify \(t^i\) with \(s^{i+1}\) and add arcs such that \(B^j\Rightarrow B^i\) for all \(i\) and \(j\) such that \(i<j\). If \(b=2\), also add the vertices \(w_1,\dots,w_{2n+1}\) such that \(N^+(w_i)=\{w_{i+1}\}\) for all \(i\) such that \(1\leq i<2n+1\) and \(N^+(w_{2n+1})=\{s_1\}\). All vertices not in \(N^+(w_i)\) dominate \(w_i\). The color classes are defined as follows:

•  \(V_i\) is a color class for all \(1\leq i\leq m\).

•  \(\{y_0^i,z_{q_i+1}^i,w_i\}\) is a color class for all \(1\leq i\leq n\) (if \(b\neq2\), remove \(w_i\) from the set).

•  \(\{s_i,w_{n+i}\}\) is a color class for all \(1\leq i\leq n\). The same remark as above applies.

•  \(\{t_n,w_{2n+1}\}\) is a color class.

Remove all arcs between vertices in the same color class. Call the resulting SMD \(D\). Set \(s\mathrel{\vcenter{:}}= w_1\) if \(b=2\) and \(s\mathrel{\vcenter{:}}= s_1\) otherwise. Set \(t\mathrel{\vcenter{:}}= t_n\). We map \(\varphi\) to \((D^+,s,t)\). We now prove correctness of our reduction.

“\(\Rightarrow\)”: Let \(P\) be an \((s,t)\)-path witnessing that \((D^+,s,t)\) is a yes-instance. The vertex \(t^i\) separates \(B^i\) from \(B^{i+1}\), so \(B^1,\dots,B^n\) are traversed in this order in \(P\). In particular, \(P\) uses all of the vertices \(s_1,\dots,s_n\). As \(P\) satisfies the upper bound \(b\), it can only contain one element of \(\{y^i_0,z^i_{q_i+1}\}\) for any \(1\leq i\leq n\). If \(b=1\), this is immediate as these vertices are in the same color class. If \(b=2\), \(P\) starts with the subpath \(w_1\dots w_{2n+1}s_1\) and \(w_i\) is in the same color class as \(y^i_0\) and \(z^i_{q_i+1}\). Therefore, the size constraint of 2 for \(\{y^i_0,z^i_{q_i+1},w_i\}\) is effectively a size constraint of 1 for \(\{y^i_0,z^i_{q_i+1}\}\).

This implies that \(P\) contains either the subpath \(s^iy^i_0\dots y^i_{p_i}t^i\) or \(s^iz^i_1\dots z^i_{q_i+1}t^i\). The vertex \(s^i\) has only two positive neighbors, \(y^i_0\) and \(z^i_1\). If \(P\) contains \(z^i_j\), then \(z^i_j\dots z^i_{q_i+1}t^i\) is a subpath of \(P\) as \({N^+(z^i_j)\subseteq\{z^i_1,\dots,z^i_{j+1}\}}\) for all \(1\leq j\leq q_i\). This makes using an arc to a previous \(z\)-vertex impossible when trying to reach \(t^i\). Additionally, \(P\) cannot contain \(y^i_0\) and \(z^i_j\) for any \(j\) such that \(1\leq j\leq q_i+1\) as \(y^i_0\) and \(z^i_{q_i+1}\) are mutually exclusive. Therefore, \(P\) must contain the subpath \(s^iy_0^i\dots y^i_{p_i}t^i\) if it does not contain \(s^iz^i_1\dots z^i_{q_i+1}t^i\) as this is the only path from \(s^i\) to \(t^i\) that does not use any of the \(z^i_j\).

We construct an \((a,b)\)-satisfying assignment \(\sigma:\{X_1,\dots,X_n\}\to\{0,1\}\) in the following way: Set \({\sigma(X_i)\mathrel{\vcenter{:}}=1}\) if \(s^iy_0\dots y^i_{p_i}t^i\) is a subpath of \(P\), else set \(\sigma(X_i)\mathrel{\vcenter{:}}=0\). As the literals associated to the clause \(C_i\) form a color class in \(D^+\), this assignment sets at least \(a\) and at most \(b\) literals to \(1\) for each clause.

“\(\Leftarrow\)”: Let \(\sigma\) be an \((a,b)\)-satisfying assignment of \(\psi\). Let \(P_0=w_1\dots w_{2n+1}s_1\) if \(b=2\) and \(P_0=s_1\) if \(b\neq2\). For each \(1\leq i\leq n\), set \(P_i\mathrel{\vcenter{:}}= y_0\dots y^i_{p_i}t^i\) if \(\sigma(X_i)=1\) and \(P_i\mathrel{\vcenter{:}}= z^i_1\dots z^i_{q_i+1}t^i\) if \(\sigma(X_i)=0\). These paths exist in \(D^+\) as the literals in each clause are pairwise different so that none of the arcs of the paths are removed. Then \(P_0\dots P_n\) is an \((s,t)\)-path satisfying the cardinality constraints imposed by the parameters \((a,b)\).

This leaves the case \(b=3\) and \(a\in\{1,2\}\), both of which use the \(W\)-gadget. The prototypical \(W\)-gadget is visualized in 4. The \(W\)-gadget \(W[x,y,n_1,n_2]\) is then obtained from 4 by replacing \(s\) with \(x\), \(t\) with \(y\), \(T\) with a clique \(y_1,\dots,y_{n_1+1}\) and \(F\) with a clique \(z_1,\dots,z_{n_2+1}\). Here, a clique is a set of vertices where all possible arcs between any pair of different vertices exist. The arcs between the cliques and the remaining vertices are given by the arcs of 4.

Let \(\varphi\) be an instance of \((a,b)\)-3-\(\mathsf{SAT}\). If \(a=1\), set \(\psi\mathrel{\vcenter{:}}=\varphi\). If \(a=2\), apply 2 to determine if \(\varphi\) is \((2,3)\)-satisfiable or obtain the formula \(\psi\). In the first case, map \(\varphi\) to some fixed yes-instance or no-instance depending on whether it is satisfiable or not. Let \(X_1,\dots,X_n\) and \(C_1,\dots,C_m\) denote the variables and clauses of \(\psi\). Let \(p_i\) be the number of positive occurrences of \(X_i\) and \(q_i\) the number of its negative occurrences. Introduce a \(W\)-gadget \(W^i[s^i,t^i,p_i,q_i]\) for each \(1\leq i\leq n\). Give each vertex in \(W^i\) the superscript \(i\) to uniquely identify it. The \(j\)-th positive (resp. negative) occurrence of \(X_i\) is associated with \(y^i_j\) (resp. \(z^i_j\)). The vertices \(y^i_{p_i+1}\) and \(z^i_{q_i+1}\) are not associated to any literal. They ensure that the paths \(s^ia^iy^i_1\dots y^i_{p_i+1}b^it^i\) and \(s^ib^iz^i_1\dots z^i_{p_i+1}a^it^i\) exist even if \(p_i=0\) or \(q_i=0\). Denote the vertices associated to the literals of clause \(C_i\) by \(V_i\). Add arcs such that \(W_j\Rightarrow W_i\) and add the arc \(t_is_{i+1}\) for all \(i\) and \(j\) such that \(1\leq i<j\leq n\). The color classes are \(\{s^i,t^i\}\), \(\{a^i,b^i\}\), \(\{y^i_{q_i+1},z^i_{p_i+1}\}\) and \(V_i\) for all \(i\) such that \(1\leq i\leq n\). Remove arcs between vertices of the same color and call the resulting SMD \(D\). We map \(\varphi\) to \((D^+,s^1,t^n)\).

“\(\Rightarrow\)”: Let \(P\) be an \((s,t)\)-path witnessing that \((D^+,s^1,t^n)\) is a yes-instance. The crucial property of the \(W\)-gadget is that any \((s,t)\)-path cannot contain both \(F\) and \(T\). This was proven in [5] but can also be seen by inspecting 4. Replacing \(F\) and \(T\) with cliques does not change this fact. Set \(\sigma(X_i)\coloneq1\) if \(\{y^i_1,\dots,y^i_{p_i}\}\cap V(P)\neq\emptyset\) and \(\sigma(X_i)=0\) otherwise. As \(P\) contains at least \(a\) vertices from each \(V_i\), this assignment satisfies at least \(a\) variables from each clause, so \(\varphi\) is \((a,b)\)-satisfiable.

“\(\Leftarrow\)”: Let \(\sigma\) be an assignment witnessing that \(\varphi\) is \((a,b)\)-satisfiable. Let \(Q_i\) be a quasi-Hamiltonian path in \(D^+[y^i_1,\dots,y^i_{p_i}]\) if \(\sigma(X_i)=1\) and a quasi-Hamiltonian path in \(D^+[z^i_1,\dots,z^i_{q_i}]\) if \(\sigma(X_i)=0\). Set \({P_i=s^ia^iQ_ib^it^i}\) if \(\sigma(X_i)=1\) and \(P_i=s^ib^iQ_ia^it^i\) otherwise. Then \(P=P_1\dots P_n\) witnesses that \((D^+,s^1,t^n)\) is a yes-instance as \(\sigma\) satisfies at least \(a\) variables in every clause. In the case \(a=2\), the literals in each clause are pairwise different, so that each color class \(V_i\) will be hit twice. ◻

Proof. The witness-characterization of \(\mathsf{NP}\) implies membership of \((a,b,\alpha)\text{-}\mathsf{CCP}\) in \(\mathsf{NP}\). The hardness for \(\alpha=3\) follows from 1. We inductively prove hardness for \(\alpha+1>3\) assuming the statement for \(\alpha\). By padding all color classes with unreachable vertices, \((a,b,\alpha)\text{-}\mathsf{CCP}\) reduces to \((a,b,\alpha+1)\text{-}\mathsf{CCP}\). Additionally, changing the start vertex to a new vertex \(s'\) and forcing every \((s',t)\)-path to begin with a path covering one vertex from each color class whose final vertex can then only go to \(s\) shows that \((a,b,\alpha)\text{-}\mathsf{CCP}\) reduces to \((a+1,b+1,\alpha+1)\text{-}\mathsf{CCP}\). This is similar to how paths are prefixed in the first part of the proof of 1.

This leaves the cases \((0,\alpha,\alpha+1)\) and \((1,\alpha+1,\alpha+1)\). In the first case, the starting vertex of an instance of \((0,\alpha-1,\alpha)\text{-}\mathsf{CCP}\) may be modified such that one new vertex from each color class is hit before reaching the original start vertex to reduce \((0,\alpha-1,\alpha)\text{-}\mathsf{CCP}\) to \((0,\alpha,\alpha+1)\text{-}\mathsf{CCP}\). In the second case, the color classes of an instance of \((1,\alpha,\alpha)\text{-}\mathsf{CCP}\) may simply be padded with unreachable vertices to reduce \((1,\alpha,\alpha)\text{-}\mathsf{CCP}\) to \((1,\alpha+1,\alpha+1)\text{-}\mathsf{CCP}\). ◻

Proof. : In this situation, \(P\) is also an \((x,y)\)-quasi-Hamiltonian path in \(D\).

: The path \(P\) and \(v_0\dots v_izv_j\dots v_{\ell+1}\) can be merged using [lem:merging] to obtain the desired path.

: As we may assume that neither of the previous situations are applicable, \(|H(z)|=1\). Consider the case \(zy\in A\). As \(D\) is 2-strong, there exists a path from \(V(P)\) to \(z\) that does not contain \(y\). Let \(Q\) be a shortest such path and let its starting vertex be \(v_i\). Then \(P\) and \(v_0\dots v_{i-1}Qy\) can be merged using [lem:merging] to obtain the desired path. The case \(xz\in A\) is treated analogously by considering a shortest path from \(z\) to \(V(P)\) that does not contain \(x\). ◻

Proof. Clearly, \(D'\) contains an \((x,y)\)-path intersecting each element of \(\mathcal{C}(D)\) if \(D\) contains an \((x,y)\)-quasi-Hamiltonian path. Let \(P\) be an \((x,y)\)-path intersecting each element of \(\mathcal{C}(D)\) in \(D'\). If \(P\) does not use any of the additional arcs, there is nothing to prove, so assume \(P\) uses the new arc \(vu\). The case where \(P\) uses \(uv\) instead is symmetric. Let \(P_1\) and \(P_2\) be two internally disjoint \((x,y)\)-paths in \(D\). Because \(\{u,v\}\) is a separator of \(x\) and \(y\), one of the paths contains \(u\) and the other path contains \(v\). Without loss of generality, assume that \(P_1\) contain \(v\). Let \(w_1\) be the first vertex in \(P_1[v,y]\) from \(V(P[u,y])\) and let \(w_2\) be the last vertex in \(P_2[x,u]\) from \(V(P[x,v])\). Then \(V(P[x,v[)\) is disjoint from \(V(P_1]v,w_1])\) as otherwise \(\{u,v\}\) would not separate \(x\) and \(y\). Similarly, \(V(P]u,y])\) is disjoint from \(V(P_2[w_2,u[)\). Define \({Q_1\coloneq P[xv]P_1]v,w_1[P[w_1,y]}\) and \({Q_2\coloneq P[xw_2]P_2]w_2,u[P[u,y]}\). These paths only use arcs that are present in \(D\) and \(Q_1\cup Q_2\) does not contain a directed cycle. Applying [lem:merging] yields an \((x,y)\)-quasi-Hamiltonian path in \(D\). ◻

Proof. This is the most technical proof of the paper, so we first give a high-level overview before beginning the proof itself. Using the structure of the linear decomposition \(R_1,\dots,R_k\) of \(D-\{x,y,z\}\), we obtain an \((x,y)\)-quasi-Hamiltonian path \(P=v_0\dots v_{\ell+1}\) in \(D-z\) with [lem:non-strong]. By [prop:shortcut], it then only remains to integrate \(z\) into \(P\) to obtain an \((x,y)\)-quasi-Hamiltonian path in \(D\). We choose \(P\) as the longest possible quasi-Hamiltonian path with \(v_1\in R_1\) and \(v_\ell\in R_k\). A longest path is used as this restricts the arcs between vertices on \(P\) and vertices outside of \(P\) which simplifies the analysis. We first show that \(zv_2,v_{\ell-1}z\in A\) in [claim:second-vertex-arc-to-z]. Technically, [claim:second-vertex-arc-to-z] only shows \(v_2z\in A\). However, note that reversing all arcs in \(D\) and swapping the roles of \(x\) and \(y\) yields a graph that also satisfies the conditions of [thm:not-2-strong-without-xy]. Applying [claim:second-vertex-arc-to-z] to this reversed graphs yields \(v_{\ell-1}z\in A\).

The arcs \(zv_2\) and \(v_{\ell-1}z\) give a starting point for integrating \(z\) into the path \(P\): Find a way to skip over \(v_2\), then follow \(P\) to \(v_{\ell-1}\), go to \(v_2\) via \(z\) and find a way to reach \(y\) without using any of the previously visited vertices. Vertices from \(R_1\) and \(R_k\) often play a special role in this process. Vertices from \(R_1\) dominate all vertices from other linear components offering an opportunity to skip over \(v_2\). Similarly, vertices from \(R_k\) are dominated by all vertices from other linear components, so they are potential re-entry points into \(P\) from \(v_2\). The vertex \(v_l\) is not the only negative neighbor of \(y\) in \(D-x\). We call such vertices dominators. Dominators offer an alternative way to reach \(y\) from \(v_2\) that does not require going to \(v_l\). This is used when \(v_l\) is already required to skip over \(v_2\).

To prove [claim:second-vertex-arc-to-z], we show that an \((x,y)\)-quasi-Hamiltonian path exists if \(v_2\rightarrow z\). Under this assumption, there exists a positive neighbor \(u\) of \(z\) outside of \(P\) that lies in the same linear component \(R_\alpha\) as \(v_2\). In the case \(\alpha<k\), we use the idea of skipping over \(v_2\) and then going to \(v_l\) from \(v_2\) after moving through \(z\). In the case \(\alpha=k\), we use a dominator to get to \(y\) from \(v_2\).

After proving [claim:second-vertex-arc-to-z], we proceed with a case distinction depending on the index \(q\) of the first vertex of \(P\) in \(R_k\). When the vertex \(v_q\) is in the middle of the path, it is easy to integrate \(z\) into \(P\). Only the cases \(q\leq 3\) and \(\ell-1\leq q\) require deeper analysis. The main part of the proof deals with the case \(q\leq 3\), which is divided into two subcases. In the first subcase, \(P\) does not contain a dominator. We show that there either exists an \((x,y)\)-quasi-Hamiltonian path or a vertex of \(P\) can be replaced with a dominator. This replacement is carried out in a careful way so as to ensure that the new path also satisfies \(q\leq3\). This leads to the second subcase, in which \(P\) contains a dominator. We then show that an \((x,y)\)-quasi-Hamiltonian path exists in this subcase.

The case \(\ell-1\leq q\) is significantly restricted by another reversal argument: Unless the structure is very constrained, reversing all arcs results in a digraph that falls into one of the previously analyzed cases resulting in an \((x,y)\)-quasi-Hamiltonian path. A simple analysis then completes the proof.

We now begin with the proof. We may assume that \(H(x)\) and \(H(y)\) are singletons by adding the arcs \(vx\) or \(yv\) whenever necessary. This only makes finding an \((x,y)\)-QHP harder. Let \(R_1,\dots,R_k\) be the linear decomposition of \(D-\{x,y,z\}\). As \(D-x\), \(D-y\) and \(D-z\) are strong, \(x\), \(y\) and \(z\) each have a positive neighbor in \(R_1\) as well as a negative neighbor in \(R_k\). In particular, there is an \((x,y)\)-quasi-Hamiltonian path in \(D-z\) whose second vertex is in \(R_1\) and whose penultimate vertex is in \(R_k\) by [lem:non-strong]. Let \({P=v_0v_1\dots v_\ell v_{\ell+1}}\) be a longest path in \(D-z\) with these properties. By [prop:shortcut], we may assume that \(|H(z)|=1\) and that there exists a \(j\) with \(0<j<\ell+1\) such that \(\{v_{j+1},\dots,v_{\ell+1}\}\rightarrow z\rightarrow\{v_0,\dots,v_{j-1}\}\). Because \(D-\{x,y,z\}\) consists of at least 4 color classes, it follows that \(l\geq 4\).

By reversing all arcs in \(D\), we obtain a digraph \(D'\) which also satisfies the conditions of [thm:not-2-strong-without-xy]. Applying [claim:second-vertex-arc-to-z] to \(D'\) yields \(zv_{\ell-1}\in A(D')\), i.e. \(v_{\ell-1}z\in A\). The existence of the arcs \(zv_2\) and \(v_{\ell-1}z\in A\) implies \(zv_1,v_{\ell}z\in A\) by [prop:shortcut]. Let \(q\) be the minimal index such that \(v_q\) is in \(R_k\). Then \(\{v_1,\dots,v_{q-1}\}\Rightarrow R_k\). The vertices \(x\) and \(y\) are not a part of the linear decomposition and \(v_1\) lies in \(R_1\), so \(2\leq q\leq l\).

Case 1, \(3<q<\ell-1\): If \(v_1v_q\in A\), set \(a=q\), otherwise set \(a=q+1\). If \(v_{q-1}v_\ell\in A\), set \(b=q-1\), otherwise set \(b=q-2\). Then \(xv_1v_av_{a+1}\dots v_{\ell-1}zv_2v_3\dots v_bv_{\ell}y\) is an \((x,y)\)-quasi-Hamiltonian path in \(D\).

Case 2, \(q\leq3\): Recall that dominators are vertices in \(N^-(y)-\{x,v_\ell\}\). We distinguish the case where \(P\) contains a dominator and the case where \(P\) does not contain a dominator.

Case 2.1, \(V(P)\) does not contain any dominators: Let \(w\) be an arbitrary dominator. Assume that \(w\) only has positive neighbors in \(V(P)-y\). Let \(Q=v_i\dots w\) be a shortest path from \(V(P)\) to \(w\) in \(D-y\). Then \(Q\) must have internal vertices. If \(z\in V(Q)\), merging \(P\) and \(v_0\dots v_{i-1}Qy\) using [lem:merging] yields the desired path. Otherwise, \(v_0\dots v_{i-1}Qv_{i+1}\dots v_{\ell+1}\) or \(v_0\dots v_{i-1}Qv_{i+2}\dots v_{\ell+1}\) is a longer \((x,y)\)-quasi-Hamiltonian path in \(D-z\).

Now assume \(w\) has a negative neighbor in \(V(P)-y\). If \(zw\in A\), \(xv_1\dots v_{\ell}zwy\) is the desired path. If \(xw\in A\), \(xwzv_1\dots v_{\ell}y\) is the desired path. If \(v_1w\in A\), \(xv_1wzv_2\dots v_{\ell}y\) is the desired path. Let \(j\) be minimal with the property that \(wv_j\in A\) and there exists \(i<j\) such that \(v_iw\in A\). The value \(\ell+1\) satisfies this property, so \(j\) is well-defined. If \({H(v_{j-1})\neq H(w)}\), \(v_0\dots v_{j-1}wv_j\dots v_{\ell}y\) would be a longer \((x,y)\)-QHP in \(D-z\), so \(H(w)=H(v_{j-1})\). Minimality of \(j\) implies \(v_{j-2}w\in A\).

If \(j=3\), \(P'\coloneq v_0v_1wv_3\dots v_\ell y\) is an \((x,y)\)-quasi-Hamiltonian path in \(D-z\) of equal length. By [claim:second-vertex-arc-to-z], we may assume \(zw\in A\), which has already been excluded previously, a contradiction.

If \(3\neq j<\ell+1\), \(P'\coloneq v_0\dots v_{j-2}wv_j\dots v_{\ell}y\) is an \((x,y)\)-quasi-Hamiltonian path in \(D-z\) of equal length that contains a dominator. By a previous argument, \(w\rightarrow x\), so \(1\leq j-2\). As \(j\neq 3\), \(j\) must be at least four. Consequently, the path \(P'\) begins with the prefix \(xv_1v_2v_3\). In particular, one of the first four vertices of \(P'\) lies in \(R_k\). Additionally, the second vertex of \(P'\) is still \(v_1\in R_1\) and the penultimate vertex of \(P'\) remains \(v_\ell\in R_k\). Thus, we may restart the proof with \(P'\) instead of \(P\). The proof will then finish in case 2.2, so there is no circular reasoning.

If \(j=\ell+1\), \(xv_1v_{\ell}zv_2\dots v_{\ell-1}wy\) is the desired path unless \(H(v_1)=H(v_\ell)\). As the arc \(v_{\ell-1}w\) exists, \({w\in R_k}\). The previous analysis precludes the arc \(v_1w\), so \(H(v_1)=H(w)\). As \(D-y\) is 2-strong, \(w\) has a predecessor \(w'\neq v_{\ell-1}\). If \(w'=v_i\in V(P)\), then \({1<i<\ell-1}\) as \(w\Rightarrow\{x,v_1,v_\ell\}\). Thus, one of \(xv_1v_{i+1}\dots v_{\ell}zv_2\dots v_iwy\) or \(xv_1v_{i+2}\dots v_{\ell}zv_2\dots v_iwy\) is the desired path. Otherwise, \({w'\notin V(P)}\). There must be an arc between \(v_1\) and \(w'\). If \({v_1w'\in A}\), \(xv_1w'wzv_2\dots v_{\ell}y\) is an \((x,y)\)-QHP. Else, \(w'\in R_1\) and there exists a path \(Q'\) from \(v_1\) to \(w'\) in \(R_1\). If \({v_2\notin V(Q')}\), then \(xQ'wzv_2\dots v_{\ell}y\) is the desired path. Otherwise, \({v_2\in V(Q')\subseteq R_1}\) and \(xv_1v_3\dots v_{\ell-1}zv_2v_{\ell}y\) or \(xv_1v_4\dots v_{\ell-1}zv_2v_{\ell}y\) is the desired path.

Case 2.2, \(V(P)\) contains a dominator: Let \(1\leq i<l\) be maximal such that \(v_i\) is a dominator. We differentiate the cases \(i\neq1\) and \(i=1\). Assume \(i\neq 1\). Then one of \(xv_1v_{i+1}\dots v_{\ell}zv_2\dots v_iy\) or \(xv_1v_{i+2}\dots v_{\ell}zv_2\dots v_iy\) is the desired path unless \(H(v_1)=H(v_\ell)\) and \(i=\ell-1\). If there exists a \(j\) with \(2\leq j<\ell-1\) and \(v_jv_\ell\in A\), then \(xv_1v_{j+1}\dots v_{\ell-1}zv_2\dots v_jv_{\ell}y\) or \(xv_1v_{j+2}\dots v_{\ell-1}zv_2\dots v_jv_{\ell}y\) is the desired path. Otherwise, it follows that \(v_\ell\Rightarrow\{v_1,\dots,v_{\ell-2}\}\). As \(y\) is not contained in any 2-cycles, we obtain \(v_\ell\rightarrow \{y,z\}\), but \(D-x\) is 2-strong, so there exists a vertex \({u\in V-\{x,y,z,v_{\ell-1}}\}\) such that \(uv_\ell\in A\). Let \(Q=v_j\dots u\) be a shortest path from \(V(P)\) to \(u\) in \(D-\{y,v_\ell\}\). If \({z\in V(Q)}\), \(P[x,v_j[Qv_{\ell}y\) and \(P\) can be merged to obtain the desired path, so assume this is not the case. If \({j=l-2}\), then \(xv_1v_{\ell-1}zv_2\dots v_{\ell-3}Qv_{\ell}y\) is the desired path. If \({j=\ell-1}\), \(xv_1\dots v_{\ell-2}Qv_{\ell}y\) is a longer \((x,y)\)-QHP in \(D-z\), which is a contradiction. If \(j=0\), \(Qv_{\ell}zv_1\dots v_{\ell-1}y\) is the desired path. If \(0<j<l-2\), \(P[x,v_j[Qv_\ell v_{j+1}\dots v_{\ell-1}y\) is a longer \((x,y)\)-QHP in \(D-z\) unless \(H(v_{j+1})=H(v_\ell)\). Then \(xv_1v_{j+2}\dots v_{\ell-1}zP[v_2,v_j[Qv_{\ell}y\) is the desired path.

Now assume \(i=1\). As \(y\) has a positive neighbor in \(R_1\) and does not lie on a 2-cycle, \(|R_1|>1\). Additionally, \(R_1\) must be strong as otherwise \(N^-(v_1)\subseteq\{x,y,z\}\) which contradicts the fact that \(D-x\) is 2-strong and \(y\) does not lie on a 2-cycle. Let \(u\in R_1\cap N^+(v_1)\). Note the it may be that \(u=v_2\). If the arc \(uv_2\) exists, we obtain a longer \((x,y)\)-QHP in \(D-z\). If the arc \(v_2u\) exists, we obtain \(v_2\in R_1\) and one of \(xv_1v_3\dots v_{\ell-1}zv_2v_{\ell}y\), \(xv_1uv_3\dots v_{\ell-1}zv_2v_{\ell}y\), \(xv_1v_3\dots v_{\ell-1}zv_2uv_{\ell}y\) or \(xv_1v_4\dots v_{\ell-1}zv_2uv_{\ell}y\) is the desired path. Thus, there can be no arcs between \(v_2\) and \(u\), so \(H(u)=H(v_2)\). Then \(xv_1uv_3\dots v_{\ell}y\) is an \((x,y)\)-QHP in \(D-z\) with the same length as \(|P|\), so we may assume \(zu\in A\) by previous arguments. If \({H(u)\neq H(v_\ell)}\), one of \(xv_1v_3\dots v_{\ell-1}zuv_{\ell}y\) or \(xv_1v_4\dots v_{\ell-1}zuv_{\ell}y\) is the desired path, so we may assume this is not the case. Thus, the vertex \(u\) is a vertex in \(R_1\) with \(H(u)=H(v_\ell)\) that behaves similarly to \(v_2\) and potentially even is \(v_2\).

If there exists \(2\leq j<\ell-2\) such that \(v_jv_\ell\in A\), one of the paths \(xv_1v_{j+1}\dots v_{\ell-1}zv_2\dots v_jv_{\ell}y\) or \(xv_1v_{j+2}\dots v_{\ell-1}zv_2\dots v_jv_{\ell}y\) is the desired path. If there exists \(2\leq j<\ell-2\) with \({v_jz\in A}\), then one of the paths \(xv_1v_3\dots v_jzuv_{j+1}\dots v_{\ell}y\), \(xv_1v_4\dots v_jzuv_{j+1}\dots v_{\ell}y\), \(xv_1v_3\dots v_jzuv_{j+2}\dots v_{\ell}y\) or \(xv_1v_4\dots v_jzuv_{j+2}\dots v_{\ell}y\) is the desired path. Thus, assume no such \(j\) exists. As \(i=1\) is maximal, this implies \(\{y,z,v_\ell\}\Rightarrow\{v_2,\dots,v_{\ell-3}\}\). If the arc \(v_{\ell-2}v_\ell\) exists, one of \(xv_1v_{\ell-1}zv_2\dots v_{\ell-2}v_\ell y\) or \(xv_1uv_{\ell-1}zv_3\dots v_{\ell-2}v_\ell y\) is the desired path. Otherwise, it is impossible that \(R_k\subseteq\{v_2,\dots,v_\ell\}\) as the vertex \(v_{\ell-2}\) separates \(v_3\in R_k\) from \(v_1\) in \(D-x\) in this case contradicting the fact that \(D-x\) is 2-strong. Therefore, there exists \(w\in R_k-\{v_2,\dots,v_\ell\}\) such that \(wz\in A\) or \(wy\in A\). In the first case, \(xv_1wzv_2\dots v_{\ell}y\) or \(xv_1uwzv_3\dots v_{\ell}y\) is the desired path. Otherwise, \(z\rightarrow w\) and \(xv_1\dots v_{\ell}zwy\) is the desired path.

Case 3, \(3<\ell-1\leq q\): If \(|R_1\cap V(P)|>2\), reversing all arcs and applying the previous arguments to the reversal of \(P\) yields a \((y,x)\)-QHP in the reversed graph, i.e. the desired path in \(D\). Thus, we may assume that \(R_1\cap V(P)\subseteq\{v_1,v_2\}\). Assume \(v_1v_{\ell-1}\in A\). Then the path \(xv_1v_{\ell-1}zv_2\dots v_{\ell-2}v_{\ell}y\) or \(xv_1v_{\ell-1}zv_2\dots v_{\ell-3}v_{\ell}y\) is the desired path unless \(l=4\) and \({H(v_2)=H(v_4)}\). However, this is impossible as \(\chi(D-\{x,y,z\})\geq4\), so we may assume that \(v_1v_{\ell-1}\notin A\). This implies \(H(v_1)=H(v_{\ell-1})\) and \(l>4\). Then \(H(v_1)\neq H(v_{\ell-2})\), so \({v_1v_{\ell-2}\in A}\). If \(H(v_{\ell-3})\neq H(v_\ell)\), \(xv_1v_{\ell-2}v_{\ell-1}zv_2\dots v_{\ell-3}v_{\ell}y\) is the desired path. Otherwise, \({l>5}\) as \(\chi(D-\{x,y,z\})\geq4\), \(H(v_1)=H(v_{\ell-1})\) and \(H(v_{\ell-3})=H(v_\ell)\). Thus, the path \(xv_1v_{\ell-2}v_{\ell-1}zv_2\dots v_{\ell-4}v_{\ell}y\) is an \((x,y)\)-quasi-Hamiltonian path in \(D\). ◻

Proof. As this only makes finding an \((x,y)\)-QHP harder, we may assume that \(H(x)\) and \(H(y)\) are singletons by adding the arcs \(vx\) or \(yv\) whenever necessary while ensuring that \(y\rightarrow x\). If no 2-separators exist, we obtain the desired path by [thm:3-paths]. By [thm:not-2-strong-without-xy], we may assume that \(D-\{x,y\}\) is 2-strong. Let \(u,w\in V\) be a 2-separator of \(x\) and \(y\). Assume that \(uwu\) is a 2-cycle using 3. We will assume that \(N^-(y)=\{u,w\}\) as the case \(N^+(x)=\{u,w\}\) is symmetric.

Assume there is an arc from \(x\) to \(\{u,w\}\), without loss of generality let \(xu\in A\). If \(xw\in A\), let \(Q\) be a \([u,w]\)-QHP in \(D-\{x,y\}\) as given by [thm:weak-qhp]. [thm:weak-qhp] is applicable as we have \[\chi(D-\{x,y,u,w\})\geq\left\lceil\frac{|V|-4}{\alpha(D)}\right\rceil\geq6.\] Then \(xQy\) is the desired path. Otherwise, \(xw\notin A\). If there are 2 internally disjoint \((x,w)\)-paths in \(D-\{y,u\}\), there are 3 internally disjoint \((x,w)\)-paths of length at least 2 in \(D-y\) and so [thm:3-paths] yields an \((x,w)\)-QHP in \(D-y\) and with that an \((x,y)\)-QHP in \(D\). Thus, there exists \(r\in V-\{x,y,u,w\}\) such that \(\{u,r\}\) is a 2-separator of \(x\) and \(w\) in \(D-y\). As this is also a 2-separator of \(x\) and \(y\) in \(D\), it must be a trivial 2-separator, so \(N^+(x)=\{u,r\}\). By 3, we may assume \(uru\) to be a 2-cycle in \(D\). If \(rw\notin A\), there must be 2 internally disjoint \((r,w)\)-paths in \(D-\{x,y,u\}\) because all 2-separators of \(x\) and \(y\) are trivial. With the third path \(ruw\), this yields an \((r,w)\)-QHP in \(D-\{x,y\}\) through [thm:3-paths] and with that an \((x,y)\)-QHP in \(D\), so assume \(rw\in A\).

Set \(D'\coloneq D-\{x,y\}\). If \(D'-r\) contains a \([u,w]\)-QHP, we obtain the desired path, so assume this is not the case. Thus, one of the two conditions of [thm:weak-qhp] must apply as we have \[\chi(D-\{x,y,r,u,w\})\geq\left\lceil\frac{|V|-5}{\alpha(D)}\right\rceil\geq5.\] If the first condition applies, \(D'-\{r,u\}\) is not strong. As \(D'\) is 2-strong, there exists an \((r,u)\)-QHP \(Q\) in \(D'\) by [lem:not-2-strong] and \(xQy\) is the desired path. If the alternative condition applies, \({D'-\{r,w\}}\) is not strong and contains an \((r,w)\)-QHP in \(D'\) by a symmetric argument, which also leads to the desired path. This completes the proof if there is an arc from \(x\) to \(\{u,w\}\), so we may assume \(\{u,w\}\Rightarrow x\).

If there are 3 internally disjoint \((x,\{u,w\})\)-paths in \(D-y\), there are 3 internally disjoint \((x,u)\)-paths or 3 internally disjoint \((x,w)\)-paths of length at least 2, so [thm:3-paths] yields an \((x,y)\)-QHP. Therefore, we may assume that there are \(r,s\in V-\{x,y,u,w\}\) such that \(\{r,s\}\) is a 2-separator of \(x\) and \(\{u,w\}\). Then \(\{r,s\}\) also separates \(x\) and \(y\), so \({N^+(x)=\{r,s\}}\). As before, assume that \(srs\) is a 2-cycle in \(D\). If \(\{u,w\}\Rightarrow\{r,s\}\), then the fact that all \((x,y)\)-separators of size 2 are trivial implies that there are 3 internally disjoint \((\{r,s\},\{u,w\})\)-paths in \(D-\{x,y\}\). Thus, there are 3 internally disjoint \((v_0,v_1)\)-paths for some \(v_0\in\{r,s\}\) and \(v_1\in \{u,w\}\) in \(D-\{x,y\}\) completing the proof using [thm:3-paths]. Without loss of generality, assume that \(ru\in A\). If \(\{u,w\}\Rightarrow s\), there are 3 internally disjoint \((s,\{u,w\})\)-paths of length at least 2 in \(D-\{x,y\}\) because all 2-separators of \((x,y)\) are trivial, which again completes the proof through [thm:3-paths]. Thus, we may assume that \(su\in A\) or \(sw\in A\).

Consider the case \(su\in A\). If \(D-\{x,y,u\}\) contains an \([r,s]\)-QHP \(Q\), \(xQuy\) is the desired path. Otherwise, [thm:weak-qhp] implies that \(D-\{x,y,u,r\}\) or \(D-\{x,y,u,s\}\) is not strong. If \(D-\{x,y,u,r\}\) is not strong, [lem:not-2-strong] yields an \((r,u)\)-QHP \(Q\) in \(D-\{x,y\}\) as \(D-\{x,y\}\) is 2-strong. If \(D-\{x,y,u,s\}\) is not strong, [lem:not-2-strong] yields an \((s,u)\)-QHP \(Q\) in \(D-\{x,y\}\). In either case, \(xQy\) is the desired path. If \(rw,sw\in A\), we argue similarly to obtain an \((x,y)\)-QHP. Thus, we may assume that the only arcs from \(\{r,s\}\) to \(\{u,w\}\) are \(ru\) and \(sw\).

Set \(R\coloneq D-\{x,y,r,s,u,w\}\). As \(D-\{x,y\}\) is 2-strong, there are at least 2 arcs in each direction between \(R\) and \(\{r,s,u,w\}\). Assume \(R\) is not strong with linear decomposition \(R_1,\dots,R_k\). Then there exists an \((a,b)\)-QHP in \(R\) for any pair of vertices \(a\in R_1\) and \(b\in R_k\) by [lem:non-strong]. If there exists \({v_0\in\{r,s\}}\) and \({v_1\in\{u,w\}}\) such that \(N^+(v_0)\cap R_1\neq\emptyset\) and \(N^-(v_1)\cap R_k\neq\emptyset\), there exists a \((v_0,v_1)\)-QHP in \({D[V(R)\cup\{v_0,v_1\}]}\). This path easily expands to an \((x,y)\)-QHP in \(D\). Thus, \(R_1\Rightarrow\{r,s\}\) or \(\{u,w\}\Rightarrow R_k\). In the first case, both \(u\) and \(w\) must have positive neighbors in \(R_1\) as \(D-\{x,y\}\) is 2-strong. A vertex in \(R_k\) must have a positive neighbor \(v_1\in\{r,s,u,w\}\). No matter which one it is, it can be combined with some \(v_0\in\{u,w\}\) to obtain a \((v_0,v_1)\)-QHP in \(D[V(R)\cup\{v_0,v_1\}]\) which extends to an \((x,y)\)-QHP in \(D\). The case \(\{u,w\}\Rightarrow R_k\) is symmetric. Therefore, we may assume that \(R\) is strong, so there exists a quasi-Hamiltonian cycle in \(R\) by [lem:cycle-cover].

Let \(C=v_0\dots v_{\ell-1} v_0\) be a quasi-Hamiltonian cycle in \(R\). If \(\{r,s\}\Rightarrow V(C)\), let \(P=v_i\dots a\) be a shortest \((V(C),\{r,s\})\)-path in \(D-\{x,y\}\). As \({D-\{x,y\}}\) is 2-strong, both \(u\) and \(w\) must have negative neighbors in \(C\) so that \(P\) consists of 3 vertices, i.e. \(P=v_iba\) with \({b\in\{u,w\}}\). Let \(c\in\{r,s\}\setminus\{a\}\) and \(d\in\{u,w\}\setminus\{b\}\). Then one of \(xcC[v_{i+1},v_i[Pdy\) or \(xcC[v_{i+2},v_i[Pdy\) is the desired path where indices are viewed modulo \(\ell\). Thus, we may assume that there exists an arc from \(V(C)\) to \(\{r,s\}\). Without loss of generality, assume that \(v_1r\in A\). If \(sv_2\in A\) or \(wv_2\in A\), we obtain the \((x,y)\)-QHP \(xsC[v_2,v_1]ruwy\) or \(xswC[v_2,v_1]ruy\), so \(v_2\Rightarrow\{s,w\}\). As \(H(s)\neq H(w)\), one of the arcs \(v_2s\) or \(v_2w\) must exist in \(D\). Using an analogous argument, we obtain \(v_3\Rightarrow\{r,u\}\). Inductively, we conclude that \(v_{2i+1}\Rightarrow\{r,u\}\) and \(v_{2i}\Rightarrow\{s,w\}\) for all \(i\in\mathbb{N}\). In particular, \(\ell\) can be assumed to be even as otherwise both properties are satisfied by all vertices of the cycle, which results in the desired path.

If \(V(C)\Rightarrow\{r,s\}\), let \(P=a\dots v_i\) be a shortest \((\{r,s\},V(C))\)-path in \(D-\{x,y\}\). Because \({D-\{x,y\}}\) is 2-strong, both \(u\) and \(w\) must have positive neighbors in \(C\), so that \(P\) consists of 3 vertices, i.e. \({P=abv_i}\) with \({(a,b)\in\{(s,u),(r,w)\}}\). Let \(c\in\{r,s\}\setminus\{a\}\) and \(d\in\{u,w\}\setminus\{b\}\). Then, \({xPC]v_i,v_{i-1}]cdy}\) or \({xPC]v_i,v_{i-2}]cdy}\) is the desired path. Thus, we may assume that \(r\) or \(s\) has a positive neighbor on \(C\), i.e. \(rv_{2i}\in A\) or \(sv_{2i+1}\in A\) for some \(i\in\mathbb{N}\). In either case, an inductive argument analogous to the previous one yields \(\{s,w\}\Rightarrow v_{2i+1}\Rightarrow\{r,u\}\) and \(\{r,u\}\Rightarrow v_{2i}\Rightarrow\{s,w\}\) for all \(i\in\mathbb{N}\).

Assume the set \(R\) contains at least 5 pairwise different color classes. Then, by [lem:2-out-of-3-path], there exists a QHP \(Q=w_1\dots w_\ell\) in \(D[R]\) with end vertices in \(\{v_0,v_2,v_4\}\). One of the arcs \(rw_1\) and \(uw_1\) must exist as \(\alpha(D)\leq2\). Similarly, one of the arcs \(w_{\ell}s\) and \(w_{\ell}w\) must exist. If \(rw_1\in A\), then \(xrQswuy\) or \(xsrQwuy\) is an \((x,y)\)-quasi-Hamiltonian path in \(D\). Otherwise, \(uw_1\in A\), so \(xruQswy\) or \(xsruQwy\) is a quasi-Hamiltonian path.

Finally, assume that \(R\) intersects at most 4 pairwise different color classes. Then \({\alpha(D)=1}\) because \(\alpha(D)=2\) would imply \(|V(R)|=|V|-6\geq9\) which yields \({|\mathcal{C}(R)|\geq 5}\). The assumption \({|V|\geq5+5\alpha(D)}\) implies \(|V(R)|\geq4\), so \(C\) consist of exactly 4 vertices. As \(\alpha(D)=1\), we have \(v_3\rightarrow\{r,u\}\rightarrow v_0\), so \(xsrv_0v_1v_2v_3uwy\) is a Hamiltonian path in \(D\). ◻

Proof. Clearly, \(D\) is unilaterally connected if it contains a Hamiltonian path, so let \(D\) be unilaterally connected. We will show that \(D\) contains a spanning unilaterally connected tournament by induction over the number of 2-cycles. By [thm:unilateral-to-traceable], this implies that \(D\) contains a Hamiltonian path. If \(D\) does not contain any 2-cycles, \(D\) already is a multipartite tournament.

Let \(R_1,\dots,R_k\) be the linear decomposition of \(D\). As \(D\) is unilaterally connected, every linear component either induces a strong component or is a singleton set. Due to the structure of the linear decomposition, every 2-cycle is contained in some linear component. Let \(R_i\) be a linear component containing a 2-cycle. If \(|R_i|\geq5\), then we may assume that \(D[R_i]\) is a strong multipartite tournament by [thm:spanning95mtournament]. This leaves only the cases where \(R_i\) intersects exactly two color classes, so \(2\leq|R_i|\leq4\). By inserting two new vertices, one with outgoing arcs to all other vertices and one with incoming arcs from all other vertices, we may without loss of generality assume that \(1<i<k\).

If \(|R_i|=2\), let \(R_i=\{v,w\}\). First assume \(R_{i-1}\rightarrow R_i\). By [lem:linear-decomp], one of \(v\) or \(w\) has an outgoing arc to \(R_{i+1}\), say \(w\). Then \(D-wv\) is unilaterally connected with one fewer 2-cycle, so it contains a spanning unilaterally connected tournament by the induction hypothesis. Otherwise, exactly one of \(v\) or \(w\) does not have an incoming arc from \(R_{i-1}\), say \(w\). Then \(w\) must have an outgoing arc to \(R_{i+1}\) as the unique vertex with the same color as \(w\) lies in \(R_{i-1}\). Again, \(D-wv\) is unilaterally connected, so it contains a spanning unilaterally connected tournament by the induction hypothesis.

If \(|R_i|=3\), let \(R_i=\{u,v,w\}\) with \(H(u)=H(w)\). Because \(D[R_i]\) is strong, it contains a \((u,w)\)-path \(P\), which must be \(uvw\). Remove all arcs from \(D\) that run against the direction of \(P\), i.e. the arcs \(vu\) and \(wv\). As all color classes have size at most 2, \(R_{i-1}\rightarrow\{u,w\}\rightarrow R_{i+1}\). Thus, \(D-\{vu,wv\}\) is unilaterally connected, so it contains a spanning unilaterally connected tournament by the induction hypothesis.

If \(|R_i|=4\), let \(R_i=\{v_1,v_2,v_3,v_4\}\) with \(H(v_1)=H(v_3)\) and \(H(v_2)=H(v_4)\). If \(D[R_i]\), contains a Hamiltonian path \(P\), remove all arcs from \(D\) that run against the direction of \(P\). As \(R_{i-1}\rightarrow R_i\rightarrow R_{i+1}\), the resulting digraph is still unilaterally connected, so it contains a spanning unilaterally connected tournament by the induction hypothesis. Otherwise, let \(P\) be a \((v_1,v_j)\)-path. Without loss of generality, assume that \(P=v_1v_2v_3\). Because \(D[R_i]\) does not contain a Hamiltonian path, \(v_3v_4,v_4v_1\notin A\). This yields the \((v_1,v_3)\)-path \(Q=v_1v_4v_3\). Because \(D[R_i]\) does not contain a Hamiltonian path, \(v_2v_1,v_3v_2\notin A\). However, this contradicts the assumption that \(R_i\) contains a 2-cycle. ◻

Proof. A semicomplete multipartite digraph is unilaterally connected if and only if no linear component is an independent set of size at least 2. As the input graph \(D\) has independence number at most 2, \(D\) is unilaterally connect if and only if every linear component of size 2 is a 2-cycle. The linear decomposition can be computed in time \(\mathcal{O}(n^2)\) [5], so this condition can also be checked in time \(\mathcal{O}(n^2)\). ◻