Éndagerskurs om [[Kompleksitetsteori]] ved NSM, Fornebu, [[12024-08-08]], av [Daniel Lokshtanov](https://cs.ucsb.edu/people/faculty/daniel-lokshtanov) (bergenser?) ved UC Santa Barbara. TO-DO: Ekstraher notater til [[Eviggrønne notater]]. #### Speaker bio Fra [nettsiden](https://cs.ucsb.edu/people/faculty/daniel-lokshtanov): > Daniel Lokshtanov is a Professor and Vice Chair of Computer Science at UCSB, and a Visiting Professor at the University of Bergen. He received his PhD in Computer Science (2009), from the University of Bergen. Lokshtanov spent two years (2010-2012) as a Simons Postdoctoral Fellow at University of California at San Diego. His main research interests are in graph algorithms, parameterized algorithms and complexity. He is a recipient of the Meltzer prize, the Bergen Research Foundation young researcher grant, and of an ERC starting grant on parameterized algorithms. He is a co-author of the [Parameterized Algorithms](http://parameterized-algorithms.mimuw.edu.pl/) book and the [Kernelization](http://kernelization.ii.uib.no/) book. #### Time 1 Vil ha *korrekte* og *effektive* algoritmer. Eksempel på problem: *Room scheduling* (lag notat?) - Oppgave: Gitt mengde med ønskede aktiviteter, velg maks antall som ikke overlapper. - "What should a program do such that it outputs the maximum number of pairwise *compatible* (i.e. disjoint) activities?" - Trivial solution of listing all possible subsets and picking the largest one is obviously exponential ($T = 2^n \cdot n^2$). - Efficient solution: - Sort activities from lowest end-time to highest end-time ($b_i$, where activity $i$ lasts from $a_i$ until $b_i$). Time: $n \log n$. - Set solution $S = \emptyset$, and let the set of "active" (or "possible") activities be $A = \{1, \dots, n\}$. - While $A \neq \emptyset$: - Let $i = $ minimum element i n $A$ - Add $i$ to $S$ - Remove from $A$ all activities that are not disjoint from activity $i$. - Return $S$. - Runtime analysis of naive implementation: for each iteration of the loop, the size of $A$ is decreased by *at least* one (namely activity $i$), and so there are at most $n$ iterations. Meanwhile, inside the loop there are $n$ checks that need to be made for disjointness. Therefore, $T = O(n^2)$. - (*However*, there is a way to do this in linear time. Left as an exercise for the reader.) - So obviously faster than trivial solution, but correctness is less clear: - Loop invariant: $S$ and $A$ are always disjoint. - Let $S$ be output by the algorithm. Then $\forall i \leq n, \exists j \in S$ such that $b_j \in [a_i, b_i]$ (but not necessarily vice versa? I.e. $b_i \in [a_j, b_j]$. See pictorial representation and have a think). That is, every endpoint overlaps with the interval of some rejected activity. - In essence: At some point, every activity goes from being active to being inactive. - Proof by pigeonhole principle. (The details escaped me.) Second problem: *System of linear equations* - Variables take on real values. - Gaussian elimination: $T = O(n^3)$ - (Are more efficient alternatives too.) - What about other kinds of systems of equations? Third problem: *Satisfiability* - Variables take values T or F - Coefficients are now identity and negation (corresponding roughly to positive and negative signage) - Plus is replaced by $\lor$, times is replaced by $\land$. - Right-hand-side is always T. - Problem: *Is there a way to set the variables such that the equation is satisfied?* - 1-SAT: Trivially solved - 2-SAT: Efficient solution via "variable elimination" (*can* actually be solved in *linear* time): - ![[IMG_7977.jpeg]] - ... and then there is an efficient reduction between $\phi$ and $\phi_x$, i.e., the latter has a satisfying assignment iff the former has a satisfying assignment (and either can furthermore be efficiently found). - Elegant proof. - Algorithm: If both X and not-X are clauses, return UNSAT. If X is clause, set X to T. Else if not-X is clause, set X to F. Else, eliminate X. - Running time: $O(n^2)$ if a little careful! Can do $O(n+m)$ using other methods (where $n$ is the number of variables and $m$ is the number of clauses—which is optimal, as you need to at least *read the input*). - Reason this doesn't work for 3-SAT: number of new clauses now grow exponentially? #### Time 2 - $\exists$ problems for which there are *provably* no efficient solution. - However, for most *interesting* problems: - no efficient solution known - can't prove no efficient solution exists - But things are not so bad if you make a small leap of faith and believe that: - *3-SAT has no efficient algorithm.* - This is just saying P $\neq$ NP. - Reason why 2-SAT solution doesn't work: the backwards direction doesn't work. Eliminating a variable leads to two new variables (?), so we get an exponential blow-up of variables (? did he mean clauses?). Algorithm is still correct though, it will just take exponential time. - *Bigger* leap of faith: ETH (Exponential Time Hypothesis), i.e. 3-SAT *requires exponential time to solve*. - Good reasons to believe this too. - Specifically: $\exists c > 1$ s.th. 3-SAT requires $T = O(c^{n+m})$. Fourth problem: System of linear *inequalities* - (Note, *just* having $\leq$ is equally powerful as having all of $\leq, \geq, =$.) - Problem known as *Linear Programming* (LP) (... why? historical reasons?) - This problem is *poly-time solvable*, though we will not look at the algorithms. (They're complicated.) - (But if you need it just use pip install scipy -> scipy.lpsolve. Others: Gurobi, Cplex, HiGHS.) - LPs are *really* versatile. (There are companies whose whole business model is formulate real-world problems as LPs and sell the solution back to the customer.) - Can e.g. use them to solve Sudokus! - For every $0 \leq X_{i,j,k} \leq 1$, where $X_{i,j,k}=1$ if number is filled, where $i,j$ are rows/columns and $k$ is ... the relevant number? - Each cell is filled exactly once: $\forall i,j: \sum_k X_{i,j,k} = 1$ - ... and likewise for rows and columns, where the sums go over $i$ and $j$, and for every cell (which is a more complicated sum to write down). - a) If Sudoku has solution, then this LP problem has solution. - True. - b) Claim: If LP problem has solution, then Sudoku has solution. - False! E.g., start with blank puzzle and set every variable to $1/9$. - Solution: require integer solutions - -> *Integer Linear Programming* (ILP) - Good news, many LP solvers also work well for ILP: - Convert Sudoku puzzle to ILP instance - Run ILP solver - Use solution to extract Sudoku solution - ... but this solution is not poly-time, because *ILP is NP-hard*. - But *on many instances* it will actually be efficient. Just not on *all*. - Proof: reduce ILP to 3-SAT. - 3-SAT to ILP: variables stay variables, F/T becomes 0/1. - Clauses like $(x_1 \lor \neg x_3 \lor x_{10})$ become $x_1 + (1-x_3) + x_{10} \geq 1$, etc. Fifth problem: Independent set - Input: graph G, size $k$. - Question: is there a set $S$ of size $k$ such that there are no edges between any of the members of $S$? - Again NP-hard by reduction to 3-SAT. - Make a graph where the options $x_i = T$ and $x_i = F$ are represented by a node each, with an edge between the two. - Then for every clause, e.g. $(x_1 \land x_2 \land \neg x_{10})$, draw a triangle where each node represents one of the variables in the clause. - Finally, draw edges between nodes with equal labels. - Then a satisfying assignment gives you an independent set of size $k = n + m$. - Reverse direction, just read off the solution from the independent set. - Note: do *not* need to show that every graph encodes a 3-SAT instance—the *assumption* is that there exists an algorithm that solves *every* Independent set instance, and so it is *sufficient* to show that every 3-SAT instance can be turned into a graph to be solved by the assumed efficient algorithm. - Note that reductions are transitive—can string reductions together. - Nice book from late 70s: *Computers and Intractability*. Compendium of first few hundred known NP-complete problems. Sixth problem: Vertex cover - Input: graph G, size $t$ - Question: is there a set of vertices $S$ of size *at most* $t$ such that every edge of G has at least one endpoint in $S$? - Reduce Independent set to Vertex cover: Assume Vertex cover has solution; show that then Independent set has solution. - The solution of one is just the complement of the solution of the other: if $S$ is a vertex cover, then the remaining nodes form an independent set, and vice versa. - ... where $t = n - k$. - Independent set is NP-hard -> vertex cover is NP-hard. - Now, can you give a reduction from Activity Selection *to* Independent Set? - Activities are vertices, and edges go between vertices that overlap. - Does that mean Activity Selection is NP-hard?? - No: Wrong direction. If you can solve Independent Set then you can solve Activity Selection ... obviously. (If you can solve NP-hard problems then you can solve problems in P.) - Easy mistake to make if you're not careful. #### Time 3: Approximation algorithms Unless P = NP, no algorithm finds: 1. minimum size vertex covers 2. for *all* instances 3. in polynomial time But what about finding .... 1. *pretty small* vertex covers 2. for all instances 3. in polynomial time But what does "pretty small" mean? Let OPT(G) = min size of a vertex cover of G. Note: if you can compute OPT(G), then you can efficiently *find* a vertex cover of size OPT(G)! (Also note that OPT(G) is perfectly well-defined, just hard to compute.) Theorem: There is an (greedy) algorithm that takes as input a graph G, runs in poly-time, and outputs a vertex set S such that 1. S is a vertex cover of G, and 2. $|S| \leq 2\ \cdot$ OPT(G) (call this a "2-approximation algorithm") Algorithm: - $S = \emptyset$, $i = 0$ - while exists edge $e_i$ with both ends $(u_i, v_i)$ outside $S$: - add $u_i$ and $v_i$ to $S$ - return $S$ Runtime analysis: - adds at least two vertices per iteration - hence terminates in time $\leq n/2$ - -> poly-time (linear, in fact) ... but how do you prove that $|S| \leq 2\ \cdot$ OPT(G)?? - (presented elegant counting argument) Natural question: is this bound *sharp*, i.e., are there instances such that the solution of the algorithm is *actually* twice that of the optimum? A: Yes, e.g. the graph of all parallell edges. Known: - No 1.9999-approx algorithm for this if you believe the Unique Games Conjecture(?) - No 1.4-approx algorithm for this unless P = NP (?) Ok now let's modify the problem by letting the vertices be *weighted*. Can we get a 2-approx algorithm for *weighted VC*? - Solved by Integer Linear Programming! - ... but ILP is NP-hard. - Solution: Just use LP instead. - But now you get real values, which is nonsensical (where 0 is supposed to mean "is not in set" and 1 is "is in set"). - Just round the solutions to the nearest answer. Then the solution is a vertex cover. - ... and (via elegant argument again), weight $\leq 2 \cdot \text{OPT}_{\text{LP}}$! - This is actually a general approx-algorithmic design strategy: - given problem instance I - formulate ILP for I - solve the LP relaxation - use solution to LP-relaxation to get "good" solution to I. Independent set (again): - independent set of points (where edges are replaced by euclidean distances) - independent set of points is NP-hard - *however*, this has a 1.01-approx algorithm (or "any number of zeroes as you would like") - meaning output $S$ of size 0.99(999...) $\cdot$ OPT(G). - something about cutting the plane up in 1000 strips of width 1 each (and then start counting again modulo 1000) - then $\exists i$ such that strips labelled $i$ contain a thousandth of the number of points in the optimum solution - and then do the same thing horizontally, so we get $1000 \times 1000$ boxes - key observation: *the optimum value of the solution is constant* (even if it is unknown) - ... split each box in two. at most one point per box (?) - can solve each box in time $n^{2000^2}$ – which is polynomial time! - using dynamic programming we can get this down to $n^2000$. - (Can also show that, assuming ETH, this is optimal—i.e. $T \approx n^{1/\varepsilon}$ for solutions within factor $(1-\varepsilon)$ of the optimum.) Seventh problem: Closest string - Input: strings $s_1, s_2, ..., s_n$, all of the same length $L$. - Hamming distance: $d(s_1,s_2) =$ number of positions $i$ such that $s_1[i] \neq s_2[i]$. - Task: Find a "center" string $c$ of length $L$ minimizing ERROR: NOT THE FOLLOWING $\sum_{i = 1}^n d(s_i, c)$ BUT RATHER: *max* (for $i$ from 1 to n) of $d(s_i, c)$. - (The first thing is easily solvable by just choosing the most common symbol of the alphabet for each position of the string. Pointed out towards the end—might have to change below notes correspondingly.) - If $c$ is one of the input strings, then this is efficiently solvable. - Otherwise: NP-hard - *But* has an easy 2-approximation algorithm! - (Suggestion from the audience: pick the most common character at each position. Might work? He is unsure, "probably but I can't prove it off the top of my head".) - If $c'$ is the optimum, value is OPT, then $\exists s_i$ such that $d(s_i, c') \leq \frac{\text{OPT}}{n}$. - But then we can use the triangle inequality: $\sum_j d(s_j, s_i) \leq \sum_j d(s_j, c') + d(c', s_i) \leq \text{OPT} + n \cdot \frac{\text{OPT}}{n} = 2 \cdot \text{OPT}$. - Can we do better? Yes! Use ILP. Once again leads to a $n^{1/\varepsilon}$ style solution. - For every position $1 \leq p \leq L$ - and every letter $\alpha \in A$ - variable $x_{i,\alpha} = 1$ if $c[i] = 2$ - $\forall p: \sum_{\alpha \in A} x_{p,\alpha} = 1$ - Note: $d(c, s_i)$ is intuitively $\sum_{p = 1}^L \sum_{\alpha \neq s_i[p]} x_{p, \alpha} \leq d$ for some $d$. And then $\forall i$ we have this latter inequality, and we want to minimize $d$. - This is an ILP. Solve it (as before) by treating it as an LP. Get some solution like $x_{1,A} = 1/2, x_{1,B} = 1/4, x_{1,C} = 1/8, x_{1,D} = 1/8$. - This will always sum to one. Squint and it looks like a probability distribution—so let's treat it like one! - For each position p, set $c[p] = \alpha$ with probability $x_{p,\alpha}$. - basically "randomized rounding" - Then $\forall i$, the *expected* distance between $c$ and $s_i$ is $\sum_{p = 1}^L \sum_{\alpha \neq s_i[p]} x_{p, \alpha} \leq d = \text{OPT}_\text{LP}$. - Q: Why does this not give you the optimal solution? A: Because even though this expectation holds for every string, you still expect that *some* of the outcomes will deviate (but not by much!) - Via Chernoff's bound you get that this is a $(1+\varepsilon)$ approximation algorithm *unless* $n$ is exponentially large in OPT. #### Time 4: Exact and Parameterized Algorithms *Now we're getting to the meat of things.* Vertex cover (again) - NP-hard: no algorithm finds *optimal* solutions to *all* instances in *poly* time - approx algorithm: relax "optimal" - parameterized algorithm: relax "all" - exact algorithm: relax "poly". (might have to settle with exponential, but exponential *can* be much better than $2^n$.) **Exact:** - Let $\text{ALG}(G)$ be the exact algorithm returning the best vertex cover of G: - if G has no vertex of degree at least 2 - return $\text{ALG}_1(G)$ - observe: for any graph G, vertex v, cover S, *either* v is in S *or* every neighbour of v (N(v)) is in S. - (assume at least one vertex has degree at least 2; otherwise the problem is easily solveable) - let $S_1 = \{v\} \cup \text{ALG}(G-v)$ - let $S_2 = N(v) \cup \text{ALG}(G-N[v])$ - return smallest of the two - Recursive calls! - Let $T(n)$ be number of final calls to $\text{ALG}_1(G)$ - (Then final runtime is $T(n)$ times some polynomial factor) - By inspection: $T(n) \leq T(n-1) + T(n-3)$ - Claim: $T(n) = 1.47^n$ - Proof by induction. (The number 1.47 is roughly the smallest number such that $1/x + 1/x^3 \leq 1$.) - $\approx 2^{n/2}$—so you can now handle double the size of instances - After a series of improvements someone in 2013 found a $1.199^n$-time algorithm. - Due to ETH combined with earlier *linear* reduction, we know that we can not keep improving this indefinitely. **Parameterized:** - Let $k$ be the size of the vertex cover. - What if $k$ is much smaller than $n$? - Want to exploit $ks smallness. Brute-force solution: $n^k$. Not very satisfactory. - Can we get something like $2^k n$ instead? - Yes! Algorithm is similar to above: - let $\text{ALG}(G,k)$ be the exact algorithm returning the best vertex cover of G: - if $k < 0$, refuse - if G has no vertex of degree at least 2 - return $\text{ALG}_1(G,k)$ - observe: for any graph G, vertex v, cover S, *either* v is in S *or* every neighbour of v (N(v)) is in S. - (assume at least one vertex has degree at least 2; otherwise the problem is easily solveable) - let $S_1 = \{v\} \cup \text{ALG}(G-v,k-1)$ - let $S_2 = N(v) \cup \text{ALG}(G-N[v],?)$ - Now have $T(k) \leq T(k-1) + T(k-2)$ - Running time is then bounded by $T(k) \cdot \text{poly}(n)$ (og hvis man er forsiktig kan man få den polynome faktoren ned til $n + m$). - Proof by induction as before, and what we get is $1.618^k$. -> The golden ratio! - (Best known is better, at $1.25^k$ or something like it.) - Other problems?? - ILP with $k$ variables can be solved in $(\log k)^{O(k)}$ time Recommended further reading: - Parameterized algorithms – book by "yours truly" - Approximation algorithm book, Design of Approximation algorithms - Complexity book: Sipser, used at UiB's complexity course etc.