Skip to Main content Skip to Navigation
Other publications

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

Abstract : The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n4) 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 : how does look like a triangle-free graph such that 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.
Complete list of metadatas

Cited literature [6 references]  Display  Hide  Download

https://halshs.archives-ouvertes.fr/halshs-00270623
Contributor : Lucie Label <>
Submitted on : Monday, April 7, 2008 - 10:23:55 AM
Last modification on : Tuesday, November 17, 2020 - 11:18:07 AM
Long-term archiving on: : Thursday, May 20, 2010 - 8:21:27 PM

File

B08023.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : halshs-00270623, version 1

Citation

Nicolas Derhy, Christophe Picouleau, Nicolas Trotignon. The four-in-a-tree problem in triangle-free graphs. 2008. ⟨halshs-00270623⟩

Share

Metrics

Record views

337

Files downloads

381