Unformatted text preview:

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

Princeton COS 423 - Sequencing Problems

Download Sequencing Problems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Sequencing Problems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Sequencing Problems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?