Fixed-Parameter Algorithms for DAG PartitioningI
René van Beverna,b,∗, Robert Bredereckb , Morgan Chopinc , Sepp Hartungb , Falk Hüffnerb , André Nichterleinb , Ondřej
Suchýd,b
a Novosibirsk

State University, Novosibirsk, Russian Federation
für Softwaretechnik und Theoretische Informatik, TU Berlin, Germany
c Institut für Optimierung und Operations Research, Universität Ulm, Germany
d Faculty of Information Technology, Czech Technical University in Prague, Czech Republic

arXiv:1611.08809v1 [cs.DS] 27 Nov 2016

b Institut

Abstract
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al. [ACM
SIGKDD 2009] as DAG PARTITIONING: given an arc-weighted directed acyclic graph on n vertices and m arcs,
delete arcs with total weight at most k such that each resulting weakly-connected component contains exactly one
sink—a vertex without outgoing arcs. DAG PARTITIONING is NP-hard.
We show an algorithm to solve DAG PARTITIONING in O(2k · (n + m)) time, that is, in linear time for fixed k. We
complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can
optimally solve DAG PARTITIONING on simulated citation networks within five minutes for k ≤ 190 and m being 107
and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.’s heuristic.
We show that Leskovec et al.’s heuristic works optimally on trees and generalize this result by showing that DAG
2
PARTITIONING is solvable in 2O(t ) · n time if a width-t tree decomposition of the input graph is given. Thus, we
improve an algorithm and answer an open question of Alamdari and Mehrabian [WAW 2012].
We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of
data reduction.
Keywords: NP-hard problem, graph algorithms, polynomial-time data reduction, multiway cut, linear-time algorithms,
algorithm engineering, evaluating heuristics

1. Introduction
The DAG PARTITIONING problem was introduced by Leskovec et al. [26] in order to analyze how short, distinctive
phrases (typically, parts or mutations of quotations, also called memes) spread to various news sites and blogs. To
demonstrate their approach, Leskovec et al. [26] collected and analyzed phrases from 90 million articles from the
time around the United States presidential elections in 2008; the results were featured in the New York Times [27].
Meanwhile, their approach has grown up into N IFTY, a system that allows near real-time observation of the rise and
fall of trends, ideas, and topics in the internet [33].
A core component in the approach of Leskovec et al. [26] is a heuristic to solve the NP-hard DAG PARTITIONING
problem. They use it to cluster short phrases, which may undergo modifications while propagating through the web,
with respect to their origins. To this end, they create an arc-weighted directed acyclic graph with phrases as vertices
and draw an arc from phrase p to phrase q if p presumably originates from q, where the weight of an arc represents the
I A preliminary version of this article appeared in the Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC’13) [5].
Besides providing full proof details, this revised and extended version improves our O(2k · n2 )-time algorithm to run in O(2k · (n + m)) time and
provides linear-time executable data reduction rules. Moreover, we experimentally evaluated the algorithm and compared it to known heuristics by
Leskovec et al. [26]. We prove the latter to work optimally on trees.
∗ Corresponding author.
Email addresses: rvb@nsu.ru (René van Bevern), robert.bredereck@tu-berlin.de (Robert Bredereck),
andre.nichterlein@tu-berlin.de (André Nichterlein), ondrej.suchy@fit.cvut.cz (Ondřej Suchý)

support for this hypothesis: the weight assigned to an arc (p, q) is chosen inversely proportional to the time difference
between p and q and their Levenshtein distance when using words as tokens, whereas it is proportional to the total
number of documents in the corpus that contain the phrase q.1 A vertex without outgoing arcs is called a sink and
can be interpreted as the origin of a phrase. If a phrase has directed paths to more than one sink, its ultimate origin is
ambiguous and, in the model of Leskovec et al. [26], at least one of the “p originates from q” hypotheses is wrong.
Leskovec et al. [26] introduced DAG PARTITIONING with the aim to resolve these inconsistencies by removing a set
of arcs (hypotheses) with least support:
DAG PARTITIONING
Input: A directed acyclic graph G = (V, A) with positive integer arc weights ω : A → N and a positive integer k ∈ N.
Question: Is there a set S ⊆ A with ∑a∈S ω(a) ≤ k such that each weakly-connected component in G0 = (V, A \ S)
has exactly one sink?
Herein, the model of Leskovec et al. [26] exploits that a weakly-connected component of a directed acyclic graph
contains exactly one sink if and only if all its vertices have directed paths to only one sink. We call a set S ⊆ A such
that each weakly-connected component in G0 = (V, A \ S) has exactly one sink a partitioning set.
Leskovec et al. [26] showed that DAG PARTITIONING is NP-hard and presented a heuristic to find partitioning sets
of small weight. Alamdari and Mehrabian [1] showed that, for fixed ε > 0, even approximating the minimum weight of
a partitioning set within a factor of O(n1−ε ) is NP-hard. In the absence of approximation algorithms, exact solutions to
DAG PARTITIONING become interesting for the reason of evaluating the quality of known heuristics alone.
We aim for solving DAG PARTITIONING exactly using fixed-parameter algorithms—a framework to obtain
algorithms to optimally solve NP-hard problems that run efficiently given that certain parameters of the input data are
small [15, 28, 12]. A natural parameter to consider is the minimum weight k of the partitioning set sought, since one
would expect that wrong hypotheses have little support.
Known results. To date, there are only few studies on DAG PARTITIONING. Leskovec et al. [26] showed that DAG
PARTITIONING is NP-hard and present heuristics. Alamdari and Mehrabian [1] showed that, on n-vertex graphs, DAG
PARTITIONING is hard to approximate in the sense that if P , NP, then there is no polynomial-time factor-(n1−ε )
approximation algorithm for any fixed ε > 0, even if the input graph has unit-weight arcs, maximum outdegree three,
2
and only two sinks. Moreover, Alamdari and Mehrabian [1] showed that DAG PARTITIONING can be solved in 2O(t ) · n
time if a width-t path decomposition of the input graph is given.
DAG PARTITIONING is very similar to the well-known NP-hard M ULTIWAY C UT problem [11]: given an undirected
edge-weighted graph and a subset of the vertices called terminals, delete edges of total weight at most k such that each
terminal is separated from all others. DAG PARTITIONING can be considered as M ULTIWAY C UT with the sinks being
terminals and the additional constraint that not all arcs outgoing from a vertex may be deleted, since this would create a
new sink. Xiao [34] gave an algorithm to solve M ULTIWAY C UT in O(2k · min(n2/3 , m1/2 ) · nm) time. Interestingly, in
contrast to DAG PARTITIONING, M ULTIWAY C UT is constant-factor approximable (see, e. g., Karger et al. [23]).
Our results. We provide algorithmic as well as intractability results. On the algorithmic side, we present an O(2k · (n +
m)) time algorithm for DAG PARTITIONING and complement it with linear-time executable data reduction rules. We
experimentally evaluated both and, in combination, they solved instances with k ≤ 190 optimally within five minutes,
the number of input arcs being 107 and larger. Moreover, we use the optimal solutions found by our algorithm to
evaluate the quality of Leskovec et al. [26]’s heuristic and find that it finds optimal solutions for most instances that our
algorithm solves quickly, but performs worse by a factor of more than two on other instances.
2
Also, we give an algorithm that solves DAG PARTITIONING in 2O(t ) · n time if a width-t tree decomposition of
the input graph is given. We thus answer an open question by Alamdari and Mehrabian [1]. Since every width-t path
decomposition is a width-t tree decomposition but not every graph allowing for a width-t tree decomposition allows
2
for a width-t path decomposition, our algorithm is an improvement over the 2O(t ) · n-time algorithm of Alamdari and
Mehrabian [1], which requires a path decomposition as input.
1 Unfortunately, Leskovec et al. [26] neither give a more precise description nor the range of their weights. All our hardness results even hold for
unit weights, while all our algorithms work whenever the weight of each arc is at least one; however, we choose the weights to be positive integers to
avoid representation issues.

2

On the side of intractability results, we strengthen the NP-hardness results of Leskovec et al. [26] and Alamdari and
Mehrabian [1] to graphs of diameter two and maximum degree three and we show that our O(2k ·(n+m)) time algorithm
cannot be improved to O(2o(k) · poly(n)) time unless the Exponential Time Hypothesis fails. Moreover, we show that
DAG PARTITIONING does not admit polynomial-size problem kernels with respect to k unless NP ⊆ coNP/poly.
Organization of this paper. In Section 2, we introduce necessary notation and two basic structural observations for
DAG PARTITIONING that are important in our proofs.
In Section 3, we present our O(2k · (n + m)) time algorithm and its experimental evaluation. With the help of the
optimal solutions computed by our algorithm we also evaluate the quality of a heuristic presented by Leskovec et al. [26].
Moreover, we discuss the limits of parameterized algorithms and problem kernelization for DAG PARTITIONING
parameterized by k.
2
Section 4 presents our 2O(t ) · n time algorithm. It follows that DAG PARTITIONING is linear-time solvable when at
least one of the parameters k or t is fixed. We further show that the heuristic presented by Leskovec et al. [26] works
optimally on trees.
Section 5 then shows that other parameters are not as helpful in solving DAG PARTITIONING: DAG PARTITIONING
remains NP-hard even when graph parameters like the diameter or maximum degree are constants.
2. Preliminaries and basic observations
We consider finite simple directed graphs G = (V, A) with vertex set V (G) := V and arc set A(G) := A ⊆ V ×V , as
well as finite simple undirected graphs G = (V, E) with vertex set V and edge set E(G) := E ⊆ {{u, v} | u, v ∈ V }. For
a directed graph G, the underlying undirected graph G0 is the graph that has undirected edges in the places where G has
arcs, that is, G0 = (V (G), {{v, w} : (v, w) ∈ A(G)}). We will use n to denote the number of vertices and m to denote the
number of arcs or edges of a graph.
For a (directed or undirected) graph G, we denote by G \ A0 the subgraph obtained by removing from G the arcs or
edges in A0 and by G −V 0 the subgraph obtained by removing from G the vertices in V 0 . For V 0 ⊆ V , we denote by
G[V 0 ] := G − (V \V 0 ) the subgraph of G induced by the vertex set V 0 .
The set of out-neighbors and in-neighbors of a vertex v in a directed graph is N + (v) := {u | (v, u) ∈ A} and N − (v) :=
{u | (u, v) ∈ A}, respectively. The outdegree, the indegree, and the degree of a vertex v ∈ V are d + (v) := |N + (v)|,
d − (v) := |N − (v)|, and d(v) := d + (v) + d − (v), respectively. A vertex v is a sink if d + (v) = 0; it is isolated if d(v) = 0.
A path of length ` − 1 from v1 to v` in an undirected graph G is a tuple (v1 , . . . , v` ) ∈ V ` such that {vi , vi+1 } is an
edge in G for 1 ≤ i ≤ ` − 1. An undirected path in a directed graph is a path in its underlying undirected graph. A
directed path of length ` − 1 from v1 to v` in a directed graph G is a tuple (v1 , . . . , v` ) ∈ V ` such that (vi , vi+1 ) is an arc
in G for 1 ≤ i ≤ ` − 1.
We say that u ∈ V can reach v ∈ V or that v is reachable from u in G if there is a directed path from u to v in G. We
say that u and v are connected if there is a (not necessarily directed) path from u to v in G. In particular, u is reachable
from u and connected to u. We use connected component as an abbreviation for weakly connected component, that is, a
maximal set of pairwise connected vertices. The diameter of G is the maximum length of a shortest path between two
different vertices in the underlying undirected graph of G.
Fixed-parameter algorithms. The main idea in fixed-parameter algorithms is to accept the super-polynomial running
time, which is seemingly inevitable when optimally solving NP-hard problems, but to restrict it to one aspect of the
problem, the parameter. More precisely, a problem Π is fixed-parameter tractable (FPT) with respect to a parameter k
if there is an algorithm solving any instance of Π with size n in f (k) · poly(n) time for some computable function f
[15, 28, 12, 10]. Such an algorithm is called fixed-parameter algorithm. Since Suen et al. [33] point out that the input
instances of DAG PARTITIONING can be so large that even running times quadratic in the input size are prohibitively
large, we focus on finding algorithms that run in linear time if the parameter k is a constant. An important ingredient
of our algorithms is linear-time data reduction, which recently received increased interest since data reduction is
potentially applied to large input data [32, 4, 18, 3, 22, 13].

3

Problem kernelization. One way of deriving fixed-parameter algorithms is (problem) kernelization [17, 7]. As a formal
approach of describing efficient data reduction that preserves optimal solutions, problem kernelization is a powerful
tool for attacking NP-hard problems. A kernelization algorithm consists of data reduction rules that, applied to any
instance x with parameter k, yield an instance x0 with parameter k0 in time polynomial in |x| + k such that (x, k) is a
yes-instance if and only if (x0 , k0 ) is a yes-instance, and if both |x0 | and k0 are bounded by some functions g and g0 in k,
respectively. The function g is referred to as the size of the problem kernel (x0 , k0 ).
Note that it is the parameter that allows us to measure the effectiveness of polynomial-time executable data
reduction, since a statement like “the data reduction shrinks the input by a factor α” would imply that we can solve
NP-hard problems in polynomial time.
From a practical point of view, problem kernelization is potentially applicable to speed up exact and heuristic
algorithms to solve a problem. Since kernelization is applied to shrink potentially large input instances, recently the
running time of kernelization has stepped into the focus and linear-time kernelization algorithms have been developed
for various NP-hard problems [32, 4, 18, 3, 22, 13].
Two basic observations.. The following easy to prove structural observations will be exploited in many proofs of our
work. The first observation states that a minimal partitioning set does not introduce new sinks.
Observation 1. Let G be a directed acyclic graph and S be a minimal partitioning set for G. Then, a vertex is a sink
in G \ S if and only if it is a sink in G.
P ROOF. Clearly, deleting arcs from a directed acyclic graph cannot turn a sink into a non-sink. Therefore, it remains to
show that every sink in G \ S was a sink already in G. Towards a contradiction, assume that there is a vertex s that is
a sink in G \ S but not in G. Then, there is an arc (s, v) in G for some vertex v of G. Let Cv and Cs be the connected
components in G \ S containing v and s, respectively, and let sv be the sink in Cv . Then, for S0 := S \ {(s, v)}, the
connected component Cv ∪Cs in G \ S0 has only one sink, namely sv . Thus, S0 is also a partitioning set for G, but S0 ( S,
a contradiction to S being minimal.

The second observation is that each vertex in a directed acyclic graph is connected to exactly one sink if and only if
it can reach that sink.
Observation 2. Let G be a directed acyclic graph. An arc set S is a partitioning set for G if and only if each vertex
in G can reach exactly one sink in G \ S.
P ROOF. If S is a partitioning set for G, then, by definition, each connected component of G \ S contains exactly one
sink. Therefore, each vertex in G \ S can reach at most one sink. Moreover, since G \ S is a directed acyclic graph and
each vertex in a directed acyclic graph can reach at least one sink, it follows that each vertex in G \ S can reach exactly
one sink.
Now, assume that each vertex in G \ S can reach exactly one sink. We show that each connected component of G \ S
contains exactly one sink. For the sake of contradiction, assume that a connected component C of G \ S contains
multiple sinks s1 , . . . , st . For i ∈ [t], let Ai be the set of vertices that reach si . These vertex sets are pairwise disjoint and,
since every vertex in a directed acyclic graph reaches some sink, they partition the vertex set of C.
Since C is a connected component, there are i, j ∈ [t] with i , j and some arc (v, w) in G \ S from some vertex v ∈ Ai
to some vertex w ∈ A j . This is a contradiction, since v can reach si as well as s j .

3. Parameter weight of the partitioning set sought
This section investigates the influence of the parameter “weight k of the partitioning set sought” on DAG PAR First, in Section 3.1, we present an O(2k · (n + m))-time algorithm and design linear-time executable
data reduction rules. In Section 3.2, we experimentally evaluate the algorithm and data reduction rules and—with
the help of the optimal solutions computed by our algorithm—we also evaluate the quality of a heuristic presented
by Leskovec et al. [26]. In Section 3.3, we investigate the question whether the provided data reduction rules might
have a provable shrinking effect on the input instance in form of a polynomial-size problem kernel. We will see that,
despite the fact that data reduction rules work very effectively in experiments, polynomial-size problem kernels for
DAG PARTITIONING do not exist under reasonable complexity-theoretic assumptions. Moreover, Section 3.3 will also
show that the algorithm presented in Section 3.1 is essentially optimal.

TITIONING .

4

Algorithm 1: Compute a partitioning set of weight at most k.
Input: A directed acyclic graph G = (V, A) with arc weights ω and a positive integer k.
Output: A partitioning set S of weight at most k if it exists; otherwise ‘no’.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

(v1 , v2 , . . . , vn ) ← reverse topological order of the vertices of G
L ← array with n entries
searchtree(1, 0)
/
// start with vertex v1 and S = 0/
output ‘no’
// there is no partitioning set of weight at most k
Procedure searchtree(i, S)
// vertex counter i; (partial) partitioning set S
while vi is a sink s or there is a sink s such that ∀w ∈ N + (vi ) : L[w] = s do
L[vi ] ← s
// associate vi with sink s
i ← i+1
// continue with next vertex
if i > n then
if ω(S) ≤ k then output S

// all vertices have been handled, S is a partitioning set
// a partitioning set of weight at most k has been found

else
D ← {L[w] | w ∈ N + (vi )}
// the set of feasible sinks for vi
if |D| − 1 ≤ k − ω(S) then
// check whether we are allowed to delete |D| − 1 arcs
foreach s ∈ D do
// try to associate vi to each feasible sink s
L[vi ] ← s
S0 ← S ∪ {(vi , w) | w ∈ N + (vi ) and L[w] , s}
searchtree(i + 1, S0 )

3.1. Constant-weight partitioning sets in linear time
We now present an algorithm to compute partitioning sets of weight k in O(2k · (n + m)) time. Interestingly, although
both problems are NP-hard, it will turn out that DAG PARTITIONING is substantially easier to solve exactly than the
closely related M ULTIWAY C UT problem, for which a sophisticated algorithm running in O(2k min(n2/3 , m1/2 )nm) time
was given by Xiao [34]. This is in contrast to M ULTIWAY C UT being constant-factor approximable [23], while DAG
PARTITIONING is inapproximable unless P = NP [1].
The main structural advantage of DAG PARTITIONING over M ULTIWAY C UT is the alternative characterization of
partitioning sets given in Observation 2: we only have to decide which sink each vertex v will reach in the optimally
partitioned graph. To this end, we first decide the question for all out-neighbors of v. This natural processing order
allows us to solve DAG PARTITIONING by the simple search tree algorithm shown in Algorithm 1, which we explain
in the proof of the following theorem.
Theorem 1. Algorithm 1 solves DAG PARTITIONING in O(2k · (n + m)) time.
P ROOF. Algorithm 1 is based on recursive branching and computes a partitioning set S of weight at most k for a
directed acyclic graph G = (V, A). It exploits the following structural properties of a minimal partitioning set S: by
Observation 2, a vertex v is connected to a sink s in G \ S if and only if it can reach that sink s in G \ S. Thus, consider a
vertex v of G and assume that we know, for each out-neighbor w of v in G, the sink s that w can reach in G \ S. We call a
sink s of G feasible for v if an out-neighbor of v in G can reach s in G \ S. Let D be the set of feasible sinks for v. Since
v may be connected to only one sink in G \ S, at least |D| − 1 arcs outgoing from v are deleted by S. However, S does
not disconnect v from all sinks in D, since then S would delete all arcs outgoing from v, contradicting Observation 1.
Hence, exactly one sink s ∈ D must be reachable by v in G \ S. For each such sink s ∈ D, the partitioning set S has to
delete at least |D| − 1 arcs outgoing from v. We simply try out all these possibilities, which gives rise to the following
search tree algorithm.
Algorithm 1 starts with S = 0/ and processes the vertices of G in reverse topological order, that is, each vertex is
processed by procedure ”searchtree” after its out-neighbors. The procedure exploits the invariant that, when processing
5

a vertex v, each out-neighbor w of v has already been associated with the sink s that it reaches in G \ S (in terms of
Algorithm 1, L[w] = s). It then tries all possibilities of associating v with a feasible sink and augmenting S accordingly,
so that the invariant also holds for the vertex processed after v.
Specifically, if v is a sink, then line 7 associates v with itself. If all out-neighbors of v are associated with the same
sink s, then line 7 associates v with s. Otherwise, line 12 computes the set D of feasible sinks for v. In lines 14–17,
the algorithm branches into all possibilities of associating v with one of the |D| feasible sinks s ∈ D (by way of
setting L[v] ← s in line 15) and augmenting S so that v only reaches s in G \ S. That is, in each of the |D| branches, it
adds to S the arcs outgoing from v to the out-neighbors of v that are associated with sinks different from s (the weight
of S increases by at least |D| − 1). Then, line 17 continues with the next vertex in the reverse topological order. After
processing the last vertex, each vertex of G \ S can reach exactly one sink, that is, S is a partitioning set. If a branch
finds a partitioning set with weight at most k, line 10 outputs it.
We analyze the running time of this algorithm. To this end, we first bound the total number of times that procedure
“searchtree” is called. To this end, we first analyze the number of terminal calls, that is, calls that do not recursively call
the procedure. Let T (α) denote the maximum possible number of terminal calls caused by the procedure “searchtree”
when called with a set S satisfying ω(S) ≥ α, including itself if it is a terminal call. Note that procedure “searchtree”
calls itself only in line 17, that is, for each sink s of some set D of feasible sinks with 1 ≤ |D| − 1 ≤ k − α, it calls itself
with a set S0 of weight at least α + |D| − 1. Thus, we have
T (α) ≤ |D| · T (α + |D| − 1).
We now inductively show that T (α) ≤ 2k−α for 0 ≤ α ≤ k. Then, it follows that there is a total number of T (0) ≤
2k terminal calls. For the induction base case, observe that T (k) = 1, since, if procedure “searchtree” is called with a set S
0
of weight at least k, then any recursive call is prevented by the check in line 13. Now, assume that T (α 0 ) ≤ 2k−α holds
for all α 0 with α ≤ α 0 ≤ k. We show T (α − 1) ≤ 2k−(α−1) by exploiting 2 ≤ |D| ≤ 2|D|−1 as follows:
T (α − 1) ≤ |D| · T (α − 1 + |D| − 1) ≤ |D| · 2k−(α−1)−(|D|−1) ≤ |D| ·

2k−(α−1)
≤ 2k−(α−1) .
2|D|−1

It follows that there are at most T (0) = 2k terminal calls to procedure “searchtree”.
In order to bound the total number of calls to procedure “searchtree”, observe the following: if each inner node
of a tree has at least two children, then the number of inner nodes in a tree is at most its number of leaves. Now,
since procedure “searchtree” calls itself only in line 17, that is, for each sink s of some set D of feasible sinks
with 1 ≤ |D| − 1 ≤ k − α, each non-terminal call causes at least two new calls. Thus, since there are O(2k ) terminal
calls, there are also O(2k ) non-terminal calls.
It follows that there are O(2k ) total calls of procedure “searchtree”. For each such call, we iterate, in the worst
case, over all out-neighbors of all vertices in the graph in lines 6–12, which works in O(n + m) time. Moreover,
for each call of procedure “searchtree”, we compute a set S0 in line 16 in O(n + m) time. Hence, a total amount
of O(2k · (n + m)) time is spent in procedure “searchtree”. Initially, Algorithm 1 uses O(n + m) time to compute a
reverse topological ordering [9, Section 22.4].

The experimental results in Section 3.2 will show that Algorithm 1 alone cannot solve even moderately large instances.
Therefore, we complement it by linear-time executable data reduction rules that will allow for a significant speedup.
The following data reduction rule is illustrated in Figure 1.
Reduction Rule 1. If there is an arc (v, w) such that w can reach exactly one sink s , w and v can reach multiple sinks,
then
• if there is no arc (v, s), then add it with weight ω(v, w),
• otherwise, increase ω(v, s) by ω(v, w), and
delete the arc (v, w).
Note that, in the formulation of the data reduction rule, both v and w may be connected to an arbitrary number of sinks
by an undirected path. However, we require that w can reach exactly one sink and that v can reach multiple sinks, that
is, using a directed path.
6

v

v

w
2

s1

s2

s1

s2

Figure 1: The left side shows an input graph with unit weights to which Reduction Rule 1 is applicable. The right side shows the same graph to
which Reduction Rule 1 has been applied as often as possible. Since v can reach multiple sinks and its out-neighbors each can reach only one sink,
its arcs got redirected. Unlabeled arcs have weight one.

Lemma 1. Let (G, ω, k) be a DAG PARTITIONING instance and consider the graph G0 with weights ω 0 output by
Reduction Rule 1 applied to an arc (v, w) of G. Then (G, ω, k) is a yes-instance if and only if (G0 , ω 0 , k) is a yes-instance.
P ROOF. First, assume that (G, ω, k) is a yes-instance and that S is a minimal partitioning set of weight at most k
for G. We show how to transform S into a partitioning set of equal weight for G0 . We distinguish two cases: either S
disconnects v from s or not, where s is the only sink that w can reach.
Case 1) Assume that S disconnects v from s. Note that every subgraph of a directed acyclic graph is again a
directed acyclic graph and that every vertex in a directed acyclic graph is not only connected to, but also can reach some
sink. Hence, by Observation 1, S cannot disconnect w from s, since w can only reach s in G and would have to reach
some other, that is, new sink in G \ S. It follows that S contains the arc (v, w). Now, however, S0 := (S \ {v, w}) ∪ {(v, s)}
is a partitioning set for G0 , since G \ S = G0 \ S0 . Moreover, since ω 0 (v, s) = ω(v, s) + ω(v, w), we have ω 0 (S0 ) = ω(S),
where we, for convenience, declare ω(v, s) = 0 if there is no arc (v, s) in G.
Case 2) Assume that S does not disconnect v from s and, for the sake of a contradiction, that S is not a partitioning
set for G0 . Observe that S contains neither (v, w) nor (v, s), because it is a minimal partitioning set and does not
disconnect v from s. Therefore, G0 \ S differs from G \ S only in the fact that G0 \ S does not have the arc (v, w) but an
arc (v, s) that was possibly not present in G \ S. Hence, since S is a partitioning set for G but not for G0 , two sinks are
connected to each other in G0 \ S via an undirected path using the arc (v, s). Thus, one of the two sinks is s and the
undirected path consists of (v, s) and a subpath p between v and some sink s0 . Then, however, s is connected to s0 also
in G \ S via an undirected path between s and w (S cannot disconnect s from w by Observation 1), the arc (v, w) and the
undirected path p from v to s0 . This contradicts S being a partitioning set for G. We conclude that S is a partitioning set
for G0 . Moreover, since S contains neither (v, w) nor (v, s), one has ω(S) = ω 0 (S).
Now, assume that (G0 , ω 0 , k) is a yes-instance and that S is a minimal partitioning set of weight at most k for G0 .
We show how to transform S into a partitioning set of equal weight for G. Again, we distinguish between two cases:
either S disconnects v from s or not.
Case 1) Assume that S disconnects v from s. Then, (v, s) ∈ S. Now, S0 := S ∪ {(v, w)} is a partitioning set for G,
since G \ S0 = G0 \ S. Moreover, since ω 0 (v, s) = ω(v, s) + ω(v, w), we have ω(S0 ) = ω 0 (S), where we assume that
ω(v, s) = 0 if there is no arc (v, s) in G.
Case 2) Assume that S does not disconnect v from s and, for the sake of a contradiction, assume that S is not a
partitioning set for G. Then, since S is minimal, S does not contain (v, s). Now, observe that G \ S and G0 \ S differ only
in the fact that G \ S has an additional arc (v, w) and that, possibly, (v, s) is missing. Hence, since S is a partitioning set
for G0 but not for G, there is an undirected path between two sinks in G \ S through (v, w). Because S by Observation 1
cannot disconnect w from s, one of these sinks is s and the undirected path consists of a subpath between s and w,
the arc (v, w), and a subpath p between v and a sink s0 . Then, however, s and s0 are also connected in G0 \ S via the
arc (v, s) and the subpath p between v and s0 . This contradicts S being a partitioning set for G0 . Finally, since S does not
contain (v, s), one has ω(S) = ω 0 (S).

7

v

v

2

2

s1

s2

s1

s2

Figure 2: On the left side, a graph that cannot be reduced by Reduction Rule 1 is shown. The gray background highlights the non-sink vertices that
can only reach the sink s1 . The right side shows the same graph to which Reduction Rule 2 has been applied as often as possible. Unlabeled arcs
have weight one.

After applying Reduction Rule 1 exhaustively, that is, as often as it is applicable, we apply a second data reduction rule,
which is illustrated in Figure 2.
Reduction Rule 2. If, for some sink s, the set L of non-sink vertices that can reach only s is nonempty, then delete all
vertices in L.
Lemma 2. Let G be a graph that is exhaustively reduced with respect to Reduction Rule 1 and G0 := G − L be the
graph output by Reduction Rule 2 when applied to G for some sink s. Then, any partitioning set for G is a partitioning
set of equal weight for G0 and vice versa.
P ROOF. In order to prove the lemma, we first make three structural observations about the set L.
i) There is no arc (v, w) from a vertex v < L to a vertex w ∈ L in G: for the sake of a contradiction, assume that such
an arc exists. Then, since v < L and v is obviously not a sink, v can reach a sink s0 , s. It follows that v can reach
two sinks: s via w and s0 . This contradicts the assumption that Reduction Rule 1 is not applicable.
ii) There is no arc (v, w) from a vertex v ∈ L to a vertex w < L with w , s in G: for the sake of a contradiction, assume
that such an arc exists. Then, since w < L and w , s, it follows that w can reach a sink s0 different from s. Then,
also v can reach two sinks: s0 via w and s. This contradicts v ∈ L.
iii) A minimal partitioning set S for G does not contain any arc between vertices in L ∪ {s}: this is because, by
Observation 1, no minimal partitioning set S can disconnect any vertex v ∈ L from s, since otherwise v would
reach another, that is, new sink in G \ S.
Now, let S be a minimal partitioning set for G. Then, S is also a partitioning set for G0 , since G0 \ S = (G \ S) − L and
deleting L from G \ S cannot create new sinks.
In the opposite direction, let S be a partitioning set for G0 . Then, S is also a partitioning set for G, since G \ S is just
0
G \ S with the vertices in L and their arcs added. These, however, can reach only the sink s and are only connected to
vertices to which s is connected. Hence, they do not create new sinks or connect distinct components of G0 \ S.

We now show how to exhaustively apply both data reduction rules in linear time. To this end, we apply Algorithm 2: in
lines 1–4, it computes an array L such that, for each vertex v ∈ V , we have L[v] = {s} if v reaches exactly one sink s and
L[v] = 0/ otherwise. It uses this information to apply Reduction Rule 1 in lines 6–10 and Reduction Rule 2 in lines 11
and 12.
Lemma 3. Given a directed acyclic graph G with weights ω, in O(n + m) time Algorithm 2 produces a directed acyclic
graph G0 with weights ω 0 such that G0 is exhaustively reduced with respect to Reduction Rule 1 and Reduction Rule 2.
In particular, (G, ω, k) is a yes-instance if and only if (G0 , ω 0 , k) is a yes-instance.
8

Algorithm 2: Apply Reduction Rules 1 and 2 exhaustively.
Input: A directed acyclic graph G = (V, A) with arc weights ω.
Output: The result of exhaustively applying Reduction Rules 1 and 2 to G.
1 S ← sinks of G
2 L ← array with n entries
3 foreach v ∈ S do L[v] ← {v}
// L[v] = {s} for any sink s ∈ V will mean that v only reaches the sink s.
4 foreach v ∈ V \ S in reverse topological order do
\
5
L[v] ← L[u]
// Invariant: the intersection contains at most one sink.
u∈N + (v)

foreach v ∈ V with L[v] = 0/ do
foreach w ∈ N + (v) with L[w] = {s} for some s ∈ S and w < S do
if (v, s) < A then add (v, s) with ω(v, s) := 0 to A
ω(v, s) ← ω(v, s) + ω(v, w)
delete arc (v, w)

// Application of Reduction Rule 1

foreach v ∈ V \ S such that L[v] = {s} for some s ∈ S do
delete vertex v

// Application of Reduction Rule 2

12
13

return (G, ω)

6
7
8
9
10
11

P ROOF. We first discuss the semantics of Algorithm 2, then its running time. After line 5, L[v] = {s} for some vertex v
if v can reach exactly one sink s and L[v] = 0/ otherwise: this is, by definition, true for all L[v] with v ∈ S. For v ∈ V \ S
it also holds, since v can reach exactly one sink s if and only if all of its out-neighbors u ∈ N + (v) can reach s and no
other sinks, that is, if and only if L[u] = {s} for all out-neighbors u ∈ N + (v) of v.
Hence, the loop in lines 6–10 applies Reduction Rule 1 to all arcs to which Reduction Rule 1 is applicable.
Moreover, Reduction Rule 1 does not change which sinks are reachable from any vertex and, hence, cannot create new
arcs to which Reduction Rule 1 may be applied. Hence, when reaching line 11, the graph will be exhaustively reduced
with respect to Reduction Rule 1 and we do not have to update the array L.
The loop in lines 11 and 12 now applies Reduction Rule 2, which is allowed, since the graph is exhaustively reduced
with respect to Reduction Rule 1. Moreover, an application of Reduction Rule 2 cannot create new vertices to which
Reduction Rule 2 may become applicable or arcs to which Reduction Rule 1 may become applicable. Hence, line 13
indeed returns a graph that is exhaustively reduced with respect to both data reduction rules.
It remains to analyze the running time. Obviously, lines 1–3 of Algorithm 2 work in O(n) time. To execute
line 4 in O(n + m) time, we iterate over the vertices in V \ S in reverse topological order, which can be computed
in O(n + m) time [9, Section 22.4]. Hence, when computing L[v] for some vertex in line 4, we already know the
values L[u] for all u ∈ N + (v). Moreover, L[v] is the intersection of sets with at most one element and, therefore, also
contains at most one element. It follows that we can compute L[v] in O(|N + (v)|) time for each vertex v ∈ V \ S and,
therefore, in O(n + m) total time for all vertices. The rest of the algorithm only iterates once over all arcs and vertices.
Hence, to show that it works in O(n + m) time, it remains to show how to execute lines 8 and 9 in constant time.
Herein, the main difficulty is that an adjacency list cannot answer queries of the form “(v, s) ∈ A?” in constant time.
However, since we earlier required to iterate over all out-neighbors of a vertex v in O(|N + (v)|) time, we cannot just
use an adjacency matrix instead. We exploit a different trick, which, for the sake of clarity is not made explicit in the
pseudo code: assume that, when considering a vertex v ∈ V in line 6, we have an n-element array A such that A[s]
holds a pointer to the value ω(v, s) if (v, s) ∈ A and A[s] = ⊥ otherwise. Then, we could in constant time check in line 8
whether A[s] = ⊥ to find out whether (v, s) ∈ A and, if this is the case, get a pointer to (and increment) the weight ω(v, s)
in constant time in line 9. However, we cannot afford initializing an n-entry array A for each vertex v ∈ V and we cannot
make assumptions on the value of uninitialized entries. Luckily, we access A[s] only if there is a vertex w ∈ N + (v)
with L[w] = {s} for some s. Hence, we can create an n-entry array A once in the beginning of the algorithm and then,
between lines 6 and 7, set up A for v ∈ V as follows: for each w ∈ N + (v) with L[w] = {s}, set Av [s] := ⊥. Then, for
each s ∈ N + (v) with s ∈ S, let Av [s] point to ω(v, s).

9

Lemma 3 shows that we can exhaustively apply the two Reduction Rules 1 and 2 in linear time using Algorithm 2. A
natural approach for evaluating the quality of our preprocessing would be to provide a performance guarantee in terms
of small problem kernels. Unfortunately, in Section 3.3 we show that, under widely accepted complexity-theoretic
assumptions, there is no problem kernel with size polynomial in k for DAG PARTITIONING. Nevertheless, the next
section shows that our data reduction technique performs remarkably well in empirical tests. Furthermore, we show
that the running time of Algorithm 1 is significantly improved when it is applied after Algorithm 2. We achieve the
largest speedup of Algorithm 1 by interleaving the application of Algorithm 2 and the branching; a technique that
generally works well for search tree algorithms [30].
3.2. Experimental evaluation
In this section, we aim for giving a proof of concept of our O(2k · (n + m)) time search tree algorithm presented
in Section 3.1 by demonstrating to which extent instances of DAG PARTITIONING are solvable within a time frame
of five minutes. Moreover, using the optimal solutions found by our algorithm, we evaluate the quality of a heuristic
presented by Leskovec et al. [26], which can be considered a variant of our search tree algorithm (Algorithm 1): The
difference is that, while our search tree algorithm branches into all possibilities of putting a vertex into a connected
component with some sink, the heuristic just puts each vertex into the connected component with the sink it would be
most expensive to disconnect from. This is the strategy described by Leskovec et al. [26] as yielding the best results
and is in more detail described by Suen et al. [33]. The pseudocode of the heuristics (Algorithm 3) can be found in
Section 4.1, where we prove that the heuristic works optimally on trees.
Implementation details. We implemented the search tree algorithm as well as the heuristic in three variants:
1. without data reduction,
2. with initially applying the data reduction algorithm presented in Algorithm 2, and
3. with interleaving the data reduction using Algorithm 2 with the branching of Algorithm 1.
The source code uses about 1000 lines of C++ and is freely available.2 The experiments were run on a computer with a
3.6 GHz Intel Xeon processor and 64 GiB RAM under Linux 3.2.0, where the source code has been compiled using the
GNU C++ compiler version 4.7.2 and using the highest optimization level (-O3).
Data. We tried to apply our algorithm to the data set described by Leskovec et al. [26]; unfortunately, its optimum
partitioning sets have too large weight to be found by our algorithm.3 In order to prove the feasibility of solving large
instances with small minimum partitioning sets, we generated artificial instances. Herein, however, we stick to the
clustering motivation of DAG PARTITIONING and test our algorithm using simulated citation networks: vertices in a
graph represent articles and if an article v cites an article w, there is an arc (v, w). Herein, we consider only directed
acyclic graphs, which model that an article only cites older articles. A partitioning of such a network into connected
components of which each contains only one sink can be interpreted as a clustering into different topics of which we
want to identify the origins.
To simulate citation networks, we employ preferential attachment graphs—a random graph model commonly used
to model citations between articles [31, 2, 21]. Preferential attachment graphs model the natural growth of citation
networks, in which new articles are published over time and with high probability cite the already highly-cited articles.
Indeed, Jeong et al. [21] empirically verified that in this preferential attachment model, the probability of an article
being cited is linear in the number of times the article has been cited in the past.
To create a preferential attachment graph, we first choose two parameters: the number c of sinks to create and the
maximum outdegree d of each vertex. After creating c sinks, n new vertices are introduced one after another. After
introducing a vertex, we add to it d outgoing unit-weight arcs: for each of these d outgoing arcs, the target is chosen
independently at random among previously introduced vertices such that each vertex is chosen as the target with a
2 http://fpt.akt.tu-berlin.de/dagpart/
3 The

exact weights of the optimum partitioning sets remain unknown, since our algorithm could not compute them within several hours.

10

interleaved data reduction

initial data reduction

no data reduction

400

running time [s]

running time [s]

6

4

2

0
160

300
200
100
0

170
180
190
200
weight k of optimal partitioning set

160

170
180
190
200
weight k of optimal partitioning set

Figure 3: Comparisons of the running time of Leskovec et al. [26]’s heuristic (left) with the running time of our search tree algorithm (right). All
graphs have 106 vertices and roughly 18 · 106 arcs and were generated by adding k random arcs between ten connected components, each being a
preferential attachment graph on 105 vertices with outdegree twenty and a single sink. The heuristic solved all 40 instances optimally. On the right
hand side, no instance was solved in less than an hour without data reduction.

probability proportional to its indegree plus one. We do not add an outgoing arc twice, which might result in a vertex
having less than d outgoing arcs if the target nodes of two arcs to be added coincide.
We compared our algorithm to the heuristic of Leskovec et al. [26] on these graphs, but our algorithm could solve
only instances with up to 300 arcs optimally, since the optimum solution weight grows too quickly in the sizes of the
generated graphs. To show the running time behavior of our algorithm on larger graphs with small solution sizes, we
employ an additional approach: we generate multiple connected components, each being a preferential attachment
graph with one sink, and randomly add k additional arcs between these connected components in a way so that the graph
remains acyclic. Then, obviously, an optimal partitioning set cannot be larger than k. We call the set of k randomly
added arcs embedded partitioning set and it can be viewed as noise in data that clusters well.
Experimental results. Figure 3 compares the running time of the heuristic of Leskovec et al. [26] to the running time
of our Algorithm 1 with increasing optimal partitioning set size k. On the left side, it can be seen that using the data
reduction from Algorithm 2 slows down the heuristic. This is not surprising, since the heuristic itself is implemented to
run in linear time and, hence, instead of first shrinking the input instance by Algorithm 2 in linear time, one might
right away solve the instance heuristically. On the right side, one can observe that, as expected, the running time of
Algorithm 1 increases exponentially in k. We only show the running time of the implementations with data reduction:
without data reduction, we could not solve any instance in less than an hour. We can solve instances with k ≤ 190
optimally within five minutes. This allowed us to verify that the heuristic solved all 40 generated instances optimally,
regardless of the type of data reduction applied.
Figure 4 compares the running time of the heuristic of Leskovec et al. [26] to the running time of our Algorithm 1
with increasing graph size. While the heuristic shows a linear increase of running time with the graph size (on the left
side), such a behavior cannot be observed for the search tree algorithm (on the right side). The reason for this can be
seen in Figure 5: the data reduction applied by Algorithm 2 initially shrinks most input instances to about 2000 arcs
in less than ten seconds. Thus, what we observe in the right plot of Figure 4 is, to a large extent, the running time of
Algorithm 1 for constant k = 190 and roughly constant graph size. Our search tree algorithm allowed us to verify that
the heuristic by Leskovec et al. [26] solved all 80 generated instances optimally regardless of the type of data reduction
applied.
Finally, Figure 6 presents instances that could not be optimally solved by Leskovec et al. [26]’s heuristic. In the left
plot, we see that in instances with large embedded partitioning sets of several hundred thousand arcs, the heuristic of
Leskovec et al. [26] does not find the embedded partitioning set but an about 5‰ larger one. In all cases, the heuristic
11

interleaved data reduction

initial data reduction

no data reduction

400

running time [s]

running time [s]

30

20

10

300

200

100

0
20

40

60
 
input arcs 106

0

80

20

40
60
 
input arcs 106

80

Figure 4: Comparisons of the running time of Leskovec et al. [26]’s heuristic (left) with the running time of our search tree algorithm (right). Without
interleaved data reduction, the search tree solved no instance in less than 5 minutes. The graphs were generated by adding k = 190 random arcs
between ten connected components, each being a preferential attachment graph with outdegree twenty and a single sink. The heuristic solved all
80 instances optimally.

8
running time [s]

output arcs

6,000

4,000

2,000

6
4
2

20

40

60
 6
input arcs 10

0

80

20

40

60
 6
input arcs 10

80

Figure 5: Effect (left) and running time (right) of initially running Algorithm 2 for data reduction. The graphs were generated by adding k = 190
random arcs between ten connected components, each being a preferential attachment graph with outdegree twenty and a single sink.

12

1.006

2.5
deviation factor

deviation factor

3

1.004

2
1.5
1

100

300
 
weight of embedded partitioning set 103
150

200

250

10

20
15
25
weight k of optimum partitioning set

Figure 6: Comparison of partitioning sets found by Leskovec et al. [26]’s heuristic with an embedded partitioning set of size k (left) and an optimal
partitioning set (right). All graphs on the left side have 106 vertices and roughly 18 · 106 arcs and were generated by adding k random arcs between
ten connected components, each being a preferential attachment graph on 105 vertices with outdegree fifteen and a single sink. All graphs on the
right side are preferential attachment graphs with varying number of vertices, two sinks and outdegree three.

found the same partitioning sets regardless of the type of data reduction applied. Note that the plot only gives a lower
bound on the deviation factor, since there might be even better partitioning sets in the instances than the embedded
one; we were unable to compute the optimal partitioning sets in these instances. In the right plot of Figure 6, we used
smaller preferential attachment graphs (this time without embedded partitioning sets) and see that Leskovec et al. [26]’s
heuristic can be off by more than a factor of two from the optimal partitioning set. Data reduction had no effect on the
quality of the partitioning sets found.
Summary. We have seen that solving large instances with partitioning sets of small weight is realistic using our
algorithm. In particular, instances with more than 107 arcs and k ≤ 190 could be solved in less than five minutes. A
crucial ingredient in this success is the data reduction executed by Algorithm 2; without its help, we could not solve
any of our instances in less than five minutes.
However, we also observed that our algorithm works best on those instances that can already be solved mostly optimally by Leskovec et al. [26]’s heuristic and that the data reduction executed by Algorithm 2 slows down the heuristic.
Having seen that the heuristic by Leskovec et al. [26] can be off by more than a factor of two from the optimum on
random preferential attachment graphs diminishes the hope that, in spite of the non-approximability results of DAG
PARTITIONING by Alamdari and Mehrabian [1], the heuristic of Leskovec et al. [26] might find good approximations
on naturally occurring instances. As we see, we do not have to construct adversarial instances to make the heuristic
find solutions far from optimal.
3.3. Limits of data reduction and fixed-parameter algorithms
In Section 3.1, we have seen linear-time data reduction rules for DAG PARTITIONING. Moreover, the experiments
in Section 3.2 have shown that, on all input instancse we tested our algorithm on, the running time of our O(2k · (n +
m)) time Algorithm 1 merely depended on k because Algorithm 2 shrunk our random input instances to roughly the
same size.
Therefore it is natural to ask whether we can provide data reduction rules that provably shrink the size of each
possible input instance to some fixed polynomial in k, that is, whether there is a polynomial-size problem kernel for
DAG PARTITIONING. Unfortunately, in this section, we give a negative answer to this question. Specifically, we
prove that DAG PARTITIONING does not admit problem kernels with size polynomial in k, unless NP ⊆ coNP/poly.
Moreover, we show that the running time O(2k · (n + m)) of Algorithm 1 cannot be improved to 2o(k) poly(n), unless
the Exponential Time Hypothesis fails. Herein, the Exponential Time Hypothesis as well as NP * coNP/poly are
hypotheses stronger than P , NP, but widely accepted among complexity theorists [20, 16].
13

f

t
xt1

x1f

xt2

x2f

x1

x̄1 C1

x2

x̄2
f0

t0

Figure 7: DAG PARTITIONING instance constructed from the formula consisting only of the clause C1 := (x1 ∨ x̄2 ). Heavy arcs are drawn bold;
dotted arcs are a partitioning set that corresponds to the satisfying assignment setting x1 to true and x2 to false. The variable gadgets are drawn on a
gray background.

Towards proving these results, we first recall the polynomial-time many-to-one reduction from 3-S AT to DAG
PARTITIONING given by Alamdari and Mehrabian [1]. The 3-S AT problem is, given a formula ϕ in conjunctive normal
form with at most three literals per clause, to decide whether ϕ admits a satisfying assignment.
Construction 1 (Alamdari and Mehrabian [1]). Let ϕ be an instance of 3-S AT with the variables x1 , . . . , xn and the
clauses C1 , . . . ,Cm . We construct a DAG PARTITIONING instance (G, ω, k) with k := 4n + 2m that is a yes-instance if
and only if ϕ is satisfiable. The weight function ω will assign only two different weights to the arcs: a normal arc has
weight one and a heavy arc has weight k + 1 and thus cannot be contained in any partitioning set of weight k. The
remainder of this construction is illustrated in Figure 7.
We start constructing the directed acyclic graph G by adding the special vertices f , f 0 ,t, and t 0 together with the
heavy arcs ( f , f 0 ) and (t,t 0 ). The vertices f 0 and t 0 will be the only sinks in G. For each variable xi , introduce the
vertices xti , xif , xi and x̄i together with the heavy arcs (t, xti ) and ( f , xif ) and the normal arcs (xti , xi ), (xti , x̄i ), (xif , xi ),
(xif , x̄i ), (xi , f 0 ), (x̄i , f 0 ), (xi ,t 0 ), and (x̄i ,t 0 ). For each clause C j , add a vertex C j together with the heavy arc (t,C j ).
Finally, if some clause C j contains the literal xi , then add the arc (C j , xi ); if some clause C j contains the literal x̄i , then
add the arc (C j , x̄i ).
Alamdari and Mehrabian [1] showed that, given a formula ϕ in 3-C NF with n variables and m clauses, Construction 1
outputs a graph G with arc weights ω such that ϕ is satisfiable if and only if there is a partitioning set S for G that does
not contain heavy arcs.
Since G has only the two sinks t 0 and f 0 , by Observation 1, a minimal such partitioning set has to partition G into two
connected components, one connected component containing the heavy arc (t,t 0 ) and the other containing ( f , f 0 ). Moreover, if ϕ is satisfiable, then such a partitioning set has weight at most 4n + 2m, since for each xi of the n variables of ϕ,
it deletes at most one of two arcs outgoing from each of the vertices xti , xif , xi , and x̄i , and for each C j of the m clauses,
it deletes at most two out of the three arcs outgoing from the clause vertex C j . We thus obtain the following lemma:
Lemma 4. Given a formula ϕ in 3-C NF with n variables and m clauses, Construction 1 outputs a graph G with arc
weights ω such that ϕ is satisfiable if and only if there is a partitioning set S for G that does not contain heavy arcs.
Moreover, if ϕ is satisfiable, then S has weight at most 4n + 2m and partitions G into one connected component
containing the constructed vertices t and t 0 and the other containing f and f 0 .
We will later exploit Lemma 4 to show our hardness results. Next, we show that arcs with non-unit weights in our
constructions can be simulated by arcs with unit weights. This allows us to show stronger hardness results and to keep
our constructions simple.
3.3.1. Strengthening of hardness results to unit-weight graphs
Construction 1 heavily relied on forbidding the deletion of certain arcs by giving them a high weight. The next
lemma shows that we can replace these arcs by a gadget only using unit-weight arcs without changing the weight of the
partitioning set sought.
14

v

5

w

v

w

Figure 8: Replacing an arc of weight 5 on the left by the gadget of unit-weight arcs on the right.

Lemma 5. There is a polynomial-time many-one reduction from DAG PARTITIONING with polynomially bounded
weights to unweighted DAG PARTITIONING that does not change the weight k of the partitioning set sought.
P ROOF. Let (G, ω, k) be an instance of DAG PARTITIONING. We show how to obtain an instance (G0 , ω 0 , k) by
replacing a single arc of weight more than one by arcs of weight one such that (G, ω, k) is a yes-instance if and only
if (G0 , ω 0 , k) is a yes-instance. The replacement will be done as illustrated in Figure 8. The claim then follows by
repeating this procedure for every arc of weight more than one.
Consider an arc a = (v, w) in G with ω(a) > 1. We obtain G0 and ω 0 from G and ω by setting the weight ω 0 (a) = 1,
adding a set X of ω(a) − 1 vertices to G0 , and inserting for each u ∈ X a weight-one arc (v, u) and a weight-one
arc (u, w).
First, assume that (G, ω, k) is a yes-instance and that S is a minimal partitioning set for G. We show how to obtain
a partitioning set of weight k for G0 . Clearly, if a < S, then S is a partitioning set of equal weight for (G0 , ω 0 , k). If a ∈ S,
then we get a partitioning set of equal weight for (G0 , ω 0 , k) by adding the arcs between v and X to S.
Second, assume that (G0 , ω 0 , k) is a yes-instance and that S is a minimal partitioning set for G0 . We show how to
obtain a partitioning set of weight k for G. To this end, we consider two cases: v and w are in a common or in separate
connected components of G0 \ S.
Case 1) If v and w are in one connected component of G0 \ S, then, by minimality, S does not contain a or any arc
incident to vertices in X. Hence, S is a partitioning set of equal weight for G.
Case 2) If v and w are in separate connected components of G0 \ S, then a ∈ S. Moreover, the vertices in X have
only one outgoing arc. Hence, by Observation 1, S does not contain arcs from X to w but, therefore, contains all arcs
from v to X. Removing these arcs from S results in a partitioning set of equal weight for (G, ω, k).

3.3.2. Limits of fixed-parameter algorithms
We now show that DAG PARTITIONING cannot be solved in 2o(k) poly(n) time unless the Exponential Time
Hypothesis fails. Thus, if our search tree algorithm for DAG PARTITIONING can be improved, then only by replacing
the base of the exponential 2k -term by some smaller constant.
The Exponential Time Hypothesis was introduced by Impagliazzo and Paturi [19] and states that n-variable 3-S AT
cannot be solved in 2o(n) poly(n) time. Using the reduction from 3-S AT to DAG PARTITIONING given by Alamdari
and Mehrabian [1] (Construction 1), we can easily show the following:
Theorem 2. Unless the Exponential Time Hypothesis fails, DAG PARTITIONING cannot be solved in 2o(k) poly(n)
time even if all arcs have unit weight.
P ROOF. Construction 1 reduces an instance of 3-S AT consisting of a formula with n variables and m clauses to an
equivalent instance (G, ω, k) of DAG PARTITIONING with k = 4n + 2m. Thus, a 2o(k) poly(n)-time algorithm for DAG
PARTITIONING would yield a 2o(m) poly(m)-time algorithm for 3-S AT. This, in turn, by the so-called Sparsification
Lemma of Impagliazzo et al. [20, Corollary 2], would imply a 2o(n) poly(n) time algorithm for 3-S AT, which contradicts
the Exponential Time Hypothesis. Since the weights used in Construction 1 are polynomial in the number of created
vertices and edges, we can apply Lemma 5 to transfer the result to the unit-weight case.


15

3.3.3. Limits of problem kernelization
We now show that DAG PARTITIONING has no polynomial-size problem kernel with respect to the parameter k—
the weight of the partitioning set sought. It follows that, despite the effectiveness of data reduction observed in
experiments in Section 3.2, we presumably cannot generally shrink a DAG PARTITIONING instance in polynomial
time to a size polynomial in k.
To show that DAG PARTITIONING does not allow for polynomial-size kernels, we first provide the necessary
concepts and techniques introduced by Bodlaender et al. [8].
Definition 1 (Bodlaender et al. [8, Definition 3.3]). For some finite alphabet Σ, a problem L ⊆ Σ∗ (OR-)cross-composes
into a parameterized problem Q ⊆ Σ∗ × N if there is an algorithm (a (OR-)cross-composition) that transforms instances x1 , . . . , xs of L into an instance (x∗ , k) for Q in time polynomial in ∑si=1 |xi | such that
i) k is bounded by a polynomial in maxsi=1 |xi | + log s and
ii) (x∗ , k) ∈ Q if and only if there is an i ∈ {1, . . . , s} such that xi ∈ L.
Furthermore, the cross-composition may exploit that the input instances x1 , . . . , xs belong to the same equivalence class
of a polynomial equivalence relation R ⊆ Σ∗ × Σ∗ , which is an equivalence relation such that
i) it can be decided in polynomial time whether two instances are equivalent and
ii) any finite set S ⊆ Σ∗ is partitioned into poly(maxx∈S |x|) equivalence classes.
The assumption that all instances belong to the same equivalence class of a polynomial equivalence relation can make
the construction of a cross-composition remarkably easier: when giving a cross-composition from 3-S AT, we can, for
example, assume that the input instances all have the same number of clauses and variables.
Cross-compositions can be used to prove that a parameterized problem has no polynomial-size kernel unless
NP ⊆ coNP/poly.
Theorem 3 (Bodlaender et al. [8, Corollary 3.6]). If some problem L ⊆ Σ∗ is NP-hard under polynomial-time manyone reductions and L cross-composes into the parameterized problem Q ⊆ Σ∗ × N, then there is no polynomial-size
problem kernel for Q unless NP ⊆ coNP/poly.
In the following, we show that 3-S AT cross-composes into DAG PARTITIONING parameterized by k, which yields the
following theorem:
Theorem 4. Unless NP ⊆ coNP/poly, DAG PARTITIONING does not have a polynomial-size problem kernel with
respect to the weight k of the partitioning set sought even if all arcs have unit weight.
Although the proof of Theorem 4 is based on the following construction, which requires arc weights, by using Lemma 5
from Section 3.3.1, we obtain that Theorem 4 holds even on graphs with unit weights.
Construction 2. Let ϕ1 , . . . , ϕs be instances of 3-S AT. Since we may assume ϕ1 , . . . , ϕs to be from the same equivalence class of a polynomial equivalence relation, we may assume that each of the formulas ϕ1 , . . . , ϕs has the same
number n of variables and the same number m of clauses. Moreover, we may assume that s is a power of two;
otherwise we simply add unsatisfiable formulas to the list of instances. We now construct a DAG PARTITIONING
instance (G, ω, k) with k := 4n + 2m + 3 log s that is a yes-instance if and only if ϕi is satisfiable for at least one 1 ≤ i ≤ s,
where we use “log” to denote the binary logarithm. As in Construction 1, the weight function ω will only assign two
possible weight values: a heavy arc has weight k + 1 and thus cannot be contained in any partitioning set. A normal arc
has weight one. The remainder of the construction is illustrated in Figure 9.
For each instance ϕi , let Gi be the graph produced by Construction 1. By Lemma 4, Gi can be partitioned with
4n + 2m arc deletions if and only if ϕi is a yes-instance. We now build a gadget that, by means of additional 3 log s arc
deletions, chooses exactly one graph Gi that has to be partitioned.
To distinguish between multiple instances, we denote the special vertices f , f 0 ,t, and t 0 in Gi by fi , fi0 ,ti , and ti0 .
For all 1 ≤ i ≤ s, we add Gi to the output graph G and merge the vertices f1 , f2 , . . . , fs into a vertex f and the vertices f10 , f20 , . . . , fs0 into a vertex f 0 . Furthermore, we add the vertices t,t 0 , and t 00 and the heavy arcs (t,t 0 ) and (t,t 00 ) to G.
16

t 00

t

t1

t2

t10

t20

f

O

t3

t4

t30

t40

f0
t0

I

Figure 9: Cross composition of four formulas φ1 , . . . , φ4 into a DAG PARTITIONING instance. Of each subgraph Gi corresponding to formula φi , only
the vertices ti , ti0 , and their connecting heavy arc are shown. The introduced binary trees O and I are highlighted in gray. Deleting the 3 log 4 = 6 dotted
arcs requires the graph G1 to be partitioned, since its vertices t1 and t10 are in a different connected component than its vertices f1 = f and f10 = f 0 .
The graphs Gi for i > 1 do not have to be partitioned; they are completely contained in one connected component with f and f 0 .

We add a balanced binary tree O rooted in t 00 and its leaves being the vertices t1 , . . . ,ts that is formed by normal
arcs directed from the root to the leaves. That is, O is an out-tree. Moreover, add a balanced binary tree I rooted in t 0
and its leaves being the vertices t10 , . . . ,ts0 that is formed by normal arcs directed from the leaves to the root. That is,
I is an in-tree. For each vertex v , t 0 in I, add a normal arc (v, f 0 ).
Using this construction, we can now prove Theorem 4.
P ROOF ( OF T HEOREM 4). We only have to show that the instance (G, ω, k) constructed by Construction 2 is a yesinstance if and only if at least one of the input formulas ϕi is satisfiable. Then, the theorem for the weighted case
follows from Theorem 3. Since the weights used in Construction 2 are polynomial in the number of created vertices
and edges, we can apply Lemma 5 to transfer the result to the unit-weight case.
First, assume that a formula ϕi is satisfiable for some 1 ≤ i ≤ s. By Lemma 4 it follows that Gi can be partitioned
by k0 := 4n + 2m arc deletions into two connected components Pt and Pf such that Pt contains ti and ti0 and such
that Pf contains fi = f and fi0 = f 0 . We apply these arc deletions to G and delete 3 log s additional arcs from G
as follows. Let L be the unique directed path in O from t 00 to ti . Analogously, let L0 be the unique directed path
in I from ti0 to t 0 . Observe that each of these directed paths has log s arcs. We partition G into the connected
component Pt0 = Pt ∪ {t,t 0 ,t 00 } ∪ V (L) ∪ V (L0 ) with sink t 0 and into the connected component Pf0 = V (G) \ Pt0 with
sink f 0 . To this end, for each vertex v ∈ V (L) \ {ti }, we remove the outgoing arc that does not belong to L. Hence,
exactly log s arcs incident to vertices of O are removed. Similarly, for each vertex v ∈ V (L0 ) \ {ti0 }, we remove the
incoming arc not belonging to L0 . For each vertex v , t 0 of L0 , we remove the arc to f 0 . Hence, exactly 2 log s arcs
incident to vertices of I are removed. Thus, in total, at most k = 4n + 2m + 3 log s normal arcs are removed to partition G
into Pt0 and Pf0 .
Conversely, let S be a minimal partitioning set for G with ω(S) ≤ k. Then, by Observation 1, G \ S has two
connected components, namely Pt0 with sink t 0 and Pf0 with sink f 0 . Since S cannot contain heavy arcs, t and t 00 are in Pt0 .
Hence, t 00 can reach t 0 in G \ S, since they are in the same component of G \ S. As every directed path from t 00 to t 0
goes through some vertices ti and ti0 , it follows that there is an i ∈ {1, . . . s} such that ti and ti0 are in Pt0 . Since f = fi
and f 0 = fi0 are in Pf0 , the partitioning set S ∩ A(Gi ) partitions Gi into two connected components: one containing ti
and ti0 and the other containing f = fi and f 0 = fi0 . Since S does not contain heavy arcs, from Lemma 4 it follows that
ϕi is satisfiable.


17

Algorithm 3: Leskovec et al. [26]’s heuristic to compute small partitioning sets.
Input: A directed acyclic graph G = (V, A) with arc weights ω.
Output: A partitioning set S.
1 (v1 , v2 , . . . , vn ) ← reverse topological order of the vertices of G
2 L ← array with n entries
3 S←0
/
4 for i = 1 to n do
5
if vi is a sink then L[vi ] ← vi
// associate vi with itself
6
else
7
D ← {L[w] | w ∈ N + (vi )}
// the set of feasible sinks for vi
8
for s ∈ D do
9
As ← {(vi , w) ∈ A | w ∈ N + (vi ) ∧ L[w] = s}
// set of arcs to keep if vi is associated with sink s
10
11
12
13

s∗ ← arg maxs∈D ω(As )
L[vi ] ← s∗
S ← S ∪ {(vi , w) | w ∈ N + (vi ) ∧ L[w] , s∗ }

// cheapest sink s∗ to associate vi with

return S

4. Parameter treewidth
In Section 3, we have seen that DAG PARTITIONING is linear-time solvable when the weight k of the requested
partitioning set is constant. Alamdari and Mehrabian [1] asked whether DAG PARTITIONING is fixed-parameter
tractable with respect to the parameter treewidth, which is a measure of the “tree-likeness” of a graph. We will answer
this question affirmatively.
In Section 4.1, we first show that, if the input graph is indeed a tree, then the heuristic by Leskovec et al. [26] solves
the instance optimally in linear time. Afterwards, in Section 4.2, we prove that this result can be generalized to graphs
of bounded treewidth and thus improve the algorithm for pathwidth given by Alamdari and Mehrabian [1], since the
treewidth of a graph is at most its pathwidth.
4.1. Partitioning trees
In this section, we show that the heuristic by Leskovec et al. [26] solves DAG PARTITIONING in linear time on
trees. This result will be generalized in the next section, where we show how to solve DAG PARTITIONING in linear
time on graphs of bounded treewidth. The heuristic by Leskovec et al. [26] is similar to our search tree algorithm
presented in Algorithm 1: instead of trying all possibilities of associating a vertex with one of its feasible sinks, it
associates each vertex with the sink that it would be most expensive to disconnect from. The algorithm is presented in
Algorithm 3.
Theorem 5. Algorithm 3 solves DAG PARTITIONING optimally in linear time if the underlying undirected graph is a
tree.
P ROOF. Algorithm 3 clearly works in linear time: to implement it, we only have to iterate over the out-neighbors of
each vertex vi once. In particular, all sets As in line 9 can be computed by one iteration over each w ∈ N + (vi ) and
adding the arc (vi , w) to AL[w] . Moreover, Algorithm 3 returns a partitioning set: each vertex v is associated with exactly
one sink L[v] of G and the returned set S deletes exactly the arcs (v, w) for which L[v] , L[w].
We show by induction on i that Algorithm 3 computes a minimum-weight partitioning set for G[{v1 , . . . , vi }]. For
the induction base case, observe that v1 is a sink and, thus, v1 only reaches the sink L[v1 ] = v1 in G \ S for all possible
minimum-weight partitioning sets S for G. Now, assume that there is a minimum-weight partitioning set S such that
each v ∈ {v1 , . . . , vi−1 } only reaches the sink L[v] in G \ S. We show that there is a minimum-weight partitioning set S0
such that each v ∈ {v1 , . . . , vi } reaches only the sink L[v] in G \ S0 . If vi only reaches L[vi ] in G \ S, then we are done.
Otherwise, vi reaches some sink s0 , L[vi ] in G \ S and, hence, is not itself a sink. The graph G is partly illustrated in
Figure 10.
18

v

vi

w

Rs0

RL[vi ]

s0

u

L[vi ]

Figure 10: Illustration of the proof of Theorem 5. Straight lines represent arcs. Wavy lines represent directed paths. Dashed arcs and paths represent
arcs and paths that cannot exist since the underlying undirected graph is a tree.

Let Rs be the set of vertices reachable from vi that reach some sink s in G. Since the underlying undirected graph
of G is a tree, vi has exactly one arc into Rs for each sink s reachable from vi . Let (vi , u) be the arc of vi into RL[vi ] and
(vi , w) be the arc of vi into Rs0 . Observe that the arc (vi , u) exists since the algorithm can set L[vi ] only to sinks reachable
from vi . To show that S0 := (S \ {(vi , w)}) ∪ {(vi , u)} is still a partitioning set, we only have to verify that vi and all
vertices reaching vi only reach one sink in G \ S0 . For all other vertices, this follows from S being a partitioning set.
1. The vertex vi only reaches the sink L[vi ] in G \ S0 : this is because u = v j for some j < i which, by induction
hypothesis, reaches exactly one sink in G \ S and, hence, in G \ S0 .
2. A vertex v that reaches vi in G \ S0 reaches only the sink L[vi ] in G \ S0 : otherwise v reaches s0 in G \ S0 since vi
and, therefore v, reaches s0 in G \ S. This, however, means that v has a path to s0 that bypasses vi in G \ S0 and
hence, in G \ S, which contradicts the undirected underlying graph of G \ S being a tree.
It remains to show ω(S0 ) ≤ ω(S), implying that S0 is also a minimum-weight partitioning set. To see this, we analyze
the sets As0 and AL[vi ] computed in line 9 of Algorithm 3. Observe that As0 = {(vi , w)} and that AL[vi ] = {(vi , u)}.
Since ω(As0 ) ≤ ω(AL[vi ] ) because of the choice of L[vi ] in line 10, we conclude that ω(vi , u) ≤ ω(vi , w) and hence,
ω(S0 ) ≤ ω(S).

4.2. Partitioning DAGs of bounded treewidth
We now give an algorithm that solves DAG PARTITIONING in linear time on graphs of bounded treewidth. In
contrast to Section 3, which presented our search tree algorithm and an experimental evaluation thereof, the algorithm
presented below is of rather theoretical interest: Alamdari and Mehrabian [1] asked whether DAG PARTITIONING is
fixed-parameter tractable with respect to the parameter treewidth. With a dynamic programming algorithm, we can prove
the following theorem, which answers their open question and is an improvement of Alamdari and Mehrabian [1]’s
algorithm, since the treewidth of a graph is at most its pathwidth.
Theorem 6. Given a width-t tree decomposition of the underlying undirected graph, DAG PARTITIONING can be
2
solved in 2O(t ) · n time.
We first formally define the tree decomposition of a graph and its width.
Definition 2 (Treewidth, tree decomposition). Let G = (V, A) be a directed graph. A tree decomposition (T, β ) for G
consists of a rooted tree T = (X, E) and a mapping β : X → 2V of each node x of the tree T to a subset Vx := β (x) ⊆ V ,
called bag, such that
i) for each vertex v ∈ V , there is a node x of T with v ∈ Vx ,
ii) for each arc (u, w) ∈ A, there is a node x of T with {u, w} ⊆ Vx ,
19

s4
Vx

s3

Ux
s1

s2

Figure 11: The set S consisting of the dotted arc is not a partitioning set for the shown graph G, but a partial partitioning set for G[Ux ]. Note that
S would not be a partial partitioning set if it would additionally contain the bold arc, since then the sink s1 would be in a connected component with a
vertex of Vx but not reachable from Vx . Also note that S does not separate s2 from s3 , which are sinks in G[Ux ] but not in G.

iii) for each vertex v ∈ V , the nodes x of T for which v ∈ Vx induce a subtree in T .
A tree decomposition is nice if Vr = 0/ for the root r of T and each node x of T is either
• a leaf : then, Vx = 0,
/
• a forget node: then, x has exactly one child node y and Vx = Vy \ {v} for some v ∈ Vy ,
• an introduce node: then, x has exactly one child node y and Vx = Vy ∪ {v} for some v ∈ V \Vy , or
• a join node: then, x has exactly two child nodes y and z such that Vx = Vy = Vz .
The width of a tree decomposition is one less than the size of its largest bag. The treewidth of a graph G is the minimum
width of a tree decomposition for G. For a node x of T , we denote by Ux the union of Vy for all descendants y of the
node x.
For any constant t, it can be decided in linear time whether a graph has treewidth t and the corresponding tree decomposition of width t can be constructed in linear time [6]. Also in O(tn) time, the tree decomposition of width t can
be transformed into a nice tree decomposition with the same width and O(tn) nodes [24]. Hence, we assume without
loss of generality that we are given a nice tree decomposition.
Our algorithm is based on leaf-to-root dynamic programming. That is, intuitively, we start from the leaf nodes of the
tree decomposition and compute possible partial partitioning sets for each bag from the possible partial partitioning sets
for its child bags. Since our algorithm for DAG PARTITIONING on graphs of bounded treewidth is relatively intricate,
we refer the reader that is yet inexperienced with dynamic programming on tree decompositions to introductory chapters
in corresponding text books [28, 12, 10, 24].
We will now precisely define a partial partitioning set and show that any partial partitioning set for the root bag is a
partitioning set for the entire graph. The definition is illustrated in Figure 11.
Definition 3 (Partial partitioning set). A partial partitioning set S for G[Ux ] is an arc set S ⊆ A(G[Ux ]) such that
(i) no connected component of G[Ux ] \ S contains two different sinks of Ux \Vx , and
(ii) every sink in a connected component of G[Ux ] \ S that contains a vertex of Vx can be reached from some vertex
of Vx in G[Ux ] \ S.
Since we assumed to work on a tree decomposition with a root r such that the bag Vr is empty, any partial partitioning
set for G[Ur ] = G will be a partitioning set for the entire graph G. Moreover, Definition 3(i) does not require partial
partitioning sets for G[Ux ] to separate sinks in the bag Vx . This is because vertices in Vx that are sinks in G[Ux ] might be
non-sinks for a supergraph, as illustrated in Figure 11. Thus, it might be unnecessary to separate the vertices in Vx .
However, due to Definition 2(ii and iii) of a tree decomposition, sinks in Ux \Vx are sinks in all supergraphs G[Uq ]
20

Vx
s3
P1

P2

s1

s2

Figure 12: A pattern (R, G, P), where shown are the graph G and a partition P of its vertices into two sets P1 and P2 . If the graph R is the subgraph
of G induced by the vertices Vx , then, in terms of Definition 5, R = Rx (S) and G = Gx (S) for the partial partitioning set S for G[Ux ] shown in Figure 11.
In this case, the partial partitioning set S satisfies the shown pattern. Moreover, a vertex is a sink in this figure if and only if it is a sink in G[Ux ] \ S
shown in Figure 11.

for q being an ancestor node of x. Definition 3(ii), by Observation 2, allows us to ensure that components containing
both a sink in Ux \Vx and a vertex of Vx end up with only one sink in some supergraph G[Uq ]. The precise purpose of
Definition 3(ii) will be explained in more detail after the upcoming Definition 5.
To keep the notation free from clutter, note that Definition 3 implicitly relies on the bag Vx belonging to each set Ux .
Thus, when a tree decomposition has a node x and a child node y such that Vx ( Vy but Ux = Uy , a partial partitioning
set S for G[Uy ] is not necessarily a partial partitioning set for G[Ux ], although G[Uy ] \ S = G[Ux ] \ S.
Now, assume that we want to compute partial partitioning sets for G[Ux ] from partial partitioning sets for child nodes
of x. These partial partitioning sets might, for example, disagree on which arcs to delete in the child bags or which
connected components of the child bags are meant to end up in a common connected component of the entire graph:
for a child node y of x, multiple connected components of G[Uy ] \ S might be one connected component of G[Ux ] \ S.
To prevent such incompatibilities, we only consider those partial partitioning sets for G[Ux ] that agree with partial
partitioning sets for the child nodes of x on certain patterns.
On a high level, our algorithm will store for each node of the tree decomposition a table with one row for each
possible pattern. The value of a row will be the minimum weight of a partial partitioning set satisfying this pattern. To
compute this value, our algorithm will use the rows with corresponding patterns in the tables of the child nodes. In the
following, we first formalize the terms patterns and satisfying partial partitioning sets. Then, we present our algorithm
and we specify the corresponding patterns. We start by formally defining patterns, see Figure 12 for an illustration.
Definition 4 (Pattern). Let x be a node of a tree decomposition T . A pattern for x is a triple (R, G, P) such that
i) R is a directed acyclic graph with the vertices Vx .
ii) G is a directed acyclic graph with the vertices Vx and at most |Vx | additional vertices such that each vertex
in V (G) \Vx is a non-isolated sink, and
iii) P is a partition of the vertices of G such that each connected component of G is within one set Pi ∈ P and such that
each Pi contains at most one vertex of V (G) \Vx .
We will use a pattern (R, G, P) for x to capture important properties of partial partitioning sets for G[Ux ]. Intuitively,
the graph R will describe which arcs between the vertices in the bag Vx a partial partitioning set S for G[Ux ] will not
delete. The graph G will describe which vertices of Vx can reach each other in G[Ux ] \ S and which sinks outside of Vx
they can reach. The partition P describes which vertices are meant to end up in the same connected component of G \ S
for a partitioning set S of the entire graph. For this reason, the sets of the partition P are allowed to contain only one
vertex of V (G) \Vx as these vertices are sinks.
We will now explain precisely what it means for a partial partitioning set to satisfy a pattern. The following
definition is illustrated in Figure 12.

21

Definition 5 (Pattern satisfaction). Let S be a partial partitioning set for G[Ux ]. A sink s in Ux \Vx is bag-reachable
in G[Ux ] \ S if some vertex in Vx can reach s in G[Ux ] \ S. We define a canonical pattern (Rx (S), Gx (S), Px (S)) at x for S,
where
• Rx (S) is G[Vx ] \ S,
• Gx (S) is the directed acyclic graph on the vertices Vx ∪V 0 , where V 0 is the set of bag-reachable sinks in G[Ux ] \ S,
and there is an arc (u, v) in Gx (S) if and only if the vertex u can reach the vertex v in G[Ux ] \ S, and
• Px (S) is the the partition of the vertices of Gx (S) such that the vertices u and v are in the same set of Px (S) if and
only if they are in the same connected component of G[Ux ] \ S.
Let (R, G, P) be a pattern for x. We say that S satisfies the pattern (R, G, P) at x if
i) R = Rx (S),
ii) G = Gx (S), and
iii) for each set P ∈ Px (S) there exists a set P0 ∈ P such that P ⊆ P0 , that is, P is a coarsening of Px (S).
It is easy to verify that a partial partitioning set S for G[Ux ] \ S satisfies its canonical pattern (Rx (S), Gx (S), Px (S)) at
node x: to this end, observe that (Rx (S), Gx (S), Px (S)) is indeed a pattern for x: for the vertex set Vx ∪V 0 of Gx (S), we
have |V 0 | ≤ |Vx | since each vertex in Vx can reach at most one distinct sink in V 0 ⊆ Ux \Vx in G[Ux ] \ S.
Note that, since Gx (S) contains an arc (u, v) if and only if u can reach v instead of requiring them to be merely
connected, a vertex is a sink in Gx (S) if and only if it is a sink in G[Ux ] \ S. Herein, Definition 3(ii) ensures that any
sink s connected to a vertex in Vx is a vertex in Gx (S).
While it might seem more natural to replace the condition (iii) in Definition 5 by simply P = Px (S), we prefer the
current definition, because it allows for several connected components of G[Ux ] \ S becoming a part of one connected
component of the entire graph. This greatly simplifies some parts of the algorithm.
The Algorithm. We now describe a dynamic programming algorithm. Starting from the leaves of the tree decomposition T and working our way to its root, with each node x of T , we associate a table Tabx that is indexed by all possible
patterns for x. Semantically, we want that
Tabx (R, G, P) = minimum weight of a partial partitioning set for G[Ux ] that satisfies the pattern (R, G, P) at x.
Since we have Vr = 0,
/ there is exactly one pattern (R, G, P) for the root r: R = G is the empty graph and P = 0.
/ Thus,
Tabr has exactly one entry and it contains the minimum weight of a partial partitioning set S for G[Ur ], which is
equivalent to S being a partitioning set for G. It follows that once the tables are correctly filled, to decide the DAG
PARTITIONING instance (G, ω, k), it is enough to test whether the only entry of Tabr is at most k.
We now present an algorithm to fill the tables and prove its correctness. First, we initialize all table entries of all
tables by ∞. By updating the entry Tabx (R, G, P) with m we mean setting Tabx (R, G, P) := m if m < Tabx (R, G, P). For
each leaf node x, it is obviously correct to set Tabx (R, G, P) = 0 for the only pattern (R, G, P) at x, which has the empty
graph as R and G and the empty set as P. In the following, for each type of a node x of a tree decomposition, that is,
for forget nodes, introduce nodes, and join nodes, we independently show how to compute the table Tabx given that
we correctly computed the tables for all children of x. To show that the table Tabx is filled correctly, we prove the
following lemma for each node type.
Lemma 6.
(i) There is a partial partitioning set for G[Ux ] satisfying a pattern (R, G, P) at x with weight at most Tabx (R, G, P).
(ii) The minimum weight of a partial partitioning set for G[Ux ] satisfying a pattern (R, G, P) at x is at least Tabx (R, G, P).
We present the algorithm and the proof for Lemma 6 independently for each node type in Sections 4.2.1, 4.2.2, and
4.2.3, respectively, where we assume that all tables Taby for child nodes y of x have been computed correctly.
22

4.2.1. Forget nodes
We use the following procedure to compute the table Tabx of a forget node x under the assumption that the table Taby
for the child node y of x has been computed correctly.
Procedure 1 (Forget node). Let x be a forget node with a single child y. Assume that v is the vertex being “forgotten”,
that is, v is in the child bag Vy but not in the current bag Vx . From the weights of optimal partial partitioning sets
for G[Uy ], we want to compute the weight of optimal partial partitioning sets for G[Ux ].
To this end, for each pattern (R, G, P) for y, we distinguish four cases. In each case, we will construct a pattern (R0 , G0 , P0 ) for x such that a partial partitioning set for G[Uy ] that satisfies (R, G, P) is a partial partitioning set
for G[Ux ] and satisfies (R0 , G0 , P0 ). Then, we update Tabx (R0 , G0 , P0 ) with the value of Taby (R, G, P). Herein, the
following case distinction is not exhaustive. We do not take action for patterns (R, G, P) that do not satisfy any of the
following conditions (for the reasons informally explained in the cases). In all cases, we set R0 := R − {v}.
Case 1) If v is isolated in G and there is a set {v} in P, then we let G0 := G − {v} and P0 := P \ {{v}} and update
Tabx (R0 , G0 , P0 ) with the value of Taby (R, G, P): an isolated vertex that is alone in its part of P can simply be forgotten.
Case 2) If v is a non-isolated sink in G and v ∈ Pi ∈ P such that Pi ⊆ Vy , then we let G0 := G and P0 := P. We update
Tabx (R0 , G0 , P0 ) with the value of Taby (R, G, P): in this case, the sink v “moves” from Vy to V (G0 ) \Vx . To ensure that
(R0 , G0 , P0 ) is a pattern, the part Pi containing v cannot contain any additional sink in V (G) \Vy , thus we require Pi ⊆ Vy .
Case 3) If v is not a sink in G and there is no sink in V (G) \ Vy such that v is its only in-neighbor, then let
G0 := G − {v} and P0 be the partition of the vertices of G0 obtained from P by removing v from the set it is in. Update
Tabx (R0 , G0 , P0 ) with the value of Taby (R, G, P). This the simplest case, where the vertex is somewhat unimportant to
partial partitioning sets satisfying the pattern (R, G, P) at y, so we simply forget it.
Case 4) If there is a sink u ∈ V (G) \ Vy such that v is its only in-neighbor and {u, v} is a set of P, then let
G0 := G − {u, v} and P0 be the partition of the vertices of G0 obtained from P by removing the set {u, v}. Update
Tabx (R0 , G0 , P0 ) with the value of Taby (R, G, P): If there was a sink u in V (G) \Vy only reachable from v, then it would
be unreachable from Vx since v is forgotten. Therefore, if the part Pi of P containing u and v contained more vertices,
then we could not be sure that a partial partitioning set satisfying the pattern (R, G, P) at y is a partial partitioning set
for G[Ux ] at all. Namely, it may break Definition 3(ii).
We show that Procedure 1 fills the table Tabx associated with a forget node x correctly. First, we show that there is a
partial partitioning set for G[Ux ] satisfying a pattern (R, G, P) at x and having weight at most Tabx (R, G, P) as computed
by Procedure 1.
P ROOF ( OF L EMMA 6(i) FOR FORGET NODES ). Let x be a forget node with child node y and let v be the vertex
“forgotten”, that is, v is in the child bag Vy but not in the current bag Vx . For any table entry Tabx (R0 , G0 , P0 ) < ∞, we
show that there is a partial partitioning set S for G[Ux ] satisfying (R0 , G0 , P0 ) and having weight at most Tabx (R0 , G0 , P0 ).
To this end, observe that, since Tabx (R0 , G0 , P0 ) < ∞ there is a pattern (R, G, P) for y from which Procedure 1 generates (R0 , G0 , P0 ) and such that Tabx (R0 , G0 , P0 ) = Taby (R, G, P). Since there is a partitioning set for G[Uy ] that
satisfies (R, G, P) and has weight at most Taby (R, G, P), it is sufficient to show that any partial partitioning set S
for G[Uy ] that satisfies the pattern (R, G, P) at y is also a partial partitioning set for G[Ux ] that satisfies at x the
pattern (R0 , G0 , P0 ) generated in each of the cases (1)–(4) of Procedure 1.
We first argue that S is a partial partitioning set for G[Ux ] if any of the cases (1)–(4) of Procedure 1 applies. We first
verify Definition 3(i). To this end, observe that by Definition 5, a vertex u ∈ Vy is a sink in Gy (S) if and only if it is a
sink in G[Uy ] \ S. Now, assume that there is a connected component of G[Ux ] \ S = G[Uy ] \ S that contains two different
sinks s1 , s2 in Ux \Vx . Then, one of these sinks, say s1 , must be v. Since, then, v ∈ Vy is a sink in G[Ux ] \ S = G[Uy ] \ S,
it is a sink in G = Gy (S) and none of the cases (3) and (4) apply. Moreover, since s2 is connected to v ∈ Vy in G[Uy ] \ S,
by Definition 3(ii), some vertex in Vy can reach s2 , implying that s2 is a vertex of G = Gy (S). Thus, by Definition 5(iii),
s2 is in the same set Pi ∈ P as s1 = v and, hence, (1) does not apply. Since s2 < Vy , also (2) does not apply.
We now verify Definition 3(ii). It can only be violated if v is the only vertex of Vy that can reach some sink u in
the connected component of v in G[Uy ] \ S. However, then, v is the only in-neighbor of u in Gy (S) = G. Hence, only
case (4) might become applicable. When this case applies, however, {u, v} ∈ P implies that no vertex in Vy ⊇ Vx is
connected to v or u in G[Uy ] \ S = G[Ux ] \ S. Thus, Definition 3(ii) is satisfied.
23

It remains to show that S satisfies the generated pattern (R0 , G0 , P0 ), that is, to verify R0 = Rx (S) (Definition 5(i)),
= Gx (S) (Definition 5(ii)) and that P0 is a coarsening of Px (S) (Definition 5(iii)). Herein, R0 = R − {v} = Ry (S) −
{v} = Rx (S) is trivial. To show G0 = Gx (S), we distinguish between the case of Procedure 1 applied.
Case 1) In this case, v is not in Vx and, obviously, not a bag-reachable sink in G[Ux ] \ S. Hence, v is not in Gx (S).
Moreover, v is isolated in G = Gy (S). Therefore, Procedure 1 sets G0 := G − {v} = Gy (S) − {v} = Gx (S).
G0

Case 2) In this case, v is not in Vx but it is a bag-reachable sink in G[Ux ] \ S, since it is not isolated in G. Therefore,
Procedure 1 sets G0 := G = Gy (S) = Gx (S).
Case 3) In this case, v is not a sink in G (and thus also not in G[Ux ] \ S) and, therefore, clearly does not appear
in Gx (S). Moreover, any sink not in Vy is reachable from a vertex in Vy \ {v} = Vx in Gy (S) if and only if it is reachable
in Gy (S) − {v}. Hence, Procedure 1 sets G0 := G − {v} = Gy (S) − {v} = Gx (S).
Case 4) In this case, u was a bag-reachable sink in G[Uy ] \ S but is not bag-reachable in G[Ux ] \ S. Moreover, since
{v, u} ∈ P, no vertex of Vx is connected to v in G[Uy ] \ S = G[Ux ] \ S. Hence, neither v nor u are vertices of Gx (S).
Hence, Procedure 1 sets G0 := G − {u, v} = Gy (S) − {u, v} = Gx (S).
Finally, we verify Definition 5(iii) by showing that P0 is a coarsening of Px (S). Assume the contrary. Then, there
are two vertices u, w of Gx (S) in the same set of Px (S) but in different sets of P0 . By construction of P0 from P, they are
also in different sets of P = Py (S). It follows that u and w lie in the same connected component of G[Ux ] \ S but in
different connected components of G[Uy ] \ S. Since these two graphs are the same, we have a contradiction.

We now show that the minimum weight of a partial partitioning set for G[Ux ] satisfying a pattern (R, G, P) at x is at
least Tabx (R, G, P) as computed by Procedure 1.
P ROOF ( OF L EMMA 6(ii) FOR FORGET NODES ). Let x be a forget node with child node y. Let v be the vertex
“forgotten” that is, v ∈ Vy but v < Vx . Assume that S is a partial partitioning set for G[Ux ] satisfying the pattern (Rx , Gx , Px )
at x. It is sufficient to construct a pattern (R, G, P) that S satisfies at y and from which Procedure 1 generates exactly the
pattern (Rx , Gx , Px ) to update the table Tabx (Rx , Gx , Px ) with Taby (R, G, P). Then, Lemma 6(ii) follows for forget nodes,
because we have Tabx (Rx , Gx , Px ) ≤ Taby (R, G, P) ≤ ω(S). Herein, the last inequality follows from the induction
hypothesis.
We first show that S is a partial partitioning set for G[Uy ], that is, we verify Definition 3. Definition 3(i) is easy
to verify: since S is a partial partitioning set for G[Ux ], each connected component of G[Ux ] \ S = G[Uy ] \ S contains
at most one sink in Ux \ Vx ⊇ Uy \ Vy . It remains to verify Definition 3(ii). Assume, for a contradiction, that there
is a connected component C in G[Uy ] \ S that contains a vertex of Vy such that no vertex of Vy ⊇ Vx can reach some
sink s ∈ C \ Vy . Then, since S is a partial partitioning set for G[Ux ] \ S, the connected component C cannot contain
vertices of Vx and, hence, C ∩Vy = {v}. However, since G[Uy ] \ S is a directed acyclic graph, v reaches some sink in C.
Since v cannot reach s ∈ C, it follows that C contains two sinks. Since C ∩Vx = 0,
/ this contradicts S being a partial
partitioning set for G[Ux ] \ S. It follows that S is a partial partitioning set for G[Uy ].
We now construct a pattern (R, G, P) that S satisfies at y. Consider R := Ry (S) and G := Gy (S). Note that there are
at most two vertices in G that are not in Gx : one of them is v, the possibly other vertex is a sink u in V (G) \Vy only
reachable from v. We define P as a partition of the vertices of G that partitions the set V (Gx ) in the same way as Px . We
add the possibly missing vertices v and u to that partition as follows: if there is a vertex w ∈ Vx in the same connected
component of G[Uy ] \ S = G[Ux ] \ S as v, then we put v and u into same set as w. Otherwise, we add the set {v} or {u, v},
respectively, to P. By choice of R, G, and P, the partial partitioning set S clearly satisfies the pattern (R, G, P) at y.
We have shown that S satisfies the pattern (R, G, P) at y. Moreover, if any of the cases (1)–(4) of Procedure 1
applies to (R, G, P), then it generates a pattern (R0 , G0 , P0 ) with R0 = Rx and G0 = Gx , since we showed in the proof of
Lemma 6(i) for forget nodes that S satisfies the pattern generated by Procedure 1 at x. Hence, it remains to show that
indeed at least one of the cases (1)–(4) of Procedure 1 applies and that in all cases P0 = Px .
Case 1) If v is an isolated sink in G, then no vertex in Vy ⊇ Vx can reach v in G[Uy ] \ S = G[Ux ] \ S. Hence, there
is no vertex of Vx in the same connected component of G[Ux ] \ S as v, as otherwise v would be a sink in Ux \Vx not
reachable from the vertices of Vx . Hence, by construction of P, we have {v} ∈ P and case (1) of Procedure 1 applies. It
sets P0 := P \ {{v}} = Px .
Case 2) If v is a non-isolated sink in G, then v is a bag-reachable sink in G[Ux ] \ S. Hence, it is contained in Gx
and we have V (Gx ) = V (G). By construction of P, we also have Px = P. The set Pi ∈ Px containing v < Vx cannot
24

contain any other vertex in V (Gx ) \ Vx by Definition 4(iii). Thus, Pi ⊆ Vy and case (2) of Procedure 1 applies. It
sets P0 := P = Px .
Case 3) If v is not a sink in G and there is no sink in V (G) \ Vy only reachable from v in G, then case (3) of
Procedure 1 applies. Since the sink s reachable from v is also reachable from some vertex u < {v, s}, and thus, connected
to u in G[Uy ] \ S, the set in P containing v also contains u. Procedure 1 sets P0 to be P with v removed from the set it is
in. This, by construction of P, is exactly Px .
Case 4) Finally, if there is a sink u in V (G) \Vy only reachable from v, then the connected component of G[Uy ] \ S =
G[Ux ] \ S containing the vertex v does not contain any vertex of Vx , since u is not reachable from any vertex of Vx . It
follows that {u, v} is a set of P. Case (4) of Procedure 1 applies. It sets P0 := P \ {{v, u}} = Px .

4.2.2. Introduce nodes
We use the following procedure to compute the table Tabx of an introduce node x under the assumption that the
table Taby for the child node y of x has been computed correctly.
Procedure 2 (Introduce node). Let x be an introduce node with a single child y. Assume that v is the node being
“introduced”, that is, v is not in the child bag Vy but in the current bag Vx . Moreover, let B ⊆ A(G[Ux ]) be the set of arcs
incident to v. By Definition 2(ii and iii) of a tree decomposition, one actually has B ⊆ A(G[Vx ]).
We now try each possible subset B0 ⊆ B and consider it not deleted by a partial partitioning set for the graph G[Ux ].
Similarly as in the case for forget nodes, we will transform each pattern (R, G, P) for y into a pattern (R0 , G0 , P0 ) for x
such that if a partial partitioning set S for G[Uy ] satisfies (R, G, P), then S ∪ (B \ B0 ) is a partial partitioning set for G[Ux ]
and satisfies (R0 , G0 , P0 ). Then, we update Tabx (R0 , G0 , P0 ) with the value of Taby (R, G, P) + ω(B) − ω(B0 ).
For each pattern (R, G, P) for y such that all vertices incident to the arcs in B0 (if any) except for v are contained
in the same set Pi ∈ P, we obtain R0 from R by adding v and the arcs in B0 to R. Similarly, we obtain G0 from G by
adding v and the arcs in B0 to G. Moreover, for each u, w ∈ V (G0 ) such that u can reach w in G0 we add the arc (u, w)
to G0 . For obtaining P0 , we distinguish two cases.
Case 1) If B0 = 0,
/ then we try all possibilities of adding v to a set in P. That is, for every Pi ∈ P, we get a set P0
from P by adding v to Pi and update Tabx (R0 , G0 , P0 ) with Taby (R, G, P) + ω(B). Additionally, for P0 := P ∪ {{v}}, we
update the entry Tabx (R0 , G0 , P0 ) with Taby (R, G, P) + ω(B).
Case 2) If B0 , 0,
/ then let Pi be the set of P that contains all vertices incident to arcs in B0 except v and let P0 be
obtained from P by adding v to the set Pi . We update Tabx (R0 , G0 , P0 ) with Taby (R, G, P) + ω(B) − ω(B0 ).
Note that, since P simulates the connected components of the resulting graph, all arcs incident on v remaining in
the graph must be within one set of P, i.e., their endpoints different from v must be in one set of P.
We show that Procedure 2 fills the table associated with an introduce node x correctly. First, we show that there is a
partial partitioning set for G[Ux ] satisfying a pattern (R, G, P) at x and having weight at most Tabx (R, G, P) as computed
by Procedure 2.
P ROOF ( OF L EMMA 6(i) FOR INTRODUCE NODES ). Let x be an introduce node with child node y and let v be the
vertex “introduced” that is, v is not in the child bag Vy but in the current bag Vx . Let B ⊆ A(G[Vx ]) be the arcs incident
to v, B0 ⊆ B and, finally, (R, G, P) be some pattern for y such that all vertices incident to the arcs in B0 (if any) except
for v are contained in the same set Pi ∈ P. For any partial partitioning set S for G[Uy ] satisfying the pattern (R, G, P)
at y, we show that S0 = S ∪ (B \ B0 ) is a partial partitioning set for G[Ux ] that satisfies the pattern (R0 , G0 , P0 ) constructed
by Procedure 2. From this, since ω(S0 ) = ω(S) + ω(B) − ω(B0 ), Lemma 6(i) follows (as already discussed in the
beginning of the proof of Lemma 6(i) for forget nodes).
We start by showing that S0 is a partial partitioning set for G[Ux ]. First, we verify Definition 3(i). For the sake of a
contradiction, assume that there is a connected component of G[Ux ] \ S0 that contains two distinct sinks s1 , s2 in Ux \Vx .
Since there is no such connected component in G[Uy ] \ S = (G[Ux ] \ S0 ) − {v}, there are vertices s01 , s02 ∈ Vy in the same
connected components of G[Uy ] \ S as s1 and s2 , respectively, that are incident to some arcs in B0 . By Definition 3(ii),
there are vertices in Vy that can reach s1 and s2 in G[Uy ] \ S. Hence, s1 and s2 are bag-reachable and, therefore, in
G = Gy (S). Since s01 , s02 ∈ Pi and S satisfies (R, G, P), by Definition 4(iii), we also have s1 , s2 ∈ Pi . Then, however,
Pi contains the two different vertices s1 and s2 of V (G) \Vy , which contradictions Definition 4(iii).
25

To show that S0 is a partial partitioning set, it remains to verify Definition 3(ii). For the sake of contradiction,
assume that some connected component of G[Ux ] \ S0 contains some sink s ∈ Ux \Vx , some vertex in Vx , but s is not
reachable from any vertex in Vx . Then, s is not reachable from any vertex in Vy ⊆ Vx in the subgraph G[Uy ] \ S either.
Thus, the connected component does not contain any vertex of Vy and, therefore, not of Vx , since the only vertex
in Vx \Vy is v and the added arcs B0 connect only vertices in Vy .
We have shown that S0 is a partial partitioning set for G[Ux ]. We now show that it satisfies the pattern (R0 , G0 , P0 )
generated by Procedure 2; we verify Definition 5. Definition 5(i), that is, R0 = Rx (S0 ) is trivial by the construction
of R0 .
We verify Definition 5(ii), that is, Gx (S0 ) = G0 . First, observe that V (Gx (S0 )) = V (Gy (S)) ∪ {v} = V (G0 ). We have
to show that there is an arc (u, w) in G0 if and only if u can reach w in G[Ux ] \ S0 . Let (u, w) be such an arc in G0 . If
(u, w) is already in G, then u can reach w in G[Uy ] \ S = (G[Ux ] \ S0 ) − {v}. Otherwise, u reaches w in G0 via some
arcs (u0 , v), (v, w0 ) ∈ B0 , that is, u can reach u0 and w0 can reach w in G[Ux ] \ S0 . It follows that u can reach w in
G[Ux ] \ S0 . Now, for the opposite direction, let u, w be vertices of G0 such that u can reach w in G[Ux ] \ S0 . If u can
reach w in (G[Ux ] \ S0 ) − {v} = G[Uy ] \ S, then the arc (u, w) is already present in G. Otherwise, u reaches w via some
arcs (u0 , v), (v, w0 ) ∈ B0 . The arcs (u0 , v) and (v, w0 ) are in G0 , since u0 , w0 ∈ Vx . Moreover, u reaches u0 and w0 reaches w
in G[Ux ] \ S0 . Hence, there are arcs (u, u0 ) and arc (w0 , w) in G0 and u reaches w in G0 via u0 and w0 . By construction
of G0 , it follows that G0 contains the arc (u, w).
Finally, we verify Definition 5(iii); we show that P0 is a coarsening of Px (S0 ). For the sake of a contradiction,
assume that there are two vertices u, w that are in the same set of Px (S0 ) but in different sets of P0 . By construction
of P0 from P, this implies that u and w are in different sets of P and, therefore, in different connected components
of G[Uy ] \ S. Thus, in order for u and w to be connected in G[Ux ] \ S0 , there are vertices u0 , w0 in the same connected
components of G[Uy ] \ S as u and w, respectively, that are incident to arcs in B0 and, hence, u0 , w0 ∈ Pi ∈ P. But then,
also u, w ∈ Pi ∈ P — a contradiction.

We now show that the minimum weight of a partial partitioning set for G[Ux ] satisfying a pattern (R, G, P) at x is at
least Tabx (R, G, P) as computed by by Procedure 2.
P ROOF ( OF L EMMA 6(ii) FOR INTRODUCE NODES ). Let x be an introduce node with child node y. Let v be the vertex
“introduced”, that is, v < Vy but v ∈ Vx . Assume that S is a minimum-weight partial partitioning set for G[Ux ] satisfying
the pattern (Rx , Gx , Px ) at x. Let B be the set of arcs incident to v in G[Ux ] and B00 := B ∩ S. It is sufficient to construct
a pattern (R, G, P) that S \ B00 satisfies at y and from which Procedure 2 generates exactly the pattern (Rx , Gx , Px ) to
update the table Tabx (Rx , Gx , Px ) with Taby (R, G, P) + ω(B) − ω(B0 ), where B0 = B \ B00 . Then, Lemma 6(ii) follows
for introduce nodes, since Tabx (Rx , Gx , Px ) ≤ Taby (R, G, P) + ω(B) − ω(B0 ) ≤ ω(S \ B00 ) + ω(B) − ω(B0 ) = ω(S).
It is easy to verify that S \ B00 is a partial partitioning set for G[Uy ] (Definition 3), since G[Uy ] \ (S \ B00 ) =
(G[Ux ] \ S) − {v} and S is a partial partitioning set for G[Ux ]; to this end, observe that, by Definition 2(ii and iii) of a
tree decomposition, v only has arcs B ⊆ A(G[Vx ]) incident to vertices in Vy .
We now construct a pattern. Let R = Ry (S \ B00 ) and G = Gy (S \ B00 ). Let P be the partition obtained from Px by
removing the vertex v from the set it is in or by removing the set {v} if it exists in Px . It is easy to verify that S \ B00
satisfies (R, G, P) at y: Definition 5(i) and (ii) are trivially satisfied by choice of R and G; Definition 5(iii) holds by
construction of P from Px , since G[Uy ] \ (S \ B00 ) is a subgraph of G[Ux ] \ S.
It remains to show that Procedure 2 applies to the pattern (R, P, G) and the set B0 in order to generate the
pattern (Rx , Px , Px ). Since S satisfies (Rx , Gx , Px ) at x, all vertices incident to arcs in B0 (if any) are contained in
the same set Pi ∈ Px and, hence, all of them except v are contained in the set Pi \ {v} ∈ P. Therefore, Procedure 2
applies to B0 and the pattern (R, G, P), produces some new pattern (R0 , G0 , P0 ), and updates Tabx (R0 , G0 , P0 ) with
Taby (R, G, P) + ω(B) − ω(B0 ).
It remains to show that, for at least one of the generated patterns, R0 = Rx , G0 = Gx , and P0 = Px . If B0 , 0/ then
0
P = Px by construction of P0 from P in Procedure 2. If B0 = 0,
/ then Px is clearly among the partitions P0 generated
from P by Procedure 2. Moreover, we already proved in the proof of Lemma 6(i) that S = (S \ B00 ) ∪ (B \ B0 ) satisfies
the pattern generated by Procedure 2 at x. Hence, R0 = Rx and G0 = Gx .

4.2.3. Join nodes
We use the following procedure to compute the table Tabx of a join node x under the assumption that the tables Taby
for all child nodes y of x have been computed correctly.
26

Procedure 3 (Join node). Let x be a join node with children y and z, that is, Vx = Vy = Vz . For each pair of patterns (R, Gy , Py ) for y and (R, Gz , Pz ) for z such that Py and Pz partition the vertices of Vy = Vz = Vx in the same way,
we construct a new pattern (R, G, P) as follows.
Let G0 be the graph containing all vertices and arcs of Gy and Gz , and for each u, w ∈ V (G0 ) such that u can reach w
in G0 add the arc (u, w) to G0 . Note that by Definition 2(iii) of a tree decomposition, Gy and Gz have only the vertices
in Vx in common.
Let P0 be the partition of Vx that partitions Vx in the same way as Py and Pz . We extend P0 to a partition for the
vertices of G0 : for each u ∈ V (G0 ) \Vx , add u to a set Pi of P0 that contains a vertex v with (v, u) being an arc of G0 . Since
there are no arcs between different sets of P in Gy or Gz , there is exactly one such set Pi ∈ P0 .
If we created some set P ∈ P0 with more than one vertex of V (G0 ) \Vx , then continue with a different pair of patterns.
Otherwise, we update Tabx (R, G0 , P0 ) with Taby (R, Gy , Py ) + Tabz (R, Gz , Pz ) − ω(A(G[Vx ])) + ω(A(R)).
We show that Procedure 3 fills the table associated with a join node x correctly. First, we show that there is a partial
partitioning set for G[Ux ] satisfying a pattern (R, G, P) at x and having weight at most Tabx (R, G, P) as computed by
Procedure 3.
P ROOF ( OF L EMMA 6(i) FOR JOIN NODES ). Let x be a join node with child nodes y and z, that is, Vx = Vy = Vz . Let
Sy be a partial partitioning set for G[Uy ] satisfying the pattern (R, Gy , Py ) at y and let Sz be a partial partitioning
set for G[Uz ] satisfying the pattern (R, Gz , Pz ) at z. We show that S = Sy ∪ Sz is a partial partitioning set for G[Ux ]
that satisfies the pattern (R, G0 , P0 ) constructed by Procedure 3. Since ω(S) = ω(Sy ) + ω(Sz ) − ω(Sy ∩ Sz ), wherein
Sy ∩ Sz = A(G[Vx ]) \ A(R), Lemma 6(i) follows for join nodes.
We show that S is indeed a partial partitioning set for G[Ux ], that is, we verify Definition 3. We first verify
Definition 3(ii) and then use it to verify Definition 3(i). Let s ∈ Ux \Vx be a sink such that the connected component
containing s in G[Ux ]\S contains a vertex of Vx . Then, s ∈ Uy \Vx or s ∈ Uz \Vx . Without loss of generality, let s ∈ Uy \Vx .
From Definition 2(iii) of a tree decomposition, we see that Uz ∩Uy ⊆ Vx and, hence, G[Uy ] \ Sy = G[Ux ] \ S − (Uz \Vz ).
It follows that there is also a connected component of G[Uy ] \ Sy = G[Ux ] \ S − (Uz \Vz ) that contains s and a vertex
of Vx and, therefore, s is reachable from some vertex v ∈ Vx in G[Ux ] \ S − (Uz \Vz ) and, hence, in G[Ux ] \ S. It also
follows that (v, s) is an arc in Gy and, by construction in Procedure 3, of G0 .
To verify Definition 3(i), for the sake of a contradiction, assume that there is a connected component of G[Ux ] \ S
that contains two sinks s1 , s2 in Ux \ Vx . Note that, by Definition 2(iii) of a tree decomposition, there are no arcs
between Uy \ Vx and Uz \ Vx . Hence, this connected component contains a vertex v of Vx ; otherwise, it would be a
connected component with two sinks outside of Vx already in either G[Uy ] \ Sy or G[Uz ] \ Sz . Thus, as seen in the
previous paragraph, we have arcs (s01 , s1 ) and (s02 , s2 ) with s01 , s02 ∈ Vx . It follows by construction of P0 from G0 in
Procedure 3 that s1 and s01 are in a set Pi ∈ P0 and s2 and s02 are in a set Pj ∈ P0 . We show i = j, which contradicts the
construction of P0 , since then Pi = Pj contains two vertices s1 < Vx and s2 < Vx .
Since s1 and s2 are in the same connected component of G[Ux ] \ S, also s01 and s02 are, since they can reach s1
and s2 , respectively. Hence, there is an undirected path p between s1 and s2 in G[Ux ] \ S. It consists of consecutive path
segments p0 that only have their endpoints u, w in Vx (possibly, such a path segment only consists of one arc). It follows
that such a path segment p0 is entirely contained in G[Uy ] \ Sy or G[Uz ] \ Sy and, hence, its endpoints u and w are in the
same set of Py or Pz . Since u, w ∈ Vx , by construction of P0 in Procedure 3, u and w are in the same set of P0 . It follows
that s01 and s02 are in the same set of P0 , and so are s1 and s2 .
It follows that S is indeed a partial partitioning set for G[Ux ] \ S. It remains to verify that S satisfies the pattern (R, G0 , P0 ) (Definition 5). Herein, Definition 5(i), R = Rx (S), is trivial. We verify (ii), that is, Gx (S) = G0 . Herein,
V (Gx (S)) ⊆ V (G0 ) we already verified when verifying Definition 3(ii). Now, assume that there are two vertices u, w
in G0 such that u can reach w in G[Ux ] \ S. Since, then, u is not a sink, it is in Vx . The directed path from u to w consists
of consecutive subpaths, each being entirely contained in G[Uy ] \ Sy or G[Uz ] \ Sz and thus, causing an arc in Gy or Gz
and, therefore, in G0 . It follows that u can reach w in G0 , which therefore has an arc (u, w). In the opposite direction, for
every arc (u, w) in G0 that is already in Gy or Gz , there is an directed path in either G[Uy ] \ Sy or in G[Uz ] \ Sz from u
to w and, thus, u can reach w in G[Ux ] \ S. For an arc (u, w) in G0 that is neither present in Gy nor Gz , there is an directed
path in G0 from u to w consisting only of arcs that are already present in Gy or Gz . Since we have seen that for each such
arc there is a corresponding directed path in G[Ux ] \ S, we have that u can reach w in G[Ux ] \ S.
For Definition 5(iii), it has been shown above that if two vertices of G0 are in the same connected component
of G[Ux ] \ S, then they are in the same set in P0 .

27

We now show that the minimum weight of a partial partitioning set for G[Ux ] satisfying a pattern (R, G, P) at x is at
least Tabx (R, G, P) as computed by by Procedure 3.
P ROOF ( OF L EMMA 6(ii) FOR JOIN NODES ). Let x be a join node with the child nodes y and z, that is Vx = Vy = Vz .
Assume that S is a minimum-weight partial partitioning set for G[Ux ] satisfying the pattern (R, Gx , Px ) at x. It is sufficient
to construct patterns (R, Gy , Py ) and (R, Gz , Pz ) that are satisfied by Sy := S ∩ A(G[Uy ]) at y and by Sz := S ∩ A(G[Uz ])
at z, respectively, such that from these patterns Procedure 3 generates exactly the pattern (R, Gx , Px ) to update
Tabx (R, Gx , Px ) with
Taby (R, Gy , Py ) + Tabz (R, Gz , Pz ) − ω(A(G[Vx ])) + ω(A(R))
≤ ω(Sy ) + ω(Sz ) − ω(Sy ∩ Sz )
= ω(S).
We first show that Sy is a partial partitioning set for G[Uy ]. Symmetrically, it follows that Sz is a partial partitioning
set for G[Uz ]. We first verify Definition 3(i). Since by Definition 2(iii), there are no arcs between vertices in Uy \Vy
and Uz \ Vz in G[Ux ], it follows from G[Uy ] \ Sy = G[Ux ] \ S − (Uz \ Vz ) that no connected component of G[Uy ] \ Sy
contains two sinks not in Vy = Vx . It remains to verify Definition 3(ii). To this end, let u be a sink in Uy \ Vy in a
connected component of G[Uy ] \ Sy containing a vertex of Vy . Then, by Definition 3(ii), the connected component
of G[Ux ] \ S containing u contains a directed path from some vertex in Vx to u. The subpath of this directed path that
contains only one vertex of Vx is preserved in G[Uy ] \ Sy . Hence, u is reachable from some vertex of Vx = Vy .
We now construct the patterns. To this end, let Gy := Gy (Sy ) and Gz := Gz (Sz ). Moreover, we choose Py and Pz such
that they partition the set Vx = Vy = Vz in the same way as Px and such that the vertices of V (Gy ) \Vy (or V (Gz ) \Vz ) are
in the same set as the other vertices of their connected components in G[Uy ] \ Sy (or G[Uz ] \ Sz ).
We show that Sy satisfies (R, Gy , Py ) at y. Analogously, it then follows that Sz satisfies (R, Gz , Pz ) at z. We verify
Definition 5. Since R = Rx (S) = Ry (Sy ) = Rz (Sz ) and Gy = Gy (Sy ) hold by definition, it remains to verify Definition 5(iii). To this end, observe that G[Uy ] \ Sy = G[Ux ] \ S − (Uy \Vy ). Now, assume, for the sake of a contradiction,
that there are two vertices v, w of Gy in different sets of Py but in the same connected component of G[Uy ] \ Sy . It
follows that v and w are in the same connected component of G[Ux ] \ S. If v, w ∈ Vy , then, by construction of Py from Px ,
the vertices v and w are in different sets of Px , contradicting Sx satisfying (R, Gx , Px ). If exactly one of v, w is in Vy ,
then v and w being in different sets of Py contradicts the construction of Py . If both v, w < Vy , then v and w are two
bag-reachable sinks in G[Uy ], which contradicts v and w being in the same connected component of G[Uy ] \ Sy .
Hence, indeed Sy satisfies (R, Gy , Py ) at y and Sz satisfies (R, Gz , Pz ) at z. Moreover, since Py and Pz partition Vx in
the same way, Procedure 3 applies to the patterns (R, Gy , Py ) and (R, Gz , Pz ) and produces a pattern (R, G0 , P0 ). If no
set of P0 contains more than one vertex of V (G0 ) \Vx , it indeed updates Tabx (R, G0 , P0 ).
Hence it remains to show that G0 = Gx and P0 = Px , as no set of Px contains two vertices of V (Gx ) \Vx by Definition 4(iii). We already showed in the proof of Lemma 6(i) for join nodes that S satisfies the pattern (R, G0 , P0 ) generated
by Procedure 3. Hence, G0 = Gx . Finally, by construction of P0 in Procedure 3, the vertices of Vx are partitioned the
same way by P0 and Px . For a vertex v ∈ V (G0 ) \ Vx , there is a vertex u in Vx that can reach v in G0 and, therefore,
in G[Ux ] \ S. Hence, u and v must be in the same set of both Px and P0 by construction of P0 in Procedure 3.

4.2.4. Running time
Having shown the correctness of the Procedures 1–3, we can finally complete the proof of Theorem 6 by analyzing the
running time of the procedures.
P ROOF ( OF T HEOREM 6). Lemma 6 showed that the presented dynamic programming algorithm is correct, that is, it
solves DAG PARTITIONING given a tree decomposition of the input graph. It remains to analyze the running time.
To this end, recall that each bag in a tree decomposition of width t contains at most t + 1 vertices. This allows
t+1
us to give an upper bound on the number of possible patterns (R, G, P). There are at most 3( 2 ) directed acyclic
graphs R on at most t + 1 vertices: for each pair (v, w) of vertices: there is either no arc, or an arc from v to w, or
2t+2
an arc from w to v. Similarly, there are at most 3( 2 ) directed graphs G on at most 2t + 2 vertices. Moreover, there
are at most (2t + 2)2t+2 partitions P of at most 2t + 2 vertices into at most 2t + 2 sets. Hence, each table has at most
28

2t+2
t+1
2
2
3( 2 ) · 3( 2 ) · (2t + 2)2t+2 = 3O(t +t logt) = 2O(t ) entries and looking up entries in the tables can be implemented to
2
run in O(log 2t ) time, which is polynomial in t.
In each leaf node, we set the single table entry to 0 in constant time.
In each forget node, Procedure 1 iterates over the entries of the table of the child node and for each entry spends
2
time polynomial in t. Thus, it spends a total of 2O(t ) time in each forget node.
To analyze the running time Procedure 2 spends in an introduce node, observe that there are at most t arcs
in A(G[Vx ]) incident to the introduced vertex v. Hence, there are at most 2t subsets of them. For each of these subsets
2
and for each entry of the child node, Procedure 2 spends time polynomial in t. This makes a total of 2O(t ) time spent in
each introduce node.
Finally, in a join node, Procedure 3 considers every pair of patterns of its two child nodes and for each combination
2
2
spends time polynomial in t. Hence, the total time spent in a join node is (2O(t ) )2 = 2O(t ) .
2
Since the nice tree decomposition has O(tn) nodes, the algorithm runs in 2O(t ) · n time.


5. Other parameters yield stronger NP-hardness results
In Sections 3 and 4, we have seen that DAG PARTITIONING is solvable in linear time when fixing the weight of the
partitioning set sought or the treewidth of the input graph. The question whether fixed-parameter algorithms can be
obtained for parameters that are smaller than the solution weight or the treewidth naturally arises [29, 25, 14]. One
parameter of interest is the maximum vertex outdegree in the graph: a citation network of journal articles will, for
example, have a small outdegree since journal articles seldom contain more than 50 references. In this section, however,
we will show that, among others, this parameter being small will not help solving DAG PARTITIONING efficiently.
Alamdari and Mehrabian [1] already showed that DAG PARTITIONING remains NP-hard even if the input graph
has only two sinks. We complement this negative result by showing that the problem remains NP-hard even if the
diameter or the maximum vertex degree of the input graph are constant. In conclusion, parameters like the number of
sinks, the graph diameter or maximum degree cannot lead to fixed-parameter algorithms unless P = NP.
Theorem 7. DAG PARTITIONING is solvable in linear time on graphs of diameter one, but NP-complete on graphs of
diameter two even if all arcs have unit weight.
P ROOF. On graphs of diameter one, the problem is trivial: a directed acyclic graph with diameter one is an acyclic
tournament, that is, there is no pair of vertices not joined by an arc. As such, it already contains exactly one source and
one sink. Hence, we just verify in linear time whether the input graph is an acyclic tournament and answer “yes” or
“no” accordingly.
For graphs of diameter two, we show NP-hardness by means of a polynomial-time many-one reduction from DAG
PARTITIONING, which is NP-hard even when all arcs have weight one. Therefore, we agree on all arcs in this proof
having weight one.
Given an arbitrary instance (G, ω, k) of DAG PARTITIONING, we add a gadget to G to obtain in polynomial
time an instance (G0 , ω 0 , k0 ) such that G0 is a graph of diameter two and such that (G, ω, k) is a yes-instance if and
only if (G0 , ω 0 , k0 ) is a yes-instance. We obtain a graph G0 from G by adding an acyclic tournament T consisting of
k + n + 2 vertices and outgoing arcs from the source s of T to all vertices of V (G) in G0 . We set k0 := k + n. Since every
vertex in G0 is in distance one from s, the constructed graph G0 has diameter two.
If (G, ω, k) is a yes-instance, then let S be a partitioning set with k arcs for G. A partitioning set S0 with k0 arcs
for G0 is obtained by adding to S the n arcs from the source s of T to all vertices of V (G) in G0 . Thus, (G0 , ω 0 , k) is a
yes-instance.
If (G0 , ω 0 , k0 ) is a yes-instance, then let S0 be a partitioning set with k0 arcs for G0 . By Observation 2, every vertex
in V (G) reaches at least one sink in G0 \ S0 . This sink cannot be the sink of T , since no vertex in T is reachable
from V (G). Thus, S0 has to disconnect the sink of T from all vertices of V (G) in G0 , where all paths between the sink
of T and V (G) are via the source s of T . Since T has k + n + 2 vertices, S0 cannot disconnect s from the sink of T and
thus, has to remove from G0 the n arcs connecting s to the vertices of V (G). Then, the remaining k arcs in S0 have to
be a partitioning set for G0 without the tournament T , which is precisely the original graph G. Thus, (G, ω, k) is a
yes-instance.

29

t1

t2

v2

t3

e{t1 ,t2 }

Z
e{t1 ,v1 }
Y

v1

t1

e{v1 ,t2 }

e{t2 ,v2 }

v1

t2

e{v2 ,t3 }
v2

t3

X
s1

s2

s3

Figure 13: Reduction from a M ULTIWAY C UT instance with the terminals t1 ,t2 , and t3 to DAG PARTITIONING. The top shows an instance I1 of
M ULTIWAY C UT, where the dotted edges are a multiway cut of size k1 = 3. The bottom shows the corresponding instance I2 of DAG PARTITIONING,
where the dotted arcs are a corresponding partitioning set of size k2 = k1 + 2(n − 3) = 7 (n is the number of vertices in the graph of the M ULTIWAY
C UT instance). The constructed vertex sets X,Y , and Z are highlighted using a gray background.

Theorem 8. DAG PARTITIONING is solvable in linear time on graphs of maximum degree two, but NP-complete on
graphs of maximum degree three even if all arcs have unit weight.
P ROOF. Any graph of maximum degree two consists of undirected cycles or undirected paths. Thus, the underlying
graph has treewidth at most two. We have seen in Theorem 6 that DAG PARTITIONING is linear-time solvable when
the treewidth of the input graph is bounded by a constant.
We prove the NP-hardness on graphs of maximum degree three. To this end, we adapt the polynomial-time manyone reduction from M ULTIWAY C UT to DAG PARTITIONING presented by Leskovec et al. [26]. In their reduction, we
replace vertices of degree greater than three by equivalent structures of lower degree.
M ULTIWAY C UT
Input: An undirected graph G = (V, E), a weight function ω : E → N, a set T ⊆ V of terminals, and an integer k.
Question: Is there a subset S ⊆ E with ∑e∈S ω(e) ≤ k such that the removal of S from G disconnects each terminal
from all the others?
We first recall the reduction from M ULTIWAY C UT to DAG PARTITIONING. From a M ULTIWAY C UT instance I1 :=
(G1 , ω1 , T, k1 ), we construct in polynomial time a DAG PARTITIONING instance I2 := (G2 , ω2 , k2 ) such that I1 is a
yes-instance if and only if I2 is. From I2 , we then obtain an instance I3 with maximum degree three. Since M ULTIWAY
C UT remains NP-hard even for three terminals and unit weights [11], we may assume |T | = 3 and, similarly as in the
proof of Theorem 7, we agree on all arcs in this proof having weight one. We now construct the DAG PARTITIONING
instance I2 = (G2 , ω2 , k2 ) from I1 = (G1 , ω1 , T, k1 ) as follows. The construction is illustrated in Figure 13.
1. Add three vertices s1 , s2 , s3 to G2 , forming the vertex set X,
2. add each vertex of G1 to G2 , forming the vertex set Y ,
3. for each edge {u, v} of G1 , add a vertex e{u,v} to G2 , forming the vertex set Z,
4. for each terminal ti ∈ T , add the arc (ti , si ) to G2 ,
5. for each vertex v ∈ Y \ T , add the arcs (v, si ) for i = 1, 2, 3 to G2 , and
6. for each edge {u, v} of G1 , add the arcs (e{u,v} , u) and (e{u,v} , v) to G2 .

30

w1

w3

w2

w4

w1

w3

w2

w4

w02
w03
w04
v

v
v0

s1

s2

s3

s1

Tv

s2

s3

Figure 14: Reduction of the degree of a vertex v to three. On the left, the original neighborhood of v is shown. The right side shows v after
modification. The tree structure Tv constructed in the proof is highlighted using a gray background.

Set k2 = k1 + 2(n − 3), where n is the number of vertices of G1 . We claim that I1 is a yes-instance if and only if I2 is a
yes-instance.
First, suppose that there is a multiway cut S of size at most k1 for G1 . Then, we obtain a partitioning set of size
at most k2 for G2 as follows: if a vertex v belongs to the same connected component of G1 \ S as terminal ti , then
remove every arc (v, s j ) with j , i from G2 . Furthermore, for each edge {u, v} ∈ S, remove either the arc (e{u,v} , u) or
the arc (e{u,v} , v) from G2 . One can easily check that we end up with a valid partitioning set of size k2 = k + 2(n − 3)
for G2 : we delete at most k arcs from Z to Y and, for each of the n − 3 vertices in Y \ T , delete two arcs from Y to X.
There are no arcs from X to Z.
Conversely, suppose that we are given a minimal partitioning set S of size at most k2 for G2 . Note that it has
to remove at least two of the three outgoing arcs of each vertex v2 ∈ Y \ T but cannot remove all three of them:
contrary to Observation 1, this would create a new sink. Thus, S deletes 2(n − 3) arcs from Y to X and the remaining
k2 − 2(n − 3) = k1 arcs from Z to Y . Therefore, we can define the following multiway cut of size k1 for G1 : remove an
edge {u, v} from G1 if and only if one of the arcs (e{u,v} , u) and (e{u,v} , v) is removed from G2 by S. Again, one can
easily check that we end up with a valid multiway cut.
It remains to modify the instance I2 = (G2 , ω2 , k2 ) to get an instance I3 = (G3 , ω3 , k3 ) of maximum degree three.
To this end, first we show how to reduce the outdegree of each vertex of G2 to two. Thereafter, we show how to reduce
the indegree of each vertex of G2 to one by introducing gadget vertices, each having indegree two and outdegree one.
The construction is illustrated in Figure 14.
Note that all vertices of G2 with outdegree larger than two are in Y . In order to decrease the degree of these
vertices, we obtain a graph G03 from G2 by carrying out the following modifications (see Figure 14) to G2 : for each
vertex v ∈ Y , with N + (v) = {s1 , s2 , s3 }, remove (v, s1 ) and (v, s2 ) add a new vertex v0 , and insert the three arcs (v, v0 ),
(v0 , s1 ), and (v0 , s2 ).
We show that (G03 , ω30 , k2 ) is a yes-instance if and only if (G2 , ω2 , k2 ) is. To this end, for v ∈ Y , let Tv be the
induced subgraph G03 [{v, v0 , s1 , s2 , s3 }]. In G2 , a minimal partitioning set removes exactly two of the outgoing arcs of v,
since s1 , s2 , and s3 are sinks. It is enough to show that a minimal partitioning set S removes exactly two arcs in Tv from G03
in such a way that there remains exactly one directed path from v to exactly one of s1 , s2 , or s3 . This remaining directed
path then one-to-one corresponds to the arc that a partitioning set would leave in G2 between v and s1 , s2 , or s3 . Since
s1 , s2 , and s3 are sinks, S indeed has to remove at least two arcs from Tv : otherwise, two sinks will belong to the same
connected component. However, due to Observation 1, S cannot remove more than two arcs from Tv . Moreover, again
exploiting Observation 1, the two arcs removed by S leave a single directed path from v to exactly one of s1 , s2 , or s3 .
We have seen that (G03 , ω30 , k2 ) is equivalent to (G2 , ω2 , k2 ) and that all vertices of G03 have outdegree two. To shrink
31

the overall maximum degree to three, it remains to reduce the indegrees. Note that the vertices newly introduced
in the previous step already have indegree one. We obtain graph G3 of maximum degree three from G03 as follows.
For each vertex v with |N − (v)| = |{w1 , . . . , wd − (v) }| ≥ 2, do the following (see Figure 14): for j = 2, . . . , d − (v), remove the arc (w j , v) and add a vertex w0j together with the arc (w j , w0j ). Moreover, add the arcs (w1 , w02 ), (wd − (v) , v),
and (w0j , w0j+1 ) for each j ∈ {2, . . . , d − (v) − 1}. Now, every vertex of V (G03 ) in G3 has indegree one and outdegree two,
while the newly introduced vertices have indegree two and outdegree one. It follows that all vertices in G3 have degree
at most three.
It remains to show that (G3 , ω3 , k2 ) is a yes-instance if and only if (G03 , ω30 , k2 ) is. It then follows that (G3 , ω3 , k2 ) is
a yes-instance if and only if (G2 , ω2 , k2 ) is. To this end, note that by Observation 1, among the introduced arcs, only the
arcs w1 , w02 and (w j , w0j ) can be removed by a minimal partitioning set. From this, there is a one-to-one correspondence
between deleting the arc w1 , w02 or (w j , w0j ) in the graph G3 and deleting the arc (w j , v) in the graph G03 .

6. Outlook
We have presented two fixed-parameter algorithms for DAG PARTITIONING, one with respect to the weight k of
the partitioning set sought and one with respect to the parameter treewidth t.
We demonstrated the feasibility of applying the fixed-parameter algorithm for the parameter k (Algorithm 1) to
large input instances with optimal partitioning sets of small weight. However, we were unable to solve the instances in
the data set of Leskovec et al. [26], since the weight of optimal partitioning sets is too large. We found out that the
heuristic presented by Leskovec et al. [26] finds nearly optimal partitioning sets on the instances that our algorithm
works on best. However, we have also seen that one does not have to specially craft adversarial instances to make the
heuristic perform badly. Surprisingly, our algorithm for DAG PARTITIONING is much simpler and more efficient than
the algorithm for M ULTIWAY C UT by Xiao [34], although M ULTIWAY C UT is much easier to approximate than DAG
PARTITIONING [23, 1].
On the theoretical side, we improved a fixed-parameter algorithm by Alamdari and Mehrabian [1] such that the
running time now depends on the treewidth of the input graph rather than on its pathwidth. However, our algorithm, as
well as the algorithm of Alamdari and Mehrabian [1], are practically inapplicable.
Towards solving the instances of Leskovec et al. [26] exactly in reasonable time, a challenging task would be to
analyze the data used by Leskovec et al. [26] in order to find parameters that are small and make DAG PARTITIONING
fixed-parameter tractable, that is, to take a data-driven approach to parameterizing DAG PARTITIONING.
Acknowledgments
We are thankful to Rolf Niedermeier and to the anonymous referees of CIAC’13 and Discrete Applied Mathematics for
helpful comments.
René van Bevern acknowledges supported by the Russian Foundation for Basic Research (RFBR), project 16-3160007 mol a dk, while working at Novosibirsk State University, and by the German Research Foundation (DFG),
project DAPA (NI 369/12), while working at TU Berlin. Robert Bredereck acknowledges support by DFG project PAWS
(NI 369/10). Morgan Chopin was supported by the DAAD during a three-month visit to TU Berlin in summer 2012.
Falk Hüffner acknowledges support by DFG projects PABI (NI 369/7) and ALEPH (HU 2139/1). Ondřej Suchý
acknowledges support by DFG project AREG (NI 369/9) while at TU Berlin and by the Czech Science Foundation,
project 14-13017P.
References
[1] S. Alamdari and A. Mehrabian. On a DAG partitioning problem. In Proceedings of the 9th International Workshop on Algorithms and
Models for the Web Graph (WAW’12), volume 7323 of Lecture Notes in Computer Science, pages 17–28. Springer, 2012. doi: 10.1007/
978-3-642-30541-2 2.
[2] A.-L. Barabási and R. Albert. Emergence of scaling in random networks. Science, 286(5439):509–512, 1999. doi: 10.1126/science.286.5439.
509.
[3] R. van Bevern. Towards optimal and expressive kernelization for d-Hitting Set. Algorithmica, 70(1):129–147, 2014. doi: 10.1007/
s00453-013-9774-3.

32

[4] R. van Bevern, S. Hartung, F. Kammer, R. Niedermeier, and M. Weller. Linear-time computation of a linear problem kernel for Dominating Set
on planar graphs. In Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC’11), volume 7112 of
Lecture Notes in Computer Science, pages 194–206. Springer, 2012. doi: 10.1007/978-3-642-28050-4 16.
[5] R. van Bevern, R. Bredereck, M. Chopin, S. Hartung, F. Hüffner, A. Nichterlein, and O. Suchý. Parameterized complexity of DAG Partitioning.
In Proceedings of the 8th International Conference on Algorithms and Complexity (CIAC’13), number 7878 in Lecture Notes in Computer
Science, pages 49–60. Springer, 2013.
[6] H. L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305–1317,
1996. doi: 10.1137/S0097539793251219.
[7] H. L. Bodlaender. Kernelization: New upper and lower bound techniques. In Proceedings of the 4th International Workshop on Parameterized
and Exact Computation (IWPEC’09), volume 5917 of Lecture Notes in Computer Science, pages 17–37. Springer, 2009. doi: 10.1007/
978-3-642-11269-0 2.
[8] H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch. Kernelization lower bounds by cross-composition. SIAM Journal on Discrete Mathematics,
28(1):277–305, 2014. doi: 10.1137/120880240.
[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, 2nd edition, 2001.
[10] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer,
2015. doi: 10.1007/978-3-319-21275-3.
[11] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on
Computing, 23(4):864–894, 1994. doi: 10.1137/S0097539792225297.
[12] R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013. doi: 10.1007/978-1-4471-5559-1.
[13] S. Fafianie and S. Kratsch. A shortcut to (sun)flowers: Kernels in logarithmic space or linear time. In Proceedings of the 40th International
Symposium on Mathematical Foundations of Computer Science (MFCS’15), volume 9235 of Lecture Notes in Computer Science, pages
299–310. Springer, 2015. doi: 10.1007/978-3-662-48054-0 25.
[14] M. R. Fellows, B. M. P. Jansen, and F. A. Rosamond. Towards fully multivariate algorithmics: Parameter ecology and the deconstruction of
computational complexity. European Journal of Combinatorics, 34(3):541–566, 2013. doi: 10.1016/j.ejc.2012.04.008.
[15] J. Flum and M. Grohe. Parameterized Complexity Theory. Springer, 2006. doi: 10.1007/3-540-29953-X.
[16] L. Fortnow and R. Santhanam. Infeasibility of instance compression and succinct PCPs for NP. Journal of Computer and System Sciences, 77
(1):91–106, 2011. doi: 10.1145/1374376.1374398.
[17] J. Guo and R. Niedermeier. Invitation to data reduction and problem kernelization. ACM SIGACT News, 38(1):31–45, 2007. doi: 10.1145/
1233481.1233493.
[18] T. Hagerup. Simpler linear-time kernelization for Planar Dominating Set. In Proceedings of the 6th International Symposium on Parameterized
and Exact Computation (IPEC’11), volume 7112 of Lecture Notes in Computer Science, pages 181–193. Springer, 2012. doi: 10.1007/
978-3-642-28050-4 15.
[19] R. Impagliazzo and R. Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367–375, 2001. doi:
10.1006/jcss.2000.1727.
[20] R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63
(4):512–530, 2001. doi: 10.1006/jcss.2001.1774.
[21] H. Jeong, Z. Néda, and A. L. Barabási. Measuring preferential attachment in evolving networks. Europhysics Letters, 61(4):567–572, 2003.
doi: 10.1209/epl/i2003-00166-9.
[22] F. Kammer. A linear-time kernelization for the rooted k-leaf outbranching problem. Discrete Applied Mathematics, 193:126–138, 2015. doi:
10.1016/j.dam.2015.04.028.
[23] D. R. Karger, P. Klein, C. Stein, M. Thorup, and N. E. Young. Rounding algorithms for a geometric embedding of Minimum Multiway Cut.
Mathematics of Operations Research, 29(3):436–461, 2004. doi: 10.1287/moor.1030.0086.
[24] T. Kloks. Treewidth. Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer, 1994.
[25] C. Komusiewicz and R. Niedermeier. New races in parameterized algorithmics. In Proceedings of the 37th International Symposium on
Mathematical Foundations of Computer Science (MFCS’12), volume 7464 of Lecture Notes in Computer Science, pages 19–30. Springer, 2012.
doi: 10.1007/978-3-642-32589-2 2.
[26] J. Leskovec, L. Backstrom, and J. Kleinberg. Meme-tracking and the dynamics of the news cycle. In Proceedings of the 15th ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining (KDD’09), pages 497–506. ACM, 2009. doi: 10.1145/1557019.1557077.
[27] S. Lohr. Study measures the chatter of the news cycle. New York Times, July 13th:B1, 2009. New York edition.
[28] R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006. doi: 10.1093/acprof:oso/9780198566076.001.0001.
[29] R. Niedermeier. Reflections on multivariate algorithmics and problem parameterization. In Proceedings of the 27th International Symposium
on Theoretical Aspects of Computer Science (STACS’10), volume 5 of LIPIcs, pages 17–32. Schloss Dagstuhl–Leibniz-Zentrum für Informatik,
2010. doi: 10.4230/LIPIcs.STACS.2010.2495.
[30] R. Niedermeier and P. Rossmanith. A general method to speed up fixed-parameter-tractable algorithms. Information Processing Letters, 73
(3-4):125–129, 2000. doi: 10.1016/S0020-0190(00)00004-1.
[31] D. D. S. Price. A general theory of bibliometric and other cumulative advantage processes. Journal of the American Society for Information
Science, 27(5):292–306, 1976. doi: 10.1002/asi.4630270505.
[32] F. Protti, M. Dantas da Silva, and J. Szwarcfiter. Applying modular decomposition to parameterized cluster editing problems. Theory of
Computing Systems, 44(1):91–104, 2009. doi: 10.1007/s00224-007-9032-7.
[33] C. Suen, S. Huang, C. Eksombatchai, R. Sosic, and J. Leskovec. NIFTY: A system for large scale information flow tracking and clustering. In
Proceedings of the 22nd International Conference on World Wide Web (WWW’13), pages 1237–1248. IW3C2, 2013. doi: 10.1145/2488388.
2488496.
[34] M. Xiao. Simple and improved parameterized algorithms for multiterminal cuts. Theory of Computing Systems, 46(4):723–736, 2010. doi:
10.1007/s00224-009-9215-5.

33

