Princeton COS 423 - Sequencing Problems (12 pages)

Previewing pages 1, 2, 3, 4 of 12 page document View the full content.
View Full Document

Sequencing Problems



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

Sequencing Problems

56 views


Pages:
12
School:
Princeton University
Course:
Cos 423 - Interacting With Data
Unformatted text preview:

Hamiltonian Cycle 8 4 Sequencing Problems HAM CYCLE given an undirected graph G V E does there exist a simple cycle that contains every node in V Basic 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 YES vertices and faces of a dodecahedron Algorithm Design by va Tardos and Jon Kleinberg Copyright 2005 Addison Wesley Slides by Kevin Wayne 2 Hamiltonian Cycle Directed Hamiltonian Cycle HAM CYCLE given an undirected graph G V E does there exist a DIR HAM CYCLE given a digraph G V E does there exists a simple simple cycle that contains every node in V directed cycle that contains every node in V Claim DIR HAM CYCLE P HAM CYCLE 1 1 2 2 3 3 Pf Given a directed graph G V E construct an undirected graph G with 3n nodes aout a din d 4 b 4 v e c 5 G bout cout vin v vout ein G NO bipartite graph with odd number of nodes 3 4 Directed Hamiltonian Cycle 3 SAT Reduces to Directed Hamiltonian Cycle Claim G has a Hamiltonian cycle iff G does Claim 3 SAT P DIR HAM CYCLE Pf Suppose G has a directed Hamiltonian cycle Then G has an undirected Hamiltonian cycle same order Pf Given an instance of 3 SAT we construct an instance of DIRHAM CYCLE that has a Hamiltonian cycle iff is satisfiable Construction First create graph that has 2n Hamiltonian cycles which correspond in a natural way to 2n possible truth assignments 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 or reverse of one 5 6 3 SAT Reduces to Directed Hamiltonian Cycle 3 SAT Reduces to Directed Hamiltonian Cycle Construction 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 Construction Given 3 SAT instance with n variables xi and k clauses For each clause add a node and 6 edges C 1 x1 V x 2 V x 3 s clause node C 2 x1 V x 2 V x 3 s x1 x1 x2 x2 x3 x3 t 3k 3 clause node t 7 8 3 SAT Reduces to Directed Hamiltonian Cycle 3 SAT Reduces to Directed Hamiltonian Cycle Claim is satisfiable iff G has a Hamiltonian cycle Claim 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 we are going in correct direction to splice node Cj into tour 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 an edge e in G removing Cj from cycle and replacing it with edge e yields Hamiltonian cycle on G Cj Continuing in this way we are left with Hamiltonian cycle in G 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 is traversed in correct direction and each clause is satisfied 9 Longest Path 10 The Longest Path SHORTEST PATH Given a digraph G V E does there exists a simple t Lyrics Copyright 1988 by Daniel J Barrett Music Sung to the tune of The Longest Time by Billy Joel path of length at most k edges LONGEST PATH Given a digraph G V E does there exists a simple Woh oh oh oh find the longest path Woh oh oh oh find the longest path path of length at least k edges 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 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 The algorithm I would like to see Is of polynomial degree But it s elusive Nobody has found conclusive Evidence 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 1 Is 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 fool If 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 11 12 Traveling Salesperson Problem Traveling Salesperson Problem TSP Given a set of n cities and a pairwise distance function d u v is TSP Given a set of n cities and a pairwise distance function d u v is there a tour of length D there a tour of length D All 13 509 ci ti es i n US w i th a populati on of at least 500 Reference http w w w tsp gatech edu Opti mal TSP tour Reference http w w w tsp gatech edu 13 Traveling Salesperson Problem 14 Traveling Salesperson Problem TSP Given a set of n cities and a pairwise distance function d u v is TSP Given a set of n cities and a pairwise distance function d u v is there a tour of length D there a tour of length D 11 849 holes to dri ll i n a programmed logi c array Reference http w w w tsp gatech edu Opti mal TSP tour Reference http w w w tsp gatech edu 15 16 Traveling Salesperson Problem 8 5 3 Dimensional Matching TSP Given a set of n cities and a pairwise distance function d u v is there a tour of length D HAM CYCLE given a graph G V E does there exists a simple cycle that contains every node in V Basic genres Claim HAM CYCLE P TSP Pf Given instance G V E of HAM CYCLE create n cities with distance function 1 if u v E d u v 2 if u v E 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 …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

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 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?