The Theory of Computation

Bernard M.E. Moret

NP-Completeness Proofs

These problems can all be shown complete through very simple reductions from one of the standard NP-complete problems in the text (mostly from some variety of 3SAT or HC).
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.
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),y1,...,y1}, then it is the implication x -> y1 or ... or yn.
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.
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 S1 and S2 such that every subset in the collection C has at least one element in S1 and one in S2.
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'.
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.)
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.
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.
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={f1,...,fk} (for k<|V|) with (positive integer) weight assignment w: F -> N, and positive integer bound B. (The value w(fi) denotes the time it takes fire truck fi 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.
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?
Comparative Divisibility. An instance of this problem is given by two sequences of positive integers, say {ai} and {bj}. (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.
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 u1,...,uk, then the label of u is the smallest non-negative integer that differs from the labels assigned to the vertices u1,...,uk. (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.)
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.
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.
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 V1,...,VK, such that each induced subgraph Gi=(Vi,Ei) is a forest.
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.
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.
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?
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?
Expected Projected Sum. An instance of this problem is given by a collection C of n-dimensional binary vectors -- denote vector v by (v1,...,vn) -- and a positive integer bound B. The question is whether the collection C can be partitioned into three non-empty collections, C1, C2, and C3, 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
sumi=13(max1<=j<=n(sumv in Ci vj)) <= B
Intersection Pattern. An instance of this problem is given by a symmetric NxN matrix A=(aij) with non-negative integer entries. The question is whether there exists a collection C={C1,...,Cn} of sets such that, for all i,j between 1 and N, we have
aij = |Ci inter Cj|
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=aK can be generated by G?
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).
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

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.
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.)
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.
(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.
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.
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 Sigma2.
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.
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.