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

DOI10.1007/S00373-009-0867-3zbMATH Open1186.05101arXiv1309.0978OpenAlexW3099919903MaRDI QIDQ844235FDOQ844235

Authors: Nicolas Derhy, Christophe Picouleau, Nicolas Trotignon 

Publication date: 18 January 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• The three-in-a-tree problem
• Excluding induced subgraphs
• On the complexity of testing for odd holes and induced odd paths

Cited In (9)

• FPT and kernelization algorithms for the induced tree problem
• MIP formulations for induced graph optimization problems: a tutorial
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• 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)