FPT and kernelization algorithms for the induced tree problem

DOI10.1007/978-3-030-75242-2_11MaRDI QIDQ2692722zbMATH OpenOpenAlexFDO

Authors Guilherme Castro Mendes Gomes, Vinícius F. dos Santos, Murilo V. G. da Silva, Jayme L. Szwarcfiter

Publication date 22 March 2023

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

zbMATH Keywords

cross-compositionFPT algorithminduced treeparameterized complexitypolynomial kernel

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A fast branching algorithm for cluster vertex deletion
• A faster algorithm to recognize even-hole-free graphs
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Cluster vertex deletion: a parameterization between vertex cover and clique-width
• Cross-composition: a new technique for kernelization lower bounds
• Detecting a Theta or a Prism
• Detecting an induced net subdivision
• Detecting an Odd Hole
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Finding induced trees
• Graph minors. II. Algorithmic aspects of tree-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• Infeasibility of instance compression and succinct PCPs for NP
• Kernelization. Theory of parameterized preprocessing
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• On problems without polynomial kernels
• On the complexity of k-SAT
• On the complexity of testing for odd holes and induced odd paths
• Parameterized algorithms
• Parameterized complexity of vertex colouring
• Paths, Trees, and Flowers
• Reducibility among combinatorial problems
• Some consequences of non-uniform conditions on uniform classes
• The \(k\)-in-a-path problem for claw-free graphs
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The disjoint paths problem in quadratic time
• The four-in-a-tree problem in triangle-free graphs
• The graph motif problem parameterized by the structure of the input graph
• The parameterized complexity of the induced matching problem
• The power of cut-based parameters for computing edge disjoint paths
• The steiner problem in graphs
• The strong perfect graph theorem
• The three-in-a-tree problem
• Three-in-a-tree in near linear time
• Upper bounds to the clique width of graphs

Cited in

(7)

• Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
• Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
• scientific article; zbMATH DE number 6739965 (Why is no real title available?)
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• Finding a shortest even hole in polynomial time
• The three-in-a-tree problem
• FPT algorithms and kernels for the directed k-leaf problem

This page was built for publication: FPT and kernelization algorithms for the induced tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2692722)