Insights into Advanced Algorithmic Problems
Delve into discussions surrounding complex algorithmic challenges, such as the limitations in solving the 3-SAT problem within specific time bounds, the Exponential Time Hypothesis, proving lower bounds for algorithms in various scenarios, and exploring approximation ratios in algorithm design. These insights touch upon crucial topics in computational complexity theory and highlight the interplay between theoretical assumptions and algorithmic performance.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Talks on parts of 4 papers. 1) M. Hajiaghayi, Khandekar and K. 2) M. Cygan, K 3) R Chitnis, M. Hajiaghayi, K 4) M. Hajiaghayi, K and some students of M. Hajiaghayi
The 3-SAT problem with n variables and m clauses can not be solved in time 2o(n) Due to Impagliazzo, Paturi and Zane. FOCS 1998. Do you think its false? Lemma of Calabro, Impagliazzo and Paturi: The 3-SAT problem with n variables and m clauses can not be solved in time 2o(m) This is called the Sparsification Lemma.
What can we prove under the Exponential Time Hypothesis? Many problems have optimum running time algorithms under this assumption. We later present such a result in connectivity. Tight lower bound that uses the Exponential Time Hypothesis
How can we prove that there is no f(k) poly(n) algorithm for Clique? The assumption of P=NP implies that f(k) is polynomial in n. show Clique FPT we need to show P NP. Instead: assume the much stronger ETH assumption. To
If you want approximation ratio of for some problem what is the best possible running time? You need to do two things First give an approximation ratio of in some time t(n). Then show that approximation of , with time better than t(n) would contradict the ETH. We start with this.
In approximation algorithms I do not think somebody tried to show that in linear time you can not get better than 2 ratio for Vertex Cover. Should we create a new subject? If its possible to prove such things. Using the ETH this may be possible. Needs knowledge far from FPT. Needs a knowledge of almost linear PCP and about gap reductions and about deep theorems in Inapproximability theory. See more later.
s 6 3 1 1 2 1 1 4 6 3 1 3 2 4 5 4 2
Optimum solution with all terminals s 3 1 1 2 1 1 3 4 2
A very important problem in Approximation Algorithms. Key for other problems. This problem is FPT by the cost of the optimum solution. It admits n for every . In the next slide I will give the correct credit for this result. Never done.
The best approximation algorithm for the problem was designed in SODA 1997 by K,Peleg. The credit (by mistake) is given to Charikar et al. Implies ratio f( ) n for any . In SODA 1998 Charikar et al used the same algorithm. Said explicitly that Implies ratio f( ) n for any for the Directed Steiner tree. Charikar et al: better f( ) term. Charikar et al also implied that the problem has log3 n ratio, time quasi-polynomial in n.
At the time such an algorithm was considered as a sign that a polynomial polylogarithmic approximation exists. A paper by Chandra Chekuri and Martin Pal: under the ETH, P Quasi-P Conjecture (Kortsarz): Under the ETH there is no polynomial time polylogarithmic ratio approximation for the Directed Steiner Tree problem.
It turns out that linear reductions are crucial for Fixed Parameter Inapproximability. This is known for quite some time. This means a reduction from SAT with m cluases and n variables that creates a gap. The size of the instance of the new problem is O(m+n) Unfortunately, if the ETH is correct there are almost no linear reductions.
Unfortunately, a linear reduction from PCP to Set-Cover implies that ETH fails. If we had that we could show that Set-Cover admits no (r(k),t(k)) FPT-approximation for any r,t. There is a linear reduction from SAT to Clique. This does not help because first we need to do a gap reduction from SAT to 3- SAT.
SAT with n variables and m clauses. An almost linear reduction is a reduction to Label-Cover of size m1+o(1) Known (Dinur). Reduction of size m polylog(m) to Label-Cover, gap 2. The projection game conjecture: Moskowitz: Reduction to Label-cover of size m 2 log1- m but gap nc for some c.
W[1]-Hard problem. nratio approximation This problem is clearly finding a Directed Steiner tree and a reverse directed Steiner tree. The Directed Steiner Tree problem is FPT when parameterized by the optimum solution A rare case in which FPT time improves drastically the approximation ratio. As we saw, ratio 2 is possible in time t(k) poly(n). Due to Chitnis, Hajiaghayi, K.
M. Cygan, K If you want a ratio of ln n/2 the time required is roughly 2sqrt{n} log n Using the ETH we show that this time is optimal(the exponent can not be o(sqrt{n})).
The upper bound is designing an algorithm. The problematic part is the lower bound. Relies on Almost Linear PCP, Projection Game conjecture. Different kind of knowledge. Maybe because of that I found very very few results of this kind.
In this paper we define a new way to use the known definition for Fixed Parameter Inapproximability. We call this method inapproximability in opt The definition requires k=opt(I) for some I. The definition was heavily influenced by talks with Cygan and Marx.
Since approximation is in opt, inapproximability should also be in opt. This is the logical counter statement. We were trying to avoid reduction under FPT W[1], FPT W[2]. The ETH implies both statements above. Far reaching consequences.
ETH implies FPT W[1], FPT W[2]. We are given that no time t(k) is enough. The value is usually k versus k+1 for minimization. Hard to get strong hardness. The proof above reduces k below any given function. Thus k is not related to any opt(I).
However, if approximation in opt why not inapproximabiliy in opt? Also our definition does not throw all problems in the same bin. Does not seem logical that all prolems behave the same. Completely different problems. By our definition we get a much richer behavior. Each problem, its own behavior.
Start with SAT. A yes instance goes to value X for our problem. A no instance goes to value larger than X, >1 for our problem. Important: can produce huge gaps, solving the k versus k+1 issue.
Polynomial algorithm with ratio implies P=NP A approximation algorithm with running time 2o(m+n) implies that the ETH fails.
A good ((opt), t(opt)) ratio needs gap preserving reduction that makes opt very small. Not well understood. We gave the first super exponential time inapproximability for Clique and Set Cover. In fact for Clique Almost doubly exponential.
FPTW[1], FPT W[2] does not imply anything on the optimum solution of any instance. The problems are not thrown in the same bin. In fact for every problem we check what kind of gap reduction do we have? For every problem: is there a gap preserving (increasing, slightly decreasing) reduction that makes opt very small? The latter is the new technical challenge.
It looks for simple variants of Directed Steiner Network that can be solved exactly. Its seem that there are not many. The lower bounds do not use almost linear PCP but rather something standard in FPT theory.
Let the vertices be 1,2,..,n Given G(V,E) and a demand dij for every i and j (could be 0) and cost c(e) for every e. The goal is to select a subgraph G(V,E ) so that there are dij edge disjoint paths from i to j (separately). Use minimum cost. Hopeless problem to approximate. For Directed Steiner Forest: Feldman,K,Nutov gave an O(n3/4) ratio. But that is it. What are the simplest solvable cases?
Given a graph G(V,E) with unit costs (makes a difference!) and a root s output minimum cost subgraph that contains 2 edge disjoint paths from s to the other terminals. Our usual trick (Set Families, Uncrossable, Weakly Super Modular functions, Laminar Basic Feasible solution The idea of starting with and then add edges to give two paths from to all vertices seems to badly fail. Super Modular functions, Laminar Basic Feasible solution) do not work. The idea of starting with Directed Steiner tree and then add edges to give two paths from s s to all vertices seems to badly fail. ) do not work. Directed Steiner tree
Given a DIRECTED graph G(V,E) and two nodes s and t find a minimum cost graph so that there is a path from s to t and from t to s The paths may not be edge disjoint. Minimize the number of vertices in the solution (reduction from the edge case). We generalize this problem, and gave a tight upper lower bound on the time. Even the solution of the above non trivial.
We will have two tokes both in s. One tokens, f goes on edges in the regular way. This creates the path from s to t. A second token called b goes in the wrong direction. This token would create a path from t to s. Bring the two tokens from (s,s) to (t,t). Due to Jon Feldman.
Token f moving forward (u,x) (v,x) for an edge with (u,v). Token b moves backward (creating an t to s path): (x,u) (x,v) for the edge (v,u) adding a back edge in the path from t to s. If both tokens reach t in the best way, we solved the problem.
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) (t,y)
Edges : (s,q), (q,p), (p,x), (x,t) (r,u) (r,y) (u,t), (r,u), (y,r), (t,y) ,(p,x) (s,u) (s,s) (p,u) (p,r) (x,r) (t,t) (t,r) (q,u) q p s x t (t,y) s u r y t
At the moment we enter a vertex, this vertex is declared a dead vertex. At every moment there must be a path from the location of f to t using live vertices. And there must be a back path from b into t of live vertices.
The backward needs x. The forward needs y. s f x b y t
The following three paths must exist: s f b x y t
This contradicts f needing y to get to t. s f b x y t
We now move (x,y) to (y,x). Clearly a must. s f b x y t
We move from (x,y) to (y,x) but with one edge. s b f x y alive alive t
We make the graph with all pairs vertices and edges as discussed. We add edges from (x,y) to (w,y) with cost c: the cost of the shortest path from x to w. Since direct edge move, dead vertices do not present a problem. We apply the Dijkstra s algorithm to find the shortest path on the graph of pairs, finding the optimum
