The three-in-a-tree problem (Q653792): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00493-010-2334-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2104062785 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of testing for odd holes and induced odd paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Detecting a Theta or a Prism / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Recognizing Berge graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithms for Perfectly Contractile Graphs / rank | |||
Normal rank |
Latest revision as of 19:08, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The three-in-a-tree problem |
scientific article |
Statements
The three-in-a-tree problem (English)
0 references
19 December 2011
0 references
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)].
0 references
induced subgraph testing, theta, pyramid
0 references