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