The four-in-a-tree problem in triangle-free graphs

DOI10.1007/S00373-009-0867-3MaRDI QIDQ844235zbMATH OpenOpenAlexFDO

Authors Nicolas Derhy, Christophe Picouleau, Nicolas Trotignon

Publication date 18 January 2010

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

induced treetriangle-free graphthree-in-a-tree algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Abstract: The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time $O(n^4)$ whether three given vertices of a graph belong to an induced tree. Here, we study four-in-a-tree for triangle-free graphs. We give a structural answer to the following question: what does a triangle-free graph look like if no induced tree covers four given vertices? Our main result says that any such graph must have the "same structure", in a sense to be defined precisely, as a square or a cube. We provide an $O(nm)$-time algorithm that given a triangle-free graph $G$ together with four vertices outputs either an induced tree that contains them or a partition of $V(G)$ certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree $T$ covering the four vertices such that at most one vertex of $T$ has degree at least 3 is NP-complete.

Recommendations

• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The three-in-a-tree problem
• Induced trees in triangle-free graphs
• Induced trees in triangle-free graphs
• Rooted induced trees in triangle-free graphs

Cites work

• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• Excluding induced subgraphs
• On the complexity of testing for odd holes and induced odd paths
• The three-in-a-tree problem

Cited in

(9)

• FPT and kernelization algorithms for the induced tree problem
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• MIP formulations for induced graph optimization problems: a tutorial
• The three-in-a-tree problem
• Induced disjoint paths in claw-free graphs
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• 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 four-in-a-tree problem in triangle-free graphs

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