Fixed-Parameter Tractability and Completeness I: Basic Results
From MaRDI portal
Publication:4852629
DOI10.1137/S0097539792228228zbMath0830.68063WikidataQ56620258 ScholiaQ56620258MaRDI QIDQ4852629
Michael R. Fellows, Rodney G. Downey
Publication date: 4 February 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30) Turing machines and related notions (03D10)
Related Items
On the parametric complexity of schedules to minimize tardy tasks., Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Tractability in constraint satisfaction problems: a survey, Describing parameterized complexity classes, The Turing way to parameterized complexity, The \(k\)-feature set problem is \(W[2\)-complete], Solving large FPT problems on coarse-grained parallel machines, Compactors for parameterized counting problems, On the efficiency of polynomial time approximation schemes, An improved fixed-parameter algorithm for vertex cover, An improved deterministic parameterized algorithm for cactus vertex deletion, Scheduling with conflicts: Online and offline algorithms, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], Unnamed Item, Fixed-parameter approximation: conceptual framework and approximability results, The Birth and Early Years of Parameterized Complexity, A Basic Parameterized Complexity Primer, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, On the kernelization of split graph problems, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, On fixed-parameter tractability and approximability of NP optimization problems, An improved parameterized algorithm for the minimum node multiway cut problem, Courcelle's theorem for triangulations, Parameterized complexity of graph burning, Proof systems and transformation games, Reoptimization of parameterized problems, Parameterized complexity of fair feedback vertex set problem, Towards a polynomial kernel for directed feedback vertex set, Parameterized circuit complexity and the \(W\) hierarchy, Evaluation and Enumeration Problems for Regular Path Queries, Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}, Knapsack problems: a parameterized point of view, Fast local search methods for solving limited memory influence diagrams, On the hardness of labeled correlation clustering problem: a parameterized complexity view, Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs, Fixed-parameter decidability: Extending parameterized complexity analysis, Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, On spanning galaxies in digraphs, Connections between cutting-pattern sequencing, VLSI design, and flexible machines, Parameterized Learnability of k-Juntas and Related Problems, Kernel bounds for disjoint cycles and disjoint paths, Extended dynamic subgraph statistics using \(h\)-index parameterized data structures, Lower bounds on kernelization, Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms, Confronting intractability via parameters, Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP, Efficient algorithms for counting parameterized list \(H\)-colorings, The complexity of irredundant sets parameterized by size, On directed covering and domination problems, The complexity of dominating set in geometric intersection graphs, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, Efficient computation of the oriented chromatic number of recursively defined digraphs, \(K\)-adaptability in stochastic combinatorial optimization under objective uncertainty, Fixed-parameter tractability and completeness II: On completeness for W[1], Online dominating set, A linear-time algorithm for computing the intersection of all odd cycles in a graph, Advice classes of parametrized tractability, Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits, On domination and reinforcement numbers in trees, On the \(p\)-reinforcement and the complexity, Minimal proper interval completions, Colored hypergraph isomorphism is fixed parameter tractable, The complexity of maximum matroid--greedoid intersection and weighted greedoid maximiza\-tion, A problem reduction based approach to discrete optimization algorithm design, Efficient algorithms for clique problems, The intractability of computing the Hamming distance, Applying modular decomposition to parameterized cluster editing problems, On the computational hardness based on linear fpt-reductions, On the parameterized complexity of \([1,j\)-domination problems], Mim-width. II. The feedback vertex set problem, On the parameterized complexity of multiple-interval graph problems, The complexity ecology of parameters: An illustration using bounded max leaf number, On the independent set problem in random graphs, The complexity of the matroid-greedoid partition problem, A heuristic approach for the max-min diversity problem based on max-clique, Finding a Forest in a Tree, Derivation of algorithms for cutwidth and related graph layout parameters, Algorithms and Complexity of Signed, Minus, and Majority Domination, On the induced matching problem in Hamiltonian bipartite graphs, The complexity of dependency detection and discovery in relational databases, Threshold dominating sets and an improved characterization of \(W[2\)], Computational properties of argument systems satisfying graph-theoretic constraints, Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers, Approximation algorithms for knapsack problems with cardinality constraints, Parameterized learnability of juntas, An improved linear kernel for complementary maximal strip recovery: simpler and smaller, Kernelization: New Upper and Lower Bound Techniques, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Approximability of flow shop scheduling, Sparse parameterized problems, On the complexity of singly connected vertex deletion, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, The inapproximability of non-NP-hard optimization problems., Parameterized complexity of finding subgraphs with hereditary properties., On the complexity of database queries, Preprocessing of intractable problems, Perfect Code is \(W[1\)-complete], Fixed-parameter complexity in AI and nonmonotonic reasoning, On the impact of treewidth in the computational complexity of freezing dynamics, Continuous facility location on graphs, On the Complexity of Singly Connected Vertex Deletion, Parameterized Complexity of Fair Feedback Vertex Set Problem, A Retrospective on (Meta) Kernelization, An analysis of the W*-hierarchy, Parameterized Complexity for Domination Problems on Degenerate Graphs, Improved Upper Bounds for Partial Vertex Cover, NP-completeness: A retrospective, New Results on Directed Edge Dominating Set, On the parameterized complexity of the structure of lineal topologies (depth-first spanning trees) of finite graphs: the number of leaves, Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules, A note on hardness of computing recursive teaching dimension, Controlling entity integrity with key sets, Exact and heuristic methods for a workload allocation problem with chain precedence constraints, k-Efficient domination: Algorithmic perspective, On the partial vertex cover problem in bipartite graphs -- a parameterized perspective, Parameterized Counting and Cayley Graph Expanders, Unnamed Item, Domino treewidth, Parameterized Complexity of Safe Set, Unnamed Item, Bounded Tree-Width and CSP-Related Problems, The Constant Inapproximability of the Parameterized Dominating Set Problem, Parameterized Complexity of Graph Burning, A multiple-population evolutionary approach to gate matrix layout, Unnamed Item, An improved derandomized approximation algorithm for the max-controlled set problem, The Parameterized Complexity of Graph Cyclability, Unnamed Item, Obtaining a proportional allocation by deleting items, On the Parameterized Complexity of [1,j-Domination Problems], A HYBRID HEURISTIC FOR THE MINIMUM WEIGHT VERTEX COVER PROBLEM, The Dominating Set Problem in Geometric Intersection Graphs, Transducing Markov sequences, On Directed Covering and Domination Problems, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
