Incompressibility through Colors and IDs

DOI10.1007/978-3-642-02927-1_32zbMath1248.68243MaRDI QIDQ3638049

Saket Saurabh, Michael Dom, Daniel Lokshtanov

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02927-1_32

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

68R10: Graph theory (including graph drawing) in computer science

Related Items

Fractals for Kernelization Lower Bounds, How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs, Lossy Kernels for Hitting Subgraphs, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On Structural Parameterizations of 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, Parameterizations of test cover with bounded test sizes, Finding shortest paths between graph colourings, Kernelization of edge perfect code and its variants, Kernelization using structural parameters on sparse graph classes, Planar graph vertex partition for linear problem kernels, 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, 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\), 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, Kernel bounds for disjoint cycles and disjoint paths, Quadratic kernelization for convex recoloring of trees, Kernels for feedback arc set in tournaments, FPT algorithms for connected feedback vertex set, 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, Obtaining split graphs by edge contraction, Kernelization complexity of possible winner and coalitional manipulation problems in voting, 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, 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, Contracting graphs to paths and trees, 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, 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, From Few Components to an Eulerian Graph by Adding Arcs, New Limits to Classical and Quantum Instance Compression, A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity, Kernelization: New Upper and Lower Bound Techniques