Fixed-parameter tractability and completeness II: On completeness for W[1]
From MaRDI portal
Publication:673779
DOI10.1016/0304-3975(94)00097-3zbMath0873.68059OpenAlexW2061513598WikidataQ55891725 ScholiaQ55891725MaRDI QIDQ673779
Michael R. Fellows, Rodney G. Downey
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00097-3
Related Items
Length-bounded cuts: proper interval graphs and structural parameters, Chordless paths through three vertices, Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Envy-free allocations respecting social networks, The Turing way to parameterized complexity, Solving large FPT problems on coarse-grained parallel machines, Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity?, Compactors for parameterized counting problems, On the efficiency of polynomial time approximation schemes, An improved fixed-parameter algorithm for vertex cover, Refined memorization for vertex cover, Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes, Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues], Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs, On notions of regularity for data languages, Kernelization of edge perfect code and its variants, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products, Parameterized complexity classes beyond para-NP, Checking regular invariance under tightly-controlled string modifications, Parameterized complexity of \(k\)-anonymity: hardness and tractability, A multivariate framework for weighted FPT algorithms, Reoptimization of parameterized problems, \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling], Parameterized algorithms for graph partitioning problems, Parameterized circuit complexity and the \(W\) hierarchy, The density maximization problem in graphs, Enhancing quantum annealing performance for the molecular similarity problem, Approximation for vertex cover in \(\beta\)-conflict graphs, Change-making problems revisited: a parameterized point of view, Parameterized complexity of conflict-free matchings and paths, On testing monomials in multivariate polynomials, The \(l\)-diversity problem: tractability and approximability, Improved parameterized algorithms for network query problems, Fast local search methods for solving limited memory influence diagrams, Parameterized complexity of independent set reconfiguration problems, Sublinear separators, fragility and subexponential expansion, On the hardness of labeled correlation clustering problem: a parameterized complexity view, The challenges of unbounded treewidth in parameterised subgraph counting problems, Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables, On bounded block decomposition problems for under-specified systems of equations, A structural/temporal query language for business processes, Parameterized complexity of generalized domination problems, Kernel bounds for disjoint cycles and disjoint paths, Assigning times to minimise reachability in temporal graphs, On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs, Path-contractions, edge deletions and connectivity preservation, Lower bounds on kernelization, Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms, Confronting intractability via parameters, Approximation schemes for deal splitting and covering integer programs with multiplicity constraints, Turbocharging treewidth heuristics, Efficient algorithms for counting parameterized list \(H\)-colorings, The complexity of irredundant sets parameterized by size, Maximum disjoint paths on edge-colored graphs: approximability and tractability, Correcting gene tree by removal and modification: tractability and approximability, Finding a potential community in networks, The envy-free matching problem with pairwise preferences, Computing the number of induced copies of a fixed graph in a bounded degree graph, Improved approximation algorithms for capacitated fault-tolerant \(k\)-center, Advice classes of parametrized tractability, Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem, On the complexity of finding and counting solution-free sets of integers, Detecting fixed patterns in chordal graphs in polynomial time, Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy, Parameterized computational complexity of finding small-diameter subgraphs, Multivariate complexity analysis of Swap Bribery, Parameterized complexity of coloring problems: treewidth versus vertex cover, Cliques with maximum/minimum edge neighborhood and neighborhood density, On the complexity of fixed parameter clique and dominating set, The intractability of computing the Hamming distance, Partial information network queries, Applying modular decomposition to parameterized cluster editing problems, Causal graphs and structurally restricted planning, Hardness and tractability of the \(\gamma\)\textsf{-Complete Subgraph} problem, Complexity and kernels for bipartition into degree-bounded induced graphs, On the parameterized complexity of multiple-interval graph problems, The complexity ecology of parameters: An illustration using bounded max leaf number, A heuristic approach for the max-min diversity problem based on max-clique, Parameterized complexity of vertex colouring, CP decomposition and weighted clique problem, On the induced matching problem in Hamiltonian bipartite graphs, The complexity of dependency detection and discovery in relational databases, Parameterized complexity of finding regular induced subgraphs, Threshold dominating sets and an improved characterization of \(W[2\)], Before and after vacuity, There is no EPTAS for two-dimensional knapsack, Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers, Approximation algorithms for knapsack problems with cardinality constraints, An improved linear kernel for complementary maximal strip recovery: simpler and smaller, The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs, Parameterized algorithms and complexity for the traveling purchaser problem and its variants, On the complexity of approximately matching a string to a directed graph, The complexity of finding harmless individuals in social networks, Few induced disjoint paths for \(H\)-free graphs, Parameterized complexity of finding subgraphs with hereditary properties., Preprocessing of intractable problems, Finding disjoint paths in networks with star shared risk link groups, Perfect Code is \(W[1\)-complete], An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems, Parameterized Complexity in Multiple-Interval Graphs: Domination, A Retrospective on (Meta) Kernelization, An analysis of the W*-hierarchy, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, The Birth and Early Years of Parameterized Complexity, The Impact of Parameterized Complexity to Interdisciplinary Problem Solving, A Basic Parameterized Complexity Primer, FPT Suspects and Tough Customers: Open Problems of Downey and Fellows, On the kernelization of split graph problems, Parameterized Complexity for Domination Problems on Degenerate Graphs, Parameterized Complexity Classes under Logical Reductions, Exact Weight Subgraphs and the k-Sum Conjecture, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs, Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs, Evaluation and Enumeration Problems for Regular Path Queries, Improved Parameterized Algorithms for Network Query Problems, Maximum Minimal Vertex Cover Parameterized by Vertex Cover, Optimizing reachability sets in temporal graphs by delaying, An algorithmic framework for locally constrained homomorphisms, Knapsack problems: a parameterized point of view, Unnamed Item, Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems, Improving the non‐compensatory trace‐clustering decision process, A Purely Democratic Characterization of W[1], Controlling entity integrity with key sets, Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs, Exact and heuristic methods for a workload allocation problem with chain precedence constraints, On the 2-Club Polytope of Graphs, Fixed-parameter decidability: Extending parameterized complexity analysis, Exact algorithms for restricted subset feedback vertex set in chordal and split graphs, Parameterized Counting and Cayley Graph Expanders, Stable matching with multilayer approval preferences: approvals can be harder than strict preferences, On computing large temporal (unilateral) connected components, Domino treewidth, Perfect domination and small cycles, Distance-\(d\) independent set problems for bipartite and chordal graphs, Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier, Unnamed Item, Exact algorithms for problems related to the densest \(k\)-set problem, Bounded Tree-Width and CSP-Related Problems, Parameterized Complexity of k-Anonymity: Hardness and Tractability, Improved Approximations for Hard Optimization Problems via Problem Instance Classification, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Open problems around exact algorithms, Parameterized algorithms for the happy set problem, Components in time-varying graphs, Unnamed Item, Ruling out FPT algorithms for weighted coloring on forests, A characterization of trees having a minimum vertex cover which is also a minimum total dominating set, On the independent set problem in random graphs, The Parameterized Complexity of Graph Cyclability, Balanced stable marriage: how close is close enough?, Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack, Subgraph isomorphism on graph classes that exclude a substructure, Kernelization: New Upper and Lower Bound Techniques, Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking, Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure, Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements, Computing the Tandem Duplication Distance is NP-Hard, A Branch-Price-and-Cut Algorithm for Packing Cuts in Undirected Graphs, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
Cites Work
- Graph minors. XX: Wagner's conjecture
- On the parameterized complexity of short computation and factorization
- Graph minors. XIII: The disjoint paths problem
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Nondeterminism within $P^ * $
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
