advertisement

advertisement

Information about The Exponential Time Hypothesis

advertisement

“Easy” for small values of the parameter An O(nk) algorithm exists. Fixed-Parameter Tractable: f(k)poly(n) As hard as solving Clique

We are going to focus on problems that have O*(kk) algorithms, ! but are not expected to have O*(2o(k log k)) algorithms.

Input A graph over the vertex set [k] x [k]. Is there a clique that picks one vertex from each row, Question and one vertex from each column? Permutation Clique

Input A graph over the vertex set [k] x [k]. Is there a clique that picks one vertex from each row, Question and one vertex from each column? Permutation Clique

Unless ETH fails, there is no algorithm that solves Permutation Clique in 2o(k log k) time.

Input A family of subsets over the universe [k] x [k]. Is there a hitting set that picks one vertex from each row, and one vertex from each column? Permutation Hitting Set Question

Permutation Clique Permutation Hitting Set Permutation Clique

Permutation Clique Permutation Hitting Set Permutation Clique

Permutation Clique Permutation Hitting Set Permutation Hitting Set

Permutation Clique Permutation Hitting Set Every Clique is in fact a hitting set too.

Permutation Clique Permutation Hitting Set Every Clique is in fact a hitting set too.

Permutation Clique Permutation Hitting Set Every Clique is in fact a hitting set too.

Permutation Clique Permutation Hitting Set Every Clique is in fact a hitting set too.

Input A family of subsets over the universe [k] x [k], such that every set has at most one element from every row. Is there a hitting set that picks one vertex from each row, and one vertex from each column? Question Permutation Hitting Set With Thin Sets

Input n strings, x1, x2, …, xn of length L each over an alphabet A, and a budget d. Is there a string of length d over A whose hamming distance from each xi is at most d? x1 … x2 xn Closest String Question

Input n strings, x1, x2, …, xn of length L each over an alphabet A, and a budget d. Is there a string of length d over A whose hamming distance from each xi is at most d? x1 … x2 xn Closest String Question

A family of subsets over the universe [k] x [k], such that every set has at most one element from every row. Is there a hitting set that picks one vertex from each row, and one vertex from each column? Permutation Hitting Set With Thin Sets

A family of subsets over the universe [k] x [k], such that every set has at most one element from every row. Is there a hitting set that picks one vertex from each row, and one vertex from each column? 132♠♠ 1 Permutation Hitting Set With Thin Sets

A family of subsets over the universe [k] x [k], such that every set has at most one element from every row. Is there a hitting set that picks one vertex from each row, and one vertex from each column? 132♠♠ 1 4♠3555 Permutation Hitting Set With Thin Sets

A family of subsets over the universe [k] x [k], such that every set has at most one element from every row. Is there a hitting set that picks one vertex from each row, and one vertex from each column? 132♠♠ 1 4♠3555 ♠6543♠ Permutation Hitting Set With Thin Sets

A family of subsets over the universe [k] x [k], such that every set has at most one element from every row. Is there a hitting set that picks one vertex from each row, and one vertex from each column? 132♠♠ 1 4♠3555 ♠6543♠ ♠♠♠♠12 Permutation Hitting Set With Thin Sets

A family of subsets over the universe [k] x [k], such that every set has at most one element from every row. 111111 Is there a hitting set that picks one vertex from each row, and one vertex from each column? 333333 444444 555555 666666 222222 132♠♠ 1 4♠3555 ♠6543♠ ♠♠♠♠12 Permutation Hitting Set With Thin Sets

Permutation Hitting Set with Thin Sets is unlikely to admit a 2o(k log k) algorithm. Closest String is unlikely to admit a 2o(d log d) algorithm. Closest String is unlikely to admit a 2o(d log |A|) algorithm.

Input A graph over the vertex set [k] x [k]. Is there a clique that picks one vertex from each row? Question [k]x[k] Clique

Unless ETH fails, there is no algorithm that solves 3-Colorability in 2o(n) time.

Unless ETH fails, there is no algorithm that solves 3-Colorability in 2o(n) time. Unless ETH fails, there is no algorithm that solves [k]x[k] Clique in 2o(k log k) time.

No 2o(k) algorithm. A 2(k log k) algorithm.

A 2(k log k) algorithm.

A 2(k log k) algorithm.

Unless ETH fails, there is no algorithm that solves 3-Colorability in 2o(n) time. Unless ETH fails, there is no algorithm that solves [k]x[k] Clique in 2o(k log k) time.

3-Colorability [N] [k]x[k] Clique Reduce 3-COL to [k]x[k] Clique, and suppose n —> k* ! Run a 2o(k* log k*) algorithm. ! This should be a 2o(n) algorithm.

3-Sat [N] Edge Clique Cover [k] Reduce 3-SAT to Edge Clique Cover, and suppose n —> k* ! Run a 2 o(2k ) algorithm. ! This should be a 2o(n) algorithm.

3-Colorability for a graph with N vertices reduces to [k]x[k] Clique with k = O(N/log N).

2N k= log3 N V1 V2 … Vk

2N k= log3 N V1 V2 … All possible 3-colorings of the Vi’s. Vk

2N k= log3 N V1 V2 … Vk Add edges between compatible colorings…

Clique does not admit a f(k)no(k) algorithm unless ETH fails, for any computable function f. Specifically, if W[1] = FPT, then ETH fails.

Exponential Time Hypothesis [ETH] 3-SAT cannot be solved in 2o(n+m) time.

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo ...

Read more

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo ...

Read more

The Exponential Time Hypothesis and the Parameterized Clique Problem Yijia Chen1, Kord Eickmeyer2?, and J org Flum3 1 Department of Computer Science ...

Read more

Lecture 14 (25.01.2013) Author: Marcin Wrochna Strong Exponential Time Hypothesis 1 Motivation The Exponential Time Hypothesis gives us lower bounds of the ...

Read more

An algorithm is said to take linear time, or O(n) time, if its time complexity is O(n). ... The exponential time hypothesis (ETH) is that 3SAT, ...

Read more

In computational complexity theory, the exponential time hypothesis is an unproven computational hardness assumption that was formulated by Impagliazzo ...

Read more

Can we improve the exponents? • Is k-SAT always in 2 ±npoly(m) time for a universal ±< 1 ? Let SETH be the hypothesis that the answer is “no”

Read more

In parameterized complexity there are three natural definitions of fixed-parameter tractability called strongly uniform, weakly uniform and nonuniform fpt.

Read more

Lower bounds based on the Exponential Time Hypothesis Daniel Lokshtanov Dániel Marxy Saket Saurabhz Abstract ...

Read more

## Add a comment