The k-in-a-tree problem for graphs of girth at least k

DOI10.1016/J.DAM.2010.06.005MaRDI QIDQ602681zbMATH OpenOpenAlexFDO

Authors Sumit K. Garg

Publication date 5 November 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

treealgorithminduced subgraphgirth\(k\)-in-a-treethree-in-a-tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12)

Abstract: For all integers $kgeq3$, we give an $O(n^4)$ time algorithm for the problem whose instance is a graph $G$ of girth at least $k$ together with $k$ vertices and whose question is "Does $G$ contains an induced subgraph containing the $k$ vertices and isomorphic to a tree?". This directly follows for $k=3$ from the three-in-a-tree algorithm of Chudnovsky and Seymour and for $k=4$ from a result of Derhy, Picouleau and Trotignon. Here we solve the problem for $kgeq5$. Our algorithm relies on a structural description of graphs of girth at least $k$ that do not contain an induced tree covering $k$ given vertices ($kgeq5$).

Recommendations

• The four-in-a-tree problem in triangle-free graphs
• On graphs which contain each tree of given size
• The three-in-a-tree problem
• Coloring graphs without short cycles and long induced paths
• The tree number of a graph with a given girth

Cites work

• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• Excluding induced subgraphs
• The four-in-a-tree problem in triangle-free graphs
• The three-in-a-tree problem

Cited in

(11)

• FPT and kernelization algorithms for the induced tree problem
• MIP formulations for induced graph optimization problems: a tutorial
• The four-in-a-tree problem in triangle-free graphs
• The three-in-a-tree problem
• Induced disjoint paths in claw-free graphs
• Constructing Trees in Graphs whose Complement has no K_2,s
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• The \(k\)-in-a-tree problem for chordal graphs
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• The \(k\)-in-a-path problem for claw-free graphs

This page was built for publication: The \(k\)-in-a-tree problem for graphs of girth at least \(k\)

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