Kernelization lower bounds through colors and IDs
From MaRDI portal
Recommendations
Cited in
(86)- On problems without polynomial kernels
- Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
- Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- On the complexity of broadcast domination and multipacking in digraphs
- On the approximate compressibility of connected vertex cover
- Exact multi-covering problems with geometric sets
- On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
- Refined parameterizations for computing colored cuts in edge-colored graphs
- Twin-width and polynomial kernels
- Eternal vertex cover on bipartite graphs
- Parameterized complexity of graph burning
- Reoptimization of parameterized problems
- Parameterized aspects of strong subgraph closure
- Complexity of independency and cliquy trees
- Alternative parameterizations of \textsc{Metric Dimension}
- On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
- Revisiting connected vertex cover: FPT algorithms and lossy kernels
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- Sparsification upper and lower bounds for graph problems and not-all-equal SAT
- On kernelization and approximation for the vector connectivity problem
- Extending the kernel for planar Steiner tree to the number of Steiner vertices
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- The structural complexity landscape of finding balance-fair shortest paths
- \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
- Building large \(k\)-cores from sparse graphs
- Circumventing connectivity for kernelization
- On polynomial kernels for sparse integer linear programs
- Constrained hitting set problem with intervals
- Clique cover and graph separation: new incompressibility results
- Parameterized complexity dichotomy for \textsc{Steiner Multicut}
- On the Kernelization Complexity of Colorful Motifs
- Polynomial kernels and user reductions for the workflow satisfiability problem
- On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
- Unique covering problems with geometric sets
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Incompressibility through Colors and IDs
- Covering Vectors by Spaces: Regular Matroids
- How Bad is the Freedom to Flood-It?
- Point line cover: the easy kernel is essentially tight
- Lossy kernelization
- Dual parameterization of weighted coloring
- The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
- On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
- Hans Bodlaender and the Theory of Kernelization Lower Bounds
- Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
- An approximate kernel for connected feedback vertex set
- Building large \(k\)-cores from sparse graphs
- Parameterized aspects of strong subgraph closure
- Parameterized complexity of safe set
- On the maximum colorful arborescence problem and color hierarchy graph structure
- Kernelization of packing problems
- Parameterized approximation schemes for Steiner trees with small number of Steiner vertices
- Parameterized pre-coloring extension and list coloring problems
- Approximate Turing Kernelization for Problems Parameterized by Treewidth
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- Finding large degree-anonymous subgraphs is hard
- On the lossy kernelization for connected treedepth deletion set
- Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
- Parameterized Complexity of Graph Burning
- Essentially tight kernels for (weakly) closed graphs
- An ETH-tight algorithm for bidirected Steiner connectivity
- Balanced substructures in bicolored graphs
- Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms
- Max-SAT with cardinality constraint parameterized by the number of clauses
- Placing green bridges optimally, with a multivariate analysis
- On the parameterized complexity of connected cluster vertex deletion
- When can cluster deletion with bounded weights be solved efficiently?
- Balanced substructures in bicolored graphs
- No polynomial kernels for knapsack
- Approximate Turing kernelization for problems parameterized by treewidth
- (Independent) Roman domination parameterized by distance to cluster
- Max-SAT with cardinality constraint parameterized by the number of clauses
- Approximate Turing kernelization and lower bounds for domination problems
- Parameterized complexity of biclique contraction and balanced biclique contraction
- On the parameterized complexity of controlling amendment and successive winners
- Dominator coloring and CD coloring in almost cluster graphs
- Parameterized complexity of dominating set variants in almost cluster and split graphs
- When can cluster deletion with bounded weights be solved efficiently?
- Does subset sum admit short proofs?
- On the polynomial kernelizations of finding a shortest path with positive disjunctive constraints
- Kernelization of compressing two-dimensional routing tables with order
- Repairing schedules by removing waiting times: a parameterized complexity analysis
- Dual parameterization of weighted coloring
- Exploiting hidden structure in selecting dimensions that distinguish vectors
This page was built for publication: Kernelization lower bounds through colors and IDs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4962171)
