The three-in-a-tree problem (Q653792): Difference between revisions

The authors show that, given a graph \(G=(V,E)\) together with three vertices \(v_1, v_2, v_3\) of \(G\), deciding if there exists an induced tree of \(G\) that contains \(v_1, v_2, v_3\) can be done in time \(O(| V| ^4)\). Using this as a subroutine, they show that there is {\parindent=6mm \begin{itemize}\item[(1)]a polynomial time algorithm to test whether a graph contains a theta as an induced subgraph (this was an open question of interest), where a theta is a graph consisting of two nonadjacent vertices \(a, b\) and three paths \(P_1, P_2, P_3\), each joining \(a, b\) and otherwise vertex-disjoint, such that for \(1\leq i<j\leq 3\) the subgraph induced on \(V(P_i)\cup V(P_j)\) is a cycle, and \item[(2)]an alternative way to test whether a graph contains a pyramid (a fundamental step in checking whether a graph is perfect), where a pyramid is a graph consisting of a vertex \(a\) and a triangle \(\{b_1, b_2, b_3\}\), and three paths \(P_1, P_2, P_3\), such that: \(P_i\) is between \(a\) and \(b_i\) for \(i=1,2,3\); for \(1\leq i<j \leq 3\) \(P_i, P_j\) are vertex-disjoint except for \(a\) and the subgraph induced on \(V(P_i)\cup V(P_j)\) is a cycle; and at most one of \(P_1, P_2, P_3\) has only one edge. \end{itemize}} The more general \(k\)-in-a-tree problem has been discussed by \textit{W. Liu} and \textit{N. Trotignon} [``The \(k\)-in-a-tree problem for graphs of girth at least \(k\),'' Discrete Appl. Math. 158, No.\,15, 1644--1649 (2010; Zbl 1198.05142)].