Fixed-Parameter Algorithms, IA166 Sebastian Ordyniak Faculty of Informatics Masaryk University Brno Spring Semester 2013 Basic Ideas and Foundations Parameterized Complexity Outline 1 Basic Ideas and Foundations Parameterized Complexity Fixed-Parameter Tractability VERTEX COVER an illustrative example The Art of Problem Parameterization Algorithmic Techniques Fixed-Parameter Intractabilty Basic Ideas and Foundations Parameterized Complexity Classical Complexity The complexity of a problem is measured in terms of its input size. A problem is considered tractable if it can be solved in polynomial time and intractable if it is at least NP-hard. Unfortunately, many important problems are NP-hard so what can we do to tackle these problems? Basic Ideas and Foundations Parameterized Complexity Parameterized Complexity The complexity of a problem is measured in terms of its input size and any number of additional parameters. Taking into account additional parameters: provides a more fine-grained view of the complexity of a problem. tells us where the exponential explosion of an NP-hard problem comes from. allows us to design tailored algorithms for different parameterizations. Basic Ideas and Foundations Parameterized Complexity Parameterized Complexity Problem: MINIMUM VERTEX COVER MAXIMUM INDEPENDENT SET Input: Graph G, integer k Graph G, integer k Question: Is it possible to cover Is it possible to find the edges with k vertices? k independent vertices? Classical NP-complete NP-complete Basic Ideas and Foundations Parameterized Complexity Parameterized Complexity Problem: MINIMUM VERTEX COVER MAXIMUM INDEPENDENT SET Input: Graph G, integer k Graph G, integer k Question: Is it possible to cover Is it possible to find the edges with k vertices? k independent vertices? Classical NP-complete NP-complete trivial algorithm O(nk ) O(nk ) Basic Ideas and Foundations Parameterized Complexity Parameterized Complexity Problem: MINIMUM VERTEX COVER MAXIMUM INDEPENDENT SET Input: Graph G, integer k Graph G, integer k Question: Is it possible to cover Is it possible to find the edges with k vertices? k independent vertices? Classical NP-complete NP-complete trivial algorithm O(nk ) O(nk ) O(2k n2 ) algorithm exists No no(k) algorithm known Basic Ideas and Foundations Parameterized Complexity A simple algorithm for MINIMUM VERTEX COVER Input: Graph G and integer k. e1 = x1y1 e2 = x2y2 x2 y2 x1 y1 . . . Basic Ideas and Foundations Parameterized Complexity A simple algorithm for MINIMUM VERTEX COVER Input: Graph G and integer k. e1 = x1y1 e2 = x2y2 x2 y2 x1 y1 . . . Basic Ideas and Foundations Parameterized Complexity A simple algorithm for MINIMUM VERTEX COVER Input: Graph G and integer k. e1 = x1y1 e2 = x2y2 x2 y2 x1 y1 . . . Basic Ideas and Foundations Parameterized Complexity A simple algorithm for MINIMUM VERTEX COVER Input: Graph G and integer k. e1 = x1y1 e2 = x2y2 x2 y2 x1 y1 . . . Basic Ideas and Foundations Parameterized Complexity A simple algorithm for MINIMUM VERTEX COVER Input: Graph G and integer k. e1 = x1y1 e2 = x2y2 x2 y2 x1 y1 . . . Basic Ideas and Foundations Parameterized Complexity A simple algorithm for MINIMUM VERTEX COVER Input: Graph G and integer k. e1 = x1y1 e2 = x2y2 x2 y2 x1 y1 . . . Running time at every node there are 2 choices; height of the search tree is at most k; number of nodes in the search tree is at most 2k ; complete search possible in O(2k nc) Basic Ideas and Foundations Fixed-Parameter Tractability Outline 1 Basic Ideas and Foundations Parameterized Complexity Fixed-Parameter Tractability VERTEX COVER an illustrative example The Art of Problem Parameterization Algorithmic Techniques Fixed-Parameter Intractabilty Basic Ideas and Foundations Fixed-Parameter Tractability Fixed-Parameter tractability Definition A parameterization of a decision problem is a function that assigns an integer parameter (usually denoted by k) to each input instance. What can the parameter be? The size of the solution we are looking for. The maximum degree of the input graph. The diameter of the input graph. The length of clauses in the input SAT-formula. . . . Basic Ideas and Foundations Fixed-Parameter Tractability Fixed-Parameter Tractability Definition A parameterized problem is a language L ⊆ Σ∗ × Σ∗ where Σ is a finite alphabet. The first component is the classical input and second component is the parameter of the problem. Definition A parameterized problem is fixed-parameter tractable (FPT) if there is an f(k)nc time algorithm for an arbitrary function f of the parameter k, input size n, and some constant c. Basic Ideas and Foundations Fixed-Parameter Tractability Fixed-Parameter Tractability Definition A parameterized problem is fixed-parameter tractable (FPT) if there is an f(k)nc time algorithm for an arbitrary function f of the parameter k, input size n, and some constant c. Example: MINIMUM VERTEX COVER parameterized by the solution size is FPT: we have already seen that it can be solved in time O(2k n2). Better algorithms are known (and are still being developed), e.g., O(1.2832k k + kn). Main goal (of parameterized complexity): to find efficient FPT algorithms for NP-hard problems. Basic Ideas and Foundations Fixed-Parameter Tractability Fixed-Parameter Tractability Definition A parameterized problem is fixed-parameter tractable (FPT) if there is an f(k)nc time algorithm for an arbitrary function f of the parameter k, input size n, and some constant c. Remarks O∗–notation: O∗(f(k)) means O(f(k)nc) for some constant c. unless otherwise stated we always use k to denote the parameter and n to denote the input size. Basic Ideas and Foundations Fixed-Parameter Tractability Fixed-Parameter Tractability Examples of NP-hard problems that are FPT: Finding a vertex cover of size k. Finding a path of length k. Finding k disjoint triangles. Drawing the graph in the plane with k edge crossings. Finding disjoint paths that connect k pairs of points. . . . Basic Ideas and Foundations Fixed-Parameter Tractability Fixed-Parameter Tractability Fixed-parameter algorithms limit the exponential explosion to the parameter instead of the whole input size. instead of + Guaranteed optimality of the solution. + Provable upper bounds on the computational complexity. – Exponential running time. Basic Ideas and Foundations Fixed-Parameter Tractability Other approaches to tackle intractable problems: Randomized algorithms Approximation algorithms Heuristics Average Case Analysis New models of computing (DNA or quantum computing) Basic Ideas and Foundations VERTEX COVER an illustrative example Outline 1 Basic Ideas and Foundations Parameterized Complexity Fixed-Parameter Tractability VERTEX COVER an illustrative example The Art of Problem Parameterization Algorithmic Techniques Fixed-Parameter Intractabilty Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example VERTEX COVER Parameter: k Input: An undirected graph G = (V, E) and a natural number k. Question: Find a subset of vertices C ⊆ V of size at most k such that each edge in E has at least one of its endpoints in C. Solution methods: Bounded Search Tree: O∗(1.28k ). Data reduction by preprocessing: techniques by Buss, Nemhauser Trotter. Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example Parameterizing Specializing Generalizing Counting or Enumeration Lower bounds Implementing and applying Exploiting the structure given by a VERTEX COVER for other problems Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example Parameterizing Size of the vertex cover; Dual parameterization: INDEPENDENT SET; Parameterizing above guaranteed values, e.g., in planar graphs; Structure of the input graph, e.g., treewidth Specializing Generalizing Counting or Enumeration Lower bounds Implementing and applying Exploiting the structure given by a VERTEX COVER for other problems Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example Parameterizing Specializing: special graph classes, e.g., planar graphs O∗(c √ k ). Generalizing Counting or Enumeration Lower bounds Implementing and applying Exploiting the structure given by a VERTEX COVER for other problems Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example Parameterizing Specializing Generalizing: WEIGHTED VERTEX COVER, CAPACITATED VERTEX COVER, HITTING SET, . . . Counting or Enumeration Lower bounds Implementing and applying Exploiting the structure given by a VERTEX COVER for other problems Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example Parameterizing Specializing Generalizing Counting or Enumeration: Counting: O∗ (1.47k ). Enumeration: O∗ (2k ). Lower bounds Implementing and applying Exploiting the structure given by a VERTEX COVER for other problems Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example Parameterizing Specializing Generalizing Counting or Enumeration Lower bounds: widely open! Implementing and applying Exploiting the structure given by a VERTEX COVER for other problems Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example Parameterizing Specializing Generalizing Counting or Enumeration Lower bounds Implementing and applying: re-engineering case distinctions, parallelization, . . . Exploiting the structure given by a VERTEX COVER for other problems Basic Ideas and Foundations VERTEX COVER an illustrative example VERTEX COVER an illustrative example Parameterizing Specializing Generalizing Counting or Enumeration Lower bounds Implementing and applying Exploiting the structure given by a VERTEX COVER for other problems: solve related problems using an optimal vertex cover. Basic Ideas and Foundations The Art of Problem Parameterization Outline 1 Basic Ideas and Foundations Parameterized Complexity Fixed-Parameter Tractability VERTEX COVER an illustrative example The Art of Problem Parameterization Algorithmic Techniques Fixed-Parameter Intractabilty Basic Ideas and Foundations The Art of Problem Parameterization The Art of Problem Parameterization Parameter really small? Guaranteed parameter value? More than one obvious parameterization? Close to “trivial” problem instances? Basic Ideas and Foundations Algorithmic Techniques Outline 1 Basic Ideas and Foundations Parameterized Complexity Fixed-Parameter Tractability VERTEX COVER an illustrative example The Art of Problem Parameterization Algorithmic Techniques Fixed-Parameter Intractabilty Basic Ideas and Foundations Algorithmic Techniques Algorithmic Techniques Powerful toolbox for designing FPT algorithms with significant advances over the last 20 years: Bounded Search Tree Kernelization Color Coding Treewidth Integer Linear Programming Iterative Compression Basic Ideas and Foundations Fixed-Parameter Intractabilty Outline 1 Basic Ideas and Foundations Parameterized Complexity Fixed-Parameter Tractability VERTEX COVER an illustrative example The Art of Problem Parameterization Algorithmic Techniques Fixed-Parameter Intractabilty Basic Ideas and Foundations Fixed-Parameter Intractabilty Fixed-Parameter Intractability Corresponding to the class NP in the classical setting in parameterized complexity there is a whole hierarchy of complexity classes (the W-hierarchy). All problems that are at least W[1]-hard are considered fixed-parameter intractable. Most natural problems are either FPT, W[1]-complete or W[2]-complete. FPT W[1] W[2] W[P] Parameterized Complexity Classes Basic Ideas and Foundations Fixed-Parameter Intractabilty Fixed-Parameter Intractability VERTEX COVER INDEPENDENT SET DOMINATING SET NP-complete NP-complete NP-complete FPT W[1]-complete W[2]-complete Basic Ideas and Foundations Fixed-Parameter Intractabilty Literature Rolf Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press 2006 Joerg Flum and Martin Grohe, Parameterized Complexity Theory, Springer 2006 Micheal R. Fellows and Rodney G. Downey, Parameterized Complexity, Springer 1999