Exponential Time Algorithms: Understanding Complexity
Delve into the realm of exponential time algorithms with a focus on CNF-Sat, 3-coloring, and vertex cover problems. Explore the intricacies of clever enumeration and the challenges posed by NP-complete problems. Gain insights into the fascinating world of algorithmics and the nuances of solving complex computational tasks efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Algorithms and Complexity Lecture 6 Introduction to Exponential Time: Clever Enumeration 1
Overview of Today Introduction CNF-Sat 3-coloring Vertex Cover + Definition of FPT Cluster Editing Feedback Vertex Set Subset Sum (extra) 2
Exponential time Many problems NP-complete How fast can solve in worst-case? Sometimes all else fails Exponential time isn t too bad sometimes (FPT) Interesting algorithmics 3
CNF-Sat Recall the definition of CNF-formula literal ??: expression of the type ?? or ??. clause ??: disjunction of literals (e.g. ?? ??) CNF-formula: conjunction of clauses (e.g. ?? ??) k-CNF-formula: all clauses of size at most k Examples: ?1 ?2 ?3 ?4 ?2 ?1 ?2 ?3 ?3 ?5 (k-)CNF-SAT: is the given (k-)CNF-formula satisfiable? n denotes #vars, m denotes #clauses 4
CNF-Sat Easy ?(2???) time algorithm: Footnote: nothing substantially better is known! (the `Strong Exponential Time Hypothesis even states O(1.99n(n+m)c) is not possible). 5
3-coloring in O(2n(n+m)) time k-coloring of G=(V,E): map ?:? {1, ,?} s.t. ? ? ? ? , for every ?,? ?. Not 2-colorable 6
3-coloring in O(2n(n+m)) time k-coloring of G=(V,E): map ?:? {1, ,?} s.t. ? ? ? ? , for every ?,? ?. 2-colorable 7
3-coloring in O(2n(n+m)) time k-coloring of G=(V,E): map ?:? {1, ,?} s.t. ? ? ? ? , for every ?,? ?. 2-colorable 8
3-coloring in O(2n(n+m)) time k-coloring of G=(V,E): map ?:? {1, ,?} s.t. ? ? ? ? , for every ?,? ?. 2-colorable 9
Vertex Cover A vertex cover of G=(V,E) is a subset ? ? such that for every edge ?,? ?, ? ? or ? X. Can you find a vertex cover of size 7 in the graph below? 10
Vertex Cover A vertex cover of G=(V,E) is a subset ? ? such that for every edge ?,? ?, ? ? or ? X. Can you find a vertex cover of size 7 in the graph below? 11
Time Bound and Branching tree We spend at most O(n+m) time per recursive call Recursion depth is at most k Thus, the number of recursive calls is at most k*#non-rec. calls. Let ? ? be #non-rec calls ? 0 = 1 ? ? ? ? 1 + ?(? 1) ? ? 2? Running time: ?( ? + ? ?2?) Depth at most k Number of leaves at most 2k 14
Parameterized Complexity ? + ? ?2? is linear time. As long as k is constant, ? In our example n=27, k=7, 227= 134217728, 27= 128 In general, we can often isolate the exponential dependency of the RT in a parameter that is often small. A parameterized problem is a language ? {0,1} . For an instance ?,? {0,1} ,? is called the input, and ? is called the parameter. A parameterized problem is called Fixed Parameter Tractable (FPT) if there exists an algorithm for it that runs in time ? ? ??, for some constant ? and function ?( ). So, vertex cover parameterized by k is FPT 15
Time Bound and Branching tree We spend at most O(n+m) time per recursive call Recursion depth is at most k Thus, the number of recursive calls is at most k*#non-rec. calls. Let ? ? be #non-rec calls ?(0) = 1 ? ? max ? 2? ? 1 + ?(? ?) ? ? 1.62? Running time: ?( ? + ? ?1.62?) 18
Time Bound and Branching tree We spend at most O(n+m) time per recursive call Recursion depth is at most k Thus, the number of recursive calls is at most k*#non-rec. calls. Let ? ? be #non-rec calls ?(0) = 1 ? ? max ? 2? ? 1 + ?(? ?) ? ? 1.62? Running time: ?( ? + ? ?1.62?) How to guess ? ? 1.62?? Since it s a linear recurrence, ? ? = ?? ?(?) max ?? 1+ ?? 2 ??, Dividing both sides by ?? gives ? 1+ ? 2 1 So for any ? satisfying this, ? ? ??. Use educated guess or a numerical method for finding min ? (there is no easy formula). ? 2 ?? 1+ ?? ? (want) 19
Cluster Editing Given graph G=(V,E), a cluster editing of size k is a set of k `modifications to G, such that each connected component is a clique (cluster graph), modification: addition of deletion of an edge. Models biological questions: partition species in families, where available data contains mistakes NP-complete. Example with k=4: 20
Cluster Editing via induced P3s G is a cluster graph if and only it does not contain an induced ?3 If cluster graph, clearly no induced ?3 If not cluster graph, there are non-adjacent u and x. Let ?,?1, ,? be a shortest path from u to x. Then ?,?1,?2 is an induced ?3. u v w 21
Cluster Editing via induced P3s G is a cluster graph if and only it does not contain an induced ?3 G has cluster editing of size at most k if and only if at least one of the graphs ?,? ?? , ? ,? ?? , ?,? ?? has a cluster editing of size at most k-1. u v w Runs in ?(3??3) time. Usually we focus on f(k): ? (3?) time. ? () suppresses factors poly in input size 22
Feedback Vertex Set via Iterative Compression A feedback vertex set (FVS) of an undirected graph ? = (?,?) is a subset ? ?such that ? ? ? is a forest. In operating systems, feedback vertex sets play a prominent role in the study of deadlock recovery. In the wait-for graph of an operating system, each directed cycle corresponds to a deadlock situation. In order to resolve all deadlocks, some blocked processes have to be aborted. 23
Crux: it helps if we are given a FVS of size k+1 Iterative compression allows us to assume this Iterative compression? Use X to find the minimum FVS of ?[{?1, ,??}]. Write the found FVS to X again 24
Crux: it helps if we are given a FVS of size k+1 Iterative compression allows us to assume this Iterative compression? Use X to find the minimum FVS of ?[{?1, ,??}]. Write the found FVS to X again ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?? 25
Crux: it helps if we are given a FVS of size k+1 Iterative compression allows us to assume this Iterative compression? Use X to find the minimum FVS of ?[{?1, ,??}]. Write the found FVS to X again ?1 ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?? 26
Crux: it helps if we are given a FVS of size k+1 Iterative compression allows us to assume this Iterative compression? Use X to find the minimum FVS of ?[{?1, ,??}]. Write the found FVS to X again ?1 ?2 ?3 ?3 ?4 ?5 ?6 ?7 ?? 27
Crux: it helps if we are given a FVS of size k+1 Iterative compression allows us to assume this Iterative compression? Use X to find the minimum FVS of ?[{?1, ,??}]. Write the found FVS to X again ?1 ?2 ?3 ?4 ?4 ?5 ?6 ?7 ?? 28
Crux: it helps if we are given a FVS of size k+1 Iterative compression allows us to assume this Iterative compression? Use X to find the minimum FVS of ?[{?1, ,??}]. Write the found FVS to X again determines there exists a FVS of G disjoint from W of size at most k. ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?? 29
forest W= X\Y L3: ? is not on any cycle so not relevant L5: the only way to hit the cycle is to pick ? L7: if ? ? = {?,?}, all cycles including ? also include ? and ?. In any FVS ? can be replaced with ?,? Thus we may discard including ? Delete ?, account for the connections via ? by adding ??. w u v v v 30
forest W= X\Y Let ? be leaf in forest with 2 nbs in ? ? if ? has no such neighbor, L3 applies if x has 1 such neighbor, L7 applies. Now decide whether ? is in or not. if it is, simply remove it if it is not, discard by adding to ? Finishes correctness w u x 31
forest W= X\Y Running time: Does not decrease k every time. But surely instance should get easier?! ? + #cc(?[?]) does decrease ? decreases in first branch #cc ? ? in second So as in previous analyses, algo runs in ? 2?+#?? ? ? Total running time: ? (8?). w u x = ? (4?) 32
Subset Sum (extra) Given integers ?1, ,??,? find ? {1, ,?} such that ? X ??= ? {1 2 3 4 5 6 7 8 9 10 11 12}, t= 50 We ll see ? (2?/2) time algorithm here. 2SUM: given ?1, ,??,?1, ,??,? find ?,? such that ??+ ??= ?. We ll see: 2SUM in ?(? lg ? ) time. {1 2 3 4 5 6 7 8 9 10 11 12}, t= 50 33
Subset Sum via 2SUM (extra) Use as follows; suppose ? even. Create an int ??= ? ???for all ? {1, ,?/2} Create an int ??= ? ???for all ? {?/2 + 1, ,?} There exist ?,? with ??+ ??= ? iff there exists ? {1, ,?/2}, ? {?/2 + 1, ,?} such that ? ???+ ? ???= ? (? ? is a solution) 2SUM in ? ?lg? time, ? = 2?/2. 34
Linear Time for 2SUM (extra) j ?1,?2, ,?? 1,?? ?1,?2, ,?? 1,?? If ??+ ??< ? -> increase i, If ??+ ??> ? -> decrease j, If ??+ ??= ? -> solution Declare NO if i or j out of range Linear Search i 35
Linear Time for 2SUM (extra) Clearly correct if it returns true If there exists ?,? such that ??+ ??= ?, consider the first moment where ? = ? or ? = ? say it is ? = ?, since ? < ?, ? will be lowered until ??+ ??= ?. Case ? = ? is similar Clearly run in ?(?lg?) time. 36
Recommended Reading Lectures notes found online 37
