Incompressibility through Colors and IDs
From MaRDI portal
Recommendations
Cited in
(91)- On problems without polynomial kernels
- FPT algorithms for domination in sparse graphs and beyond
- On the kernelization complexity of string problems
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- Parameterized measure \& conquer for problems with no small kernels
- Towards optimal kernel for connected vertex cover in planar graphs
- On some FPT problems without polynomial Turing compressions
- Steiner tree in \(k\)-star caterpillar convex bipartite graphs: a dichotomy
- Color spanning objects: algorithms and hardness results
- The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy
- Facility location problems: a parameterized view
- Backdoors to planning
- A completeness theory for polynomial (Turing) kernelization
- Possible winner problems on partial tournaments: a parameterized study
- The parameterized complexity of unique coverage and its variants
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- On the hardness of losing width
- Parameterizations of test cover with bounded test sizes
- Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
- Color spanning objects: algorithms and hardness results
- Complexity of Steiner tree in split graphs -- dichotomy results
- Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
- A multivariate approach for checking resiliency in access control
- Clique cover and graph separation: new incompressibility results
- Kernel bounds for path and cycle problems
- On the hardness of losing width
- Studies in Computational Aspects of Voting
- Clique Cover and Graph Separation
- Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
- On the Kernelization Complexity of Colorful Motifs
- Enumerate and measure: improving parameter budget management
- On making a distinguished vertex minimum degree by vertex deletion
- Parameterized complexity of vertex deletion into perfect graph classes
- Finding shortest paths between graph colourings
- From few components to an Eulerian graph by adding ARCS
- Kernelization of edge perfect code and its variants
- Kernelization using structural parameters on sparse graph classes
- New limits to classical and quantum instance compression
- A structural approach to kernels for ILPs: treewidth and total unimodularity
- On Problems without Polynomial Kernels (Extended Abstract)
- Planar graph vertex partition for linear problem kernels
- Kernelization: new upper and lower bound techniques
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Incremental list coloring of graphs, parameterized by conservation
- Kernel bounds for path and cycle problems
- Parameterized complexity of vertex deletion into perfect graph classes
- Parameterized Eulerian strong component arc deletion problem on tournaments
- Lower bounds on kernelization
- Fractals for kernelization lower bounds
- Confronting intractability via parameters
- The kernelization complexity of connected domination in graphs with (no) small cycles
- On the parameterized complexity of vertex cover and edge cover with connectivity constraints
- Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
- Kernelization lower bounds through colors and IDs
- Lossy Kernels for Hitting Subgraphs
- How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
- A linear kernel for planar red-blue dominating set
- On making a distinguished vertex of minimum degree by vertex deletion
- Fixed-parameter tractability of satisfying beyond the number of variables
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Kernelization of packing problems
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
- On structural parameterizations of \textsc{Hitting Set}: hitting paths in graphs using 2-SAT
- Parameterized complexity and kernelizability of max ones and exact ones problems
- On structural parameterizations of Hitting Set: hitting paths in graphs using 2-SAT
- P versus NPC: minimum Steiner trees in convex split graphs
- On the kernel and related problems in interval digraphs
- On convexity in split graphs: complexity of Steiner tree and domination
- Kernel bounds for disjoint cycles and disjoint paths
- Quadratic kernelization for convex recoloring of trees
- Kernels for feedback arc set in tournaments
- Parameterized analysis of the cops and robber problem
- Parameterized complexity of incomplete connected fair division
- FPT algorithms for connected feedback vertex set
- Preprocessing complexity for some graph problems parameterized by structural parameters
- Parameterized complexity of (d, r)-domination via modular decomposition
- Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- Dynamic parameterized problems
- Tight (double) exponential bounds for identification problems: locating-dominating set and test cover
- When does FTP become FPT??
- Boundaried kernelization
- When does FTP become FPT?
- Obtaining split graphs by edge contraction
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
This page was built for publication: Incompressibility through Colors and IDs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638049)
