Structural Parameters for Steiner Orientation

Our NP-completeness proof for Steiner Orientation on graphs of treewidth $2$ is based on a direct reduction from a variant of 3-SAT, where we naturally use undirected edges to represent variables of the initial formula, with directions representing truth assignments (this is standard). The key new insight is the following: we can transmit information between copies of such edges, ensuring they must be oriented in a consistent way, by adding demand pairs which must be routed through two main hub vertices. By using appropriately oriented arcs to connect our gadgets to the two hubs we ensure that gadgets don’t interfere with each other. In a sense, the take-home message of this construction is that the structure of $G$ alone is not enough to measure the complexity of an instance, because the way that demand pairs interact with the graph can significantly complicate the structure of the instance.

The XP algorithm parameterized by vertex cover is based on a simple branching procedure: for each pair $u,v$ of vertices of the vertex cover, guess if there is a directed path of length at most $2$ from $u$ to $v$ in the solution and, if yes, which is (potentially) the vertex $w$ in the middle of the path. This clearly leads to at most $n^{𝒪({\text{vc}}^2)}$ guesses, and once we have fixed these decisions it is not hard to complete the solution because we can infer exactly which vertices of the cover have directed paths to each other.

Given the simplicity of the algorithm sketched above for vertex cover, it is somewhat surprising that this is essentially optimal (under the ETH). We establish this by giving a reduction from $k$-Clique producing a Steiner Orientation instance with vertex cover $𝒪(\sqrt{k})$. The key intuition is again that we can use a small number ($𝒪(\sqrt{k})$) of hubs, through which information will be routed. In particular, we set up a complete bipartite graph $K_{\sqrt{k},\sqrt{k}}$ and for each edge of this graph we set up a gadget encoding a selection in the original instance: the number of edges of this graph is sufficient to encode all selections, but the vertex cover of the construction is determined by the number of vertices of the complete bipartite graph.

To obtain an algorithm for parameter $|A|$ we face significantly more obstacles than for parameter $|E|$ (which is trivially FPT). Our approach relies on exhaustive applications of some (standard) reduction rules for this problem, which eliminate all cycles and degree $1$ vertices. We then focus on a restricted special case of Steiner Orientation, where all undirected components are paths, all internal vertices of the paths are incident on no arcs, and the endpoints of each path are incident on at most one arc. We solve this restricted case using a reduction to 2-SAT. We then show, using arguments which essentially take into account that $A$ is a feedback edge set of the underlying graph, that a simple branching algorithm can reduce any instance into $2^{𝒪(|A|)}$ instances of the (polynomial-time solvable) restricted case.

The FPT algorithm for distance to clique relies again on exhaustively applying reduction rules that eliminate cycles and then making some simple structural observations: there are few edges incident on the modulator vertices (so we can guess their orientation); and the edges contained in the clique must have a very simple structure (they form a matching). The FPT algorithm for $\text{tw}+k$ relies on a formulation of the problem in MSO₂ logic and Courcelle’s theorem – we leave it as an interesting open problem to determine the best dependence for this parameterization. Finally, for the more restrictive parameter $\text{vc}+k$ we obtain a polynomial kernel via a maximum matching argument. In particular, we show that by calculating a maximum matching between pairs of vertices of the vertex cover and non-terminals in the indpendent set, we can identify a set of $𝒪({\text{vc}}^2)$ vertices of the independent set which are sufficient to obtain a solution and delete the rest, giving a kernel of order $𝒪({\text{vc}}^2+k)$.

In $k$-Multicolored Clique we are given a graph $G$ and a partition of $V(G)$ into $k$ independent sets each of size $n$, and we are asked to determine whether $G$ contains a $k$-clique. It is well-known that $k$-Multicolored Clique parameterized by $k$ is W[1]-hard and does not admit any $f(k)n^{o(k)}$-time algorithm, where $f$ is any computable function, unless the ETH is false [6]. Let $(G,k)$ be an instance of $k$-Multicolored Clique, where we assume without loss of generality that $\sqrt{k}\in \mathbb{N}$ (one can do so by adding dummy independent sets connected to all the other vertices of the graph). Recall that we assume that $G$ is given to us partitioned into $k$ independent sets $V_1,\mathrm{\dots }{V}_k$, where $V_i=\{v_1^i,\mathrm{\dots },v_n^i\}$. We will construct in polynomial time an equivalent instance $(H,𝒯)$ of Steiner Orientation, with $\text{vc}(H)=𝒪(\sqrt{k})$.

We first introduce the vertices $\{{\mathrm{\ell }}_{\alpha },{\mathrm{\ell }}_{\alpha }^{\prime },r_{\alpha },r_{\alpha }^{\prime }:\alpha \in [\sqrt{k}]\}$ and add the arcs ${\mathrm{\ell }}_{\alpha }\to {\mathrm{\ell }}_{\beta }^{\prime }$ and $r_{\alpha }\to r_{\beta }^{\prime }$ for all $\alpha ,\beta \in [\sqrt{k}]$. For all $i\in [k]$, we further introduce the independent sets $X_i=\{x_1^i,\mathrm{\dots },x_n^i\}$ and $Y_i=\{y_1^i,\mathrm{\dots },y_n^i\}$. We fix a bijective function $h:[k]\to {[\sqrt{k}]}^2$ that maps every independent set $V_i$ to a distinct pair $(\alpha ,\beta )\in {[\sqrt{k}]}^2$, and for all $i\in [k]$ with $h(i)=(\alpha ,\beta )$

• $\mathrm{■}$

  we add the edge $\{{\mathrm{\ell }}_{\alpha },x_j^i\}$ for all $x_j^i\in X_i$,

• $\mathrm{■}$

  we add the arc $(x_j^i,r_{\beta })$ for all $x_j^i\in X_i$,

• $\mathrm{■}$

  we add the arc $({\mathrm{\ell }}_{\alpha }^{\prime },y_j^i)$ for all $y_j^i\in Y_i$,

• $\mathrm{■}$

  we add the edge $\{r_{\beta }^{\prime },y_j^i\}$ for all $y_j^i\in Y_i$.

This completes the construction of the graph $H$, and we refer to Figure 2 for an illustration of a part of it. As for the terminal pairs, we proceed in three steps:

1. 1.

   We initially add into $𝒯$ the pairs $({\mathrm{\ell }}_{\alpha },r_{\beta })$ and $({\mathrm{\ell }}_{\alpha }^{\prime },r_{\beta }^{\prime })$, for all $\alpha ,\beta \in [\sqrt{k}]$.

2. 2.

   Next, for all $i\in [k]$ and $j\in [n]$, we add the terminal pair $(x_j^i,y_{j^{\prime }}^i)$ into $𝒯$, for all $j^{\prime }\in [n]\setminus \{j\}$. We refer to the terminal pairs added in this step as consistency terminal pairs.

3. 3.

   Lastly, for distinct $i_1,i_2\in [k]$, if $\{v_{j_1}^{i_1},v_{j_2}^{i_2}\}\notin E(G)$ we add the terminal pairs $(x_{j_1}^{i_1},y_{j_2}^{i_2}),(x_{j_2}^{i_2},y_{j_1}^{i_1})$ into $𝒯$, where $j_1,j_2\in [n]$. We refer to the terminal pairs added in this step as edge-checking terminal pairs.

This completes the construction of the instance $(H,𝒯)$.

It is easy to see that $\{{\mathrm{\ell }}_{\alpha },{\mathrm{\ell }}_{\alpha }^{\prime },r_{\alpha },r_{\alpha }^{\prime }:\alpha \in [\sqrt{k}]\}$ is a vertex cover of $H$, thus $\text{vc}(H)=𝒪(\sqrt{k})$. To complete the proof, we show the following claim.

$◀$

First we note that contracting all mixed cycles as in Proposition 1 does not increase the size of a minimal vertex cover, so we can suppose that our graph is mixed acyclic.

Let $G$ be a graph of vertex cover number vc. Let $S\subseteq V$ be a vertex cover $G$ of size vc. It can be computed in time $2^{𝒪(\text{vc})}$ [13]. First we guess the orientation of the edges of $G[S]$. There are $2^{𝒪({\text{vc}}^2)}$ possibilities. Then, for all pairs $(u,v)\in S^2$, we guess if there is, in the final solution, an oriented path $u\to w\to v$ with $w\in V\setminus S$; if we guessed there is at least one, we guess one such $w$, and orient its edges in consequence. There are $n^{𝒪({\text{vc}}^2)}$ possibilities. As we will see in Claim 12, after this guessing phase, as $S$ is a vertex cover, the connectivity of $S$ in any solution respecting the guesses is already decided. This will allow us to check the existence of such a solution in polynomial time.

The above claim shows that for any $w\in V\setminus S$, after the guessing steps, either all of its undirected edges must be oriented from $w$ to $S$ or from $S$ to $w$.

This claim shows us that after the guessing steps, for any $(s_i,t_i)$ pair of terminals that is not already satisfied, the only way to satisfy them while respecting the guessing steps is to orient the edges of $s_i$ and $t_i$.

We now argue that there exists a demand pair $(s_i,t_i)$ which should be treated “first”. To see this, consider an auxiliary directed graph which has a vertex for each demand pair, and an arc from $(s_i,t_i)$ to $(s_j,t_j)$ when $s_j=t_i$. If this auxiliary graph contains a directed cycle, this implies that the original instance must be oriented in a way that creates a directed cycle, but since we assumed that $G$ is mixed acyclic, this is impossible. Hence, the interesting case is when the auxiliary graph is a DAG, therefore there exists a demand pair $(s_i,t_i)$ such that for all other demands $(s_j,t_j)$ we have, $t_j\ne s_i$

We can apply the following method: take such a pair $(s_i,t_i)$ (as described in the previous paragraph). If $s_i\in V\setminus S$, then orient all undirected edges between $s_i$ and $S$ from $s_i$ to $S$. If the demand $(s_i,t_i)$ is now satisfied, that is, there is a path from $s_i$ to $t_i$ using arcs and oriented edges, we remove this demand.

If $(s_i,t_i)$ is still unsatisfied, if $t_i\in V\setminus S$, then orient all undirected edges between $t_i$ and $S$ from $S$ to $t_i$.

We have now handled the demand $(s_i,t_i)$: if it is satisfied after the steps above, we remove it from the instance and continue with the remaining demands; otherwise this demand cannot be satisfied and we reject. We eat this method until there are no unsatisfied terminals.

This method is correct: indeed, from Claim 12, after the guessing steps, the satisfaction of $(s_i,t_i)$ only depends on the orientation of the undirected edges incident on $\{s_i,t_i\}\setminus S$. Furthermore, from the same claim, if $s_i\in V\setminus S$, in any feasible solution, its undirected edges will only be used to satisfy pairs of terminals that contain $s_i$. But our choice of terminals ensures that for any such pair $(s_j,t_j)$, $s_i\ne t_j$, so $s_i=s_j$. So in a feasible solution respecting the guessing steps, if an undirected edge of $s_i$ is used to satisfy such a pair, it will be oriented from $s_i$ to $S$, so it was safe to select this orientation. For the second step, if $(s_i,t_i)$ is still not satisfied, then from Claim 12, the only way to satisfy it while respecting the guessing steps is, if $t_i\in V\setminus S$, to direct one undirected edge between $t_i$ and $S$ from $S$ to $t_i$. But from Claim 11, they all have the same orientation, so it was safe to orient all of them from $S$ to $t_i$. If $(s_i,t_i)$ is still unsatisfied after these steps, then, from Claim 12, there is no way to satisfy those terminals while respecting the guessing steps.

The above method can be applied in time $n^{𝒪(1)}$, and must be applied at most $n^2$ times. In the end, we have an algorithm of complexity $n^{𝒪({\text{vc}}^2)}$. $◀$

We begin by applying Proposition 1 and Proposition 2 exhaustively. This does not increase $|A|$, so we can assume that the input is mixed acyclic and has no vertices of degree at most $1$. Our algorithm is now the following: take all vertices of mixed degree $3$ or more, and for each possible orientation of their edges, create a new instance. We claim that we obtain at most $2^{6|A|}$ restricted instances, such that at least one of them will have a solution if and only if the original instance did.

First, we argue that if we perform this branching on all vertices of mixed degree $3$ or more, we obtain an instance conforming to Definition 15. Indeed, after the orientation, all vertices of mixed degree $3$ are not incident on any unoriented edges, only arcs.

In order to bound the number of instances, let us count the number of edges to orient. We will need the following lemma:

Armed with this claim, let us continue: take $T\subseteq G[E]$ composed of the non-trivial connected components of $G[E]$. As $G$ is mixed acyclic, it is a forest. Furthermore, as $G$ does not contain any leaf, each leaf of $T$ has at least one arc. Let $V_0$ be the set of leaves of $T$ with a unique arc, $V_1$ be the set of leaves of $T$ with two arcs or more, $V_2$ the set of vertices with two edges and at least one arc, and $V_3$ the set of vertices with at least $3$ edges. We need to orient the unoriented edges of $V_1,V_2$ and $V_3$, which make $|V_1|+2|V_2|+{\sum }_{v\in V_3}d(v)$ edges. But, as each arc has only two endpoints, $|V_0|+2|V_1|+|V_2|\le 2|A|$. And, from the previous claim, ${\sum }_{v\in V_3}d(v)\le 3(|V_0|+|V_1|)$. Therefore, $|V_1|+2|V_2|+{\sum }_{v\in V_3}d(v)\le 3|V_0|+4|V_1|+2|V_2|\le 3(|V_0|+2|V_1|+|V_2|)\le 6|A|$:, so we need to orient at most $6|A|$ edges, thus obtaining at most $2^{6|A|}$ restricted instances. $◀$