FPT and kernelization algorithms for the induced tree problem

DOI10.1007/978-3-030-75242-2_11OpenAlexW3158785744MaRDI QIDQ2692722

Murilo V. G. da Silva, Guilherme Castro Mendes Gomes, Vinícius Fernandes dos Santos, Jayme Luiz Szwarcfiter

Publication date: 22 March 2023

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

zbMATH Keywords

parameterized complexitypolynomial kernelFPT algorithminduced treecross-composition

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items

Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes, Finding a shortest even hole in polynomial time, Induced disjoint paths in AT-free graphs

Cites Work

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