15-251Great Theoretical Ideas in Computer ScienceforSomeComplexity Theory: Efficient Reductions Between Computational ProblemsLecture 26 (April 21, 2009)A Graph Named “Gadget”K-ColoringWe define a k-coloring of a graph:Each node gets colored with one colorAt most k different colors are usedIf two nodes have an edge between them they must have different colorsA graph is called k-colorable if and only if it has a k-coloringA 2-CRAYOLA Question!Is Gadget 2-colorable?No, it contains a triangleA 2-CRAYOLA Question!Given a graph G, how can we decide if it is 2-colorable?Answer: Enumerate all 2npossible colorings to look for a valid 2-colorHow can we efficiently decide if G is 2-colorable?Else, output an odd cycleAlternate coloring algorithm:To 2-color a connected graph G, pick an arbitrary node v, and color it whiteColor all v’s neighbors blackColor all their uncolored neighbors white, and so onIf the algorithm terminates without a color conflict, output the 2-coloringTheorem: G contains an odd cycle if and only if G is not 2-colorableA 2-CRAYOLA Question!Theorem: G contains an odd cycle if and only if G is not 2-colorableA 3-CRAYOLA Question!Is Gadget 3-colorable?Yes!A 3-CRAYOLA Question!3-Coloring Is Decidable by Brute ForceTry out all 3ncolorings until you determine if G has a 3-coloring3-Colorability Oracle YES/NOA 3-CRAYOLA Oracle3-Colorability Search Oracle NO, orYES here is how: gives 3-coloring of the nodesBetter 3-CRAYOLA Oracle3-Colorability Decision Oracle 3-Colorability Search OracleGIVEN: 3-Colorability Decision Oracle BUT I WANTED a SEARCH oracle for Christmas I am really bummed outChristmas PresentHow do I turn a mere decision oracle into a search oracle?GIVEN: 3-Colorability Decision Oracle Christmas PresentWhat if I gave the oracle partial colorings of G? For each partial coloring of G, I could pick an uncolored node and try different colors on it until the oracle says “YES”Beanie’s Flawed IdeaRats, the oracle does not take partial colorings….Beanie’s FixGIVEN: 3-Colorability Decision OracleLet’s now look at two other problems:1. K-Clique2. K-Independent SetK-CliquesA K-clique is a set of K nodes with all K(K-1)/2 possible edges between themThis graph contains a 4-cliqueA Graph Named “Gadget”Given: (G, k)Question: Does G contain a k-clique?BRUTE FORCE: Try out all n choose k possible locations for the k cliqueThis graph contains an independent set of size 3Independent SetAn independent set is a set of nodes with no edges between themA Graph Named “Gadget”Given: (G, k)Question: Does G contain an independent set of size k?BRUTE FORCE: Try out all n choose k possible locations for the k independent setClique / Independent SetTwo problems that are cosmetically different, but substantially the sameComplement of GGiven a graph G, let G*, the complement of G, be the graph obtained by the rule that two nodes in G* are connected if and only if the corresponding nodes of G are not connectedGG*G has a k-cliqueG* has an independent set of size kLet G be an n-node graphGIVEN: Clique Oracle BUILD:Independent Set Oracle(G,k)(G*, k)Let G be an n-node graphGIVEN: Independent Set Oracle BUILD:Clique Oracle(G,k)(G*, k)Clique / Independent SetTwo problems that are cosmetically different, but substantially the sameThus, we can quickly reduce a clique problem to an independent set problem and vice versa There is a fast method for one if and only if there is a fast method for the otherLet’s now look at two other problems:1. Circuit Satisfiability2. Graph 3-ColorabilityCombinatorial CircuitsAND, OR, NOT, 0, 1 gates wired together with no feedback allowedx3x2x1ANDANDORORORANDANDNOT0111Yes, this circuit is satisfiable: 110Circuit-SatisfiabilityGiven a circuit with n-inputs and one output, is there a way to assign 0-1 values to the input wires so that the output value is 1 (true)?BRUTE FORCE: Try out all 2nassignmentsCircuit-SatisfiabilityGiven: A circuit with n-inputs and one output, is there a way to assign 0-1 values to the input wires so that the output value is 1 (true)?3-ColorabilityCircuit SatisfiabilityANDANDNOTTFXYX YF F FF T TT F TT T TORTFXNOT gate!ORORNOTx y zxyzORORNOTx y zxyzORORNOTx y zxyzORORNOTx y zxyzORORNOTx y zxyzHow do we force the graph to be 3 colorable exactly when the circuit is satifiable?Let C be an n-input circuitGIVEN: 3-colorOracle BUILD:SATOracleGraph composed of gadgets that mimic the gates in C CYou can quickly transform a method to decide 3-coloring into a method to decide circuit satifiability!Given an oracle for circuit SAT you can also quickly solve 3-colorability!Circuit-SAT / 3-ColorabilityTwo problems that are cosmetically different, but substantially the sameFour problems that are cosmetically different, but substantially the sameFACT: No one knows a way to solve any of the 4 problems that is fast on all instancesSummaryMany problems that appear different on the surface can be efficiently reduced to each other, revealing a deeper
View Full Document