Plaintext
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2012
Hardness of Vertex Deletion
and Project Scheduling∗
Ola Svensson†
Received November 4, 2012; Revised May 4, 2013; Published September 26, 2013
Abstract: Assuming the Unique Games Conjecture, we show strong inapproximability
results for two natural vertex-deletion problems on directed graphs: for any integer k ≥ 2
and arbitrary small ε > 0, the Feedback Vertex Set problem and the DAG Vertex Deletion
problem are inapproximable within a factor k − ε even on graphs where the vertices can be
almost partitioned into k solutions. This gives a more structured and yet simpler UG-hardness
result for the Feedback Vertex Set problem than the previous hardness result (albeit using the
“It Ain’t Over Till It’s Over” Theorem).
In comparison with the classical Feedback Vertex Set problem, the DAG Vertex Deletion
problem has received little attention. Although we think it is a natural and interesting
problem, the main motivation for our inapproximability result stems from its relationship
with the classical Discrete Time–Cost Tradeoff Problem. More specifically, our results imply
that the deadline version is UG-hard to approximate within any constant. This explains the
difficulty in obtaining good approximation algorithms for that problem and further motivates
previous alternative approaches such as bicriteria approximations.
ACM Classification: F.1.3, G.1.6, G.2.2
AMS Classification: 68Q17, 68W25, 68Q25
Key words and phrases: inapproximability, graphs, scheduling, vertex-deletion problems
∗ An extended abstract of this paper appeared in the Proceedings of the 15th International Workshop on Approximation
Algorithms for Combinatorial Optimization Problems, 2012 [19].
† This research was supported by Grant228021-ECCSciEng of the European Research Council.
© 2013 Ola Svensson
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2013.v009a024
O LA S VENSSON
1 Introduction
Many interesting discrete optimization problems can be formulated as the problem of finding, in a given
(directed) graph, a large induced subgraph with a desired property. One of the most studied such problems
is the Feedback Vertex Set (FVS) problem where the property is acyclicity, i. e., given a directed graph
G = (V, E) we wish to delete the minimum number of vertices so that the resulting graph is acyclic.
Another example is the DAG Vertex Deletion (DVD) problem, where we are given an integer k and a
directed acyclic graph and we wish to delete the minimum number of vertices so that the resulting graph
has no path of length1 k.
The FVS problem and the related Feedback Arc Set problem (FAS) were shown to be NP-complete
already in Karp’s seminal paper [9] and there is a long history of approximation algorithms for these
problems. Leighton and Rao [13] first gave a O(log2 |V |)-approximation algorithm for FAS. Seymour [17]
gave an approximation guarantee of O(log |V | log log |V |) for FVS by showing that a certain linear
program approximates the value within a factor O(log |V | log log |V |). Seymour’s arguments were then
generalized by Even et al. [5] to obtain the best known approximation algorithms achieving a factor
O(log |V | log log |V |) for both problems on weighted graphs. For weighted instances, easy reductions
show that FVS and FAS are in fact equivalent in terms of approximability [5].
Motivated by certain VLSI design and communication problems, Paik et al. [15] considered the
DVD problem and showed it to be NP-complete on general graphs and polynomial time solvable on
series-parallel graphs. One can also see that DVD for a fixed k is a special case of the Vertex Cover
problem on k-uniform hypergraphs and has a fairly straightforward k-approximation algorithm.
In comparison to FVS, the DVD problem has received little attention. Our main motivation for
studying its approximability comes from its relationship (that we prove in Section 5) with the classical
deadline version of the project scheduling problem known as the Discrete Time–Cost Tradeoff problem
(DTCT). Informally (see Section 5 for a formal definition), this is the problem where we are given a
deadline and a project consisting of tasks related by precedence constraints, and the time it takes to
execute each task depends, via a given cost function, on how much we pay for it. The objective is to
minimize the cost of executing all the tasks in compliance with the precedence constraints so that they all
finish within the given deadline. Due to its obvious practical relevance, the problem has been studied in
various contexts over the last 50 years (see the paper [11] by Kelly and Walker for an early reference).
Fulkerson [6] and Kelley [10] obtained polynomial time algorithms if all cost functions are linear. In
contrast, the problem becomes NP-hard for arbitrary cost functions [3] and there is even no known
constant-factor approximation algorithm in the general case. However, better (approximation) algorithms
have been obtained for special cases. For example, Grigoriev and Woeginger [7] gave polynomial time
algorithms for special classes of precedence constraints and one of several algorithms by Skutella [18] is
a bicriteria approximation that, for any µ ∈ (0, 1), approximates DTCT within a factor 1/(1 − µ) if the
deadline is allowed to be violated by a factor 1/µ.
In summary, there are no known constant-factor approximation algorithms for FVS, DVD, and DTCT
although few strong inapproximability results are known. The best known NP-hardness of approximation
results follow from the fact that they are all as hard to approximate as Vertex Cover which is NP-hard to
1 For notational convenience, we shall measure the length of a path as the number of vertices it contains instead of the number
of edges.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 760
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
approximate within a factor 1.3606 [4]. It is indeed easy to see that Vertex Cover is a special case of FVS
and DVD, and Grigoriev and Woeginger [7] gave an approximation-preserving reduction from Vertex
Cover to DTCT. If we assume the Unique Games Conjecture (UGC) [12], our understanding of the
approximability of FVS becomes significantly better: the hardness of approximation result for Maximum
Acyclic Subgraph by Guruswami et al. [8] implies that it is NP-hard to approximate FVS within any
constant factor assuming the UGC. However, the results in [8] use very sophisticated techniques that are
not known to imply a similar hardness for DVD and DTCT. Specifically, the techniques in [8] are inspired
by Raghavendra’s [16] beautiful results on constraint-satisfaction problems that relate UG-hardness
results to the integrality gap of a canonical semidefinite programming relaxation. To apply a similar
framework, the authors of [8] treat ordering problems as n-ary constraint-satisfaction problems, show
that one can restrict the domain to a large constant, and make a similar connection between integrality
gaps of a semidefinite programming relaxation and UG-hardness. The framework developed in [8] is
very powerful and leads to optimal UG-hardness results for all so-called ordering-constraint satisfaction
problems. However, the hardness reductions obtained from integrality gaps in this way are not explicit
in the sense that it is difficult to grasp if the instances obtained have any particular structure that can be
useful for obtaining hardness results for other problems, such as DTCT and DVD.
Even though the initial motivation of this work was to better understand the approximability of DTCT
(and DVD), the techniques that we develop also lead to a more structured UGC-based hardness result for
FVS: similar to the recent results for Vertex Cover on k-uniform hypergraphs by Bansal and Khot [1, 2],
we show that, for any integer k ≥ 2 and arbitrarily small ε > 0, there is no (k −ε)-approximation algorithm
for FVS even on graphs where the vertices can be almost partitioned into k feedback vertex sets. Our
reduction is also much simpler and more “direct” than the one in [8] (albeit using the “It Ain’t Over
Till It’s Over” Theorem) but is tailored to FVS and does not yield any inapproximability result for the
Maximum Acyclic Subgraph problem. As already noted, feedback vertex set and feedback arc set are
equivalent for weighted instances [5] and therefore a non-constant UG-hardness result for weighted
feedback arc set also follows from our results. (The hardness result in [8] is also for weighted instances.)
More importantly, our techniques also lead to an analogous result for the DVD problem (and thereby for
DTCT). Formally, our results for the vertex-deletion problems considered can be stated as follows.
Theorem 1.1. For any integer k ≥ 2 and arbitrary constant ε > 0, the following problems are UG-hard:
FVS: Given a graph G(V, E), distinguish between the following cases:
• (Completeness): there exist k disjoint subsets V1 , . . . ,Vk ⊂ V satisfying |Vi | ≥ 1−ε
k |V | and such
that a subgraph induced by any k − 1 of these subsets is acyclic.
• (Soundness): every induced subgraph of ε|V | vertices has a directed cycle.
DVD: Given a DAG G(V, E), distinguish between the following cases:
• (Completeness): there exist k disjoint subsets V1 , . . . ,Vk ⊂ V satisfying |Vi | ≥ 1−ε
k |V | and such
that a subgraph induced by any k − 1 of these subsets has no path of length k.
• (Soundness): every induced subgraph of ε|V | vertices has a path of length |V |1−ε .
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 761
O LA S VENSSON
Note that completeness says that if we let V 0 = V \ (V1 ∪ · · · ∪Vk ) then the sets V 0 ∪Vi for i = 1, . . . , k
are almost disjoint solutions of size at most (1/k + ε)|V | each. In contrast, soundness says that any
solution basically needs to delete all vertices (even to avoid paths of length |V |1−ε for DVD).
When proving UGC-based inapproximability results, the main task is usually to design “gadgets” for
the problems considered that simulate a so-called dictatorship test. Once we have such “dictatorship
gadgets,” the process of obtaining UGC-based hardness results often follows from (by now) fairly standard
arguments. In particular, the main ideas needed for our reductions leading to Theorem 1.1 are already
present in the design of the gadgets. We have therefore chosen to present those gadget constructions with
less cumbersome notation in Section 3 and the reductions from Unique Games can be found in Section 4.
As alluded to above, our main interest in DVD stems from its relationship with DTCT. More
specifically, in Section 5, we give an approximation-preserving reduction from DVD to DTCT that
combined with Theorem 1.1 yields:
Theorem 1.2. It is UG-hard to approximate DTCT within any constant factor.
This explains the difficulty in obtaining good approximation algorithms for DTCT and also further
motivates alternative approaches such as the bicriteria approach by Skutella [18] that approximates the
DTCT within a constant factor if the deadline is allowed to be violated by a constant factor.
2 Preliminaries
2.1 Low-degree influence and “It Ain’t Over Till It’s Over” Theorem
Let [k] = {0, 1, . . . , k − 1}. When analyzing our hardness reductions, we shall use known properties
regarding the behavior of functions of the form f : [k]R → {0, 1} depending on whether they have
influential coordinates. Similar to [14, Section 3], we define the influence of the i-th coordinate by
Infli ( f ) = Ex [Varxi ( f (x))] .
We note that if f : {−1, 1}R → {−1, 1} then this definition coincides with the intuitive expression
Pr[ f (x1 , . . . , xi , . . . , xR ) 6= f (x1 , . . . , −xi , . . . , xR )] .
x
It is well known that if we let f = ∑Φ fˆ(φ )Xφ be the multi-linear representation of f (where, in
analogy with the standard Fourier representation, the characters (Xφ )φ ∈[k]R define an orthonormal basis of
the vector space of all functions [k]n → R) then the influence can also be expressed as
Infli ( f ) = ∑ fˆ2 (φ ) ,
φ :φi 6=0
which motivates the following definition of the degree-d influence of the i-th coordinate:
Infldi ( f ) = ∑ fˆ2 (φ ) .
φ :φi 6=0,|φ |≤d
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 762
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
As we shall not work directly with these definitions or with the multi-linear representation, we refer
the reader to [14] for the precise definitions and cut the discussion short by mentioning the property
of low-degree influence that will be crucial to us. This property follows from the fact that ∑φ fˆ2 (φ ) =
Ex [ f (x)2 ] ≤ 1.
Observation 2.1 (see, e. g., Proposition 3.8 in [14]). For a boolean function f : [k]R → {0, 1}, the sum of
all degree-d influences is at most d.
We shall now introduce a simplified version of the “It Ain’t Over Till It’s Over” Theorem that is
sufficient for the applications in this paper. The first proof was given by Mossel et al. [14, Theorem 4.9]
and a more combinatorial proof of a simplified version (very similar to the one used here) was given by
Bansal and Khot [1, Theorem 3.1] who used it to prove tight inapproximability results for Vertex Cover
and a classical single-machine scheduling problem. In fact many of our ideas are inspired by [1]. For
x ∈ [k]R and a subset Sε ⊆ R of εR indices, let
Cx,Sε = {z ∈ [k]R : z j = x j ∀ j 6∈ Sε }
denote the sub-cube defined by fixing the coordinates not in Sε according to x. Let also f (Cx,S ) ≡ 0
denote the expression that f is identical to 0 on the sub-cube Cx,Sε .
Theorem 2.2 (special case of Theorem 4.9 in [14]). For every ε, δ > 0 and integer k, there exists η > 0
and integer d such that any f : [k]R → {0, 1} that satisfies
E[ f ] ≥ δ and ∀i ∈ [R], Infldi ( f ) ≤ η ,
has
Pr [ f (Cx,Sε ) ≡ 0] ≤ δ .
x,Sε
Here and throughout the paper, the probability over x, Sε is such that x and Sε are taken independently
uniformly at random. When ε is clear from the context we often also abbreviate Sε by S. We remark
that, as the above statement only considers whether a function is identical to 0 on a chosen sub-cube, the
randomly picked set Sε can be interpreted as a truncated version of the operator V in [14] that picks the
set by including each vertex independently with probability ε 0 (by selecting ε 0 ε sufficiently small only
an insignificant fraction of the outcomes will be disregarded). This slight change is not necessary but it
will simplify the explanation of the reductions in this paper.
The theorem says that a reasonably balanced function with no low-degree influential coordinates has
very low probability to be identical to 0 over the random choice of sub-cubes. In contrast, it is easy to see
that a dictatorship function (on the boolean domain) f (x) = xs , for some s, has
Pr [ f (Cx,Sε ) ≡ 0] = Pr [ f (Cx,Sε ) ≡ 1] ≥ 1/2 − ε .
x,Sε x,Sε
It is this drastic difference that we will exploit in our hardness reductions.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 763
O LA S VENSSON
2.2 Unique Games Conjecture
An instance of Unique Games L = (G(V,W, E), [R], {πv,w }(v,w) ) consists of a regular bipartite graph
G(V,W, E) and a set [R] of labels. For each edge (v, w) ∈ E there is a constraint specified by a
permutation πv,w : [R] → [R]. The goal is to find a labeling ρ : (V ∪ W ) → [R] so as to maximize
val(ρ) := Pre∈E [ρ satisfies e], where a labeling ρ is said to satisfy an edge e = (v, w) if ρ(v) = πv,w (ρ(w)).
For a Unique Games instance L, we let
OPT(L) = max val(ρ) .
ρ:V ∪W →[R]
The now famous Unique Games Conjecture that has been extensively used to prove strong hardness of
approximation results can be stated as follows.
Conjecture 2.3 ([12]). For any constants ζ , γ > 0, there is a sufficiently large integer R = R(ζ , γ) such
that, for Unique Games instances L with label set [R] it is NP-hard to distinguish between:
• (Completeness): OPT(L) ≥ 1 − ζ .
• (Soundness): OPT(L) ≤ γ.
3 Dictatorship gadgets for vertex-deletion problems
We give simple gadgets for the vertex-deletion problems considered that informally correspond to a
dictatorship test in the following sense: (Completeness:) any dictatorship function f : [k]R → [k] (defined
by f (x) = xs for some s ∈ [R]) corresponds to a good solution whereas (Soundness:) any non-trivial
solution corresponds to a function f : [k]R → {0, 1} with a high-influence coordinate. These gadgets are
then used in Section 4 together with a more general form of the “It Ain t Over Till It’s Over” Theorem (see
Theorem 4.1) to obtain analogous hardness results assuming the Unique Games Conjecture. Specifically,
Theorem 4.1 generalizes Theorem 2.2 in the sense that it tests whether at least two of a given set of
functions have a common coordinate with high influence instead of only verifying if a single function
has a high-influence coordinate. This generalization will allow us to check consistency of labels in the
Unique Games instance in a fairly standard way. Apart from this difference, the reductions in Section 4
are similar to the gadget constructions. However, as Section 4 has a more cumbersome notation, we
believe that the gadget constructions here present the underlying ideas more clearly.
Throughout this section, we fix k to be an integer, ε, δ > 0 to be arbitrarily small constants, and let η
and d be as in Theorem 2.2 (depending on k, ε and δ ).
3.1 Feedback Vertex Set
Here we shall describe a graph G = (V, E) that naturally corresponds to a dictatorship test in the following
sense:
• (Completeness:) A dictatorship function partitions the vertex set into subsets V 0 ,V0 , . . . ,Vk−1
satisfying V j ≥ 1−ε 0 0
k |V |, |V | ≤ ε|V |, and for j ∈ [k] the graph obtained by deleting V ∪V j is acyclic.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 764
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
• (Soundness:) Any feedback vertex set that deletes less than (1 − 2δ )|V | vertices corresponds to a
function f : [k]R → {0, 1} with a coordinate i so that Infldi ( f ) > η.
3.1.1 Dictatorship gadget
To make the analysis more intuitive, it will be convenient to first present a gadget that consists of two types
of vertices that we refer to as bit-vertices and test-vertices and all arcs are between bit- and test-vertices:
• There is a bit-vertex bx of weight ∞ for every x ∈ [k]R .
• There is a test-vertex tx,S of weight 1 for every x ∈ [k]R and every subset S ⊆ [R] of εR indices.
• The arcs incident to a test-vertex tx,S are the following. There is an arc (bz ,tx,S ) if z ∈ Cx,S and an
⊕
arc (tx,S , bz ) if z ∈ Cx,S , where
⊕
Cx,S = {z ⊕ 1 : z ∈ Cx,S }
(here ⊕ denotes coordinatewise-addition mod k and 1 is the all-ones vector of appropriate dimen-
sion).
As the bit-vertices have weight ∞, they will never be deleted in an optimal solution. We can therefore
obtain an unweighted graph G of the same optimal value by omitting the bit-vertices and having an arc
(tx,S ,tx0 ,S0 ) between two test vertices if there exists a bit-vertex bz so that (tx,S , bz ) and (bz ,tx0 ,S0 ). The
vertex set of G will therefore correspond to the set T of test-vertices. The analysis of G therefore
follows from proving that (completeness:) any dictatorship function partitions the test-vertices as required
(Section 3.1.2) and (soundness:) that any solution that deletes less than a (1 − 2δ ) fraction of the
test-vertices corresponds to a function with a coordinate of high influence (Section 3.1.3).
3.1.2 Completeness
We show that a dictatorship function f : [k]R → [k] of index s, i. e., f (x) = xs , naturally partitions the
test-vertices into subsets T 0 , T0 , . . . , Tk−1 satisfying |T j | ≥ ((1 − ε)/k)|T |, |T 0 | ≤ ε|T |, and such that the
sets T 0 ∪ T j for j ∈ [k] are almost disjoint feedback vertex sets of size at most (1/k + ε)|T | each.
As f (x) = xs , it partitions the bit-vertices in k equal sized sets
B j = {bx : f (x) = j} for j ∈ [k] .
We say that a test-vertex tx,S is good if s 6∈ S and partition the good test-vertices into k equal sized sets
T j = {tx,S : s 6∈ S and f (x) = j} for j ∈ [k] .
The sets are of equal size since they are partitioned according to x and whether a test-vertex is good
only depends on S. Furthermore, as at least a (1 − ε) fraction of the test-vertices are good we have that
|T j | ≥ ((1 − ε)/k)|T | for j ∈ [k] and therefore the remaining test-vertices in T 0 are at most ε|T | many.
It remains to show that T j ∪ T 0 defines a feedback vertex set for any j ∈ [k]. The key observation
is that T j only have incoming edges from bit-vertices in B j and outgoing edges to bit-vertices in B j⊕1 .
Indeed, consider a test-vertex tx,S ∈ T j and an arc (bz ,tx,S ). By definition we have that z ∈ Cx,S and as S is
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 765
O LA S VENSSON
B0 T0 B1 Tk−1
T0
Figure 1: The structure of the graph after partitioning the vertices according to a dictatorship function.
They gray and black vertices depict test-vertices and bit-vertices, respectively.
good we have that f (z) = f (x) = j, which shows that z ∈ B j . We infer that tx,S only has outgoing edges
to B j⊕1 by the exact same argument.
By the above arguments we have that, in the graph without bad test-vertices, any cycle must visit
at least one vertex in each of the sets T0 , T1 , . . . , Tk−1 (see also Figure 1). This is because all outgoing
edges from a test-vertex in T j go to bit-vertices in B j⊕1 and these bit-vertices have only outgoing edges to
test-vertices in T j⊕1 and so on. Therefore, the graph obtained by deleting all bad test-vertices and one of
the sets T0 , T1 , . . . , Tk−1 is acyclic as required.
3.1.3 Soundness
Let A be the last 1/2 fraction of the bit-vertices according to a topological sort of the graph. Let fA be
the indicator function of A. Note that a test-vertex tx,S has incoming arcs from all bit-vertices in Cx,S and
⊕
outgoing arcs to all bit-vertices in Cx,S . Therefore, if a test-vertex tx,S is not deleted then we must have
that either fA is identical to 0 on Cx,S (if tx,S is placed before the last bit-vertex for which fA evaluates to
⊕
0) or identical to 1 on Cx,S (if tx,S is placed after the last bit-vertex for which fA evaluates to 0) depending
on where tx,S is placed according to the topological sort.
As E[ fA ] = 1/2, we have by Theorem 2.2 that if Infldi ( fA ) ≤ η for all i ∈ [R] then
Pr[ f (Cx,S ) ≡ 0] ≤ δ
x,S
and
⊕
Pr[ f (Cx,S ) ≡ 1] = Pr[ f (Cx,S ) ≡ 1] = Pr[(1 − f )(Cx,S ) ≡ 0] ≤ δ .
x,S x,S x,S
Therefore, if the solution does not correspond to a function with a coordinate of high low-degree
influence it must have deleted at least a (1 − 2δ ) fraction of the test-vertices.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 766
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
3.2 DAG Vertex Deletion problem
We shall describe a directed acyclic graph (DAG) G = (V, E) that naturally corresponds to dictatorship
test in the following sense:
• (Completeness:) A dictatorship function partitions the vertex set into subsets V 0 ,V0 , . . . ,Vk−1
satisfying V j ≥ 1−ε 0 0
k |V |, |V | ≤ ε|V |, and such that for j ∈ [k] the graph obtained by deleting V ∪V j
has no path of length k.
• (Soundness:) Any graph obtained by deleting less than (1 − 6δ )|V | vertices either has a path
of length |V |1−δ or corresponds to a function f : [k]R → {0, 1} with a coordinate i such that
Infldi ( f ) > η.
3.2.1 Dictatorship gadget
As in Section 3.1, it will be convenient to first present a gadget that consists of two types of vertices that
we refer to as bit-vertices and test-vertices, and all edges will be between bit- and test-vertices:
• The bit-vertices are partitioned into L +1 bit-layers (L is selected below). Each bit-layer ` = 0, . . . , L
contains a bit-vertex b`x of weight ∞ for every x ∈ [k]R .
• Similarly, the test-vertices are partitioned into L test-layers. Each test-layer ` = 0, . . . , L − 1 has a
` of weight 1 for every x ∈ [k]R and every subset S ⊆ [R] of εR indices.
test-vertex tx,S
0 0
• The arcs are the following: there is an arc (b`z ,tx,S
` ) if ` ≤ `0 and z ∈ C , and there is an arc (t ` , b` )
x,S x,S z
0 ⊕
if ` > ` and z ∈ Cx,S .
• Finally, L is selected so as δ L ≥ |T |1−δ , where T is the set of test-vertices.
Note that, as there are only arcs from a bit-layer ` to a test-layer `0 if `0 ≥ ` and only arcs from a
test-layer `0 to a bit-layer ` if ` > `0 , the constructed graph is acyclic. Similar to the gadget for FVS, the
bit-vertices can be omitted to obtain an unweighted graph G (with the set T of test-vertices as vertices)
with the same optimal value by having an arc between two test-vertices if there was a path between
them through one bit-vertex. Note that a path in G of length k is a path in the gadget that consists of k
test-vertices. When arguing about the gadget, we will therefore say that a path has length k if it consists
of k test-vertices.
Similarly to Section 3.1, the analysis of G follows from proving that (completeness:) any dictatorship
function partitions the test-vertices as required (Section 3.1.2) and (soundness:) that any solution that
deletes less than a (1 − 6δ ) fraction of the test-vertices either has a path of length |T |1−δ or corresponds
to a function with a coordinate of high influence (Section 3.1.3).
3.2.2 Completeness
We show that a dictatorship function f : [k]R → [k] of index s naturally partitions the test-vertices into
subsets T 0 , T0 , . . . , Tk−1 satisfying T j ≥ ((1 − ε)/k)|T |, |T 0 | ≤ ε|T |, and such that for j ∈ [k] the graph
obtained by deleting T 0 ∪ T j has no path of length k.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 767
O LA S VENSSON
This can be seen by the same arguments as in Section 3.1.2. Indeed if we “collapse” the different
layers by identifying the different copies of bit- and test-vertices then the gadget constructed here is
identical to the gadget in that section. We can therefore (by the arguments of Section 3.1.2), partition
the bit-vertices into k equal sized sets B0 , B1 , . . . , Bk−1 and all but an ε fraction of the test-vertices into k
equal sized sets T0 , T1 , . . . , Tk−1 so that any test-vertex in T j has only incoming arcs from bit-vertices in
B j and outgoing arcs to bit-vertices in B j⊕1 .
Any j ∈ [k] therefore corresponds to a solution by removing an ε fraction of the test-vertices (i. e., the
set T 0 ) and those test-vertices in T j .
3.2.3 Soundness
Before proceeding to the analysis it will be convenient to consider a different but equivalent formulation
of the problem.
First, note that in any solution to DVD, i. e., a subgraph so that each path contains less than k
test-vertices, we can find a coloring χ (using for example depth-first search) that assigns a color in
{1, 2, . . . , k} to the bit-vertices with the property that, for each remaining test-vertex, the maximum color
assigned to its predecessors is strictly less than the minimum color assigned to its successors. Similarly,
any such coloring χ can be turned into a solution to DVD by deleting those test-vertices for which not all
predecessors are assigned lower colors than all its successors. Furthermore, from the construction of the
0
arcs, we can assume without loss of generality that the coloring satisfies χ(b`x ) ≤ χ(b`x ) if ` ≤ `0 .
From the above discussion, the following equivalent formulation of DVD on the instances constructed
can be obtained: find a coloring χ that assigns a color in {1, 2, . . . , k} to each bit-vertex satisfying
0
χ(b`x ) ≤ χ(b`x ) if ` ≤ `0 so as to minimize the number of unsatisfied test-vertices where a test-vertex tx,S
`
is said to be satisfied if
max χ(b`z ) < min ⊕
χ(b`+1
z ),
z∈Cx,S z∈Cx,S
that is, all its predecessors are assigned lower colors than any of its successors.
It will also be convenient to consider the following lower bound on the colors assigned to most
bit-vertices in each layer: define the color χ(`) of a bit-layer ` = 0, 1, . . . , L as the maximum color that
satisfies Prx [χ(b`x ) ≥ χ(`)] ≥ 1 − δ .
Now, with each test-layer ` = 0, 1, . . . , L − 1 we associate the indicator function f ` : [k]R → {0, 1}
defined as follows (
0 if χ(b`+1
x ) > χ(`),
f ` (x) =
1 otherwise.
The key observation for the soundness analysis is the following.
Claim 3.1. For ` = 0, . . . , L − 1, assuming that Infldi ( f ` ) ≤ η for all i ∈ [R]: if a 3δ fraction of the
test-vertices of test-layer ` are satisfied, then χ(`) < χ(` + 1).
Proof. As at least a 3δ fraction of the test-vertices of test-layer ` are satisfied,
" #
Pr max χ(b`z ) < min
⊕
χ(b`+1
z ) ≥ 3δ .
x,S z∈Cx,S z∈Cx,S
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 768
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
By the definition of χ(`) we have Prx [χ(b`x ) ≥ χ(`)] ≥ 1 − δ and therefore
" #
h i
`+1 `
Pr χ(`) < min ⊕
χ(b z ) = Pr f (Cx,S ) ≡ 0 ≥ 2δ .
x,S z∈Cx,S x,S
As Infldi ( f ` ) ≤ η for all i ∈ [R], we conclude by using Theorem 2.2 that E[ f ` ] < δ and hence χ(` + 1) >
χ(`).
If a coloring satisfies more than a 6δ fraction of the test-vertices then at least a 3δ fraction of the
test-layers are such that at least a 3δ fraction of the test-vertices of that layer are satisfied, which in turn
by the preceding claim implies that either one of them corresponds to a function with a coordinate of
high influence or 3δ L many colors are needed (or equivalently the graph contains a path consisting of at
least 3δ L − 1 ≥ δ L ≥ |T |1−δ test-vertices).
4 Hardness assuming the Unique Games Conjecture
In order to turn our dictatorship gadgets into hardness proofs (assuming the Unique Games Conjecture),
we need a more general “It Ain’t Over Till It’s Over” Theorem that not only verifies that a given number
of functions all are dictatorships but ideally they should also be dictators of the same coordinate. Again
an even more general variant of the theorem follows from [14, Theorem 4.9] and an easier proof of a very
similar version to the case presented here can be found in [1, Theorem 3.4].
Theorem 4.1 (special case of Theorem 4.9 in [14]2 ). For every ε, δ > 0 and integer k, there exist η > 0
and integers t, d such that any collection of functions f1 , . . . , ft : [k]R → {0, 1} that satisfies
n o
∀ j, E[ f j ] ≥ δ and ∀i ∈ [R], ∀1 ≤ `1 6= `2 ≤ t, min Infldi ( f`1 ), Infldi ( f`2 ) ≤ η ,
has " #
t
^
Pr ( f j (Cx,Sε ) ≡ 0) ≤ δ .
x,Sε
j=1
For the applications of the above Vtheorem that appear
in this paper, the interesting conclusion can
t
be reformulated as follows: if Prx,Sε j=1 f j (Cx,Sε ) ≡ 0 > δ for t fairly balanced functions then at least
two of them must have a common influential coordinate.
In our (soundness) analyses, we associate a boolean function fw : [k]R → {0, 1} with each w ∈ W
of the considered Unique Games instance. Let N(v) denote the set of neighbors of a vertex v. We then
2 To see that Theorem 4.1 is a special case of Theorem 4.9 in [14], consider the function g : [k]R → [0, 1] that outputs
the average of the functions f1 , f2 , . . . , ft , i. e., g(x) = (1/t) ∑t`=1 f` (x). If the functions f1 , f2 . . . , ft satisfy the premises then
E[g] ≥ δ and g has no coordinate of high low-degree influence because Infldi (g) ≤ (1/t)Infldi ( f ) and t is selected to be sufficiently
large. Theorem 4.9 says that the probability that such a g is identical to 0 on a randomly chosen sub-cube is very small which is
equivalent to our conclusion
t
^
Pr f j (Cx,Sε ) ≡ 0 ≤ δ .
x,Sε
j=1
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 769
O LA S VENSSON
use the preceding theorem to test whether t (or more) neighbors w1 , . . . wt ∈ N(v) of a vertex v ∈ V
are “close to” consistent, i. e., fw1 , . . . , fwt are dictatorships on coordinates ρ(w1 ), . . . , ρ(wt ) such that
πv,w1 (ρ(w1 )) = πv,w2 (ρ(w2 )) = · · · = πv,wt (ρ(wt )). Indeed, if we let
fw j ◦ πv,w j (x) = fw j (xπv,w j (1) , xπv,w j (2) , . . . , xπv,w j (R) )
denote the function whose coordinates have been permuted according to πv,w j then on the one hand,
" #
t
^
Pr fw j ◦ πv,w j (Cx,Sε ) ≡ 0 ≥ 1/2 − ε if they are consistent ,
x,Sε
j=1
and on the other hand (assuming fw1 , . . . , fwt are fairly balanced) if no two of them are “close to” consistent
then Theorem 4.1 implies that
" #
^ t
Pr fw j ◦ πv,w j (Cx,Sε ) ≡ 0 ≤ δ .
x,Sε
j=1
Similar to the gadget reductions, it is this drastic difference that we exploit to obtain our hardness results.
For the reductions, it shall be convenient to let Cx,S,v,w denote the sub-cube
Cx,S,v,w = {z : z j = xπv,w ( j) ∀ j : πv,w ( j) 6∈ S} ,
i. e., the image of the sub-cube Cx,S via πv,w . Note that with this notation we have that
" # " #
t
^ t
^
Pr fw j ◦ πv,w j (Cx,S ) ≡ 0 = Pr fw j (Cx,S,v,w j ) ≡ 0 .
x,S x,S
j=1 j=1
We now present the adaptations of the dictatorship gadgets for FVS and DVDP to obtain reductions
from Unique Games in Sections 4.1 and 4.2, respectively. Throughout this section (as in Section 3), we
fix k to be an integer, ε, δ > 0 to be arbitrarily small constants and let η, d, and t be as in Theorem 4.1
(depending on k, ε and δ ).
4.1 Feedback Vertex Set
We prove the following theorem from which the hardness of FVS stated in Theorem 1.1 clearly follows.
Theorem 4.2. Assuming the Unique Games Conjecture, for any integer k ≥ 2 and arbitrary constants
ε, δ > 0, given a directed graph G(V, E), distinguishing between the following cases is NP-hard:
• (Completeness): there exist disjoint subsets V1 , . . . ,Vk ⊂ V satisfying |Vi | ≥ 1−2ε
k |V | and such that
a subgraph induced by all but one of these subsets is acyclic.
• (Soundness): every induced subgraph of 8δ |V | vertices contains a cycle.
We first present the reduction in the following subsection followed by the completeness (Lemma 4.3)
and soundness (Lemma 4.4) analyses.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 770
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
4.1.1 Reduction
We describe a reduction from Unique Games to FVS. Let L(G(V,W, E), [R], {πv,w }(v,w)∈E ) be a Unique
Games instance. As in Section 3.1, the FVS instance consists of two types of vertices that we refer to as
bit-vertices and test-vertices and all edges are between bit- and test-vertices.
• For every w ∈ W and x ∈ [k]R , there is a bit-vertex bw,x of weight ∞.
In other words, each w ∈ W is replaced by a k-ary hypercube [k]R where each vertex has weight ∞
so that none of them will ever be deleted in an optimal solution.
• For every x ∈ [k]R , S ⊆ [R] of εR indices, v ∈ V, and (w1 , w2 . . . , w2t ) ∈ N(v)2t , we have a test vertex
tx,S,v,w1 ,...,w2t .
• The arcs incident to a test-vertex tx,S,v,w1 ,...,w2t are the following. For j = 1, . . . , 2t,
– there is an arc (bw j ,z ,tv,x,S,w1 ,...,w2t ) if z ∈ Cx,S,v,w j ,
⊕
– and an arc (tv,x,S,w1 ,...,w2t , bw j ,z ) if z ∈ Cx,S,v,w j
= {z ⊕ 1 : z ∈ Cx,S,v,w j }.
As the bit-vertices have weight ∞, they are never deleted in an optimal solution and we can obtain an
unweighted graph G (with the set T of test-vertices as vertices) with the same optimal value by having
an arc between two test-vertices if there is a path between them through one bit-vertex. Theorem 4.2
therefore follows from that (i) in the proof of completeness, we can partition the test-vertices as required
(Lemma 4.3) and (ii) in the proof of soundness, any solution deletes almost all test-vertices (Lemma 4.4).
4.1.2 Completeness
We prove the following.
Lemma 4.3. If there is a labeling ρ of the Unique Games instance L satisfying a (1 − ζ ) fraction of the
constraints then we can partition the test-vertices into subsets T 0 , T0 , . . . , Tk satisfying
1 − 2ε
|T j | ≥ |T |, |T 0 | ≤ 2ε|T | ,
k
and for j ∈ [k] the graph obtained by deleting T 0 ∪ T j is acyclic.
Proof. Let ρ be such a labeling of the Unique Games instance. We now use ρ to partition the bit-vertices
in k equal sized sets:
B j = {bw,x : w ∈ W and xρ(w) = j} for j ∈ [k] .
We say that a test-vertex tx,S,v,w1 ,...,w2t is good if (i) ρ(v) 6∈ S and (ii) ρ satisfies all the edges
(v, w1 ), (v, w2 ), . . . , (v, w2t ). Note that property (i) holds with probability at least 1 − ε and property
(ii) holds with probability at least 1 − 2ζ t. Therefore, at least a (1 − 2ε) fraction (for ζ small enough) of
the test-vertices are good. As we did for the bit-vertices, we partition the test-vertices into k equal sized
sets:
T j = {tx,S,v,w1 ,...,w2t : tx,S,v,w1 ,...,w2t is good and xρ(v) = j} for j ∈ [k] .
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 771
O LA S VENSSON
The sets are of equal size since they are partitioned according to x and whether a test-vertex is good only
depends on S and v, w1 , . . . , w2t . Furthermore, since at least (1 − 2ε)|T | test-vertices are good we have
that
1 − 2ε
|T j | ≥ |T |
k
for j ∈ [k] and the remaining test-vertices in T 0 are therefore at most 2ε|T | many.
It remains to show that T j ∪ T 0 defines a feedback vertex set for any j ∈ [k]. The key observation is
that T j only has incoming arcs from bit-vertices in B j and outgoing arcs to bit-vertices in B j⊕1 . To see
this, consider a test-vertex tx,S,v,w1 ,...,w2t in T j and let (bwi ,z ,tx,S,v,w1 ,...,w2t ) be an arc. Then, by definition we
have that z ∈ Cx,S,v,wi . As πv,wi (ρ(wi )) = ρ(v) 6∈ S,
zρ(wi ) = xπv,wi (ρ(wi )) = xρ(v) = j ,
and hence bwi ,z ∈ B j . The exact same argument also shows that all outgoing arcs from tx,S,v,w1 ,...,w2t go
to bit-vertices in B j⊕1 . We can therefore conclude that test-vertices in T j have only incoming arcs from
bit-vertices in B j and outgoing arcs to bit-vertices in B j⊕1 .
By the key observation, we can obtain an acyclic graph by deleting all bad test-vertices and one of the
sets T0 , . . . , Tk−1 which proves the lemma.
4.1.3 Soundness
As we can choose the soundness parameter γ of the Unique Games Conjecture to be arbitrarily small, the
following lemma says that in the proof of soundness, there is no feedback vertex set containing less than
a (1 − 8δ ) fraction of the test-vertices (or equivalently, any induced subgraph containing an 8δ fraction
of the test-vertices contains a cycle).
Lemma 4.4. If the graph has a FVS containing less than a (1 − 8δ ) fraction of the test-vertices, then the
Unique Games instance has a labeling that satisfies at least a δ η 2 /(t 2 k2 ) fraction of the constraints.
Proof. Consider a topological sort σ of the graph obtained by deleting a FVS and assume that it contains
at least an 8δ fraction of the test-vertices, i. e., if we let T be the set of remaining test-vertices then
Pr [tx,S,v,w1 ,...,w2t ∈ T ] ≥ 8δ .
x,S,v,w1 ,...,w2t
We shall show that it follows that there is a labeling of L that satisfies at least a δ η 2 /(t 2 k2 ) fraction of
the constraints.
With each w ∈ W , we associate the indicator function fw : [k]R → {0, 1} that takes value 0 for the first
half of the bit-vertices corresponding to w (according to σ ) and value 1 for the remaining half. We then
define the set L[w] of candidate labels for every w ∈ W as:
L[w] := {i ∈ [R] : Infldi ( fw ) ≥ η} .
By Observation 2.1, we have |L[w]| ≤ d/η.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 772
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
Now, for every w ∈ W , we define ρ(w) to be a random label from L[w] (if L[w] is empty we assign
any label to w) and, for every v ∈ V we pick a random neighbor w ∈ N(v) and define ρ(v) = πv,w (ρ(w)).
We shall now calculate a lower bound on the expected number of edges the labeling ρ satisfies.
We call a tuple (v, w1 , . . . , w2t ) good if
Pr[tx,S,v,w1 ,...,w2t ∈ T ] ≥ 4δ .
x,S
Since T contains an 8δ fraction of the test-vertices we have that at least a 4δ fraction of the tuples are
good. Consider such a good tuple (v, w1 , . . . , w2t ) and let Tv,w1 ...,w2t = {tx,S,v,...,w2t ∈ T }. Suppose without
loss of generality that
max σ (bwi ,x ) < max σ (bwi+1 ,x ) for i = 1, 2, . . . , 2t − 1 .
fwi (x)=0 fwi+1 (x)=0
Then if a test-vertex tx,S,v,w1 ,...,w2t is in Tv,w1 ,...,w2t then we conclude by the arcs incident to the test-vertex
that
fwt+1 (Cx,S,v,wt+1 ) ≡ · · · ≡ fw2t (Cx,S,v,w2t ) ≡ 0 if σ (tx,S,v,w1 ...,w2t ) ≤ maxx: f (x)=0 σ (bwt ,x ) ,
wt
f (C⊕ ⊕
w1 x,S,v,w1 ) ≡ · · · = f wt (Cx,S,v,wt ) ≡ 1 otherwise, i. e., σ (tx,S,v,w1 ...,w2t ) > maxx: fwt (x)=0 σ (bwt ,x ) .
Therefore, one of these conditions must be satisfied by at least half of the test-vertices in Tx,S,v,w1 ,...,w2t ,
i. e., either " #
2t
^
Pr fw j (Cx,S,v,w j ) ≡ 0 ≥ 2δ
x,S
j=t+1
or " # " #
t t
⊕
^ ^
Pr fw j (Cx,S,v,w j
)≡1 = Pr (1 − fw j )(Cx,S,v,w j ) ≡ 1 ≥ 2δ .
x,S x,S
j=1 j=1
In either case, Theorem 4.1 gives that there exist j ∈ L[w`1 ] and j0 ∈ L[w`2 ] for some 1 ≤ `1 6= `2 ≤ 2t
such that πv,w`1 ( j) = πv,w`2 ( j0 ).
We now follow the same argumentations as used in [1]. Overall, if we pick the tuple (v, w1 , w2 , . . . , w2t )
at random and then w, w0 at random from the set {w1 , . . . , w2t }, then with probability at least 4δ the tuple
is good, with probability 1/(4t 2 ) we have w = w`1 and w0 = w`2 , and with probability 1/(k2 /η 2 ), the
labeling procedure defines j = ρ(w), j0 = ρ(w0 ). Hence
4δ η 2
Pr 0 [πv,w (ρ(w)) = πv,w0 (ρ(w0 ))] ≥ ,
v,w,w 4t 2 k2
and (expected over the randomness of the labeling procedure)
δ η2
Pr [ρ(v) = πv,w (ρ(w))] ≥ .
(v,w) t 2 k2
This shows that there exists a ρ that satisfies a δ η 2 /(t 2 k2 ) fraction of the constraints.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 773
O LA S VENSSON
4.2 DAG Vertex Deletion Problem
We prove the following theorem from which the hardness of DVD stated in Theorem 1.1 follows.
Theorem 4.5. Assuming the Unique Games Conjecture, for any integer k ≥ 2 and arbitrary constants
ε, δ > 0, given a directed graph G(V, E), distinguishing between the following cases is NP-hard:
• (Completeness): there exist disjoint subsets V1 , . . . ,Vk ⊂ V satisfying |Vi | ≥ 1−2ε
k |V | and such that
a subgraph induced by all but one of these subsets has no path of length k.
• (Soundness): every induced subgraph of 32δ |V | vertices contain a path of length |V |1−δ .
We first present the reduction in the following subsection followed by the completeness (Lemma 4.6)
and soundness (Lemma 4.7) analyses.
4.2.1 Reduction
We describe a reduction from Unique Games to DVD. Let L(G(V,W, E), [R], {πv,w }(v,w)∈E ) be a Unique
Games instance. As before, it will be convenient to present the DVD instance as it consists of two types
of vertices that we refer to as bit-vertices and test-vertices and all edges are between bit- and test-vertices.
• The bit-vertices are partitioned into L +1 bit-layers (L is selected below). Each bit-layer ` = 0, . . . , L
contains a bit-vertex b`w,x of weight ∞ for every w ∈ W and x ∈ [k]R .
In other words, each w ∈ W is replaced by a Q-ary hypercube [k]R in each layer.
• Similarly, the test-vertices are partitioned into L test-layers. Each test-layer ` = 0, . . . , L − 1 has
`
a test-vertex tx,S,v,w of weight 1 for every x ∈ [k]R , every subset S ⊆ [R] of εR indices, every
1 ,...,w2t
v ∈ V and every sequence (w1 , . . . , w2t ) ∈ N(v)2t of (not necessarily distinct) 2t neighbors of v.
` 0
• The arcs incident to a test-vertex tx,S,v,w1 ,...,w2t
are the following. For j = 1, . . . , 2t,
0
– there is an arc (b`w j ,z ,tx,S,v,w
`
1 ,...,w2t
) if ` ≤ `0 and z ∈ Cx,S,v,w j ,
` 0 ⊕
– and an arc (tx,S,v,w1 ,...,w2t
, b`w j ,z ) if ` > `0 and z ∈ Cx,S,v,w j
.
• Finally, L is selected so as δ 2 L ≥ |T |1−δ where T is the set of test-vertices.
Similar to before, we can obtain an unweighted graph G (with the set T of test-vertices as vertices)
with the same optimal value by having an arc between two test-vertices if there is a path between them
through one bit-vertex. Theorem 4.5 therefore follows from that (i) in the proof of completeness, we can
partition the test-vertices as required (Lemma 4.6) and (ii) in the proof of soundness, any solution deletes
almost all test-vertices (Lemma 4.7) in order to avoid long paths.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 774
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
4.2.2 Completeness
We show the following.
Lemma 4.6. If there is a labeling ρ of the Unique Games instance L satisfying a (1 − ζ ) fraction of the
constraints then we can partition the test-vertices into subsets T 0 , T0 , . . . , Tk satisfying T j ≥ 1−2ε 0
k |T |, |T | ≤
2ε|T |, and for j ∈ [k] the graph obtained by deleting T 0 ∪ T j has no path of length k.
Proof. Note that if we collapse all layers by identifying the different copies of a bit-vertex and test-vertex
in different layers then the DVD instance is equivalent to the FVS instance constructed in Section 4.1.
We can therefore (by the arguments of Section 4.1.2), partition the bit-vertices into k equal sized sets
B0 , B1 , . . . , Bk−1 and all but an 2ε fraction of the test-vertices into k equal sized sets T0 , T1 , . . . , Tk−1 so
that any test-vertex in T j has only incoming arcs from bit-vertices in B j and outgoing arcs to bit-vertices
in B j⊕1 .
Any j ∈ [k] therefore corresponds to a solution by removing an 2ε fraction of the test-vertices (i. e.,
the set T 0 ) and those test-vertices in T j .
4.2.3 Soundness
As we can choose the soundness parameter γ of the Unique Games Conjecture to be arbitrarily small and
δ 2 L ≥ |T |1−δ , the proof of soundness follows from the following lemma.
Lemma 4.7. If the Unique Games instance has no labeling that satisfies a δ η 2 /(t 2 k2 ) fraction of the
constraints then every induced subgraph of the bit-vertices and 32δ |T | test-vertices has a path of length
δ 2 |L|.
Proof. As in Section 3.2.3, it will be convenient to look at the equivalent formulation of the problem
where we wish to find a coloring χ that assigns a color in {1, 2, . . . , k} to each bit-vertex satisfying
0
χ(b`w,x ) ≤ χ(b`w,x ) if ` ≤ `0 so as to minimize the number of unsatisfied test-vertices where a test-vertex
`
tx,S,v,w is said to be satisfied if
1 ,...,w2t
max χ(b`w j ,z ) < min χ(b`+1
w j ,z ) ,
1≤ j≤2t 1≤ j≤2t
z∈Cx,S,v,w j ⊕
z∈Cx,S,v,w
j
that is, all its predecessors are assigned lower colors than its successors.
We also generalize the concept of a lower bound on the colors assigned to most bit-vertices corre-
sponding to w ∈ W in each layer: define the color χ(w, `) of w ∈ W and a bit-layer ` = 0, 1, . . . , L as the
maximum color that satisfies Prx [χ(b`w,x ) ≥ χ(w, `)] ≥ 1 − δ .
Now, with w ∈ W and each test-layer ` = 0, 1, . . . , L − 1 we associate the indicator function fw` : [k]R →
{0, 1} defined as follows (
0 if χ(b`+1
w,x ) > χ(w, `),
fw` (x) =
1 otherwise.
Analogous to Claim 3.1, the key statement for the soundness analysis is the following.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 775
O LA S VENSSON
Claim 4.8. Assume the Unique Games instance L has no labeling satisfying a δ η 2 /(t 2 k2 ) fraction of the
constraints. If a 16δ fraction of the test-vertices of test-layer ` are satisfied, then χ(w, `) < χ(w, ` + 1)
for at least a 2δ fraction of the vertices in W .
Proof. If we let T be the set of satisfied test-vertices of test-layer ` then (as T contains at least a 16δ
fraction of the test-vertices in that layer)
Pr max χ(b`w j ,z ) < min χ(b`+1
w j ,z ≥ 16δ .
)
x,S,v,w1 ,...,w2t 1≤ j≤2t 1≤ j≤2t
z∈Cx,S,v,w j ⊕
z∈Cx,S,v,w
j
Similar to Section 4.1.3, we call a tuple (v, w1 , . . . , w2t ) good if
Pr max χ(b`w j ,z ) < min χ(b`+1
w j ,z ≥ 8δ
)
x,S 1≤ j≤2t 1≤ j≤2t
z∈Cx,S,v,w j ⊕
z∈Cx,S,v,w
j
and note that at least an 8δ fraction of the tuples are good.
By the definition of χ(w, `) we have Prx [χ(b`w,x ) ≥ χ(w, `)] ≥ 1 − δ and therefore for a good tuple
(v, w1 , . . . , w2t ),
" #
2t
`+1 `
^
7δ ≤ Pr max χ(w j , `) < min χ(bw j ,z ) ≤ Pr f (Cx,S,v,w j ) ≡ 0 ,
x,S 1≤ j≤2t 1≤ j≤2t x,S j=1 w j
⊕
z∈Cx,S,v,w
j
which, by Theorem 4.1, shows that either
(i) more than t of the functions are such that E[ fw` j ] < δ and hence χ(w j , ` + 1) > χ(w j , `); or
(ii) there exists 1 ≤ `1 6= `2 ≤ t and j ∈ L[w`1 ], j0 ∈ L[w`2 ] such that πv,w`1 ( j) = πv,w`2 ( j0 ), where (similar
to Section 4.1.3)
L[w] = {i ∈ [R] : Infldi ( fw` ) ≥ η} .
If condition (i) holds for half the good tuples, i. e., a 4δ fraction of all tuples, then the statement follows
because we can pick a vertex w in W uniformly at random by first picking a tuple (v, w1 , . . . , w2t ) at
random and then picking one of the vertices w1 , . . . , w2t at random. With probability 4δ the tuple is good
and satisfy condition (i) and (conditioned upon that fact) with probability 1/2 the picked vertex w j will be
such that χ(w j , ` + 1) > χ(w j , `). Therefore, we have that if condition (i) holds for half the good tuples
then Prw [χ(w, ` + 1) > χ(w, `)] ≥ 2δ as required.
On the other hand, we shall show that the assumption of the claim (that no labeling of the Unique
Games instance satisfies a δ η 2 /(t 2 k2 ) fraction of the constraints) is violated if condition (ii) holds for
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 776
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
more than half the good tuples. This follows from very similar arguments as in Section 4.1.3 (and in [1]).
Indeed, for every w ∈ W , define ρ(w) to be a random label from L[w] and, for every v ∈ V pick a random
neighbor w ∈ N(v) and define ρ(v) = πv,w (ρ(w)). If condition (ii) holds for half the good tuples, then
with probability 4δ a random tuple (v, w1 , . . . , w2t ) is such a tuple, with probability 1/(4t 2 ) we have
w = w`1 and w0 = w`2 for w, w0 randomly picked in the set {w1 , . . . , w2t }, and with probability 1/(k2 /η 2 ),
the labeling procedure defines j = ρ(w), j0 = ρ(w0 ). Hence (if condition (ii) holds for half the good
tuples)
4δ η 2
Pr 0 [πv,w (ρ(w)) = πv,w0 (ρ(w0 ))] ≥ 2 2 ,
v,w,w 4t k
and (expected over the randomness of the labeling procedure)
δ η2
Pr [ρ(v) = πv,w (ρ(w))] ≥ .
(v,w) t 2 k2
This shows that condition (ii) cannot hold for half the good tuples as this would imply that there is a
labeling of L that satisfies a δ η 2 /(t 2 k2 ) fraction of the constraints.
To see how the above claim implies the lemma consider a subgraph induced by all bit-vertices and a
32δ fraction of the test-vertices and consider the smallest number of colors needed for a coloring χ to
satisfy all those test-vertices.
Note that at least a 16δ fraction of the test-layers are such that at least a 16δ fraction of the test-vertices
of that layer are satisfied by χ. This in turn, by the preceding claim, shows that
Pr [χ(w, ` + 1) > χ(w, `)] ≥ 16δ · 2δ = 32δ 2
`∈[L],w∈W
and hence there exists a w ∈ W such that Pr`∈[L],w∈W [χ(w, ` + 1) > χ(w, `)] ≥ 32δ 2 . Therefore, the
coloring χ needs to use at least 32δ 2 L colors to satisfy a 32δ fraction of the test-vertices or, in other
words, any subgraph induced by the bit-vertices and a 32δ fraction of the test-vertices has a path of length
32δ 2 L − 1 ≥ δ 2 L.
5 Discrete Time–Cost Tradeoff problem
In the Discrete Time–Cost Tradeoff problem we are given a set J of activities together with a partial order
(J, <). Any execution of the activities must comply with the partial order, that is, if j < k activity k may
not be started until j is completed. The duration of an activity depends on how much of the resources are
spent on it. This tradeoff between time and cost for each job is described by a nonnegative cost function
c j : R+ → R+ ∪ {∞}, where c j (x j ) denotes the cost to run j with duration x j . The project duration t(x) of
the realization x is the makespan (length) of the schedule which starts each activity at the earliest point in
time obeying the precedence constraints and durations x j . Given a deadline T > 0, the deadline version
of the Discrete Time–Cost Tradeoff problem (DTCT) is that of finding the cheapest realization x that
obeys the deadline, i. e., t(x) ≤ T .
Theorem 5.1. DTCT is as hard to approximate as DVD.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 777
O LA S VENSSON
Proof. We reduce (in polynomial time) the problem of approximating DVD to that of approximating
DTCT. Given an instance of DVD, i. e., an integer k and a DAG G(V, A) with the vertices ordered
0, 1, . . . , n − 1 according to a topological sort, consider the instance of DTCT defined as follows:
• The deadline T is set to n.
• The set J of activities contains three activities `i , mi , ri for each vertex i ∈ V = {0, 1 . . . , n − 1} with
precedence constraints `i < ci < ri and cost functions
( ( (
0 if x ≥ i, 0 if x ≥ 9/10, 0 if x > n − 1 − i,
c`i (x) = cmi (x) = cri (x) =
∞ otherwise, 1 otherwise, ∞ otherwise.
In addition, there is an activity a(i, j) for each arc (i, j) ∈ A with precedence constraints mi < a(i, j) <
m j and cost function (
9 1
0 if x ≥ j − i − 10 + 10(k−1) ,
ca(i, j) (x) =
∞ otherwise.
See Figure 2 for an example of the DTCT instance corresponding to a DVD instance G with k = 3.
Note that the cost functions of `i , mi , and ri enforce that activity mi has to be executed in the interval
G DTCT
0 1 2 3
0 1 2 3 4
Figure 2: For each vertex i ∈ V the activity mi is depicted in light gray (activities `i and ri are omitted).
The activities corresponding to arcs are depicted in white. Finally, the depicted solution pays a cost of 1
for running activity m2 in time 0.
[i, i + 1) and that it will require time 9/10 unless we pay a cost of 1 which allows us to run the activity in
0 time. Furthermore, as an activity a(i, j) always has duration (at least)
9 1
j−i− + ,
10 10(k − 1)
the start time s j of activity m j must be such that
1
s j − j ≥ si − i + ,
10(k − 1)
where si is the start time of activity i. Using the fact that an activity mi must run in the interval [i, i + 1) in
order to obey the deadline, it follows that we have to pay a cost of 1 for at least one activity corresponding
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 778
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
to each path of length k. By similar arguments, it also follows that this is also sufficient for having a
realization respecting the deadline. Therefore, any solution to DTCT naturally corresponds to a solution
to DVD (and vice versa) by deleting those vertices corresponding to activities with a cost of 1.
Acknowledgements
The author thanks the anonymous referees and László Babai for their valuable comments that greatly
improved the presentation of the paper.
References
[1] N IKHIL BANSAL AND S UBHASH K HOT: Optimal long code test with one free bit. In Proc. 50th
FOCS, pp. 453–462. IEEE Comp. Soc. Press, 2009. [doi:10.1109/FOCS.2009.23] 761, 763, 769,
773, 777
[2] N IKHIL BANSAL AND S UBHASH K HOT: Inapproximability of hypergraph vertex cover and
applications to scheduling problems. In Proc. 37th Internat. Colloq. on Automata, Languages and
Programming (ICALP’10), pp. 250–261. Springer, 2010. [doi:10.1007/978-3-642-14165-2_22] 761
[3] P RABUDDHA D E , E. JAMES D UNNE , JAY B. G HOSH , AND C HARLES E. W ELLS: The discrete
time-cost tradeoff problem revisited. European Journal of Operational Research, 81(2):225–238,
1995. [doi:10.1016/0377-2217(94)00187-H] 760
[4] I RIT D INUR AND S HMUEL S AFRA: On the hardness of approximating minimum vertex cover.
Ann. of Math., 162(1):439–485, 2005. Preliminary version in STOC’02. See also at ECCC.
[doi:10.4007/annals.2005.162.439] 761
[5] G UY E VEN , J OSEPH NAOR , BARUCH S CHIEBER , AND M ADHU S UDAN: Approximating minimum
feedback sets and multicuts in directed graphs. Algorithmica, 20(2):151–174, 1998. Preliminary
version in IPCO’95. [doi:10.1007/PL00009191] 760, 761
[6] D ELBERT R. F ULKERSON: A network flow computation for project cost curves. Management
Science, 7(2):167–178, 1961. [doi:10.1287/mnsc.7.2.167] 760
[7] A LEXANDER G RIGORIEV AND G ERHARD J. W OEGINGER: Project scheduling with irregular
costs: complexity, approximability, and algorithms. Acta Inf., 41(2-3):83–97, 2004. Preliminary
version in ISAAC’02. [doi:10.1007/s00236-004-0150-2] 760, 761
[8] V ENKATESAN G URUSWAMI , J OHAN H ÅSTAD , R AJSEKAR M ANOKARAN , P RASAD R AGHAVEN -
DRA , AND M OSES C HARIKAR : Beating the random ordering is hard: Every ordering CSP is
approximation resistant. SIAM J. Comput., 40(3):878–914, 2011. Preliminary versions in FOCS’08
and in CCC’09. See also at ECCC. [doi:10.1137/090756144] 761
[9] R ICHARD M. K ARP: Reducibility among combinatorial problems. In R. E. M ILLER AND
J. W. T HATCHER, editors, Complexity of Computer Computations, pp. 85–103. Springer, 1972.
[doi:10.1007/978-1-4684-2001-2_9] 760
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 779
O LA S VENSSON
[10] JAMES E. K ELLEY, J R .: Critical-path planning and scheduling: Mathematical basis. Operations
Research, 9(3):296–320, 1961. [doi:10.1287/opre.9.3.296] 760
[11] JAMES E. K ELLEY, J R . AND M ORGAN R. WALKER: Critical-path planning and scheduling. In
Papers presented at the December 1-3, 1959, eastern joint IRE-AIEE-ACM computer conference,
pp. 160–173. ACM Press, 1959. [doi:10.1145/1460299.1460318] 760
[12] S UBHASH K HOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp.
767–775. ACM Press, 2002. [doi:10.1145/509907.510017] 761, 764
[13] F RANK T HOMSON L EIGHTON AND S ATISH R AO: Multicommodity max-flow min-cut theorems
and their use in designing approximation algorithms. J. ACM, 46(6):787–832, 1999. Preliminary
version in FOCS’88. [doi:10.1145/331524.331526] 760
[14] E LCHANAN M OSSEL , RYAN O’D ONNELL , AND K RZYSZTOF O LESZKIEWICZ: Noise stability of
functions with low influences: Invariance and optimality. Ann. of Math., 171(1):295–341, 2010.
Preliminary version in FOCS’05. [doi:10.4007/annals.2010.171.295] 762, 763, 769
[15] D OOWON PAIK , S UDHAKAR M. R EDDY, AND S ARTAJ S AHNI: Deleting vertices to bound path
length. IEEE Trans. Computers, 43(9):1091–1096, 1994. [doi:10.1109/12.312117] 760
[16] P RASAD R AGHAVENDRA: Optimal algorithms and inapproximability results for every CSP? In
Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414] 761
[17] PAUL D. S EYMOUR: Packing directed circuits fractionally. Combinatorica, 15(2):281–288, 1995.
[doi:10.1007/BF01200760] 760
[18] M ARTIN S KUTELLA: Approximation algorithms for the discrete time-cost tradeoff problem. Math.
Oper. Res., 23(4):909–929, 1998. Preliminary version in SODA’97. [doi:10.1287/moor.23.4.909]
760, 762
[19] O LA S VENSSON: Hardness of vertex deletion and project scheduling. In Proc. 15th Internat.
Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’12),
pp. 301–312. Springer, 2012. [doi:10.1007/978-3-642-32512-0_26] 759
AUTHOR
Ola Svensson
assistant professor
École Polytechnique Fédérale de Lausanne
ola.svensson epfl ch
http://theory.epfl.ch/osven
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 780
H ARDNESS OF V ERTEX D ELETION AND P ROJECT S CHEDULING
ABOUT THE AUTHOR
O LA S VENSSON (not to be confused with the singer Ola Svensson) graduated from IDSIA
in 2009; his advisor was Monaldo Mastrolilli. The subject of his thesis was the approx-
imability of graph and scheduling problems. After spending two years as a postdoc
with Johan Håstad at KTH Royal Institute of Technology, Sweden, he is now back in
Switzerland as an assistant professor in the theory group at EPFL. Apart from doing
research, he enjoys the Alps that are in complete contrast to the flat but still beautiful
landscape in South Sweden where he grew up.
T HEORY OF C OMPUTING, Volume 9 (24), 2013, pp. 759–781 781