On problems without polynomial kernels
From MaRDI portal
Publication:1034099
DOI10.1016/J.JCSS.2009.04.001zbMATH Open1192.68288OpenAlexW2107284348WikidataQ57359819 ScholiaQ57359819MaRDI QIDQ1034099FDOQ1034099
Authors: Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin 
Publication date: 10 November 2009
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2009.04.001
Recommendations
lower boundsparameterized complexitypolynomial hierarchykernelizationpolynomial kernelscomposition algorithmdistillation algorithm
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Parametrized complexity theory.
- On the Structure of Polynomial Time Reducibility
- Color-coding
- The complexity of theorem-proving procedures
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- The polynomial-time hierarchy
- Computation Models for Parameterized Complexity
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Fixed-parameter tractability and data reduction for multicut in trees
- On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
- Advice classes of parametrized tractability
- On self-reducibility and weak P-selectivity
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Polynomial-time data reduction for dominating set
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- The complexity of first-order and monadic second-order logic revisited
- Tight lower bounds for certain parameterized NP-hard problems
- Linear FPT reductions and computational lower bounds
- Title not available (Why is that?)
- Title not available (Why is that?)
- Efficient bounds for the stable set, vertex cover and set packing problems
- Divide-and-Color
- An efficient fixed-parameter algorithm for 3-hitting set
- Nonconstructive advances in polynomial-time complexity
- The importance of being biased
- Mathematical Foundations of Computer Science 2003
- Graph-modeled data clustering: Exact algorithms for clique generation
- \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
- Title not available (Why is that?)
- A Cubic Kernel for Feedback Vertex Set
- Automata, Languages and Programming
- STACS 2005
- Title not available (Why is that?)
- A quadratic kernel for feedback vertex set
- Algorithms and Data Structures
- Automata, Languages and Programming
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Kernel and fast algorithm for dense triplet inconsistency
- Kernel bounds for path and cycle problems
- Parameterized complexity of vertex deletion into perfect graph classes
- Polynomial kernels for proper interval completion and related problems
- Effective computation of immersion obstructions for unions of graph classes
- Facility location problems: a parameterized view
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Studies in Computational Aspects of Voting
- On the Kernelization Complexity of Colorful Motifs
- Parameterized complexity of even/odd subgraph problems
- Parameterizations of test cover with bounded test sizes
- On sparsification for computing treewidth
- Linear kernel for \textsc{Rooted Triplet Inconsistency} and other problems based on conflict packing technique
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On the hardness of losing width
- On polynomial kernels for sparse integer linear programs
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Quadratic kernelization for convex recoloring of trees
- Parameterized Complexity of Firefighting Revisited
- Solving MAX-\(r\)-SAT above a tight lower bound
- Smaller parameters for vertex cover kernelization
- Incremental list coloring of graphs, parameterized by conservation
- A basic parameterized complexity primer
- Infeasibility of instance compression and succinct PCPs for NP
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Parameterized computational complexity of finding small-diameter subgraphs
- Note on maximal bisection above tight lower bound
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- On the hardness of losing width
- Kernelizations for the hybridization number problem on multiple nonbinary trees
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- Kernelization using structural parameters on sparse graph classes
- On the parameterized complexity of the repetition free longest common subsequence problem
- Title not available (Why is that?)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- AND-compression of NP-complete problems: streamlined proof and minor observations
- Solving linear equations parameterized by Hamming weight
- Kernelization -- preprocessing with a guarantee
- Backdoors to satisfaction
- Kernel bounds for disjoint cycles and disjoint paths
- Kernelization of cycle packing with relaxed disjointness constraints
- Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
- Restricted and swap common superstring: a multivariate algorithmic perspective
- Kernelization lower bounds through colors and IDs
- Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments
- Data reduction for graph coloring problems
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- Data reduction for graph coloring problems
- Multistage vertex cover
- Kernels for feedback arc set in tournaments
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Polynomial kernels for weighted problems
- Parameterized algorithms for the module motif problem
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Kernel bounds for path and cycle problems
- New limits to classical and quantum instance compression
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- On cutwidth parameterized by vertex cover
- On the parameterized complexity of vertex cover and edge cover with connectivity constraints
- NP-completeness results for partitioning a graph into total dominating sets
- Kernels: Annotated, Proper and Induced
- Kernelization of packing problems
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- From few components to an Eulerian graph by adding ARCS
- Incompressibility through Colors and IDs
- The parameterized complexity of some minimum label problems
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- A completeness theory for polynomial (Turing) kernelization
- Kernels for packing and covering problems
- The parameterized complexity of local search for TSP, more refined
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Clique Cover and Graph Separation
- Hitting forbidden minors: approximation and kernelization
- Parameterized complexity of Min-power multicast problems in wireless ad hoc networks
- Kernel bounds for structural parameterizations of pathwidth
- Fixed-parameter tractability of treewidth and pathwidth
- Contracting graphs to paths and trees
- On making a distinguished vertex minimum degree by vertex deletion
- A Retrospective on (Meta) Kernelization
- Fine-grained complexity of safety verification
- Approximation and tidying -- a problem kernel for \(s\)-plex cluster vertex deletion
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- What's next? Future directions in parameterized complexity
- Kernelization lower bound for permutation pattern matching
- Spanners in sparse graphs
- On the kernelization complexity of string problems
- A complete parameterized complexity analysis of bounded planning
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Data-compression for parametrized counting problems on sparse graphs
- On Problems without Polynomial Kernels (Extended Abstract)
- Parameterized Algorithms for Maximum Edge Biclique and Related Problems
- FPT and kernelization algorithms for the induced tree problem
- Parameterized Eulerian strong component arc deletion problem on tournaments
- On the parameterized complexity of contraction to generalization of trees
- Parameterized low-rank binary matrix approximation
- Known Algorithms for Edge Clique Cover are Probably Optimal
- Parameterized complexity of firefighting
This page was built for publication: On problems without polynomial kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1034099)
