CSCC63, Winter 2019 Assignment # 4
Due: Friday April 05 at 11:59 pm
You may work with a single partner. If you do work with a partner, please list both of your names on your assignment. You are not allowed to discuss the assignment with anyone other than your partner, the TAs, and the instructor.
We stated in class that a number of languages are NP-complete: these include 3SAT, CLIQUE, 3COL, VC, and HAM-PATH. You may assume that these languages are NP-complete here.
You may also refer to the fact that 2SAT and 2COL are in P. 1 PartA
One of the following languages is in P, the others are NP-complete.
For each language: either prove that it is in P or that it is NP-complete.
You may assume each language is in NP. (10 points each) 1. 99.9-%-COL:
INPUT: A graph G = (V, E).
QUESTION: Is G k-colourable, where k = 0.999|V |?
2. 2-CLIQUE-DECOMPOSITION: INPUT: A graph G = (V, E).
QUESTION: Can G be decomposed into two disjoint cliques? 3. DOUBLE-CLIQUE:
INPUT: A graph G = (V,E) and a k ∈ N.
QUESTION: Does G have two disjoint cliques whose sizes sum
to k?
4. SUBGRAPH-ISOMORPHISM:
INPUT: Two graphs G = (VG,EG) and H = (VH,EH). QUESTION: Does G have a subgraph isomorphic to H?
5. HITTING-SET:
INPUT: A set S, a finite collection C of subsets of S, a k ∈ N.
QUESTION: Does S have a subset H of size ≤ k such that for every Ci ∈ C, Ci ∩ H ̸= ∅?
1
2 PartB
In this section we’ll look at the intersection property of regular languages. We write the language
=
Each Di is a DFSA that
recognizes a finite language, {D ,D ,…,D }
F-DFSA-
6. (5 points) Show F-DFSA- ∈ NP.
12k
and Di is non-empty.
7. We’ll show that F-DFSA- is NP-complete. Suppose that we have some 3CNF formula φ.
Since φ is in 3CNF, if it has n clauses, it has 3n literals. Every truth assignment assigns these literals truth values, which we can write as strings in {T,F}3n.
Not all strings in {T,F}3n correspond to truth assignments: the same variable may occur different times in φ, and its truth assignments must be consistent.
i. (5 points) Given an arbitrary φ with n clauses and k literals, show how you could produce a DFSA for a variable xi that accepts precisely the strings in {T,F}3n that give consistent values to the variable xi.
ii. (5 points) Show how you could write a DFSA that accepts the strings in {T,F}3n that satisfy each clause, but may assign. truth values to the variables inconsistently.
iii. (5 points) Show that 3SAT ≤ F-DFSA- .
8. (5 points) We know that the intersection of DFSAs is regular, and regular languages can be decided in linear time. Why does this not give us a linear time for solving 3SAT?
2
i
e.g., If φ were (x1 ∨x2 ∨x3)∧(x1 ∨x2 ∨x4), then the truth assignment
x1 =T,x2 =F,x3 =T,x4 =F would yield the string TTFFFT.
e.g., In the φ above, the string TTFTFT would not give consistent values to the variable x1.
3 PartC
9. Consider the language
G is a graph, and k, a, b ∈ N, and if k vertices ⟨G, k, a, b⟩ are chosen uniformly at random, they have .
at least a chance of a/b of being a k-clique i. (5 points) Show L9 ∈ PSPACE.
ii. (5 points) Show L9 is NP-hard. Note: L9 is not believed to be in NP.
10. (15 points) It can be proven that unless P = NP, there is no n1−ε approximation algorithm for CLIQUE or IS. But CLIQUE can be solved exactly for graphs that are d-regular (that is, where every vertex has d edges) in O(nd+1) time. So if d is fixed, we can solve the problem in polytime.
For a fixed d ∈ N, consider the following problem: INPUT: A d-regular graph G.
OUTPUT: The largest independent set in G.
Give an approximation algorithm for this problem that differs from the true answer by some constant factor that does not depend on the size of G.
L9 =
3