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)
- On making a distinguished vertex minimum degree by vertex deletion
- A Retrospective on (Meta) Kernelization
- Fine-grained complexity of safety verification
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- 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
- 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
- On the parameterized complexity of contraction to generalization of trees
- Faster existential FO model checking on posets
- Parameterized low-rank binary matrix approximation
- Extremal kernelization: a commemorative paper
- Parameterized complexity of length-bounded cuts and multicuts
- Parameterized complexity of firefighting
- A survey of parameterized algorithms and the complexity of edge modification
- Dual parameterization of weighted coloring
- Dual parameterization of weighted coloring
- Parameterized algorithms for load coloring problem
- Fréchet distance between a line and avatar point set
- Lower bounds on kernelization
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Incompressibility of \(H\)-free edge modification problems
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- Building large \(k\)-cores from sparse graphs
- Clique cover and graph separation: new incompressibility results
- Kernelizations for Parameterized Counting Problems
- Confronting intractability via parameters
- Meta-kernelization with structural parameters
- Obtaining split graphs by edge contraction
- The kernelization complexity of connected domination in graphs with (no) small cycles
- (Meta) kernelization
- Parameterized algorithm for eternal vertex cover
- Finding two edge-disjoint paths with length constraints
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- Backdoors to tractable answer set programming
- A completeness theory for polynomial (Turing) kernelization
- On the kernel size of clique cover reductions for random intersection graphs
- Finding disjoint paths in split graphs
- On the parameterized complexity of finding separators with non-hereditary properties
- Parameterized complexity and kernel bounds for hard planning problems
- Lower bounds for kernelization
- On the computational complexity of length- and neighborhood-constrained path problems
- Fractals for kernelization lower bounds
- Pure Nash equilibria in graphical games and treewidth
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Reoptimization of parameterized problems
- On the Complexity of Bounded Context Switching.
- Parameterized complexity of critical node cuts
- A polynomial Turing-kernel for weighted independent set in bull-free graphs
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Partially polynomial kernels for set cover and test cover
- Graph editing problems with extended regularity constraints
- Fixed-parameter tractability of satisfying beyond the number of variables
- On making a distinguished vertex of minimum degree by vertex deletion
- A multistage view on 2-satisfiability
- On the maximum colorful arborescence problem and color hierarchy graph structure
- Parameterized domination in circle graphs
- Two edge-disjoint paths with length constraints
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- On the approximate compressibility of connected vertex cover
- On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
- Modifying a graph using vertex elimination
- Towards non-black-box separations of public key encryption and one way function
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Basic Terminology, Notation and Results
- On kernelization for edge dominating set under structural parameters
- Tractability, hardness, and kernelization lower bound for and/or graph solution
- On the parameterized complexity of graph modification to first-order logic properties
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- Parameterized aspects of strong subgraph closure
- What Is Known About Vertex Cover Kernelization?
- Safe approximation and its relation to kernelization
- Parameterized complexity of secluded connectivity problems
- Two edge modification problems without polynomial kernels
- Title not available (Why is that?)
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- Finding disjoint dense clubs in a social network
- Finding Disjoint Dense Clubs in an Undirected Graph
- Parameterized complexity of sparse linear complementarity problems
- FPT is characterized by useful obstruction sets
- Diminishable parameterized problems and strict polynomial kernelization
- Kernelization lower bounds for finding constant-size subgraphs
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- The parameterized complexity of \(s\)-club with triangle and seed constraints
- Meta-kernelization using well-structured modulators
- Parameterized complexity of \textsc{bandwidth} of \textsc{caterpillars} and \textsc{weighted path emulation}
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)
