Directed multicut is W [1]-hard, even for four terminal pairs∗
Marcin Pilipczuk†

Magnus Wahlström‡

arXiv:1507.02178v3 [] 12 Feb 2018

Abstract
We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W [1]-hard
and hence unlikely to be fixed-parameter tractable even if restricted to instances with only four terminal
pairs. This negative result almost completely resolves one of the central open problems in the area of
parameterized complexity of graph separation problems, posted originally by Marx and Razgon [SIAM
J. Comput. 43(2):355–388 (2014)], leaving only the case of three terminal pairs open. The case of two
terminal pairs was shown to be FPT by Chitnis et al. [SIAM J. Comput. 42(4):1674–1696 (2013)].
Our gadget methodology also allows us to prove W [1]-hardness of the Steiner Orientation problem
parameterized by the number of terminal pairs, resolving an open problem of Cygan, Kortsarz, and Nutov
[SIAM J. Discrete Math. 27(3):1503-1513 (2013)].

1

Introduction

The study of cuts and flows is one of the central areas of combinatorial optimization, with decades of intensive
research on polynomial-time exact and approximate algorithms. Since the seminal work of Marx [23], it has
also become one of the most dynamic research directions in parameterized complexity, under the name of
graph separation problems.
The key contribution of Marx’ paper [23] lies in the notion of an important separator, which is a kind of
greedy cut that is useful in some graph cut problems. Marx showed that the number of important separators of
size up to k in a graph is bounded as a function of k alone, and gave applications to a number of graph separation
problems, in particular an FPT algorithm for Multiway cut [23].1 (An improved bound was given by Chen et
al. [4], with a simple but influential proof method.) These techniques also led to FPT algorithms for Directed
Feedback Vertex Set [5] and eventually for Almost 2-SAT [30], which is a powerful generic problem
encapsulating a number of other well-studied problems, such as Odd Cycle Transversal and Vertex
Cover parameterized by the excess above a maximum matching. Further study of the graph separation
problems in the realm of parameterized complexity revealed a plethora of other algorithmic techniques: the
technique of shadow removal [28] lead to an FPT algorithm for the directed version of Multiway Cut [8], the
framework of randomized contractions [6] lead to an FPT algorithm for Minimum Bisection [11], whereas the
idea to guide a branching algorithm by the solution to the LP relaxation [12] lead not only to the fastest known
algorithm for Odd Cycle Transversal [22], but also can be cast into a very general CSP framework [31].
In tandem with these developments, we have gained a growing understanding of the structure of boundedsize cuts in graphs. Starting again with the proof that bounded size important separators are bounded in
number, we wish to highlight two further main contributions in this vein. First, Marx et al. [27] showed that
all inclusion-minimal st-cuts of size at most k in a graph G (for fixed vertices s, t) are contained in (essentially)
∗ An

extended abstract of this work has been presented at SODA 2016 [29].
of Warsaw, Poland, malcin@mimuw.edu.pl. Research done while the author was at University of Warwick,
partially supported by the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick and
by Warwick-QMUL Alliance in Advances in Discrete Mathematics and its Applications.
‡ Royal Holloway University of London, UK, Magnus.Wahlstrom@rhul.ac.uk
1 In the Multiway Cut problem, the input consists of a graph G, a set T ⊆ V (G) of terminals, and an integer p; the goal
is to delete at most p edges (in the edge-deletion variant) or nonterminal vertices (in the node-deletion variant) so that every
terminal lies in a different connected component of the resulting graph, that is, to separate all pairs of terminals.
† University

a subgraph of G of treewidth at most f (k). This statement is attractive in its simplicity, although algorithmic
applications of it tend to have a bad running time dependency on k (since f (k) is already exponential,
and a treewidth dynamic programming algorithm would normally have running time exponential in f (k)).
Second, the FPT algorithm for Minimum Bisection [11] involves a technically intricate but very powerful
decomposition of the input graph in a tree-like manner into “nearly unbreakable” parts (see the paper for
details). However, these two results apply only to undirected graphs, and for directed graphs we have a much
weaker grasp of the structure.
A central milestone in the above developments was the discovery in 2010 of FPT algorithms for Multicut,
a robust generalization of Multiway Cut, parameterized by the size of the cutset only [3, 28]. In this
problem we are given a graph G, a family T of k terminal pairs, and an integer p; the goal is to delete at most
p nonterminal vertices from the graph such that all terminal pairs are separated.2 Marx and Razgon [28] also
proved that a similar result is unlikely in directed graphs, showing that Directed Multicut is W [1]-hard
parameterized by the cutset only. In contrast, Directed Multiway Cut is FPT by the same parameter [8].
Marx and Razgon [28] asked about the complexity of Directed Multicut when you restrict also the
number of terminal pairs, either assuming it is constant or by adding it to the parameter. Since then,
this has become one of the most important open problems in the study of graph separation problems in
parameterized complexity. It was positively resolved for DAGs (i.e., the problem is FPT on directed acyclic
graphs parameterized by both the cutset and the number of terminals) [19], but otherwise little progress has
been made. In particular, it has been repeated in the survey of Marx [26] on future directions of parameterized
complexity, where also the study of cut problems in directed graphs has been identified as an important
research direction. Similarly, the question of the structure of bounded-size directed cuts (e.g., the existence
of a directed version of [27]) has been floating around the community.
Our results.

We almost completely resolve the question of Marx and Razgon [28]:

Theorem 1.1. Directed Multicut is W [1]-hard when parameterized by p, the size of the cutset, even if
restricted to instances with only four terminal pairs. Furthermore, assuming the Exponential Time Hypothesis
(ETH), there is no algorithm solving n-vertex instances of Directed Multicut with four terminal pairs
in time f (p)no(p/ log p) for any computable function f .
Since Directed Multicut is polynomial-time solvable for one terminal pair, and reduces to Directed
Multiway Cut for two terminal pairs [8], only the case of three terminal pairs remains open.
The Exponential Time Hypothesis (ETH) [18], now a standard lower bound assumption in parameterized
complexity and moderately-exponential algorithms (cf. [21]), essentially asserts that there exists no algorithm
verifying satisfiability of 3-CNF SAT formulae in time subexponential in the number of variables. The ETH
lower bound of Theorem 1.1 implies that a brute-force solution running in time nO(p) is close to optimal.
Furthermore, we observe that our gadgets and reduction outline, after minor modifications, gives also a
lower bound for the Steiner Orientation problem, answering an open question of [9]. In the Steiner Orientation problem, given a mixed graph G with k terminal pairs T , one asks for an orientation of all undirected
edges of G, such that for every terminal pair (s, t) ∈ T there is a path from s to t in the oriented graph.
Theorem 1.2. Steiner Orientation is W [1]-hard when parameterized by k, the number of terminal pairs.
Furthermore, assuming ETH, there is no algorithm solving n-vertex instances of Steiner Orientation
in time f (k)no(k/ log k) for any computable function f .
Cygan, Kortsarz, and Nutov [9] showed an nO(k) -time algorithm; Theorem 1.2 implies that there is little
hope for a fixed-parameter algorithm, and that the running time of the algorithm of Cygan, Kortsarz, and
Nutov is close to optimal.
We also show a structural result for directed st-cuts of bounded size. A graph G is k-cut-minimal (for
arc-cuts) if it contains a source vertex s and a sink vertex t, and every other vertex is incident to at least
one arc that participates in an inclusion-minimal st-cut of size at most k. (For example, one can reduce an
2 In this paper we use consistently the node-deletion variant of Multicut; note that it is equivalent to the edge-deletion
setting in the directed case, and strictly more general in the undirected case.

s

t

s

t

Figure 1: An example of 5-cut-minimal graph with unbounded treewidth of the underlying undirected graph.
The right panel shows a minimal cut of size five; observe that every edge of the graph participates in a similar
cut, except for a few edges in the four corners of the graph, which can be easily covered by other small cuts.

arbitrary graph to a k-cut-minimal one by repeatedly bypassing every vertex that is not incident to any such
arcs.) We have the following.
2

Theorem 1.3. Every k-cut-minimal graph has directed treewidth at most f (k), where f (k) = 2O(k ) .
We note that this result is likely not as tight as it could be, both in terms of the choice of width measure and
the function f (k). However, as discussed below, our results also show that Directed Multicut is essentially
hard already for four terminal pairs and directed pathwidth two, so for the purpose of the Directed Multicut
problem, a sharpening of Theorem 1.3 is not likely to help (even though it may be useful for other problems).
Discussion. In the presence of the lower bound of Theorem 1.1, whose proof in this manuscript takes less
than five pages including a figure and is not very technically complex, the natural question is why the lower
bound was so elusive in the past five years, despite significant effort.
The idea to represent an n-wise choice in the reduction (e.g., the choice of a vertex of a clique or an
image of a vertex of the pattern graph in the case of the Subgraph Isomorphism problem) as a choice of a
single-vertex cut on a n-vertex bidirectional path connecting a terminal pair, seems quite natural, especially
in the light of the FPT algorithm for Directed Multicut in DAGs [19] and a deeper study of where this
algorithm uses the assumption of acyclicity. However, a gadget to check an arbitrary binary relation between
two such choices was elusive; we stumbled upon a “correct” construction by investigating the structural
question that led to Theorem 1.3 (the idea being that a sufficiently powerful structural result could have
been useful in designing an efficient algorithm).
A few words about directed width measures may be in order (for more, see, e.g., [1, 20]). Two approaches
are possible. On the one hand, one can simply consider the underlying undirected graph and ignore the arc
orientations; e.g., if the underlying undirected graph of a directed graph G has bounded treewidth, then many
problems are solvable on G via standard dynamic programming. On the other hand, several width notions
specific to directed graphs have been proposed (to name a few: directed pathwidth; directed treewidth;
DAG-width; Kelly-width). Of these, directed treewidth is the most general and directed pathwidth the most
restrictive. It has been noted that these directed width notions are rather more difficult to use in algorithms
than the undirected variants (e.g., [16, 15]), but on the other hand they are more permissive (e.g., they all
include DAGs as a constant-width base case).
Our gadgets are based around a counterexample against the first of these approaches. Figure 1 shows a
graph which is 5-cut-minimal (in fact, where every arc participates in a minimal st-cut of bounded size), but

whose underlying undirected graph is a grid (and thus has unbounded treewidth). Our hardness reduction
uses this graph to route one commodity horizontally and one vertically, allowing us to control which pairs
of flows can be killed at unit cost.
Also note that the graph in Figure 1 is acyclic; in fact, the reduction of Theorem 1.1 outputs an instance
of integer-weighted Directed Multicut of directed pathwidth 2. Standard reductions (replacing a vertex
of weight w by w unit-weight copies) creates an instance of unweighted Directed Multicut with directed
pathwidth bounded polynomially in the parameter. Hence Directed Multicut remains W [1]-hard, even for
four terminal pairs, if we parameterize by both the size of the cutset and the directed pathwidth of the input
graph. By the discussion above, this leaves little room for generalizing the FPT-algorithm for DAGs [19]
to broader classes.
Organization and notation. We show the reduction for Theorem 1.1 in Section 2 and for Theorem 1.2
in Section 3. We prove Theorem 1.3 in Section 4.
We use standard graph notation, see e.g. [2]. Both our hardness reductions start from the W [1]-hard
Partitioned Subgraph Isomorphism problem, parameterized by the number of edges of the pattern graph.
An input to Partitioned Subgraph Isomorphism consists of two graphs G and H
U with |E(H)| = k, where
V (G) is partitioned into |V (H)| color classes, one for each vertex of H: V (G) = i∈V (H) Vi ; the goal is to
check if there exists a homomorphism φ : V (H) → V (G) such that φ(i) ∈ Vi for every i ∈ V (H). The W [1]and ETH-hardness of Partitioned Subgraph Isomorphism has been shown by Marx:
Theorem 1.4 (Cor. 6.3 of [24]). Partitioned Subgraph Isomorphism is W [1]-hard when parameterized by
k = |E(H)|. Furthermore, assuming ETH, there is no algorithm solving n-vertex instances of Partitioned
Subgraph Isomorphism in time f (k)no(k/ log k) for any computable function f .
Both our reductions work in polynomial time and, given a Partitioned Subgraph Isomorphism
instance (G, H), output an instance with the corresponding parameter bounded linearly in k = |E(H)| and
size bounded polynomially in the input size.
In both
S reductions, given an input instance (G, H) of Partitioned Subgraph Isomorphism, we denote
V (G) = i∈V (H) Vi , k = |E(H)|, and ` = |V (H)|. Furthermore, without loss of generality we assume that H
does not have any isolated vertices and thus ` ≤ 2k. Indeed, if some color class Vi of V (G) is empty, we can
output a trivial no-instance, and otherwise we can delete all isolated vertices from H and their corresponding
color classes in G without changing the answer to the problem. We also fix some total order < on the set
V (H) and, by some potential padding, assume that |Vi | = n and Vi = {vai : 1 ≤ a ≤ n} for every i ∈ V (H).
For discussion on the output of the reduction of Theorem 1.1, we need to recall the definition of directed
pathwidth; we follow here Kreutzer and Ordyniak [20].
Definition 1.1. Let G be a directed graph. A directed path decomposition is a pair (P, β) where P =
v1 , v2 , . . . , vs is a directed path and β : V (P ) → 2V (G) is a mapping satisfying:
1. For every v ∈ V (G) the set β −1 (v) is connected in P and nonempty.
2. For every arc (u, v) ∈ E(G) there are indices 1 ≤ i ≤ j ≤ s such that u ∈ β(vi ) and v ∈ β(vj ).
The width of (P, β) is max1≤i≤s |β(vi )|, and the directed pathwidth of G is the minimum width among all
its directed path decompositions. For every 1 ≤ i ≤ s, the set β(vi ) is called a bag at node vi .
Note that directed pathwidth of a nonempty directed acyclic graph G equals 1: we can take vertices of
G one-by-one in any topological ordering of G.

2

Hardness for Directed Multicut

We reduce an input Partitioned Subgraph Isomorphism instance (G, H) to a node-weighted variant of
Directed Multicut, where every non-terminal vertex has a weight being a positive integer, and the goal is to

find a cutset of total weight not exceeding the budget p. We fix some integer constant M ; in fact it suffices to set
M = 2, but it helps to think of it as a sufficiently large integer constant. We use three levels of weight: there will
be light vertices, of weight 1, heavy vertices, of various integer weights being multiples of M , usually depending
on the degree of the corresponding vertex of H, and undeletable vertices, of weight p+1. Observe that it is easy
to reduce the weighted variant to the original one by replacing every vertex of weight w with w unit-weight
vertices. Thus, it suffices to show the reduction to the weighted variant, with only four terminal pairs.
Construction. Let us now describe the construction of the (weighted) Directed Multicut instance
(G0 , T , p). We start by setting budget p = (6M + 1)k. We also introduce eight terminals, arranged in four
terminal pairs:
(sx0→n , tx0→n ),

(sy0→n , ty0→n ),

<
(s<
n→0 , tn→0 ),

>
(s>
n→0 , tn→0 ).

For every i ∈ V (H), we introduce a bidirected path on 2n + 1 vertices
z0i , ẑ1i , z1i , ẑ2i , z2i , . . . , ẑni , zni ,
called henceforth the z-path for vertex i, and denoted by Z i . Similarly, for every ordered pair (i, j) where
ij ∈ E(H), we introduce two bidirected paths on 2n + 1 vertices
i,j
i,j
i,j
i,j
i,j
i,j
xi,j
0 , x̂1 , x1 , x̂2 , x2 , . . . , x̂n , xn ;

y0i,j , ŷ1i,j , y1i,j , ŷ2i,j , y2i,j , . . . , ŷni,j , yni,j .
We call these paths the x-path and the y-path for the pair (i, j), and denote them by X i,j and Y i,j . All vertices
i,j
i
i,j
i,j
i
zai , xi,j
a , ya are undeletable, while all vertices ẑa , x̂a , ŷa are heavy: vertex ẑa has weight M · degH (i) and
i,j
i,j
the vertices x̂a and ŷa have weight M each.
Note that so far we have created 4k + ` paths, each having 2n + 1 vertices. Furthermore, if we are to
delete one heavy vertex from each of these paths, the total cost would be


X
M · 4k +
degH (i) = 6kM.
i∈V (H)
i
i
i,j
For every pair (i, j) with ij ∈ E(H), and every 0 ≤ a ≤ n, we add arcs (xi,j
a , za ) and (za , ya ). Furthermore,
we attach terminals to the paths as follows.
i,j y
• for every pair (i, j) with ij ∈ E(H), we add arcs (sx0→n , xi,j
0 ) and (yn , t0→n );

• for every i ∈ V (H) we add arcs (sy0→n , z0i ) and (zni , tx0→n );
i,j <
i,j
• for every pair (i, j) with ij ∈ E(H) and i < j we add arcs (s<
n→0 , xn ) and (y0 , tn→0 );
i,j >
i,j
• for every pair (i, j) with ij ∈ E(H) and i > j we add arcs (s>
n→0 , xn ) and (y0 , tn→0 ).

We refer to Figure 2 for an illustration. Intuitively, the so-far constructed bidirectional paths and terminals
require to delete at least one heavy vertex per bidirectional path; the connections between paths ensure that
i,j
i
for every i ∈ V (H), we need to chose one index 1 ≤ φ(i) ≤ n and delete vertices ẑφ(i)
, x̂i,j
φ(i) , and ŷφ(i) , that
is, cut all paths corresponding to the vertex i at the same place. The choice of the index φ(i) corresponds
to the choice of the image of i in the sought homomorphism.
Let us now introduce gadgets that check the edge relations between the chosen vertices. For every pair
(i, j) with ij ∈ E(H), i < j we introduce an acyclic n × n grid with vertices pi,j
a,b for 1 ≤ a, b ≤ n and arcs
i,j
i,j
i,j
i,j
(pa,b , pa+1,b ) for every 1 ≤ a < n and 1 ≤ b ≤ n, as well as (pa,b , pa,b+1 ) for every 1 ≤ a ≤ n and 1 ≤ b < n.

We call this grid p-grid for the pair (i, j), and denote it by P i,j . We set the vertex pi,j
a,b to be a light vertex
i j
if va vb ∈ E(G), and undeletable otherwise. Finally, for every 1 ≤ a ≤ n we introduce arcs:
i,j
(xi,j
a , pa,1 ),

i,j
(pi,j
a,n , ya−1 ),

i,j
(xj,i
a , p1,a ),

j,i
(pi,j
n,a , ya−1 ).

Intuitively, after deleting the aforementioned heavy vertices on the x-, y-, and z-paths, for fixed ij ∈ E(H),
i,j
<
<
i < j, there is only one remaining path from xi,j
n (an out-neighbor of sn→0 ) to y0 (an in-neighbor of tn→0 ),
passing through the φ(i)-th row of the p-grid for the pair (i, j), and there is only one remaining path from
j,i
>
>
xj,i
n (an out-neighbor of sn→0 ) to y0 (an in-neighbor of tn→0 ), passing through the φ(j)-th column of the
p-grid for the pair (i, j). We can kill both these paths with a single vertex pi,j
φ(i),φ(j) , but only the existence
j
i
of the edge vφ(i)
vφ(j)
ensures that this vertex is light, not undeletable.
This concludes the construction of the instance (G0 , T , p). We now formally show that the constructed
instance is equivalent to the input Partitioned Subgraph Isomorphism instance (G, H).

From a homomorphism to a cutset.
of H into G. Define

i
Let φ : V (H) → [n] be such that i 7→ vφ(i)
∈ Vi is a homomorphism

i,j
X = {x̂i,j
φ(i) , ŷφ(i) : (i, j) ∈ V (H) × V (H) s.t. ij ∈ E(H)}∪
i
∪ {ẑφ(i)
: i ∈ V (H)} ∪ {pi,j
φ(i),φ(j) : (i, j) ∈ V (H) × V (H) s.t. ij ∈ E(H), i < j}.

The total weight of the vertices in X equals:
X
M · degH (i) + k = (6M + 1)k = p.
2k · 2 · M +
i∈V (H)

Note that the fact that pi,j
φ(i),φ(j) is light for every ij ∈ E(H), i < j follows from the assumption that the
i
vertices i 7→ vφ(i) is a homomorphism. Consequently, X is of weight exactly p. We now show that it is a
multicut in (G0 , T ).
We start with a simple observation about the structure of the graph G0 . While the x-, y-, and z-paths
are bidirected, they — together with the p-grids — are arranged in a DAG-like fashion. That is, there are
directed arcs from X i,j to Z i , from Z i to Y i,j , from X i,j and X j,i to P i,j , and from P i,j to Y i,j and Y j,i ,
but all cycles in G0 are contained in one x-, y-, or z-path.
Consider first the terminal pair (sx0→n , tx0→n ). The out-neighbors of sx0→n are the endpoints xi,j
0 for every
pair (i, j) with ij ∈ E(H); the only in-neighbors of tx0→n are the endpoints zni for every i ∈ V (H). Thus, by
the previous observation, the only paths from sx0→n to tx0→n in the graph G0 start by going to some vertex
i,j
i,j i
i
i
xi,j
up to some vertex xi,j
a , use the arc (xa , za ) to fall to Z , and then traverse Z to the
0 , traverse X
i
x
x
endpoint zn . (In particular, there are no paths from s0→n to t0→n that contain a vertex of some grid P i,j .)
However, all such paths for a ≥ φ(i) are cut by the vertex x̂i,j
φ(i) ∈ X, while all such paths for a < φ(i) are
i
cut by the vertex ẑφ(i) ∈ X. Consequently, the terminal pair (sx0→n , tx0→n ) is separated in H \ X.
A similar argument holds for the pair (sy0→n , ty0→n ). By the same reasoning, the only paths between sy0→n
and ty0→n in the graph H are paths that start by going to some vertex z0i , traverse Z i up to some vertex zai ,
use the arc (zai , yai,j ) for some ij ∈ E(H) to fall to Y i,j , and then continue along this y-path to the vertex
i
yni,j . However, all such paths for a ≥ φ(i) are cut by the vertex ẑφ(i)
∈ X, while all such paths for a < φ(i)
i,j
are cut by the vertex ŷφ(i)
∈ X.
<
<
Let us now focus on the terminal pair (s<
n→0 , tn→0 ). Observe that there are two types of paths from sn→0
<
i,j
to tn→0 in the graph H. The first type consists of paths that starts by going to some vertex xn where i < j,
i,j i
i
i
traverse X i,j up to some vertex xi,j
a , use the arc (xa , za ) to fall to Z , then traverse Z up to some vertex
0
0
0
zbi , use the arc (zbi , ybi,j ) for some j 0 > i to fall to Y i,j , and finally traverse this y-path to the endpoint y0i,j .
i,j 0
i
However, similarly as in the previous cases, the vertices x̂i,j
φ(i) , ẑφ(i) , ŷφ(i) ∈ X cut all such paths.

The second type of paths use the p-grids in the following manner: the path starts by going to some vertex
i,j
i,j i,j
i,j
xi,j
up to some vertex xi,j
, traverse this
n where i < j, traverse X
a , use the arc (xa , pa,1 ) to fall to P
i,j
i,j
i,j
i,j
p-grid up to a vertex pb,n where b ≥ a, use the arc (pb,n , yb−1 ) to fall to Y , and traverse this path to the
endpoint y0i,j . These paths are cut by X as follows: the paths where a < φ(i) are cut by x̂i,j
φ(i) ∈ X, the paths
i,j
where b > φ(i) are cut by ŷφ(i)
, while the paths where a = b = φ(i) are cut by the vertex pi,j
φ(i),φ(j) ∈ X; note
i,j
<
that the φ(i)-th row of the grid is the only path from pi,j
φ(i),1 to pφ(i),n . Please observe that the terminal tn→0
cannot be reached from P i,j by going to the other y-path reachable from this p-grid, namely Y j,i , as Y j,i
has only outgoing arcs to the terminal t>
n→0 since j > i.
>
i,j
i
i,j 0
A similar argument holds for the pair (s>
,
n→0 , tn→0 ). The paths going through X , i > j, Z , and Y
0
i,j
i
i,j
j,i
i,j
i > j 0 , are cut by vertices x̂i,j
,
ẑ
,
ŷ
∈
X.
The
paths
going
through
X
,
i
>
j,
P
,
and
Y
,
are
cut
φ(i) φ(i) φ(i)
i,j
j,i
by the vertices x̂i,j
φ(i) , ŷφ(i) , pφ(j),φ(i) . Again, it is essential that the other y-path reachable from the p-grid for
<
the pair (j, i), namely Y j,i , does not have outgoing arcs to the terminal t>
n→0 , but only to the terminal tn→0 .
0
We infer that X is a solution to the Directed Multicut instance (G , T , p).

From a multicut to a homomorphism. Let X be a solution to the Directed Multicut instance
(G0 , T , p). Our goal is to find a homomorphism of H into G.
First, let us focus on heavy vertices in X. Observe that for every pair (i, j), ij ∈ E(H) the following
three paths needs to be cut by X:
• a path from sx0→n to tx0→n that traverses the entire path X i,j up to the vertex xi,j
n , and uses the arc
i
x
(xi,j
,
z
)
to
reach
t
,
n
n
0→n
i
i
• a path from sx0→n to tx0→n that starts with using the arc (xi,j
0 , z0 ), and then traverses Z up to the
i
vertex zn , and

• a path from sy0→n to ty0→n that starts with using the arc (z0i , y0i,j ), and then traverses Y i,j up to the
vertex yni,j .
We infer that X needs to contain at least one heavy vertex on every x-, y-, and z-path in H. Recall that
the total weight of exactly one heavy vertex from each of these paths is 6kM = p − k. Thus, we have only
k slack in the budget constraint.
We say that a path X i,j , Y i,j , or Z i is normal if it contains exactly one vertex of X, and cheated otherwise.
We say that a pair (i, j) for ij ∈ E(H) is normal if each of the paths X i,j , Y i,j , X j,i , Y j,i , Z i , and Z j is
normal. A pair (i, j) is cheated if it is not normal. Note that (i, j) is normal if and only if (j, i) is normal.
i
For every i ∈ V (H) we fix one φ(i) ∈ [n] such that ẑφ(i)
∈ X.
Fix now a normal pair (i, j), ij ∈ E(H). Assume i < j; a symmetrical argument holds for i > j but
>
<
<
i,j i i,j
uses the terminal pair (s>
n→0 , tn→0 ) instead of (sn→0 , tn→0 ). Let x̂a , ẑb , ŷc ∈ X. Observe that a ≤ b, as
i,j
x
x
i,j
i
otherwise the path from s0→n to t0→n that traverses X up to the vertex xi,j
a−1 , uses the arc (xa−1 , za−1 ),
i
i
and traverses Z up to the endpoint zn is not cut by X, a contradiction. A similar argument for the terminal
<
pair (sy0→n , ty0→n ) implies that b ≤ c. However, if a < b, then the path from s<
n→0 to tn→0 that traverses
i,j
i,j
i,j i
i
i
X up to the vertex xa , uses the arc (xa , za ), traverses Z up to the endpoint z0 , and finally uses the arc
(z0i , y0i,j ), is not cut by X, a contradiction. A similar argument implies gives a contradiction if b < c.
i,j
i
We infer that for every normal pair (i, j) we have ẑφ(i)
∈ X and x̂i,j
φ(i) , ŷφ(i) ∈ X.
Fix now a normal pair (i, j) with i < j. Observe that the following paths are not cut by the heavy vertices
in X:
i,j
i,j
<
i,j
• a path from s<
up to the vertex xi,j
n→0 to tn→0 that traverses X
φ(i) , uses the arc (xφ(i) , pφ(i),1 ), traverses
i,j
i,j
i,j
the φ(i)-th row of P i,j up to the vertex pi,j
up to
φ(i),n , uses the arc (pφ(i),n , yφ(i)−1 ), and traverses Y

the endpoint y0i,j ;

j,i
i,j
>
j,i
• a path from s>
up to the vertex xj,i
n→0 to tn→0 that traverses X
φ(j) , uses the arc (xφ(j) , p1,φ(j) ), traverses
i,j
j,i
j,i
the φ(j)-th column of P i,j up to the vertex pi,j
n,φ(j) , uses the arc (pn,φ(j) , yφ(j)−1 ), and traverses Y

up to the endpoint y0j,i .
Consequently, X needs to contain at least one light vertex in the p-grid P i,j . Furthermore, if X contains
exactly one light vertex in P i,j , then, as the only vertex in common of the two aforementioned paths for a
i,j
fixed choice of normal (i, j), i < j, is the vertex pi,j
φ(i),φ(j) , we have that pφ(i),φ(j) ∈ X is a light vertex, and,
j
i
by construction, vφ(i)
vφ(j)
∈ E(G).
It remains to show that every pair (i, j), ij ∈ E(H), is normal. Indeed, if this is the case, then, as
p = 6kM + k, the total weight of exactly one heavy vertex on each path X i,j , Y i,j , and Z i is 6kM , and there
are exactly k grids P i,j , every grid P i,j contains exactly one vertex of X, and the argumentation from the
i
previous section shows that i 7→ vφ(i)
is a homomorphism, concluding the proof of Theorem 1.1.
Recall that (i, j) is normal if and only if (j, i) is normal. Let c be the number of cheated pairs (i, j), i < j.
If (i, j), i < j, is cheated, then there is a witness for it: one of the paths X i,j , Y i,j , X j,i , Y j,i , Z i , or Z j is
cheated, that is, contains more than one vertex of X. However, note that a cheated path X i,j , Y i,j , X j,i ,
or Y j,i is a witness only that (i, j) and (j, i) is cheated. Let cXY be the number of cheated x- and y-paths.
Furthermore, a cheated path Z i is a witness that (i, j) is cheated for every ij ∈ E(H): there are only degH (i)
such pairs (i, j). We infer that
X
c ≤ cXY +
degH (i).
i∈V (H):Z i cheated

On the other hand, a cost of a second heavy vertex in X on an x- or y-path is M , while the cost of a second
heavy vertex on Z i is M · degH (i). Furthermore, recall that if (i, j), i < j, is normal, then P i,j contains at
least one vertex of X. Thus, the total weight of X is at least
X
6kM + M · cXY +
M · degH (i) + k − c
i∈V (H):z i cheated

≥ 6kM + M · c + k − c = p + (M − 1)c.
Consequently, if M > 1 and the weight of X is at most p, we have c = 0. This finishes the proof of Theorem 1.1.
The resulting digraph can easily be shown to have directed pathwidth 2. Clearly, it cannot have smaller
directed pathwidth, as it contains two-vertex cycles. In the other direction, order the vertices of the resulting
graphs as follows.
1. All source terminals.
2. The vertices xi,j
a , sorted first by the pair (i, j) lexicographically, and then by the subscript a.
3. The vertices zai , sorted first by i, and then by the subscript a.
4. The vertices pi,j
a,b , sorted first by the pair (i, j) lexicographically, and then by the pair (a, b) lexicographically.
5. The vertices yai,j , sorted first by the pair (i, j) lexicographically, and then by the subscript a.
6. All sink terminals.
Observe now that we can construct a directed path decomposition of the resulting graph by taking bags
consisting of every two consecutive vertices in this order.
We infer that Directed Multicut is W [1]-hard already for integer-weighted instances, parameterized
by total solution weight, for instances with 4 terminals and directed pathwidth 2. This is in sharp contrast
to the result that it is FPT for DAGs [19].

3

Hardness for Steiner Orientation

Construction. Given an input Partitioned Subgraph Isomorphism instance (G, H), we construct an
equivalent Steiner Orientation instance (G0 , T ) as follows.
First, we introduce a number of undirected paths on n vertices: for every i ∈ V (H) we introduce a path
C i on vertices ci1 , ci2 , . . . , cin and a path Di on vertices di1 , di2 , . . . , din , while for every ordered pair (i, j) where
i,j
i,j
i,j
ij ∈ E(H), we introduce a path X i,j on vertices xi,j
on vertices y1i,j , y2i,j , . . . , yni,j .
1 , x2 , . . . , xn and a path Y
We connect these paths as follows: for every i ∈ V (H) and 1 ≤ a ≤ n we add an arc (cia , dia ), while for every
i
i
i,j
pair (i, j) with ij ∈ E(H) and for every 1 ≤ a ≤ n we add arcs (xi,j
a , da ) and (ca , ya ). Furthermore, for
i
i
i
i
every i ∈ V (H) we add terminal pairs (c1 , dn ) and (cn , d1 ) and for every pair (i, j) where ij ∈ E(H), we add
i,j
i
i,j
i
i
i,j
i
terminal pairs (xi,j
1 , dn ), (xn , d1 ), (c1 , yn ), and (cn , y1 ).
i
For an index 1 ≤ a ≤ n, we say that the path C is oriented towards cia if for every 1 ≤ b < n, the edge
i i
cb cb+1 is oriented from cib to cib+1 if b < a and from cib+1 to cib if b ≥ a. Similarly, we say that the path Di
is oriented away from dia if for every 1 ≤ b < n, the edge dib dib+1 is oriented from dib+1 to dib if b < a and from
dib to dib+1 if b ≥ a, and similar notions are defined for the paths X i,j and Y i,j .
Informally speaking, the introduced paths play the role of x−, y−, and z− paths from the reduction for
Directed Multicut. In the currently constructed graph, the only way to satisfy both the terminal pair
(ci1 , din ) and the terminal pair (cin , di1 ) is to chose a number 1 ≤ φ(i) ≤ n and direct the path C i towards ciφ(i)
and the path Di away from diφ(i) . The choice of φ(i) corresponds to the image of i ∈ V (H) in the sought
homomorphism. The additional terminal pairs ensure that the choice is copied to other paths: X i,j needs to
i,j
i,j
be directed towards xi,j
needs to be directed away from yφ(i)
. In the remainder of the construction,
φ(i) and Y
we will not introduce any more edge nor arc incident to a vertex of any path C i or Di , and only arcs going
out of the paths X i,j and arcs going towards the paths Y i,j . In this way we will not introduce any unwanted
way of satisfying the terminal pairs introduced so far, guaranteeing the desired behavior.
Let us now proceed to the construction of the p-grids. Similarly as in the case of Directed Multicut,
for every pair (i, j) with ij ∈ E(H) and i < j we introduce an acyclic n × n grid (called again a p-grid ) with
i,j
i,j
i,j
i,j
vertices pi,j
a,b for 1 ≤ a, b ≤ n and arcs (pa,b , pa+1,b ) for every 1 ≤ a < n and 1 ≤ b ≤ n, as well as (pa,b , pa,b+1 )
for every 1 ≤ a ≤ n and 1 ≤ b < n. We connect the grid to the previously constructed vertices as follows:
for every 1 ≤ a ≤ n we introduce arcs
i,j
(xi,j
a , pa,1 ),

i,j
(pi,j
a,n , ya ),

i,j
(xj,i
a , p1,a ),

j,i
(pi,j
n,a , ya );

please note the lack of shift by one as compared to the Directed Multicut construction. Furthermore,
i,j
j,i j,i
we add terminal pairs (xi,j
n , y1 ) and (xn , y1 ).
j,i
i,j
Observe that, if the paths X and X j,i were directed towards xi,j
φ(i) and xφ(j) respectively, while the
i,j
j,i
paths Y i,j and Y j,i were directed away from yφ(i)
and yφ(j)
respectively, there are unique paths in the graph
i,j
satisfying the newly introduced terminal pairs: the one from xi,j
n to y1 needs to traverse the grid for the
j,i
j,i
pair (i, j) along the φ(i)-th row, while the one from xn to x1 needs to traverse it along the φ(j)-th column.
These two paths intersect at the vertex pi,j
φ(i),φ(j) ; we finish the construction by encoding the edges of G by

the following modification of the vertices pi,j
a,b .
i,j
j,i
For every vertex pa,b , we call its incident four arcs as follows: the north arc goes from pi,j
a−1,b (or xb if
i,j
i,j
i,j
j,i
i,j
a = 1) to pa,b , the south arc goes from pa,b to pa+1,b (or yb if a = n), the west arc goes from pa,b−1 (or
i,j
i,j
i,j
i,j
i j
xi,j
a if b = 1) to pa,b , while the east arc goes from pa,b to pa,b+1 (or ya if b = n). If va vb ∈ E(G), we keep
i,j
i,j
i,j
the vertex pi,j
a,b intact; otherwise, we split the vertex pa,b into two vertices pa,b,SW , pa,b,N E , connected by an
i,j
undirected edge, with pi,j
a,b,SW incident to the south and west arcs and pa,b,N E incident to the north and east
i,j
arcs. With this construction, we cannot traverse the split vertex pa,b from north to south and from west to
east at the same time, forbidding us from choosing φ(i) = a and φ(j) = b simultaneously. This implies that
(G0 , T ) is a positive instance if and only if (G, H) is a positive instance.
This finishes the description of the constructed Steiner Orientation instance (G0 , T ). Note that the

number of terminal pairs is bounded by O(k + `) = O(k). We now prove formally that the reduction is a
correct hardness reduction for Steiner Orientation.
i
From a homomorphism to an orientation. Let φ : [k] → [n] be such that i 7→ vφ(i)
is a homomorphism
of H into G. We start by orienting some of the edges of H as follows. For every i ∈ V (H), orient the path
C i towards ciφ(i) and the path Di away from diφ(i) . Similarly, for every pair (i, j) with ij ∈ E(H), orient the
i,j
i,j
path X i,j towards xi,j
away from yφ(i)
.
φ(i) and orient the path Y
Let G00 be the mixed graph obtained so far. For every terminal pair (s, t) ∈ T , we exhibit a path in G00
from s to t in such a way that no two such paths share an undirected edge. This proves that the remaining
undirected edges can be oriented in the desired way.
It is straightforward to observe that for every terminal pair (s, t) involving a c-vertex or a d-vertex (i.e.,
one introduced in the first part of the construction) there exists a directed path in G00 from s to t consisting of
i,j
i
i
directed arcs only: we may traverse from any endpoint of X i,j or C i up to xi,j
φ(i) or cφ(i) , fall to dφ(i) or yφ(i) ,
i,j
and go along the path Di or Y i,j to any of its endpoints. Thus, it remains to focus on the pairs (xi,j
n , y1 )
j,i j,i
and (xn , y1 ) for ij ∈ E(H), i < j.
For the first pair, we traverse X i,j up to xi,j
φ(i) , then traverse along the φ(i)-row of the grid (i.e., using

vertices pi,j
φ(i),b for 1 ≤ b ≤ n; if any of these vertices is split, we traverse it from west to east using the
i,j
intermediate undirected edge), and traverse Y i,j from yφ(i)
up to y1i,j . The path for the second pair is similar,

but uses the φ(j)-th column of the grid, and traverses every vertex pi,j
a,φ(j) for 1 ≤ a ≤ n from north to south.
j
i
These two paths intersect at pi,j
φ(i),φ(j) . Since vφ(i) vφ(j) ∈ E(G), this vertex is not split and the two
aforementioned paths do not share an undirected edge. As only these two paths are present in the grid for the
pair (i, j), and all undirected edges in G00 are contained in such grids, we conclude that (G0 , T ) is a yes-instance.

From an orientation to a homomorphism. Assume that (G0 , T ) is a yes-instance, and let G00 be an
oriented graph G0 such that for every (s, t) ∈ T , there is a path from s to t in G00 .
Fix a vertex i ∈ V (H). Recall that no arc leads toward any path C i or X i,j , and no arc leads from any
path Di or Y i,j . Furthermore, all arcs leaving C i lead to Di or one of the paths Y i,j , and all arcs going into
Di start in C i or in one of the paths X i,j . We infer that the path from ci1 to din and the path from cin to di1
in G00 both need to be completely contained in G00 [C i ∪ Di ]. Furthermore, such a path for (ci1 , din ) traverses
C i up to some vertex cia , falls to dia , and continues along Di , and similarly for the pair (cin , di1 ). We infer that
there exists an index 1 ≤ φ(i) ≤ n such that C i is oriented towards ciφ(i) , while Di is oriented away from diφ(i) .
i
We claim that i 7→ vφ(i)
is a homomorphism of H into G. Fix an edge ij ∈ E(H), i < j; we aim to show
j
i
that the vertex pi,j
φ(i),φ(j) is not split, which is equivalent to vφ(i) vφ(j) ∈ E(G).
i
i,j
i
A similar reasoning as earlier for the path X i,j and terminal pairs (xi,j
1 , dn ) and (xn , d1 ) implies that
i,j
j,i
j,i
X is oriented towards xφ(i) . Analogously, we obtain that X is oriented towards xφ(j) , Y i,j is oriented
i,j

i,j
j,i
away from yφ(i)
, and Y j,i is oriented away from yφ(j)
.
i,j
The only arcs leaving the path X are arcs going towards Di and the p-grid for the pair (i, j). Similarly,
the only arcs ending in Y i,j start in C i and in the aforementioned p-grid, and analogous claims hold for
i,j
j,i j,i
the paths X j,i and Y j,i . We infer that the paths in H 0 for terminal pairs (xi,j
n , y1 ) and (xn , y1 ) need to
traverse through the p-grid for the pair (i, j).
With the paths X i,j , X j,i , Y i,j , and Y j,i oriented as described, even with keeping the undirected edges
in the grid not oriented, the only path for the first terminal pair traverses the φ(i)-th row of the grid from
i,j
i,j
xi,j
φ(i) , through pφ(i),b for 1 ≤ b ≤ n (split or not), towards yφ(i) , and similarly the only path for the second

terminal pair traverses the φ(j)-th column of the grid. If the vertex pi,j
φ(i),φ(j) is split, these paths traverse
i,j
the undirected edge pi,j
φ(i),φ(j),SW pφ(i),φ(j),N E in opposite directions, a contradiction.
This concludes the proof of Theorem 1.2.

4

Directed treewidth bound of k-cut-minimal graphs

We now prove the directed treewidth upper bound (Theorem 1.3). For the duration of this section, we will
consider arc cuts for convenience, but the result also implies a very similar statement for vertex cuts.
We will need some further preliminaries. For a vertex set U , we let δ(U ) denote the set of arcs leaving
U . Let G = (V, A) be a digraph. A set T ⊆ V is well-linked if for every pair of equal sized subsets X and
Y of T , there are |X| vertex disjoint paths from X to Y in G − (T \ (X ∪ Y )). Well-linked sets are connected
to directed treewidth in the following sense.
Theorem 4.1 (Cor. 6.4.24 of [20]). Let G be a digraph with no well-linked set of cardinality more than k.
Then G has directed treewidth O(k).
In what follows we will work only with well-linked sets, and thus we omit the definition of directed treewidth.
For the definition of directed treewidth, and more on directed width notions, see Kreutzer and Ordyniak [20].
We will show that a k-cut-minimal graph cannot contain an arbitrarily large well-linked set. To illustrate
the approach, assume that T ⊆ V is a well-linked set of sufficiently large size (|T | > f (k) for some f (k) yet to
be specified). We will identify a set U ⊆ V with |δ(U )| ≤ k, such that |T ∩ U |, |T \ U | > k. This contradicts
the assumption that T is well-linked, and implies that G has bounded directed treewidth.
The basic engine of the proof is the anti-isolation lemma, due to Marx. For this, we need to recall the notion
of important separators. (We use the version for directed graphs [8], adapted to our purpose; in particular,
we use arc separators instead of vertex separators. The original definition for undirected graphs was [23].)
Let G = (V, A) be a digraph with s, t ∈ V . An important st-separator is a minimal s-t-cut C ⊆ A such
that there is no s-t-cut C 0 ⊆ A, C 0 =
6 C, with |C 0 | ≤ |C| such that every vertex reachable from s in G − C
0
is also reachable from s in G − C .
Lemma 4.2 ([8]). There are at most 4k important s-t-separators of size at most k.
It is important to note that every s-t-cut C can be “pushed” to an important s-t-separator C 0 with
|C | ≤ |C|, such that every vertex reachable from s in G − C is also reachable from s in G − C 0 .
We state and prove the anti-isolation lemma. (This is taken from a set of lecture slides of Marx [25]; to
the best of our knowledge, no proof has appeared in a formally reviewed publication.) Because the expression
will be used several times, define g(k) = (k + 1)4k+1 .
0

Lemma 4.3 (Anti-isolation [25]). Let s, v1 , . . . , vr be vertices in a digraph G = (V, A), and let C1 , . . . , Cr ⊆ A
be arc sets of size at most k such that for all i, j ∈ [r] there is a path from s to vj in G − Ci if and only if
i = j. Then r ≤ g(k).
Proof. Add a vertex t, and an arc (vi , t) for every i ∈ [r]. Then for every i ∈ [r], the cut Ci ∪ {vi , t} is an
s-t-cut of size at most k + 1, and can be pushed to an important separator Ci0 of size at most k + 1. Note
that necessarily (vi , t) ∈ Ci0 . Since there are only at most 4k+1 important separators of size at most k + 1,
and each of them contains at most k + 1 arcs (vj , t), j ∈ [r], and since every such arc is contained in an
important separator, we conclude that r ≤ (k + 1)4k+1 = g(k).
We will also use the following dual form.
Lemma 4.4. Let t, v1 , . . . , vr be vertices in a digraph G = (V, A), and let C1 , . . . , Cr ⊆ A be arc sets of size
at most k such that for all i, j ∈ [r] there is a path from vj to t in G − Ci if and only if i = j. Then r ≤ g(k).
Proof. Simply apply the anti-isolation lemma to the reversed graph G0 = (V, {(v, u) : (u, v) ∈ A}).
Let us now recall the sunflower lemma. A sunflower is a collection {X1 , . . . , Xr } of subsets of a ground
set V such that all pairwise intersections are identical, i.e., there is a set K ⊆ V (the core of the sunflower)
such that for all i, j ∈ [r], i 6= j we have Xi ∩ Xj = K. The (pairwise disjoint) sets Xi \ K for i ∈ [r] are
called the petals of the sunflower. The famous Sunflower Lemma says the following (original lemma is due
to Erdős and Rado [13]; the following is from Flum and Grohe [14]).

Lemma 4.5. Let H ⊆ 2V be a collection of subsets of size d of a ground set V . If |H| > d!k d , then H
contains a sunflower of cardinality more than k.
Observe that for any minimal st-cut C containing an arc (u, v), the graph G − C contains both an su-path
and a vt-path. Using the Erdős-Rado sunflower lemma, we can then sharpen these statements into the following.
Lemma 4.6. Let G = (V, A) be a digraph, with two distinguished vertices s, t ∈ V . Let F ⊆ A be a collection
of arcs such that every arc (u, v) ∈ F participates in some minimal st-cut of size at most k. If |F | > h(k)
2
where h(k) = 2O(k ) , then there is a minimal st-cut C ⊆ A in G of size at most k that splits F , i.e., there are
more than k arcs (u, v) ∈ F \ C such that G − C contains an su-path, and more than k arcs (u, v) ∈ F \ C
such that G − C contains a vt-path.
Proof. For each (u, v) ∈ F , let Cuv ⊆ A be a minimal s-t-cut with (u, v) ∈ Cuv , with |Cuv | ≤ k. Let Suv
denote the set of vertices reachable from s in G − Cuv , and let Tuv denote the set of vertices that reach t
in G − Cuv . From the observation stated before the lemma statement, by the minimality of Cuv we have
u ∈ Suv and v ∈ Tuv . Also let U = {u : (u, v) ∈ F } and W = {v : (u, v) ∈ F }. We first make a claim to
lower-bound the size of U and W . (This is standard, but we include a proof for completeness.)
Claim 4.7. For every vertex v, at most 2g(k) arcs incident to v participate in minimal s-t-cuts of size at
most k.
Proof. We bound the number of in-arcs and out-arcs separately. For the in-arcs, consider the graph resulting
by adding k + 1 arcs (v, t). Note that every minimal s-t-cut that contains an in-arc of v remains a minimal
s-t-cut. As in the proof of the anti-isolation lemma, we may push each such cut to an important separator,
and this operation will not decrease the set of in-arcs of v contained in the cut. Hence at most g(k) in-arcs of v
participate in minimal s-t-cuts of cardinality at most k. The proof bounding out-arcs is entirely analogous. y
We make a further subsidiary claim.
Claim 4.8. There are at most 2O(k

2

)

arcs (u, v) ∈ F such that |Suv ∩ U | ≤ 2k.

Proof. Consider the collection S = {Suv ∩ U : (u, v) ∈ F }. Let X1 , X2 , . . . , Xr be a sunflower in S with
core K and let Ci be the cut Cuv such that Suv ∩ U = Xi for i ∈ [r]. Pick a vertex xi ∈ Xi \ K for every
i ∈ [r]. Then, the vertices s and xi together with cuts Ci satisfy the prerequisities for the anti-isolation
lemma. Consequently, S does not contain a sunflower of cardinality more than g(k).
Hence by the sunflower lemma, it contains at most d!(g(k))d distinct sets of cardinality d, for each
2
1 ≤ d ≤ 2k. Summing, and ignoring the constant factor, we find that S contains only 2O(k ) sets of size at
most 2k. By the degree observation in the previous claim, every u ∈ U is an endpoint for at most g(k) arcs
2
2
(u, v) ∈ F ; hence there are at most g(k)2O(k ) = 2O(k ) arcs uv ∈ F such that |Suv ∩ U | ≤ 2k, as promised. y
The dual bound also holds.
Claim 4.9. There are at most 2O(k

2

)

arcs (u, v) ∈ F such that |Tuv ∩ W | ≤ 2k.

Proof. This proof is identical to the previous one (except using the form Lemma 4.4 instead of the usual
anti-isolation lemma).
y
Hence, if |F | is large enough, there is at least one arc (u, v) ∈ F such that |Suv ∩ U |, |Tuv ∩ W | > 2k.
Naturally, for every u0 ∈ Suv ∩ U there is a corresponding arc (u0 , v 0 ) ∈ F and similarly for Tuv . Since
Cuv contains at most k arcs, this leaves more than k further arcs of each type, and the cut Cuv fits the
requirements of this lemma. This finishes the proof.
From here, Theorem 1.3 follows easily. Recall that T is a proposed well-linked set. Since G is k-cut-minimal,
every vertex v ∈ T is incident to some arc that participates in a minimal st-cut of size at most k. This gives
us a collection FT ⊆ A of arcs as in Lemma 4.6, with |FT | ≥ |T |/2. If |FT | > h(k), then the cut C provided
2
by the lemma is a witness that T is not well-linked. Hence |T | is bounded by 2O(k ) , and by Theorem 4.1
the directed treewidth of G is bounded by f (k).

5

Conclusions

We have presented reductions showing W [1]- and nearly tight ETH-hardness of Directed Multicut and
Steiner Orientation.
We would like to conclude with two open problems. The first one is the most natural one: is Directed
Multicut, parameterized by the size of the cutset, fixed-parameter tractable for three terminal pairs? It
seems that our main gadget (the p-grid that we use to check an auxiliary binary relation) inherently requires
four commodities to work: two that pass through it horizontally and vertically, and two additional for
synchronizing the cutpoints of the input and output bidirectional paths. On the other hand, we were not
able to extract any combinatorial property of the solutions in the three terminal case that would warrant an
FPT algorithm. As a related question, we would also like to ask whether the two terminal case is WK[1]-hard
parameterized by the cutset, or whether it admits a so-called polynomial Turing kernel (see [17]). It is known
not to admit a polynomial kernel under standard complexity-theoretical assumptions [10], but nothing is
known about Turing kernels (even conjecturally).
Secondly, we would like to repeat from [7] the question of fixed-parameter tractability of the `-Chain
SAT problem, parameterized the cutset. In this problem (with a fixed integer ` in the problem description)
we are given an integer k and a set of n binary variables, unary constraints, and constraints of the form
(x1 ⇒ x2 ) ∧ (x2 ⇒ x3 ) ∧ . . . ∧ (x`−1 ⇒ x` ); one asks to delete at most k constraints to get a satisfiable
instance. It is easy to see that this problem can be cast as a cut problem in directed graphs via the
natural implication/arc correspondence. While it is reasonable to suspect that a strong structural result for
k-cut-minimal graphs may lead to an FPT algorithm for this problem, our lower bound methodology seems
irrelevant, as it inherently requires different commodities.
Acknowledgements. We would like to acknowledge a number of insightful discussions with various people
on the graph cut problems in directed graphs, in particular on k-cut-minimal graphs; we especially thank
Anudhyan Boral, Marek Cygan, Alina Ene, Tomasz Kociumaka, Stefan Kratsch, Daniel Loksthanov, Dániel
Marx, Michal Pilipczuk, Saket Saurabh, and Michal Wlodarczyk.

References
[1] S. A. Amiri, L. Kaiser, S. Kreutzer, R. Rabinovich, and S. Siebertz. Graph searching games and width measures
for directed graphs. In E. W. Mayr and N. Ollinger, editors, 32nd International Symposium on Theoretical
Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, volume 30 of LIPIcs, pages
34–47. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.
[2] J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Springer, 2008.
[3] N. Bousquet, J. Daligault, and S. Thomassé. Multicut is FPT. In L. Fortnow and S. P. Vadhan, editors,
Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June
2011, pages 459–468. ACM, 2011.
[4] J. Chen, Y. Liu, and S. Lu. An improved parameterized algorithm for the minimum node multiway cut problem.
Algorithmica, 55(1):1–13, 2009.
[5] J. Chen, Y. Liu, S. Lu, B. O’Sullivan, and I. Razgon. A fixed-parameter algorithm for the directed feedback
vertex set problem. J. ACM, 55(5), 2008.
[6] R. H. Chitnis, M. Cygan, M. Hajiaghayi, M. Pilipczuk, and M. Pilipczuk. Designing FPT algorithms for cut
problems using randomized contractions. In 53rd Annual IEEE Symposium on Foundations of Computer Science,
FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 460–469. IEEE Computer Society, 2012.
[7] R. H. Chitnis, L. Egri, and D. Marx. List H-coloring a graph by removing few vertices. In H. L. Bodlaender and G. F.
Italiano, editors, Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September
2-4, 2013. Proceedings, volume 8125 of Lecture Notes in Computer Science, pages 313–324. Springer, 2013.
[8] R. H. Chitnis, M. Hajiaghayi, and D. Marx. Fixed-parameter tractability of directed multiway cut parameterized
by the size of the cutset. SIAM J. Comput., 42(4):1674–1696, 2013.
[9] M. Cygan, G. Kortsarz, and Z. Nutov. Steiner forest orientation problems. SIAM J. Discrete Math.,
27(3):1503–1513, 2013.

[10] M. Cygan, S. Kratsch, M. Pilipczuk, M. Pilipczuk, and M. Wahlström. Clique cover and graph separation:
New incompressibility results. TOCT, 6(2):6, 2014.
[11] M. Cygan, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Minimum bisection is fixed parameter
tractable. In D. B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA,
May 31 - June 03, 2014, pages 323–332. ACM, 2014.
[12] M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. O. Wojtaszczyk. On multiway cut parameterized above lower
bounds. TOCT, 5(1):3, 2013.
[13] P. Erdős and R. Rado. Intersection theorems for systems of sets. Journal of the London Mathematical Society,
s1-35(1):85–90, 1960.
[14] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006.
[15] R. Ganian, P. Hlinený, J. Kneis, D. Meister, J. Obdrzálek, P. Rossmanith, and S. Sikdar. Are there any good
digraph width measures? In V. Raman and S. Saurabh, editors, Parameterized and Exact Computation - 5th
International Symposium, IPEC 2010, Chennai, India, December 13-15, 2010. Proceedings, volume 6478 of
Lecture Notes in Computer Science, pages 135–146. Springer, 2010.
[16] R. Ganian, P. Hlinn, J. Kneis, A. Langer, J. Obdrlek, and P. Rossmanith. Digraph width measures in
parameterized algorithmics. Discrete Applied Mathematics, 168(0):88 – 107, 2014. Fifth Workshop on Graph
Classes, Optimization, and Width Parameters, Daejeon, Korea, October 2011.
[17] D. Hermelin, S. Kratsch, K. Soltys, M. Wahlström, and X. Wu. A completeness theory for polynomial (turing)
kernelization. Algorithmica, 71(3):702–730, 2015.
[18] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? J. Comput.
Syst. Sci., 63(4):512–530, 2001.
[19] S. Kratsch, M. Pilipczuk, M. Pilipczuk, and M. Wahlström. Fixed-parameter tractability of multicut in directed
acyclic graphs. SIAM J. Discrete Math., 29(1):122–144, 2015.
[20] S. Kreutzer and S. Ordyniak. Width-measures for directed graphs and algorithmic applications. In M. Dehmer
and F. Emmert-Streib, editors, Quantitative Graph Theory: Mathematical Foundations and Applications.
Chapman and Hall/CRC Press, 2014.
[21] D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the exponential time hypothesis. Bulletin
of the EATCS, 105:41–72, 2011.
[22] D. Lokshtanov, N. S. Narayanaswamy, V. Raman, M. S. Ramanujan, and S. Saurabh. Faster parameterized
algorithms using linear programming. ACM Transactions on Algorithms, 11(2):15:1–15:31, 2014.
[23] D. Marx. Parameterized graph separation problems. Theor. Comput. Sci., 351(3):394–406, 2006.
[24] D. Marx. Can you beat treewidth? Theory of Computing, 6(1):85–112, 2010.
[25] D. Marx.
Important separators and parameterized algorithms, 2011.
Lecture slides; available at
http://www.cs.bme.hu/~dmarx/papers/marx-mds-separators-slides.pdf.
[26] D. Marx. What’s next? Future directions in parameterized complexity. In H. L. Bodlaender, R. Downey,
F. V. Fomin, and D. Marx, editors, The Multivariate Algorithmic Revolution and Beyond - Essays Dedicated
to Michael R. Fellows on the Occasion of His 60th Birthday, volume 7370 of Lecture Notes in Computer Science,
pages 469–496. Springer, 2012.
[27] D. Marx, B. O’Sullivan, and I. Razgon. Finding small separators in linear time via treewidth reduction. ACM
Transactions on Algorithms, 9(4):30, 2013.
[28] D. Marx and I. Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. SIAM
J. Comput., 43(2):355–388, 2014.
[29] M. Pilipczuk and M. Wahlström. Directed multicut is W [1]-hard, even for four terminal pairs. In R. Krauthgamer,
editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016,
Arlington, VA, USA, January 10-12, 2016, pages 1167–1178. SIAM, 2016.
[30] I. Razgon and B. O’Sullivan. Almost 2-SAT is fixed-parameter tractable. J. Comput. Syst. Sci., 75(8):435–450,
2009.
[31] M. Wahlström. Half-integrality, LP-branching and FPT algorithms. In C. Chekuri, editor, Proceedings of the
Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA,
January 5-7, 2014, pages 1762–1781. SIAM, 2014.

x-path for pair (j, i)
sx0→n

xj,i
0

xj,i
n

s>
n→0
t<
n→0

xi,j
0

y-path for pair (i, j)

x-path for pair (i, j)

y0i,j

xi,j
n
yni,j
s<
n→0
t>
n→0

y0j,i

ynj,i

ty0→n

y-path for pair (j, i)

x-path

sx0→n

z-path

sy0→n

y-path

t<
n→0

x̂i,j
a
s<
n→0
ẑai

ŷai,j

tx0→n

ty0→n

Figure 2: Illustration of the reduction for Directed Multicut. Black vertices are light, gray are heavy,
and white are undeletable. The top figure illustates a p-grid, together with an intended solution marked
by red circles. Here, the vertex p1,1 lies in the top-left corner of the grid, the first coordinate describes the
row of the grid, and the second one the column. The bottom figure illustrates an x-, z-, and y-path for
a pair (i, j) with ij ∈ E(H) and i < j.

X j,i

X i,j

Y i,j

Y j,i
Y i,j

Ci

Di

X i,j

Figure 3: Illustration of the reduction for Steiner Orientation. Thick gray arrows represent terminal
pairs. The top figure illustates a p-grid; dashed rectangles represent single entities pi,j
a,b . The bottom figure
i,j
i,j
i
i
illustrates synchronization between paths X , Y , C , and D .

