Confronting intractability via parameters

DOI10.1016/J.COSREV.2011.09.002zbMATH Open1298.68094arXiv1106.3161OpenAlexW2000213024MaRDI QIDQ465686FDOQ465686

Rodney G. Downey, Dimitrios M. Thilikos

Publication date: 24 October 2014

Published in: Computer Science Review (Search for Journal in Brave)

Abstract: One approach to confronting computational hardness is to try to understand the contribution of various parameters to the running time of algorithms and the complexity of computational tasks. Almost no computational tasks in real life are specified by their size alone. It is not hard to imagine that some parameters contribute more intractability than others and it seems reasonable to develop a theory of computational complexity which seeks to exploit this fact. Such a theory should be able to address the needs of practicioners in algorithmics. The last twenty years have seen the development of such a theory. This theory has a large number of successes in terms of a rich collection of algorithmic techniques both practical and theoretical, and a fine-grained intractability theory. Whilst the theory has been widely used in a number of areas of applications including computational biology, linguistics, VLSI design, learning theory and many others, knowledge of the area is highly varied. We hope that this article will show both the basic theory and point at the wide array of techniques available. Naturally the treatment is condensed, and the reader who wants more should go to the texts, Downey and Fellows, Flum and Grohe, Niedermeier, and the upcoming undergraduate text Downey and Fellows.

Full work available at URL: https://arxiv.org/abs/1106.3161

zbMATH Keywords

parameterized complexityparameterized algorithms

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Fundamentals of parameterized complexity
• Graph minors. X: Obstructions to tree-decomposition
• Automated generation of search tree algorithms for hard graphs modification problems
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Finding odd cycle transversals.
• Graph minors. XX: Wagner's conjecture
• Fixed-parameter algorithms for cluster vertex deletion
• On problems without polynomial kernels
• Almost 2-SAT is fixed-parameter tractable
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Call routing and the ratcatcher
• Which problems have strongly exponential complexity?
• Graph minors. XIII: The disjoint paths problem
• Linear time solvable optimization problems on graphs of bounded clique-width
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Spanning Trees with Many Leaves
• Easy problems for tree-decomposable graphs
• Closest Substring Problems with Small Distances
• A fixed-parameter algorithm for the directed feedback vertex set problem
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Parameterized Approximation Problems
• Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
• Incompressibility through Colors and IDs
• Nonconstructive tools for proving polynomial-time decidability
• Color-coding
• An efficient parameterized algorithm for m-set packing
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Graph-Theoretic Concepts in Computer Science
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• Quickly excluding a planar graph
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• A shorter proof of the graph minor algorithm: the unique linkage theorem
• Odd cycle packing
• Vertex packings: Structural properties and algorithms
• Courcelle's theorem -- a game-theoretic approach
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Bidimensionality and Geometric Graphs
• Computing and Combinatorics
• Infeasibility of instance compression and succinct PCPs for NP
• Improved upper bounds for vertex cover
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• On the existence of subexponential parameterized algorithms
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Constructive linear time algorithms for branchwidth
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Dynamic Programming and Fast Matrix Multiplication
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• On limited nondeterminism and the complexity of the V-C dimension
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
• An improved fixed-parameter algorithm for vertex cover
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• On the Computational Complexity of Combinatorial Problems
• Nondeterminism within $P^ * $
• Parameterized and Exact Computation
• Multicut is FPT
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Algorithmic Meta-theorems
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial-time data reduction for dominating set
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Minimizing Movement: Fixed-Parameter Tractability
• On efficient fixed-parameter algorithms for weighted vertex cover
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Perfect Code is \(W[1]\)-complete
• The Turing way to parameterized complexity
• Using nondeterminism to design efficient deterministic algorithms
• Domination problems in nowhere-dense classes of graphs
• Bidimensionality: new connections between FPT algorithms and PTASs
• Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
• Fourier meets M\"{o}bius: fast subset convolution
• Faster fixed-parameter tractable algorithms for matching and packing problems
• Graph minors. XXI. graphs with unique linkages
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
• The complexity of first-order and monadic second-order logic revisited
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Tight Bounds for Linkages in Planar Graphs
• Fast FAST
• Contraction Bidimensionality: The Accurate Picture
• Algorithms for maximum independent sets
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Subexponential parameterized algorithms
• Mathematical Foundations of Computer Science 2004
• Finding topological subgraphs is fixed-parameter tractable
• SOFSEM 2006: Theory and Practice of Computer Science
• Monadic second-order evaluations on tree-decomposable graphs
• On search, decision, and the efficiency of polynomial-time algorithms
• Properties of vertex cover obstructions
• Cutwidth I: A linear time fixed parameter algorithm
• On nowhere dense graphs
• Vertex cover: Further observations and further improvements
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Tight lower bounds for certain parameterized NP-hard problems
• The Induced Disjoint Paths Problem
• Induced Packing of Odd Cycles in a Planar Graph
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Subexponential Parameterized Algorithm for Minimum Fill-In
• On the complexity of some colorful problems parameterized by treewidth
• Algorithm engineering for color-coding with applications to signaling pathway detection
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• The Parameterized Complexity of Counting Problems
• Parameterized circuit complexity and the \(W\) hierarchy
• On computing graph minor obstruction sets
• Solving large FPT problems on coarse-grained parallel machines
• On Parameterized Approximability
• Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average
• Lower Bounds for Kernelizations and Other Preprocessing Procedures
• Measure and conquer
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
• A probabilistic approach to problems parameterized above or below tight bounds
• Linearity of grid minors in treewidth with applications through bidimensionality
• Tree decompositions of graphs: saving memory in dynamic programming
• Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Parameterized approximation of dominating set problems
• Resolution Is Not Automatizable Unless W[P] Is Tractable
• The importance of being biased
• Bidimensional Parameters and Local Treewidth
• Forbidden minors to graphs with small feedback sets
• On miniaturized problems in parameterized complexity theory
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size
• Dynamic Programming for Graphs on Surfaces
• Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• Constant ratio fixed-parameter approximation of the edge multicut problem
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• On the parameterized complexity of short computation and factorization
• The Bidimensional Theory of Bounded-Genus Graphs
• A Cubic Kernel for Feedback Vertex Set
• Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Algorithms and Data Structures
• Derivation of algorithms for cutwidth and related graph layout parameters
• LATIN 2002: Theoretical informatics. 5th Latin American symposium, Cancun, Mexico, April 3--6, 2002. Proceedings
• The structure of obstructions to treewidth and pathwidth
• Reduction algorithms for graphs of small treewidth
• Parameterized two-player Nash equilibrium
• The complexity of polynomial-time approximation
• Sparse parameterized problems
• Parameterized counting problems
• Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
• A polynomial time approximation scheme for general multiprocessor job scheduling
• Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
• Fast Sub-exponential Algorithms and Compactness in Planar Graphs
• Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract)
• The Budgeted Unique Coverage Problem and Color-Coding
• Randomized Approximations of Parameterized Counting Problems
• Parameterized Derandomization
• An Isomorphism Between Subexponential and Parameterized Complexity Theory
• Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs
• A Quadratic Kernel for 3-Set Packing
• Algorithmic Meta Theorems for Sparse Graph Classes
• A Practical Approach to Courcelle's Theorem
• Parameterized and Exact Computation
• Parameterized and Exact Computation
• Algorithms and Data Structures
• Kernelizations for Parameterized Counting Problems
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• Going Weighted: Parameterized Algorithms for Cluster Editing
• Experimental and Efficient Algorithms
• Developments in Language Theory
• Algorithms for Classes of Graphs with Bounded Expansion
• Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems
• Efficient algorithms for counting parameterized list \(H\)-colorings
• The parameterized complexity of probability amplification
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

• Studies in Computational Aspects of Voting
• The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
• A Basic Parameterized Complexity Primer
• The complexity theory companion
• On the threshold of intractability
• Graphs with few \(P_4\)'s under the convexity of paths of order three
• Parameterized approximation via fidelity preserving transformations
• Tree-coloring problems of bounded treewidth graphs

Uses Software

• QPath

This page was built for publication: Confronting intractability via parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q465686)