Confronting intractability via parameters (Q465686)

scientific article; zbMATH DE number 6361003

Language	Label	Description	Also known as
English	Confronting intractability via parameters	scientific article; zbMATH DE number 6361003

Statements

instance of

scholarly article

0 references

title

Confronting intractability via parameters (English)

0 references

author

Rodney G. Downey

0 references

Dimitrios M. Thilikos

0 references

published in

Computer Science Review

0 references

publication date

24 October 2014

0 references

full work available at URL

https://arxiv.org/abs/1106.3161

0 references

zbMATH Keywords

parameterized complexity

0 references

parameterized algorithms

0 references

describes a project that uses

0 references

0 references

0 references

Finding topological subgraphs is fixed-parameter tractable

0 references

Q3684139

0 references

On the Computational Complexity of Combinatorial Problems

0 references

Improved upper bounds for vertex cover

0 references

Solving large FPT problems on coarse-grained parallel machines

0 references

Which problems have strongly exponential complexity?

0 references

An Isomorphism Between Subexponential and Parameterized Complexity Theory

0 references

Fixed-parameter tractability and completeness. IV: On completeness for W$[$ P$]$ and PSPACE analogues

0 references

Q4395317

0 references

Q4952619

0 references

Q4250206

0 references

A polynomial time approximation scheme for general multiprocessor job scheduling

0 references

Polynomial-Time Approximation Schemes for Geometric Intersection Graphs

0 references

Developments in Language Theory

0 references

0 references

0 references

0 references

0 references

Algorithms and Data Structures

0 references

Q4503944

0 references

Q5710169

0 references

Q3396009

0 references

Fixed-Parameter Tractability and Completeness I: Basic Results

0 references

Fixed-parameter tractability and completeness II: On completeness for W[1]

0 references

On the parameterized complexity of short computation and factorization

0 references

On the existence of subexponential parameterized algorithms

0 references

Cutting up is hard to do: the parameterised complexity of $k$-cut and related problems

0 references

The Parametrized Complexity of Some Fundamental Problems in Coding Theory

0 references

Q4027320

0 references

The Turing way to parameterized complexity

0 references

Perfect Code is $W[1]$-complete

0 references

Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)

0 references

The complexity of polynomial-time approximation

0 references

Q4535023

0 references

Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs

0 references

Q4414505

0 references

Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up

0 references

On miniaturized problems in parameterized complexity theory

0 references

Tight lower bounds for certain parameterized NP-hard problems

0 references

Closest Substring Problems with Small Distances

0 references

Q4633895

0 references

Q5417642

0 references

Q5365080

0 references

Resolution Is Not Automatizable Unless W[P] Is Tractable

0 references

Q4938635

0 references

The complexity of first-order and monadic second-order logic revisited

0 references

Isomorphism of graphs of bounded valence can be tested in polynomial time

0 references

Q3758245

0 references

Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees

0 references

Parameterized counting problems

0 references

The Parameterized Complexity of Counting Problems

0 references

Parameterized circuit complexity and the $W$ hierarchy

0 references

Randomized Approximations of Parameterized Counting Problems

0 references

Parameterized Derandomization

0 references

The parameterized complexity of probability amplification

0 references

Q4281497

0 references

Sparse parameterized problems

0 references

Fixed-Parameter Approximation: Conceptual Framework and Approximability Results

0 references

On Parameterized Approximability

0 references

Parameterized Approximation Problems

0 references

Vertex packings: Structural properties and algorithms

0 references

The importance of being biased

0 references

On problems without polynomial kernels

0 references

Infeasibility of instance compression and succinct PCPs for NP

0 references

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

0 references

Lower Bounds for Kernelizations and Other Preprocessing Procedures

0 references

Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves

0 references

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

0 references

Incompressibility through Colors and IDs

0 references

Bounded fixed-parameter tractability and $\log^{2}n$ nondeterministic bits

0 references

Q4850549

0 references

Nondeterminism within $P^ * $

0 references

An improved fixed-parameter algorithm for vertex cover

0 references

Vertex cover: Further observations and further improvements

0 references

Q4251072

0 references

Q4506265

0 references

On efficient fixed-parameter algorithms for weighted vertex cover

0 references

Algorithms for maximum independent sets

0 references

Measure and conquer

0 references

Improved algorithms for feedback vertex set problems

0 references

An $\mathcal O(2^{O(k)}n^{3})$ FPT algorithm for the undirected feedback vertex set problem

0 references

Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

0 references

Going Weighted: Parameterized Algorithms for Cluster Editing

0 references

Automated generation of search tree algorithms for hard graphs modification problems

0 references

Linear time algorithms for finding a dominating set of fixed size in degenerated graphs

0 references

Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract)

0 references

Using nondeterminism to design efficient deterministic algorithms

0 references

An efficient parameterized algorithm for m-set packing

0 references

Graph-Theoretic Concepts in Computer Science

0 references

A fixed-parameter algorithm for the directed feedback vertex set problem

0 references

Paths of bounded length and their cuts: parameterized complexity and algorithms

0 references

Parameterized and Exact Computation

0 references

Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

0 references

Derivation of algorithms for cutwidth and related graph layout parameters

0 references

Constructive linear time algorithms for branchwidth

0 references

Q4472491

0 references

Cutwidth I: A linear time fixed parameter algorithm

0 references

Cutwidth II: Algorithms for partial w-trees of bounded degree

0 references

Q3396557

0 references

Branch-width, parse trees, and monadic second-order logic for matroids.

0 references

Q5491014

0 references

Graph minors. X: Obstructions to tree-decomposition

0 references

The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

0 references

Easy problems for tree-decomposable graphs

0 references

Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families

0 references

A Practical Approach to Courcelle's Theorem

0 references

Courcelle's theorem -- a game-theoretic approach

0 references

The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues

0 references

Monadic second-order evaluations on tree-decomposable graphs

0 references

On the complexity of some colorful problems parameterized by treewidth

0 references

Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms

0 references

Linear time solvable optimization problems on graphs of bounded clique-width

0 references

Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory

0 references

Approximating clique-width and branch-width

0 references

On nowhere dense graphs

0 references

Grad and classes with bounded expansion. I: Decompositions

0 references

Grad and classes with bounded expansion. II: Algorithmic aspects

0 references

Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities

0 references

Algorithmic Meta-theorems

0 references

Algorithms for Classes of Graphs with Bounded Expansion

0 references

Algorithmic Meta Theorems for Sparse Graph Classes

0 references

Q3086928

0 references

Graph minors. XX: Wagner's conjecture

0 references

Graph minors. XIII: The disjoint paths problem

0 references

On search, decision, and the efficiency of polynomial-time algorithms

0 references

Q4385515

0 references

Q3773882

0 references

Properties of vertex cover obstructions

0 references

Forbidden minors to graphs with small feedback sets

0 references

Q3579375

0 references

On computing graph minor obstruction sets

0 references

Graph minors. XXI. graphs with unique linkages

0 references

Graph minors. XXII. Irrelevant vertices in linkage problems

0 references

A shorter proof of the graph minor algorithm: the unique linkage theorem

0 references

Tight Bounds for Linkages in Planar Graphs

0 references

Domination problems in nowhere-dense classes of graphs

0 references

Induced Packing of Odd Cycles in a Planar Graph

0 references

The Induced Disjoint Paths Problem

0 references

Odd cycle packing

0 references

Q4633929

0 references

LATIN 2002: Theoretical informatics. 5th Latin American symposium, Cancun, Mexico, April 3--6, 2002. Proceedings

0 references

Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs

0 references

Tree decompositions of graphs: saving memory in dynamic programming

0 references

Dynamic Programming and Fast Matrix Multiplication

0 references

Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution

0 references

Fourier meets M\"{o}bius: fast subset convolution

0 references

Q5365079

0 references

Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

0 references

Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions

0 references

Call routing and the ratcatcher

0 references

Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus

0 references

Q3579494

0 references

Dynamic Programming for Graphs on Surfaces

0 references

Finding odd cycle transversals.

0 references

Experimental and Efficient Algorithms

0 references

Computing and Combinatorics

0 references

Almost 2-SAT is fixed-parameter tractable

0 references

Fixed-parameter algorithms for cluster vertex deletion

0 references

Iterative Compression for Exactly Solving NP-Hard Minimization Problems

0 references

Color-coding

0 references

On limited nondeterminism and the complexity of the V-C dimension

0 references

The Spatial Complexity of Oblivious k-Probe Hash Functions

0 references

Q4231923

0 references

Q2934608

0 references

Faster fixed-parameter tractable algorithms for matching and packing problems

0 references

Minimizing Movement: Fixed-Parameter Tractability

0 references

The Budgeted Unique Coverage Problem and Color-Coding

0 references

Parameterized Algorithms and Hardness Results for Some Graph Motif Problems

0 references

Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms

0 references

Algorithm engineering for color-coding with applications to signaling pathway detection

0 references

Fast FAST

0 references

Q4449224

0 references

Q2721971

0 references

Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs

0 references

Q4414496

0 references

Mathematical Foundations of Computer Science 2004

0 references

Q4708588

0 references

Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors

0 references

Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs

0 references

Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size

0 references

Quickly excluding a planar graph

0 references

Optimal branch-decomposition of planar graphs in O ( n 3 ) Time

0 references

The Bidimensional Theory of Bounded-Genus Graphs

0 references

Contraction Bidimensionality: The Accurate Picture

0 references

Linearity of grid minors in treewidth with applications through bidimensionality

0 references

Bidimensional Parameters and Local Treewidth

0 references

Subexponential parameterized algorithms

0 references

Bidimensionality: new connections between FPT algorithms and PTASs

0 references

Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs

0 references

Bidimensionality and Geometric Graphs

0 references

Q3113754

0 references

Subexponential Parameterized Algorithm for Minimum Fill-In

0 references

Faster Approximation Schemes and Parameterized Algorithms on H-Minor-Free and Odd-Minor-Free Graphs

0 references

Fast Sub-exponential Algorithms and Compactness in Planar Graphs

0 references

SOFSEM 2006: Theory and Practice of Computer Science

0 references

Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size

0 references

Parameterized and Exact Computation

0 references

Parameterized and Exact Computation

0 references

A Quadratic Kernel for 3-Set Packing

0 references

The structure of obstructions to treewidth and pathwidth

0 references

The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

0 references

A Cubic Kernel for Feedback Vertex Set

0 references

Q4633817

0 references

Q3113683

0 references

Spanning Trees with Many Leaves

0 references

Polynomial-time data reduction for dominating set

0 references

Linear Problem Kernels for NP-Hard Problems on Planar Graphs

0 references

Reduction algorithms for graphs of small treewidth

0 references

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables

0 references

Systems of Linear Equations over $\mathbb{F}_2$ and Problems Parameterized above Average

0 references

Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels

0 references

Q5417644

0 references

A probabilistic approach to problems parameterized above or below tight bounds

0 references

Parameterized Complexity and Kernelizability of Max Ones and Exact Ones Problems

0 references

Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs

0 references

Q3113681

0 references

Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization

0 references

Parameterized two-player Nash equilibrium

0 references

Q3113682

0 references

Efficient algorithms for counting parameterized list $H$-colorings

0 references

Algorithms and Data Structures

0 references

Kernelizations for Parameterized Counting Problems

0 references

Parameterized approximation of dominating set problems

0 references

Q4633878

0 references

Constant ratio fixed-parameter approximation of the edge multicut problem

0 references

Q4251980

0 references

Fixed-parameter tractability of multicut parameterized by the size of the cutset

0 references

Multicut is FPT

0 references

Fundamentals of parameterized complexity

0 references

Nonconstructive tools for proving polynomial-time decidability

0 references

Identifiers

zbMATH Open document ID

1298.68094

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

10.1016/J.COSREV.2011.09.002

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:465686