The four-in-a-tree problem in triangle-free graphs (Q844235)

The three-in-a-tree algorithm of \textit{M. Chudnovsky} and \textit{P. Seymour} [``The tree-in-a-tree problem'', Combinatorica (to appear)] decides in time \(O(n ^{4})\) whether three given vertices of a graph belong to an induced tree. Here, four-in-a-tree for triangle-free graphs are studied. The paper answers the question: what does a triangle-free graph look like if no induced tree covers four given vertices? Main Theorem: Let \(G\) be a connected graph with 4 distinct terminals. Then either (1) \(G\) is a cubic or square structure w. r. t. the four terminals, that is \(G\) is a cube or a square with 4 pending vertices, or (2) \(G\) contains an induced tree that covers the four terminals. The authors 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. They 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.