Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels

DOI10.1137/1.9781611973730.42zbMath1371.68212arXiv1410.0855OpenAlexW2951159125MaRDI QIDQ5363088

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.0855

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (16)

Finding a chain graph in a bipartite permutation graph ⋮ Kernelization Algorithms for Packing Problems Allowing Overlaps ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Extended MSO model checking via small vertex integrity ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Arbitrary Overlap Constraints in Graph Packing Problems ⋮ Turing kernelization for finding long paths in graph classes excluding a topological minor ⋮ Alternative parameterizations of \textsc{Metric Dimension} ⋮ Turing kernelization for finding long paths and cycles in restricted graph classes ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps ⋮ On some FPT problems without polynomial Turing compressions ⋮ Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor ⋮ Fine-grained parameterized complexity analysis of graph coloring problems

This page was built for publication: Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels