The three-in-a-tree problem
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)].
- The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
- Three-in-a-tree in near linear time
- The four-in-a-tree problem in triangle-free graphs
- FPT and kernelization algorithms for the induced tree problem
- Characterization of partial 3-trees in terms of three structures
- scientific article; zbMATH DE number 3866594
- On the SPANNING k-TREE problem
- Finding induced trees
- Testing for a theta
- Complexity of Finding Embeddings in a k-Tree
- Every tree is 3-equitable
- The sandwich problem for decompositions and almost monotone properties
- Detecting a long even hole
- The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
- The (theta, wheel)-free graphs. IV: Induced paths and cycles
- A faster algorithm to recognize even-hole-free graphs
- Detecting an induced subdivision of \(K_{4}\)
- Finding induced paths of given parity in claw-free graphs
- The \(k\)-in-a-path problem for claw-free graphs
- FPT and kernelization algorithms for the induced tree problem
- Testing for a theta
- Large Induced Subgraphs via Triangulations and CMSO
- Detecting a Theta or a Prism
- Three tree-paths
- scientific article; zbMATH DE number 4031768 (Why is no real title available?)
- Detecting an induced net subdivision
- The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
- Finding a subdivision of a digraph
- A class of three-colorable triangle-free graphs
- CIO and ring graphs: deficiency and testing
- Exact Solution Algorithms for the Chordless Cycle Problem
- A structure theorem for graphs with no cycle with a unique chord and its consequences
- Induced disjoint paths in claw-free graphs
- A faster algorithm to recognize even-hole-free graphs
- Faster 3-coloring of small-diameter graphs
- The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
- MIP formulations for induced graph optimization problems: a tutorial
- Finding a shortest even hole in polynomial time
- Maximum weighted induced forests and trees: new formulations and a computational comparative review
- Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
- On the forbidden induced subgraph sandwich problem
- The k-in-a-tree problem for chordal graphs
- Integer programming formulations for the \(k\)-in-a-tree problem in graphs
- Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
- Semidefinite programming bounds and a branch-and-bound algorithm for the chordless cycle problem
- Induced minor models. I: Structural properties and algorithmic consequences
- Parameterized max min feedback vertex set
- Detecting \(K_{2,3}\) as an induced minor
- Max weight independent set in graphs with no long claws: an analog of the Gyárfás' path argument
- Complexity of the list homomorphism problem in hereditary graph classes
- Improved algorithms for perfect graphs and odd holes
- Graphs with no long claws: an improved bound for the analog of the Gyárfás' path argument
- Induced disjoint paths without an induced minor
- Clique or hole in claw-free graphs
- The four-in-a-tree problem in triangle-free graphs
- Finding induced trees
This page was built for publication: The three-in-a-tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653792)
