The three-in-a-tree problem
type: Item
instance of: scholarly article
title: The three-in-a-tree problem
zbMATH Open document ID: 1231.05246
author: Maria Chudnovsky
author: Paul Seymour
published in: Combinatorica
publication date: 2011-12-19T00:00:00Z
review text: 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)].
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 5990559
zbMATH Keywords: induced subgraph testing, theta, pyramid
MaRDI profile type: Publication
full work available at URL: s00493-010-2334-4
OpenAlex ID: W2104062785
cites work: On the complexity of testing for odd holes and induced odd paths
cites work: Detecting a Theta or a Prism
cites work: Recognizing Berge graphs
cites work: Algorithms for Perfectly Contractile Graphs
DOI: 10.1007/S00493-010-2334-4
Recommended article: The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
Recommended article: Three-in-a-tree in near linear time
Recommended article: The four-in-a-tree problem in triangle-free graphs
Recommended article: FPT and kernelization algorithms for the induced tree problem
Recommended article: Characterization of partial 3-trees in terms of three structures
Recommended article: Q3334090
Recommended article: On the SPANNING \(k\)-TREE problem
Recommended article: Finding induced trees
Recommended article: Q2934642
Recommended article: Complexity of Finding Embeddings in a k-Tree
description: scientific article; zbMATH DE number 5990559