Confronting intractability via parameters
From MaRDI portal
Publication:465686
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)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1617251 (Why is no real title available?)
- scientific article; zbMATH DE number 5604125 (Why is no real title available?)
- scientific article; zbMATH DE number 5605062 (Why is no real title available?)
- scientific article; zbMATH DE number 5764786 (Why is no real title available?)
- scientific article; zbMATH DE number 5764900 (Why is no real title available?)
- scientific article; zbMATH DE number 3906520 (Why is no real title available?)
- scientific article; zbMATH DE number 4007728 (Why is no real title available?)
- scientific article; zbMATH DE number 4033746 (Why is no real title available?)
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 1303580 (Why is no real title available?)
- scientific article; zbMATH DE number 1304341 (Why is no real title available?)
- scientific article; zbMATH DE number 1305047 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 512804 (Why is no real title available?)
- scientific article; zbMATH DE number 1142299 (Why is no real title available?)
- scientific article; zbMATH DE number 1163704 (Why is no real title available?)
- scientific article; zbMATH DE number 1953093 (Why is no real title available?)
- scientific article; zbMATH DE number 1953101 (Why is no real title available?)
- scientific article; zbMATH DE number 1956210 (Why is no real title available?)
- scientific article; zbMATH DE number 2038759 (Why is no real title available?)
- scientific article; zbMATH DE number 2080246 (Why is no real title available?)
- scientific article; zbMATH DE number 2080999 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1508265 (Why is no real title available?)
- scientific article; zbMATH DE number 1754598 (Why is no real title available?)
- scientific article; zbMATH DE number 7051285 (Why is no real title available?)
- scientific article; zbMATH DE number 1929955 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- scientific article; zbMATH DE number 1405654 (Why is no real title available?)
- scientific article; zbMATH DE number 1407500 (Why is no real title available?)
- scientific article; zbMATH DE number 1445306 (Why is no real title available?)
- scientific article; zbMATH DE number 6783431 (Why is no real title available?)
- scientific article; zbMATH DE number 6783432 (Why is no real title available?)
- scientific article; zbMATH DE number 6297727 (Why is no real title available?)
- scientific article; zbMATH DE number 5057511 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- A Cubic Kernel for Feedback Vertex Set
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Practical Approach to Courcelle's Theorem
- A Quadratic Kernel for 3-Set Packing
- A fixed-parameter algorithm for the directed feedback vertex set problem
- A polynomial time approximation scheme for general multiprocessor job scheduling
- A probabilistic approach to problems parameterized above or below tight bounds
- A quadratic kernel for feedback vertex set
- A shorter proof of the graph minor algorithm: the unique linkage theorem
- Algorithm engineering for color-coding with applications to signaling pathway detection
- Algorithmic Meta-theorems
- Algorithmic lower bounds for problems parameterized by clique-width
- Algorithmic meta theorems for sparse graph classes
- Algorithms and Data Structures
- Algorithms and Data Structures
- Algorithms for classes of graphs with bounded expansion
- Algorithms for maximum independent sets
- Almost 2-SAT is fixed-parameter tractable
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- An efficient parameterized algorithm for m-set packing
- An improved fixed-parameter algorithm for vertex cover
- Approximating clique-width and branch-width
- Automated generation of search tree algorithms for hard graphs modification problems
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Bidimensional Parameters and Local Treewidth
- Bidimensionality and kernels
- Bidimensionality: new connections between FPT algorithms and PTASs
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Branch-width, parse trees, and monadic second-order logic for matroids.
- Call routing and the ratcatcher
- Clique-width: on the price of generality
- Closest Substring Problems with Small Distances
- Color-coding
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Computing and Combinatorics
- Constant ratio fixed-parameter approximation of the edge multicut problem
- Constructive linear time algorithms for branchwidth
- Contraction Bidimensionality: The Accurate Picture
- Courcelle's theorem -- a game-theoretic approach
- Cross-composition: a new technique for kernelization lower bounds
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Cutwidth I: A linear time fixed parameter algorithm
- Cutwidth II: Algorithms for partial w-trees of bounded degree
- Derivation of algorithms for cutwidth and related graph layout parameters
- Developments in Language Theory
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Domination problems in nowhere-dense classes of graphs
- Dynamic Programming and Fast Matrix Multiplication
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Dynamic programming for graphs on surfaces
- Easy problems for tree-decomposable graphs
- Efficient algorithms for counting parameterized list \(H\)-colorings
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Experimental and Efficient Algorithms
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Fast FAST
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Fast sub-exponential algorithms and compactness in planar graphs
- Faster approximation schemes and parameterized algorithms on \(H\)-minor-free and odd-minor-free graphs
- Faster fixed-parameter tractable algorithms for matching and packing problems
- Finding odd cycle transversals.
- Finding topological subgraphs is fixed-parameter tractable
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Fixed-parameter algorithms for cluster vertex deletion
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Fixed-parameter tractability of multicut parameterized by the size of the cutset
- Forbidden minors to graphs with small feedback sets
- Fourier meets M\"{o}bius: fast subset convolution
- Fundamentals of parameterized complexity
- Going Weighted: Parameterized Algorithms for Cluster Editing
- 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
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- Graph minors. XXI. graphs with unique linkages
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Graph-Theoretic Concepts in Computer Science
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- Hitting forbidden minors: approximation and kernelization
- Implicit branching and parameterized partial cover problems (extended abstract)
- Improved algorithms for feedback vertex set problems
- Improved algorithms for path, matching, and packing problems
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Improved upper bounds for vertex cover
- Incompressibility through Colors and IDs
- Induced Packing of Odd Cycles in a Planar Graph
- Infeasibility of instance compression and succinct PCPs for NP
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- Kernelizations for Parameterized Counting Problems
- LATIN 2002: Theoretical informatics. 5th Latin American symposium, Cancun, Mexico, April 3--6, 2002. Proceedings
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Linear-time algorithms for graphs of bounded rankwidth: a fresh look using game theory (extended abstract)
- Linearity of grid minors in treewidth with applications through bidimensionality
- Logic, graphs, and algorithms
- Lower bounds for kernelizations and other preprocessing procedures
- Mathematical Foundations of Computer Science 2004
- Measure and conquer
- Minimizing Movement: Fixed-Parameter Tractability
- Monadic second-order evaluations on tree-decomposable graphs
- Nonconstructive tools for proving polynomial-time decidability
- Nondeterminism within $P^ * $
- Odd cycle packing
- On Parameterized Approximability
- On computing graph minor obstruction sets
- On efficient fixed-parameter algorithms for weighted vertex cover
- On limited nondeterminism and the complexity of the V-C dimension
- On miniaturized problems in parameterized complexity theory
- On nowhere dense graphs
- On problems without polynomial kernels
- On search, decision, and the efficiency of polynomial-time algorithms
- On the Computational Complexity of Combinatorial Problems
- On the complexity of some colorful problems parameterized by treewidth
- On the existence of subexponential parameterized algorithms
- On the parameterized complexity of short computation and factorization
- Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
- Parameterized Algorithms and Hardness Results for Some Graph Motif Problems
- Parameterized Approximation Problems
- Parameterized Derandomization
- Parameterized and Exact Computation
- Parameterized and Exact Computation
- Parameterized and Exact Computation
- Parameterized approximation of dominating set problems
- Parameterized approximation scheme for the multiple knapsack problem
- Parameterized circuit complexity and the \(W\) hierarchy
- Parameterized complexity and kernelizability of Max Ones and Exact Ones problems
- Parameterized counting problems
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Perfect Code is \(W[1]\)-complete
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Polynomial-time data reduction for dominating set
- Preprocessing for treewidth: a combinatorial analysis through kernelization
- Properties of vertex cover obstructions
- Quickly excluding a planar graph
- Randomized Approximations of Parameterized Counting Problems
- Reduction algorithms for graphs of small treewidth
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- SOFSEM 2006: Theory and Practice of Computer Science
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
- Solving large FPT problems on coarse-grained parallel machines
- Spanning Trees with Many Leaves
- Sparse parameterized problems
- Subexponential parameterized algorithm for minimum fill-in
- Subexponential parameterized algorithms
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
- The Bidimensional Theory of Bounded-Genus Graphs
- The Budgeted Unique Coverage Problem and Color-Coding
- The Induced Disjoint Paths Problem
- The Parameterized Complexity of Counting Problems
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- The Spatial Complexity of Oblivious k-Probe Hash Functions
- The Turing way to parameterized complexity
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- The complexity of first-order and monadic second-order logic revisited
- The complexity of polynomial-time approximation
- The importance of being biased
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The parameterized complexity of probability amplification
- The structure of obstructions to treewidth and pathwidth
- Tight bounds for linkages in planar graphs
- Tight lower bounds for certain parameterized NP-hard problems
- Tree decompositions of graphs: saving memory in dynamic programming
- Using nondeterminism to design efficient deterministic algorithms
- Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
- Which problems have strongly exponential complexity?
- \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
- \textsc{Multicut} is FPT
Cited in
(8)- Graphs with few \(P_4\)'s under the convexity of paths of order three
- The complexity theory companion
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Parameterized approximation via fidelity preserving transformations
- The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
- Tree-coloring problems of bounded treewidth graphs
- A basic parameterized complexity primer
- Studies in Computational Aspects of Voting
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)
