When you spot an NP-complete problem you change strategies from looking
for an elegant algorithm to
- Heuristics -- greedy, genetic, dynamic programming
- Special cases
- Approximations
10.4.1 Describing NP-complete Problems 447
- Problem::=following,
Net
- Name::string.
- Short_name::string.
- Given::data defining an instance
- Goal::properties defining a solution
(End of Net)
- NP_Problem::=following,
Net
- Problem.
- Proved_NP by: explanation that typically includes the short_name of another
NP problem.
(End of Net)
The book introduces new style form of definition. (problem, input, output, reduction from). Can there be more than one reduction to solve or show the problem is NP-complete.
Yes.... there are many possible reductions. Some of these have been done,
and some of these have been published.... and the book picks one of the
published ones.
There is a pretty Graph on page 464.
10.4.2 The Problem of Independent Sets 448
Don't be mislead -- this is not just an abstract problem.
See Box on page 452.
Scheduling MS presentations so that committee
members can be present at each relevant presentation and also teach their
classes.
- For Graph (N,E), I:subset(N), I is independent::= for all i,j:N(if i!=j then {i,j} is not in E ).
- IS::=Find independent sets in a undirected graph.
- Name: Independent sets
- Short_name: IS.
- Given: An undirected graph G=(N,E) with n nodes and e edges , k:1..n.
- Goal: YES if some I:subset(N)( |I|=k and I is an independent_set(G) ).
- proved NP by: Reducing 3SAT to IS.
Why is this hard.... surely we start with the obviously independent set {}
and add one node at a time until.... ?
Answer: You can go up a blind alley that leads to a non-optimal
solution.
Ch 10.4.2 pp 450 -- Are Yes/No Problems Easier?
Do we learn from a yes/no problem easier? Shouldn't we know why it is
NP-complete with examples of problem or why it fail to be a NP-complete
problem
We use Yes/No problems because we've found proofs that use them --
apparently proofs for optimization problems are worse.
Note the clever construction of a graph that encodes 3SAT as IS.
Structure of Proof
- Prove IS is NP by constructing polynomial time NTM to solve IS.
- Prove IS is NP-hard...
- Construct a G and a k that should simulate 3SAT E.
Ch 10.4.2 pp 448-451 -- Independent Sets
How is the 3-CNF expression derived from the figure below it... or vice versa, I'm not quite sure how to read it. Figure 10.8?
Ch 10.4 pp 449 -- Figure 10.8
How was the independent set constructed from this graph?
- Map the 3-CNF into a graph
- Each node models a literal in the formula.
- The nodes in the IS reflect true literals.
- Note. The nodes outside the IS model literals that can be true or false.
- Each clause is modeled as a cycle of 3 nodes.
- Complements are modeled by adding arcs.
- Setting the threshold k = m is vital.
Because this makes sure that one literal in each clause is selected.
- The triangle of arcs for clause means that a literal is not chosen twice.
- Prove: If E is satisfiable then there is an IS in G of size K.
- Prove: If there is an IS in G of size K then E is satisfiable.
Example 10.19 and Figure 10.8
Box on page 452 -- What is IS good for?
The problem of scheduling a set of final exams so that no student has to
be in more than one final at a time is an instance of IS.
Ch 10.4.3 pp 452 -- Additional NP-Complete Problems
Could you go over the Node_cover Problem?
- NC::=the node cover problem, ...
- Name: the node cover problem.
- Short_name: NC.
- Given: A graph G=(N,E) and upper limit k:0..|N|.
- Goal: Yes iff G has node cover with k or fewer nodes.
For graph G=(N,E), , C: subset(N), C is a node_cover(G) iff for all {e1,e2}:E( either e1 or e2 is in C).
Note the duality between NC and IS.
- NC is NP
- Guess a set of k nodes.
- Check to see if every edge in G has at least one end in the set.
- Reduce IS to NC
Let- G+k be an instance of IS with n nodes
- Construct instance of NC with k= n-k.
(Close Let )
- Proof
- If...
- Only if...
10.4.4 The Directed Hamilton-Circuit Problem 453
A directed graph is an (undirected) graph with arrows on the edges. The
book gets to Hamiltonian cycles on undirected graphs by starting with
directed ones.
- Undirected_Graph G::=(N,E) when N is a set and E is a set of sets {i,j} where i!=j and i,j are in N.
(cycle): series of nodes, that begins and ends with the same node:
- (n1, n2, n3, ....., n[k], n[k+1] = n1)
where for all i:1..k, {n[i], n[i+1]} is an edge).
- Directed_Graph D::=(N, E) when N is a set and E is a set of pairs (i,j) where
i and j are in N.
A directed graph can have arrows that loop back to the node the started at: (i,j).
(directed_cycle): series of nodes, that begins and ends with the same node:
- (n1, n2, n3, ....., n[k], n[k+1] = n1)
where for all i:1..k, (n[i], n[i+1]) is an edge).
You need to know the idea of this construction but (in the final) I
do not expect you duplicate the construction of the gadgets.
- Hamilton-Circuit Problem
- HC
- Undirected graph G=(N,E).
- Output Yes if and only if G has a cycle that passes through each N once.
- Reduce the Directed Hamilton Circuit problem (DHC) to HC. See
[ $HC ]
below.
Exercise 0 points -- Does your 6 node graph have a Hamiltonian circuit?
Special case of TSP: all edges have same length = 1.
- Directed Hamilton-Circuit Problem
- DHC
- Directed graph G=(N,E).
- Output Yes if and only if G has a directed_cycle that passes through each N once.
- Reduce 3SAT to the Directed Hamilton Circuit problem (DHC)
below.
Ch 10.4 pp 454 -- DHC & HC
Why are these separated? If you know that a regular HC is NP-complete wouldn't that lead us to know the DHC is np-complete. Is there any major difference besides which way to go in these problems?
Directed graphs are like a town where every street is a one way street and
so the problem of finding a circuit through it is easier (fewer choices)
and less likely (fewer options).
It is possible that the DHC was proved
first and then some one transformed it into the undirected HC. Until this
connection is proved we can not claim that the two problems are
equivalent. Indeed it may be that one is in some sense or other
one is harder than the other: for example DHC may need O(n^10)
nondeterministic steps and
the other O(n^20). Both could still be in NP-complete but perform
differently.
You can probably go to HC first and derive DHC from it....
but I don't have the time to attempt
it right now.
Exercise 0 points -- Does your 6 node directed graph have a Hamiltonian circuit.
Proof structure
- DHC is NP -- easy!
- Reduce 3SAT to DHC
- many details and gadgets
- Proof of simulation
- if
- only-if
Example 10.22 and Figure 10.10 of DHC that models 3SAT
Figure 10.10 -- I don't quite understand
Ch 10.4 pp 454 -- DHC
Could you please go over the proof for Theorem 10.21. The part where they connect all the sub graphs together at the end is confusing.
Ch 10.4.4 pp 453-459 -- The Directed Hamilton-Circuit Problem
I'm terribly confused as to how the translation from an expression to a 'gadget' works. Could you explain the reasoning?
- HC::problem=following,
- Hamilton-Circuit Problem
- HC
- Undirected graph G=(N,E).
- Output Yes if and only if G has a cycle that passes through each N once.
- Reduce the Directed Hamilton Circuit problem (DHC) to HC. See
below.
Theorem 10.23 HC is NP-complete
Structure of Proof
- HC is NP -- OMITTED
- Reduce DHC to HC
- Model directed graph G[d] by a constructed undirected Graph G[u] with 3
times as many nodes that force a path to go in only one direction!
- Proof
- TSP::=following
- Traveling Salesperson Problem
- TSP
- An undirected graph G with integer weights on the edges and a limit k.
- Yes iff there is a HC of G with sum of weights <= k.
- Reduce from HC
Theorem 10.24 TSP is NP-Complete
Proof: the book omits a lot.... but it follows the normal pattern.
Key thought: Given G construct G' such that solving TSP on G' solves
HC on G.
10.4.6 Summary of NP-Complete Problems 461
Exercise -- 0 points -- write down the pattern of all the proofs of NP-completeness in this chapter
Notice that all the proofs depend on creating a gimmick that transform
a known problem into the unknown one.
Figure 10.12 The Family of NP-Complete problems in chapter 10
Exercise -- reproduce this from memory
Exercise -- label each arc in Figure 10.12 with the theorem number that proves the result.
* Exercise 10.4.1 Cliques
Work out a plan for this proof (with out any details/gadgets/gimmicks!)
and then look at the book's web site to see what the gimmick is.
Can you explain why a Clique in NP complete? It seems like an easy thing to do.
Ch 10.4 pp 466 -- Why is the question of 2-colorability NP-complete?
It seems as though once you've chosen on the color of one node, it automatically chooses the colors for all the other nodes in the graph.
I found these problems easier than the "!" might indicate. The
symmetry of the graph helps. I will except them as a "!" for grading however.
Ch 10.4 pp 464 -- Symmetry
You noted in class that the symmetry makes problem 10.4.3 a lot easier. Is the problem of determining whether or not a graph has symmetry in P?
My guess is NP-Complete. more TBA.
Exercise 10.4.4a Subgraph isomorphism
Easy to crate a CLIQUE solver from a subgraph isomorphism solver.
! Exercise 10.4.4b Feedback edge set -- ERRORS
The web site includes a couple of typographical errors. GJ75
state that the problem as stated is "Trivially in P"! Here is the
corrected problem:
Given a DIRECTED graph G with nodes N and arcs A, and an integer k,
does G have a set of k arcs such that every directed cycle of G contains
least one of the k arcs. Prove NP-complete by transforming NC
into this kind of problem.
! Exercise 10.4.4d Dominating Set problem
!! Exercise 10.4.4i The famous Knapsack Problem
Subtle!
Exercise 10.4.5 Hamiltonian Paths