Reduction Worksheet• Hamiltonian Path ≤pHamiltonian Circuit– Transformation R∗ Input to R (graph G = (V, E), an input to HP)∗ Output of R (graph G0= (V0, E0), an input to HC)· V0= V ∪ {x 6∈ V )}· E0= E ∪ {(x, v) | v ∈ V )– Argument that output of R, namely G0, has polynomial size∗ What is the size of G0relative to G?– Yes to Yes argument (if G has a HP, then G0has a HC)∗ Let (v1, v2, . . . , vV) be the HP in G∗ Then is a HC in G0∗ Briefly argue why– Yes from yes argument (or No to No argument) (If G’ has a HC, then G has a HP)∗ Let (x, v1, v2, . . . , vV, x) be the HC in G0∗ Then is a HP in G∗ Briefly argue why1• Hamiltonian Circuit ≤pHamiltonian Path– Transformation R∗ Input to R (graph G = (V, E), an input to what?)∗ Output of R (graph G0= (V0, E0), an input to what?)· Give a possible transformation– Argument that output of R, namely G0, has polynomial size∗ What is the size of G0relative to G?– Yes to Yes argument– Yes from yes argument (or No to No argument)2• Hamiltonian Circuit ≤pBottleneck TSP– Transformation R∗ Input to R· Input to which problem?∗ Output of R· Input to which problem?· Give appropriate details– Argument that output of R has polynomial size– Argue the yes to yes mapping– Argue the no to no (or yes from yes)
View Full Document
Unlocking...