The Theory of Computation Bernard M.E. Moret

ADDITIONAL EXERCISES FOR CHAPTER 7

NP-Completeness Proofs

• Additional Exercise 1
  NAE Max2SAT. An instance of this problem is given by a collection of 2-literal clauses, with no variable appearing more than once per clause, and a positive integer bound K. The question is whether or not there exists a truth assignment that satisfies at least K of the clauses in NAE fashion, i.e., such that each satisfied clause has exactly one true and one false literal.
• Additional Exercise 2
  Extended Horn Clause Satisfiability. An instance of this problem is an instance of Satisfiability where each clause either has two literals or has at most one complemented literal; the question is whether or not the instance is satisfiable.
  A clause with at most one complemented literal is called a Horn clause, because it can be regarded as an implication: if the clause is {not(x),y₁,...,y₁}, then it is the implication x -> y₁ or ... or y_n.
  Not that the problem is easily seen to be in P if all of its clauses have two literals (2SAT) or if all of its clauses are Horn clauses.
• Additional Exercise 3
  Set Splitting. An instance of this problem is given by a set S and a collection C of subsets of S. The question is whether or not the set S can be partitioned into two subsets S₁ and S₂ such that every subset in the collection C has at least one element in S₁ and one in S₂.
• Additional Exercise 4
  Feedback Vertex Set. An instance of this problem is given by a directed graph G=(V,A) and a positive integer bound K. The question is where or not there exists a subset V' of V of size not exceeding K such that every cycle (every feedback loop) in G includes at least one vertex from V'.
• Additional Exercise 5
  Feedback Arc Set. An instance of this problem is given by a directed graph G=(V,A) and a positive integer bound K. The question is where or not there exists a subset A' of A of size not exceeding K such that every cycle (every feedback loop) in G includes at least one arc from A'. (Contrast this result with that of Additional Exercise 2.4.)
• Additional Exercise 6
  Star Matching. An instance of this problem is given by a graph G=(V,E) and a positive integer bound K. The question is whether or not G has a star-matching of size at least K, where a star-matching is a labeling of the vertices with labels from the set {0,1} such that each vertex labelled 0 is adjacent to at least one vertex labelled 1 and the size of such a matching is the number of vertices labelled 0.
• Additional Exercise 7
  Negative Directed Simple Path. An instance of this problem is given by a directed graph G=(V,A), a weight for each arc chosen from the set {-1,1}, and distinguished vertices s and t. The question is whether or not there exists a simple path (i.e., a path that includes each vertex at most once) from s to t, the total weight of which is negative.
• Additional Exercise 8
  Fire Truck Placement. An instance of this problem is given by a graph G=(V,E), a distinguished vertex v, collection of "fire trucks" F={f₁,...,f_k} (for k<|V|) with (positive integer) weight assignment w: F -> N, and positive integer bound B. (The value w(f_i) denotes the time it takes fire truck f_i to cross a graph edge.) The question is whether or not there exists an assignment of fire trucks to graph vertices, loc: F -> V, such that the trucks can all get to vertex v within B time units, with no two trucks ever crossing the same edge at the same time.
  The edges can be thought of as bridges, which are too fragile to support more than one truck at a time; the vertices are islands, each of which -- except for the designated island v -- can serve as the base for one or more fire trucks; the problem is then to base the trucks so as to minimize the response time for a fire on island v.
• Additional Exercise 9
  Partition into Paths of Length 2. An instance of this problem is given by a graph G=(V,E), with |V|=3q for some positive integer q. The question is whether or not there exists a partition of V into q disjoints sets of 3 vertices each such that, for each 3-subset, at least of the three possible edges belong to E?
• Additional Exercise 10
  Comparative Divisibility. An instance of this problem is given by two sequences of positive integers, say {a_i} and {b_j}. (The sequences may contain multiply repeated values.) The question is whether or not there exists a positive integer c that divides evenly more elements of the first sequence than of the second sequence.
• Additional Exercise 11
  Graph Grundy Numbering. An instance of this problem is given by a directed graph G=(V,A). The question is whether this graph has a Grundy numbering, where such a numbering is an assignment of non-negative integer labels to vertices with the following property: if vertex u has arcs to vertices u₁,...,u_k, then the label of u is the smallest non-negative integer that differs from the labels assigned to the vertices u₁,...,u_k. (In particular, a simple cycle has a Grundy numbering -- of alternating 0s and 1s -- if and only if it has an even number of vertices.)
• Additional Exercise 12
  Simple Rural Postman. An instance of this problem is given by a graph G=(V,E), a designated subset E' of E, and a positive integer bound K. The question is whether there exists a (not necessarily simple) cycle in G of length at most K (that is, with at most K edges) that includes all edges in E'.
  The designated edges can be thought of as long side roads that lead to farmhouses; each such road must be travelled by the rural postman for deliveries to the farmhouse itself.
• Additional Exercise 13
  Graph Kernel. An instance of this problem is given by a directed graph G=(V,A). The question is whether or not the graph has a kernel, that is, a subset V' of V such that: (i) V' is an independent set (no arc exists between any two vertices in the kernel); and (ii) there is at least one arc from some kernel vertex to any vertex not in the kernel.
• Additional Exercise 14
  Partition into Forests. An instance of this problem is given by graph G=(V,E) and a positive integer constant K. The wuestion is whether V can be partitioned into K subsets, call them V₁,...,V_K, such that each induced subgraph G_i=(V_i,E_i) is a forest.
• Additional Exercise 15
  Maximum TR-Matching. An instance of this problem is given by a graph G=(V,E) and a positive integer bound K. The question is whether or not the graph has a TR-matching of size at least K, where a TR-matching on G is a subset M of E and a labeling of vertices from the set of labels {source,sink,null} such that: (i) M is a matching on G, i.e., no two edges in M share a vertex; (ii) vertices not included in the matching (i.e., that are not an endpoint of some edge in M) are labeled null; (iii) each edge in the matching has one endpoint labeled source and one labeled sink; and (iv) only edges in the matching have property (iii)---others have endpoints with the same label or with the null label.
  Such a matching allows the testing of edges in a single direction, with a single transmitter and a single receiver.
• Additional Exercise 16
  Strong Connectivity Augmentation. An instance of this problem is given by a directed graph G=(V,A), a positive integeer weight for each ordered pair of vertices w: VxV -> N, and a positive integer bound B. The question is whether or not there exists a set A' of ordered pairs of distinct vertices from V such that the sum of the weights of the pairs in A' does not exceed B and such that the augmented graph G'=(V,A+A') is strongly connected.
• Additional Exercise 17
  Sequencing to Minimize Tardy Task Weight. An instance of this problem is given by a set T of tasks, a positive integer length for each task w: T -> N, a positive integer weight for each task, w: T -> N, a positive integer deadline for each task, d: T -> N, and a bound, K. The question is whether there exists a single processor schedule s for T such that the sum of the weights of the tardy tasks (those tasks t for which s(t)+l(t) > d(t)) does not exceed K?
• Additional Exercise 18
  Staff Scheduling. An instance of this problem is given by three positive integers k (the number of hours of work per scheduling period), m (the number of hours per scheduling period), and n (the number of workers), a collection C of m-tuples, each having k 1s and m-k 0s (the possible worker schedules per scheduling period), and an m-tuple r of positive integers (the number of workers required at each hour of the scheduling period). The question is whether there is a schedule f: C -> {1,2,3,...} (that is, an assignment of f(c) workers to schedule c such that we have both sum (over all tuples c in C) f(c) <= n and sum (over all tuples c in C) f(c)*c >= r?
• Additional Exercise 19
  Expected Projected Sum. An instance of this problem is given by a collection C of n-dimensional binary vectors -- denote vector v by (v₁,...,v_n) -- and a positive integer bound B. The question is whether the collection C can be partitioned into three non-empty collections, C₁, C₂, and C₃, such that the sum over all three collections of the largest projected sum in each collection does not exceed K -- formally, such that we have
  sum_i=1³(max_1<=j<=n(sum_{v in Ci} v_j)) <= B
• Additional Exercise 20
  Intersection Pattern. An instance of this problem is given by a symmetric NxN matrix A=(a_ij) with non-negative integer entries. The question is whether there exists a collection C={C₁,...,C_n} of sets such that, for all i,j between 1 and N, we have
  a_ij = |C_i inter C_j|
• Additional Exercise 21
  One-Letter Context-Free Membership. An instance of this problem is given by a context-free grammar G=(N,{a},S,P) and a positive integer bound K. The question is whether the string x=a^K can be generated by G?
• Additional Exercise 22
  Consecutive Sets. An instance of this problem is given by an alphabet (a finite set) S, a collection C of subsets of S, and a positive integer bound K. The question is whether there exists a string w of length at most K over the alphabet S such that every subset in the collection C forms a substring of w (that is, such that the alphabet symbols of each subset can be ordered so as to form a substring -- not a subsequence -- of w).
• Additional Exercise 23
  Path Distinguishers (harder). An instance of this problem is given by a directed graph G=(V,A), distinguished vertices s and t of V, and a positive integer bound K. The question is whether there exists a subset A' of A of size note exceeding K such that, for any pair of paths from s to t, there exists at least one arc in A' that is part of one path but not the other (and thus distinguishes the two paths).

Other Completeness Proofs

• Additional Exercise 24
  Context-Free Emptiness. An instance of this problem is given by a context-free grammar; the question is whether or not the grammar generates an empty language. Prove that this problem is P-complete.
• Additional Exercise 25
  Context-Free Infiniteness. An instance of this problem is given by a context-free grammar; the question is whether or not the grammar generates an infinite language. Prove that this problem is P-complete. (Note that the problem becomes presumably simpler when useless non-terminals and epsilon productions are removed.)
• Additional Exercise 26
  Context-Free Membership. An instance of this problem is given by a context-free grammar and a string; the question is whether or not string can be generated by the grammar. Prove that this problem is P-complete.
• Additional Exercise 27
  (Restricted) Context-Free Infiniteness. An instance of this problem is given by a context-free grammar without epsilon productions and without useless non-terminal; the question is whether or not the grammar generates an infinite language. Prove that this problem is NL-complete.
• Additional Exercise 28
  Strong Connectivity. An instance of this problem is given by a directed graph; the question is whether or not the graph is strongly connected. Prove that this problem is NL-complete.
• Additional Exercise 29
  Inequivalence of Context-Free Grammars on a One-Symbol Alphabet (harder). An instance of this problem is given by two context-free grammars over the alphabet {a}. The question is whether or not one grammar generates a string that cannot be generated by the other. Prove that this problem is complete for Sigma₂.
• Additional Exercise 30
  Disjoint Cycle Covers. An instance of this problem is given by a directed or undirected graph; the goal is to find the smallest collection of edge- or vertex-disjoint cycles such that each vertex of the graph is included in at least one cycle.
  Prove that all four versions of this problem are NP-equivalent.
• Additional Exercise 31
  Pebbling (open-ended and harder). A pebble game is defined as follows. Given a directed acyclic graph and a designated vertex, the goal is to place (and remove) pebbles on the vertices (usually just written "to pebble the vertices") in order to pebble the designated vertex under the following rules.
  • Initially, only sources may be pebbled.
  • If all the parents of a vertex (i.e., all the vertices which are connected to the given vertex by an arc directed to said vertex) are pebbled, then the vertex may be pebbled.
  • A pebble may be removed at any time.
  The total number of pebbles present at any time on the graph is not allowed to exceed a given bound or the total number of moves is limited.
  Discuss the time and "pebble" complexity of this problem (both apply since the game is based on a trade-off between the two.) In particular, consider the influence of allowing vs. disallowing the re-pebbling of vertices.

Other Problems

• Additional Exercise 32
  We have seen that PH cannot have complete problems unless it collapses down to some level -- the argument is the same made for POLYL, except that POLYL cannot collapse, so that the statement for POLYL, unlike that for PH, need not be qualified. We have also seen that PH is a subset of PSPACE -- whether proper or not remains unknown. However, PSPACE does have complete problems; what then would be the consequences of the (hypothetical) result PH=PSPACE?
• Additional Exercise 33
  We have seen that oracles can be added to our basic Turing machine model to enhance its capabilities. Armed with some oracle set A we can define relativized complexity classes L^A, NL^A, P^A, NP^A, etc. Show that there is an oracle A such that we have P^A=NP^A. (Hint: pick a set A complete for a class in which we know that nondeterminism does not add any power.)