Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin WayneBasic genres.! Packing problems: SET-PACKING, INDEPENDENT SET.! Covering problems: SET-COVER, VERTEX-COVER.! Constraint satisfaction problems: SAT, 3-SAT.! Sequencing problems: HAMILTONIAN-CYCLE, TSP.! Partitioning problems: 3-COLOR, 3D-MATCHING.! Numerical problems: SUBSET-SUM, KNAPSACK.8.4 Sequencing Problems2Hamiltonian CycleHAM-CYCLE: given an undirected graph G = (V, E), does there exist asimple cycle ! that contains every node in V.YES: vertices and faces of a dodecahedron.3Hamiltonian CycleHAM-CYCLE: given an undirected graph G = (V, E), does there exist asimple cycle ! that contains every node in V.1351'3'242'4'NO: bipartite graph with odd number of nodes.4Directed Hamiltonian CycleDIR-HAM-CYCLE: given a digraph G = (V, E), does there exists a simpledirected cycle ! that contains every node in V?Claim. DIR-HAM-CYCLE " P HAM-CYCLE.Pf. Given a directed graph G = (V, E), construct an undirected graph G'with 3n nodes.vabcdevinaoutboutcoutdineinGG'v vout5Directed Hamiltonian CycleClaim. G has a Hamiltonian cycle iff G' does.Pf. %! Suppose G has a directed Hamiltonian cycle !.! Then G' has an undirected Hamiltonian cycle (same order).Pf. &! Suppose G' has an undirected Hamiltonian cycle !'.! !' must visit nodes in G' using one of following two orders: …, B, G, R, B, G, R, B, G, R, B, … …, B, R, G, B, R, G, B, R, G, B, …! Blue nodes in !' make up directed Hamiltonian cycle ! in G, orreverse of one. !63-SAT Reduces to Directed Hamiltonian CycleClaim. 3-SAT " P DIR-HAM-CYCLE.Pf. Given an instance # of 3-SAT, we construct an instance of DIR-HAM-CYCLE that has a Hamiltonian cycle iff # is satisfiable.Construction. First, create graph that has 2n Hamiltonian cycles whichcorrespond in a natural way to 2n possible truth assignments.73-SAT Reduces to Directed Hamiltonian CycleConstruction. Given 3-SAT instance # with n variables xi and k clauses.! Construct G to have 2n Hamiltonian cycles.! Intuition: traverse path i from left to right $ set variable xi = 1.st3k + 3x1x2x383-SAT Reduces to Directed Hamiltonian CycleConstruction. Given 3-SAT instance # with n variables xi and k clauses.! For each clause: add a node and 6 edges.stclause nodeclause node3211VVxxxC=3212VVxxxC=x1x2x393-SAT Reduces to Directed Hamiltonian CycleClaim. # is satisfiable iff G has a Hamiltonian cycle.Pf. %! Suppose 3-SAT instance has satisfying assignment x*.! Then, define Hamiltonian cycle in G as follows:– if x*i = 1, traverse row i from left to right– if x*i = 0, traverse row i from right to left– for each clause Cj , there will be at least one row i in which weare going in "correct" direction to splice node Cj into tour103-SAT Reduces to Directed Hamiltonian CycleClaim. # is satisfiable iff G has a Hamiltonian cycle.Pf. &! Suppose G has a Hamiltonian cycle !.! If ! enters clause node Cj , it must depart on mate edge.– thus, nodes immediately before and after Cj are connected by anedge e in G– removing Cj from cycle, and replacing it with edge e yieldsHamiltonian cycle on G - { Cj }! Continuing in this way, we are left with Hamiltonian cycle !' inG - { C1 , C2 , . . . , Ck }.! Set x*i = 1 iff !' traverses row i left to right.! Since ! visits each clause node Cj , at least one of the paths istraversed in "correct" direction, and each clause is satisfied. !11Longest PathSHORTEST-PATH. Given a digraph G = (V, E), does there exists a simplepath of length at most k edges?LONGEST-PATH. Given a digraph G = (V, E), does there exists a simplepath of length at least k edges?Claim. 3-SAT " P LONGEST-PATH.Pf 1. Redo proof for DIR-HAM-CYCLE, ignoring back-edge from t to s.Pf 2. Show HAM-CYCLE " P LONGEST-PATH.12The Longest Path tLyrics. Copyright © 1988 by Daniel J. Barrett.Music. Sung to the tune of The Longest Time by Billy Joel.Woh-oh-oh-oh, find the longest path!Woh-oh-oh-oh, find the longest path!If you said P is NP tonight,There would still be papers left to write,I have a weakness,I'm addicted to completeness,And I keep searching for the longest path.The algorithm I would like to seeIs of polynomial degree,But it's elusive:Nobody has found conclusiveEvidence that we can find a longest path.I have been hard working for so long.I swear it's right, and he marks it wrong.Some how I'll feel sorry when it's done:GPA 2.1Is more than I hope for.Garey, Johnson, Karp and other men (and women)Tried to make it order N log N.Am I a mad foolIf I spend my life in grad school,Forever following the longest path?Woh-oh-oh-oh, find the longest path!Woh-oh-oh-oh, find the longest path!Woh-oh-oh-oh, find the longest path.t Recorded by Dan Barrett while a grad student at Johns Hopkins during a difficult algorithms final.13Traveling Salesperson ProblemTSP. Given a set of n cities and a pairwise distance function d(u, v), isthere a tour of length " D?All 13,509 cities in US with a population of at least 500Reference: http://www.tsp.gatech.edu14Traveling Salesperson ProblemTSP. Given a set of n cities and a pairwise distance function d(u, v), isthere a tour of length " D?Optimal TSP tourReference: http://www.tsp.gatech.edu15Traveling Salesperson ProblemTSP. Given a set of n cities and a pairwise distance function d(u, v), isthere a tour of length " D?11,849 holes to drill in a programmed logic arrayReference: http://www.tsp.gatech.edu16Traveling Salesperson ProblemTSP. Given a set of n cities and a pairwise distance function d(u, v), isthere a tour of length " D?Optimal TSP tourReference: http://www.tsp.gatech.edu17Traveling Salesperson ProblemTSP. Given a set of n cities and a pairwise distance function d(u, v), isthere a tour of length " D?HAM-CYCLE: given a graph G = (V, E), does there exists a simple cyclethat contains every node in V?Claim. HAM-CYCLE " P TSP.Pf.! Given instance G = (V, E) of HAM-CYCLE, create n cities withdistance function! TSP instance has tour of length " n iff G is Hamiltonian. !Remark. TSP instance in reduction satisfies ' -inequality.! d(u, v) = 1 if (u, v) " E 2 if (u, v) # E$ % & Algorithm Design by Éva Tardos and Jon Kleinberg • Copyright © 2005 Addison Wesley • Slides by Kevin WayneBasic genres.! Packing problems: SET-PACKING, INDEPENDENT SET.! Covering problems: SET-COVER, VERTEX-COVER.! Constraint satisfaction problems: SAT, 3-SAT.! Sequencing problems: HAMILTONIAN-CYCLE, TSP.!
View Full Document