Exponential Time Paradigms in Algorithmic Studies

Exponential Time Paradigms Through the Polynomial Time Lens Presented at ESA 2016 Andy Drucker, Jesper Nederlof and Rahul Santhanam

General Pattern of Scalability Given more resources, solutions become more complex Poor man s solution Rich man s solution (Exponential time) (Polynomial time) Known exponential time algorithms mostly use algorithmic paradigms from P-time algorithms Program: Formalize such paradigms and study their power and limitations

Paradigms in exp. time / FPT algorithms Preprocessing (+brute-force) Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, some models studied Dynamic Programming Often applied; several models studied New consequences New LB s New model New model + reductions

Paradigms in exp. time / FPT algorithms Preprocessing (+brute-force) Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, some models studied Dynamic Programming Often applied; several models studied

Paradigms in exp. time / FPT algorithms Preprocessing (+brute-force) Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Strengths: Contains poly time algorithms (poly time `for free ) Lower bounds under hypothesis concerning PTIME General template to give LB s (OR/AND-composition)

Paradigms in exp. time / FPT algorithms Preprocessing (+brute-force) Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, some models studied Dynamic Programming Often applied; several models studied

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) Poly time algo s without false positives but if given YES- instance, return YES with exponentially small success prob Example: Given graph and int ?, finding ? vertices incident to all edges by picking random endpoints of uncovered edges: success prob. ? ? for Vertex Cover (VC) success prob. ? ?(?)equivalent* with f(k)-bit witnesses E.g. VC has verifiers accepting certificates of length k Backwards trivial, forwards requires hashing ideas (PP) *modulo randomness

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13) Strengths: Contains poly time algorithms (poly time `for free ) Generalizes (OR) kernelization (but not compression) Lower bounds under hypothesis concerning PTIME Many algorithms captured by this model Not well studied yet: we further explore this here All our lower bounds build on D 13

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13) Drucker 13: Let ? be NP-hard. If for ? = ? ? ????(?), there exists algo taking as input ?1, ,?? ? that outputs ?1, ,?? {0,1} such that Pr ?:?? ? ?? 2o ?.Then ?? ????/????. {0,1}? ?, Drucker 13: If an algo, given a satisfiable n-var CNF, constructs satisfying assignment with prob. 2 ?1 (1),?? ????/????.

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13) Lower bound Example Suppose there is a poly algo that, given planar graph on ? vertices, outputs a maximum independent set with probability exp( ?1 ?) for some ? > 0. Then ?? ????/????. Easily obtained from Drucker 13 (one can get probability exp( ?/ log?)) (exp( ?) time algorithms exist)

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13)

Paradigms in exp. time / FPT algorithms Branching / Bounded Search Tree Very often applied (implicitly), several models studied Modelled by One-sided Probabilistic Poly algo s(PP 10) LB s assuming ?? no subset of ????/????(D 13) Theorem If a parameterized problem (Q,k) has an AND-composition*, and witnesses* of size polynomial in k, ?? ????/????. * the actual statement requires mild additional constructivity conditions.

Theorem If a parameterized problem (Q,k) has an AND-composition*, and witnesses* of size polynomial in k, ?? ????/????. * the actual statement requires mild additional constructivity conditions.

Theorem If a parameterized problem (Q,k) has an AND-composition*, and witnesses* of size polynomial in k, ?? ????/????. * the actual statement requires mild additional constructivity conditions. all known AND-compositions are constructive indicates problems admitting AND-compositions* do not admit polynomial OR-kernelizations* Cor: Suppose there is a poly time algorithm that, given path decomposition of ? of width ? outputs a max. IS with probability 2 ????(?), then ?? ????/????

Theorem If a parameterized problem (Q,k) has an AND-composition*, and witnesses* of size polynomial in k, ?? ????/????. * the actual statement requires mild additional constructivity conditions. all known AND-compositions are constructive indicates problems admitting AND-compositions* do not admit polynomial OR-kernelizations* We currently exclude poly kernels via OR/AND compositions Observation: the known FPT algorithm for DFVS implies a poly algo finding a DFVS of size ? with succ prob 2 ?(? ?? ?) Cor: If DFVS has a AND-composition*, ?? ????/????

Paradigms in exp. time / FPT algorithms Preprocessing (+brute-force) Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, some models studied Dynamic Programming Often applied; several models studied

Parity Compression We saw strong limitations of large classes of exponential time algorithms under hypotheses on polynomial time Inspired by this, we model other paradigms similarly OPP algo s are Monte Carlo reductions to Circuit Sat with few input gates (the circuit simulates the verifier) Parity compression is a Monte Carlo reduction to Circuit Sat Circuit Sat: count #satisfying assignments modulo 2 Many algorithms can be rewritten as parity compressions BHKK 10: ?-path in ? (23?/4)-> polynomial time reduction from ?-path to Circuit Sat on 3?/4 inputs

Paradigms in exp. time / FPT algorithms Preprocessing (+brute-force) Mostly one standard model (`poly kernelization ) Existence studied explicitly, popular and successful Lower bounds assuming ?? no subset of ????/???? Branching / Bounded Search Tree Very often applied (implicitly), several models studied Evaluating Exponential Sums (inclusion exclusion/DFT/ summations over GF(2)) Often applied, some models studied Dynamic Programming Often applied; several models studied

Disjunctive Dynamic Programming CNF-REACH Given: CNF-formula ?:{0,1}? {0,1} with ? clauses and ? even, integer = ????(?). Asked: ?1, ,? {0,1}?/2with ?1= ?,? = ?and ?(??,??+1)=1 Directed path in succinctly represented graph. Some dynamic programming algorithms can be seen as a reduction to this problem. Can reduce: IS/pw to CNF-REACH where ?? ? CNF-REACH to IS/pw where ? 2?? Set Cover on universe ? to CNF-REACH where ? = 2|?| Additional indication that faster poly space algo s for IS/pw are hard to find

Summary Paradigms are modeled as polynomial time reductions to wisely chosen problems Reduction to ??? ???, ??? ???, ??? ????? Our contributions (highlights): More lower bounds on succ prob. of poly time algo s Useful in FPT setting Consequences for kernelization theory Constructive AND-compositions* exclude ????(?) witnesses* (and thus OR-kernels*) DFVS does not admit AND-compositions* Proposed `parity compression and `disjunctive DP to model other paradigms

Further Research Is there a poly algo that given ?1, ,??,? returns ? {1, ,?} with ? X ??= ? with prob 1/?????????(?) if such ? exists? Currently only known ????(??) time, poly space algo uses DFT Can we rule out such an algo with an AND-composition? Can OPP algo s refute SETH? Is there are problem with poly compressions but not poly witnesses (?-cycle)? Can we find more fine-grained lower bounds? www.win.tue.nl/~jnederlo Full version available at www.win.tue.nl/~jnederlo Thanks for listening!!