Discrete Applied Mathematics 158 (2010) 1644–1649

Contents lists available at ScienceDirect

Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam

The k-in-a-tree problem for graphs of girth at least k
W. Liu a , N. Trotignon b,∗ a Université Grenoble 1, Joseph Fourier, France

b

CNRS, LIAFA, Université Paris 7, Paris Diderot, France

article

info

Article history:
Received 10 July 2009
Received in revised form 28 May 2010
Accepted 3 June 2010
Available online 1 July 2010
Keywords:
Tree
Algorithm
Three-in-a-tree k-in-a-tree Girth
Induced subgraph

abstract
For all integers k ≥ 3, we give an O(n4 )-time algorithm for the problem whose instance is a graph G of girth at least k together with k vertices and whose question is ‘‘Does G contains an induced subgraph containing the k vertices and isomorphic to a tree?’’.
This directly follows for k = 3 from the three-in-a-tree algorithm of Chudnovsky and
Seymour and for k = 4 from a result of Derhy, Picouleau and Trotignon. Here we solve the problem for k ≥ 5. Our algorithm relies on a structural description of graphs of girth at least k that do not contain an induced tree covering k given vertices (k ≥ 5).
© 2010 Elsevier B.V. All rights reserved.

1. Introduction
Many interesting classes of graphs are defined by forbidding induced subgraphs; see [1] for a survey. This is why the detection of several kinds of induced subgraph is interesting; see [5], where many such problems are surveyed. In particular, the problem of deciding whether a graph G contains as an induced subgraph some graph obtained after possibly subdividing prescribed edges of a prescribed graph H has been studied. It turned out that this problem can be polynomial or NP-complete according to H and to the set of edges that can be subdivided. The most general tool for solving this kind of problem (when the problems are polynomial) seems to be the three-in-a-tree algorithm of Chudnovsky and Seymour:
Theorem 1.1 (See [2]). Let G be a graph and x1 , x2 , x3 be three distinct vertices of G. Deciding whether there exists an induced tree of G that contains x1 , x2 , x3 can be performed in time O(n4 ).
How to use three-in-a-tree is discussed in [2] and further evidence of its generality is given in [5]. The complexity of four-in-a-tree is not known, nor more generally of k-in-a-tree, where k ≥ 4 is a fixed integer. But these problems are more tractable when restrictions are given on the girth (length of a smallest cycle) of the graph, as suggested by Derhy, Picouleau and Trotignon who proved the following.
Theorem 1.2 (See [3]). Let G be a triangle-free graph and x1 , x2 , x3 , x4 be four distinct vertices of G. Deciding whether there exists an induced tree of G that contains x1 , x2 , x3 , x4 can be performed in time O(nm).
Here, we study k-in-a-tree for graphs of girth at least k. Note that the problem is solved by the two theorems above for k = 3 and k = 4. For k ≥ 5, we follow the method that has been already successful for Theorems 1.1 and 1.2: studying the

∗

Corresponding author. Fax: +33 144276849.
E-mail addresses: wei@cmap.polytechnique.fr (W. Liu), nicolas.trotignon@liafa.jussieu.fr (N. Trotignon).

0166-218X/$ – see front matter © 2010 Elsevier B.V. All rights reserved. doi:10.1016/j.dam.2010.06.005 W. Liu, N. Trotignon / Discrete Applied Mathematics 158 (2010) 1644–1649

1645

Fig. 1. A k-structure (k = 7).

Fig. 2. A K4 -structure.

structure of a graph that does not contain the desired tree. It turns out that, in most cases, the structure is simple. Note that the proofs in the present work are independent from [2,3]: we do not use results from [2,3], and as far as we can see, our results do not simplify [2] or [3].
We call a k-structure any graph obtained from the cycle on k vertices by adding a pending path to each vertex of cycle; see
Section 4 for a formal definition. An example is shown in Fig. 1 which obviously does not contain an induced tree covering the k pending vertices. The main result of Section 2 states that, for k ≥ 3, a graph of girth at least k that does not contain an induced tree covering k given vertices must contain a k-structure. The main result of Section 4 states that (with one exception, see below), if the graph contains a k-structure, then the k-structure decomposes the graph, meaning that every vertex of the original cycle is a cut-vertex of the graph.
But there is a noteworthy exception that arises curiously only when k = 6. The graph G on Fig. 2 is obtained from K4 by subdividing all edges once, and by adding a pending path to each vertex of degree 2. This graph has girth 6. Let H be a connected induced subgraph of G that contains the six pending vertices. We claim that H contains at least three vertices of degree 3 in G. Otherwise, it does not contain at least two of them, so the pending vertex whose neighbor is between these is isolated; a contradiction. Hence, H contains three vertices of degree 3, and a cycle of length 6 goes through them. Hence, no induced tree of G can cover the six pending vertices. This is what we call a K4 -structure. The main result of Section 3 states roughly that if a graph of girth 6 contains a K4 -structure and if no induced tree covers the six pending vertices then the K4 -structure decomposes the graph, meaning that every pair of vertices of the original K4 and every vertex of degree 2 arising from the subdivisions is a cut-set of the graph.
Let us sum up the results. Our main result, Theorem 5.1, states that, when k ≥ 5, and G is a connected graph of girth at least k together with k vertices, then either G contains a k-structure that decomposes G, or k = 6 and G contains a K4 structure that decomposes G, or G contains an induced tree covering the k vertices. All this leads to an O(n4 )-time algorithm that decides whether a graph of girth at least k contains an induced tree that covers k prescribed vertices.

1646

W. Liu, N. Trotignon / Discrete Applied Mathematics 158 (2010) 1644–1649

Notation, convention, remarks
We use standard notation from [4]. Since we use only induced subgraphs, we say that G contains H when H is an induced subgraph of G. Also, by tree of G we mean an induced subgraph of G that is a tree. By path we mean induced path. In the complexity of the algorithms, n stands for the number of vertices of the input graph and m for the number of its edges.
We call the terminal of a graph any vertex of degree 1. Solving k-vertices-in-a-tree or k-terminals-in-a-tree is an equivalent problem, because if k vertices x1 , . . . , xk of graph G are given, we build the graph G obtained from G by adding a pending neighbor yi to xi , i = 1, . . . , k. An induced tree of G covers x1 , . . . , xk if and only an induced tree of G covers y1 , . . . , yk .
Hence, in the rest of the paper we assume for convenience that the vertices to be covered are all terminals.
2. Linking a vertex to a tree
Recall that a terminal in a graph is a vertex of degree 1. A branch-vertex is a vertex of degree at least 3. The following is a basic fact whose proof is omitted.
Lemma 2.1. A tree T with k terminals contains at most k−2 branch-vertices. Moreover, if T contains exactly k−2 branch-vertices then every branch-vertex is of degree 3.
Lemma 2.2. Let k, l be integers such that k ≥ 3 and 2 ≤ l ≤ k. Let G be a graph of girth at least k and x1 , . . . , xl be l distinct terminals of G. Let T be an induced tree of G whose terminals are x1 , . . . , xl−1 . Let Q be a path from xl to w such that w has at least one neighbor in T and no vertex of Q \ w has neighbors in T . Then one and only one of the following outcomes holds:

• T ∪ Q contains a tree of G that covers x1 , . . . , xl .
• k = l. Moreover, T and Q can be described as follows (up to a relabelling of x1 , . . . , xk−1 ):
1. T is the union of k − 1 vertex-disjoint paths s1 − · · · − x1 , s2 − · · · − x2 , . . . , sk−1 − · · · − xk−1 ;
2. the only edges between these paths are such that s1 − s2 − · · · − sk−1 is a path;
3. NT (w) = {s1 , sk−1 }.

This is algorithmic in the sense that, when T and Q are given, the tree of the first outcome or the relabelling of the second can be computed in time O(n3 ).
Proof. Clearly, at most one of the outcomes holds (because if the second holds then no tree of T ∪ Q can cover x1 , . . . , xl ).
Let us prove that at least one of the outcomes holds.
Let W = {w1 , . . . , wi } be the set of the neighbors of w in T . If i = 1 then T ∪ Q is a tree that covers x1 , . . . , xl , so let us suppose that i ≥ 2. Let us call a basic path any subpath of T linking two distinct vertices of W and with no interior vertices in W . All the basic paths are on at least k − 1 vertices because the girth of G is at least k. Now we consider two cases.

Case 1: for all basic paths R of T there exists an interior vertex vR of R that has degree 2 in T . Then, let S ← T ∪ Q . For all basic paths R, if R ⊆ S , then let vR be a vertex of degree 2 (in T ) of R, let S ← S \ {vR } and go to the next path R. At the end of this loop, one vertex of degree 2 is deleted from all basic paths. We remark that one vertex vR can be contained in several basic paths. Hence, S contains no more cycle, but is still connected because the deleted vertices have all degree 2 and exactly one is deleted in each basic path. Hence, we obtain a tree S that covers x1 , . . . , xl . This takes time O(n3 ) because we enumerate all the pairs wi , wj to find the basic paths.
Case 2: we are not in Case 1, so there exists a basic path R whose interior vertices are all of degree at least 3 in T . Then, since
T has l − 1 terminals, Lemma 2.1 says that it has at most l − 3 branch-vertices. On the other hand, since a basic path is on at least k − 1 vertices (because the girth is at least k), R contains at least k − 3 branch-vertices of T . So in fact, because l ≤ k, we have k = l, and R contains all the k − 3 branch-vertices of T . Since R has no interior vertex of degree 2, in fact R contains k − 1 vertices. We name s1 , . . . , sk−1 the vertices of R. Note that w is adjacent to s1 and sk−1 because R is a basic path. In particular, s1 and sk−1 are not terminals of G.
For all 1 ≤ i ≤ k − 1, si is a cut-vertex of T that isolates one terminal among x1 , . . . , xk−1 from all the other terminals.
Up to relabelling, we suppose that this terminal is xi . We name Pi the unique path of T between xi and si .
Note that w is not adjacent to s2 , . . . , sk−2 (because R is a basic path). So the second outcome of our lemma holds, unless w has at least one neighbor in some Pi \ si . For i = 1, . . . , k − 1, we let si be the neighbor of si along Pi , if w has a neighbor in Pi then we name wi the neighbor of w closest to xi along Pi , and if no such neighbor exists, we put wi = si .
Suppose that for all i = 1, . . . , k − 1 we have wi = si . Then, the paths xi − Pi − wi , i = 1, . . . , k − 1 together with Q and s1 , . . . , sk−1 form a graph with a unique cycle: w s1 · · · sk−1 w . By deleting a vertex sj such that wj = sj , we obtain a tree that covers x1 , . . . , xk .
Hence, we may assume that, for some i, wi = si , and up to symmetry we suppose that i ≤ k/2. Then w s1 · · · si si w is a cycle on i + 2 vertices, so i + 2 ≥ k because of the girth. Hence, k − 2 ≤ k/2, so k ≤ 4. Then the paths xj − Pj − wj , j = 1, . . . , k − 1, together with Q form a tree that covers x1 , . . . , xk .
A graph is a k-structure with respect to k distinct terminals x1 , . . . , xk if it is made of k vertex-disjoint paths of length at least one P1 = x1 − · · · − s1 , . . . , Pk = xk − · · · − sk such that the only edges between them are s1 s2 , s2 s3 , . . . , sk−1 sk , sk s1 .

W. Liu, N. Trotignon / Discrete Applied Mathematics 158 (2010) 1644–1649

1647

Lemma 2.3. Let k ≥ 3 be an integer. Let G be a connected graph of girth at least k and x1 , . . . , xl be l terminals, where 1 ≤ l ≤ k.
Then either G contains a tree that covers the l terminals or l = k and G contains a k-structure with respect to x1 , . . . , xk .
This is algorithmic in the sense that we provide an O(n4 ) algorithm that finds the tree or the k-structure.
Proof. We suppose that k is fixed and we prove the statement by induction on l. For l = 1 and l = 2, the lemma is clear: a tree exists (for instance, a shortest path linking the two terminals). Suppose that the lemma holds for some l − 1 < k and let us prove it for l. By the induction hypothesis, there exists an induced tree T of G that covers x1 , . . . , xl−1 . Let Q be a path from xl to some vertex w that has neighbors in T , and suppose that Q is minimal with respect to this property. Then, no vertex of Q \ w has a neighbor in T .
We apply Lemma 2.2. If the first outcome holds, we have our tree. Otherwise, T ∪ Q is a k-structure. All this can be implemented in time O(n4 ) because the terminals are taken one by one, there are at most n of them, and for each of them we rely on basic subroutines like BFS (Breadth First Search; see [4]) to find Q and on the O(n3 ) algorithm of Lemma 2.2.
3. The K4 -structure
A graph is a K4 -structure with respect to six distinct terminals xab , xac , xad , xbc , xbd , xcd if it is made of six vertex-disjoints paths of length at least one Pab = xab − · · · − sab , Pac = xac − · · · − sac , Pad = xad − · · · − sad , Pbc = xbc − · · · − sbc , Pbd = xbd − · · · − sbd , Pcd = xcd − · · · − scd and four vertices a, b, c , d such that the only edges between them are asab , asac , asad , bsab , bsbc , bsbd , csac , csbc , cscd , dsad , dsbd , dscd . (See Fig. 2.) We put X = {xab , xac , xad , xbc , xbd , xcd }.
We use the following ordering of the vertices a, b, c , d: a < b < c < d. We say that a K4 -structure K in a graph G decomposes G if the two following conditions hold:
1. for all i, j such that a ≤ i < j ≤ d, {i, j} is a cut-set of G that separates xij from X \ {xij };
2. for all i, j such that a ≤ i < j ≤ d, {sij } is a cut-set of G that separates xij from X \ {xij }.
Lemma 3.1. If a graph G of girth 6 contains a K4 -structure K with respect to six terminals xab , xac , xad , xbc , xbd , xcd , then one and only one of the following outcomes holds:

• K decomposes G;
• G contains a tree that covers xab , xac , xad , xbc , xbd , xcd .

This is algorithmic in the sense that, if K is given, testing whether K decomposes G or outputting the tree can be performed in time
O(n4 ).
Proof. Let us first check that at most one of the output holds. Suppose that the first outcome holds, and let H be a connected induced subgraph of G covering X . Then H must contain at least three vertices among a, b, c , d, because if it fails to contain two of them, say a, b, then xab is isolated from the rest of the graph because of Condition 1. Hence, we may assume that H contains a, b, c . Also, because of Condition 2, H must contain sab , sbc and sac . Hence, H contains the cycle asab bsbc csac a. Hence,
H cannot be a tree, so the second outcome fails.
Now let H be an induced subgraph of G that contains K and such that K decomposes H (H exists since K decomposes K ).
We show that, for any vertex v of G \ H , H ∪ {v } either is decomposed by K or contains a tree covering X . This will prove the theorem by induction and will be the description of an O(n4 ) algorithm since, for each v , the proof gives the way to actually build the tree when there is one by calling the algorithm of Lemma 2.2 and searching the graph (with BFS, for instance).
Note also that testing whether K decomposes some graph can be performed in linear time by 12 checks of connectivity.
Suppose that H ∪ {v } is not decomposed by K . From the definition of decomposition, there are two cases.

Case 1: Condition 1 fails. Up to symmetry, we suppose that {a, b} is a not cut-set of H ∪ {v } that separates xab from X \ {xab }.
Let Y (resp. Z ) be the connected component of H \ {a, b} that contains xab (resp. that contains K = K \ (Pab ∪ {a, b})). Hence, v has a neighbor in Y and a neighbor in Z . Let Q be a shortest path in Y ∪ Z ∪ {v } from xab to some vertex w that has a neighbor in K . Note that Q must go through v . Because K is a tree that covers X \ {xab }, we may apply Lemma 2.2 to K and Q in Q ∪ K . Hence, either we find the tree or w has exactly two neighbors in K that have degree 2 in K and that are adjacent to c or d. Since the girth is 6, we may assume up to symmetry that these two neighbors are sbc and sad . Because of the girth 6, w is not adjacent to a, b and sab .
If w has a neighbor in Pab , we let P be a shortest path from w to xab in Pab ∪ {w }. Otherwise, we let P = Pab . We observe that P ∪ {a, d, w } ∪ Pac ∪ Pad ∪ Pbc ∪ Pbd ∪ Pcd is a tree that covers X .
Case 2: Condition 1 is satisfied but Condition 2 fails. Up to symmetry, we suppose that {sab } is a not cut-set of H ∪ {v } that separates xab from X \ {xab }. Let us consider a path R in H ∪ {v } from xab to some vertex in K \ {Pab } and let us suppose that
R is minimal with respect to this property. Since Condition 1 is satisfied, R must be from xab to a or b (a say). Note that the neighbor of a along R cannot be adjacent to b (or there is a cycle on four vertices). We observe that R ∪ (K \ ({d} ∪ Pab )) is a tree that covers X .

1648

W. Liu, N. Trotignon / Discrete Applied Mathematics 158 (2010) 1644–1649

4. The k -structure
For k-structures, we assume that notation like that in the definition is used. We put X = {x1 , . . . , xk }. We say that a k-structure K in a graph G decomposes G if, for all i such that 1 ≤ i ≤ k, {si } is a cut-set of G that separates xi from X \ {xi }.
Lemma 4.1. Let k ≥ 5 be an integer. If a graph G of girth at least k contains a k-structure K with respect to k terminals x1 , . . . , xk then one of the following outcomes holds:

• K decomposes G;
• k = 6 and there exists a vertex v of G \ K such that K ∪ {v } is a K4 -structure with respect to x1 , . . . , x6 ;
• G contains a tree that covers X .

This is algorithmic in the sense that testing whether K decomposes G or outputting the tree or outputting a relabelling showing that K ∪ {v } is a K4 -structure can be performed in time O(n4 ).

Proof. Let H be an induced subgraph of G that contains K and such that K decomposes H (H exists since K decomposes
K ). We show that, for any vertex v of G \ H , H ∪ {v } either satisfies the first outcome or is a K4 -structure or contains a tree covering X . This will prove the theorem by induction and be the description of an O(n4 ) algorithm since, for each v , the proof gives the way to actually build the tree or the relabelling by calling the algorithm of Lemma 2.2 and searching the graph
(with BFS for instance). Note also that testing whether K decomposes some graph can be performed in time O(km), or O(nm) since k ≤ n, by k checks of connectivity.
Suppose that H ∪ {v } is not decomposed by K . Let Y (resp. Z ) be the connected component of H \ {s1 } that contains x1
(resp. that contains K = K \ P1 ). Up to symmetry, we may assume that v has a neighbor in Y and a neighbor in Z . Let Q be a shortest path in Y ∪ Z ∪ {v } from x1 to some vertex w that has a neighbor in K . Note that Q must go through v . Because
K is a tree that covers X \ {x1 }, we may apply Lemma 2.2 to K and Q in Q ∪ K . Hence, either we find the tree or w has exactly two neighbors in K and NK (w) must be one of the following: {s2 , sk }, {s2 , sk−1 }, {s3 , sk }, {s3 , sk−1 }, where si denotes the neighbor of si along Pi .
When NK (w) = {s2 , sk }, we observe that s2 s1 sk w is a square, i.e., a cycle on four vertices, contradicting our assumption on the girth.
When NK (w) = {s2 , sk−1 } (or symmetrically {s3 , sk }), then w is not adjacent to s1 (otherwise s1 s1 s2 w is a square). If w has a neighbor in P1 , we let P be a shortest path from w to x1 in P1 ∪ {w}. Otherwise, we let P = P1 . We observe that
{w } ∪ P ∪ (K \ {sk−1 }) is a tree that covers X .
We are left with the case when NK (w) = {s3 , sk−1 }. Suppose first that w has no neighbor in P1 . Then {w } ∪ K \ {s3 } is a tree that covers X . Suppose now that w has a neighbor in P1 \ {s1 , s1 }. We let P be a shortest path from w to x1 in
{w } ∪ (P1 \ {s1 , s1 }). If w s1 ∈ E (G), then P ∪ {s1 } ∪ (K \ (P1 ∪ {s3 })) induces a tree that covers X . If w s1 ∈ E (G), then we observe that P ∪ {s1 } ∪ (K \ (P1 ∪ {s3 , sk−1 })) induces a tree that covers X .
So we may assume that NP1 (w) is one of {s1 }, {s1 }. If NP1 (w) = {s1 } then s1 w s3 s3 s2 is a C5 , so k = 5 because of the girth assumption. Hence {w } ∪ K \{s3 , s4 } is a tree that covers X . So we are left with the case when NP1 (w) = {s1 }. Then w s1 s1 s2 s3 s3 is a C6 , so k = 5 or 6 because of the girth. If k = 5 then {w } ∪ K \ {s3 , s4 } is a tree that covers X . If k = 6 then K ∪ {w } is a K4 -structure, as shown by the following relabelling: xab ← x1 , xac ← x3 , xad ← x5 , xbc ← x2 , xbd ← x6 , xcd ← x4 , a ← w, b ← s1 , c ← s3 , d ← s5 , sab ← s1 , sac ← s3 , sad ← s5 , sbc ← s2 , sbd ← s6 , scd ← s4 .
5. The main result
Theorem 5.1. Let k ≥ 5 be an integer. Let G be a connected graph of girth at least k and x1 , . . . , xk be terminals of G. Then one and only one of the following holds:

• G contains a k-structure K with respect to x1 , . . . , xk and K decomposes G;
• k = 6, G contains a K4 -structure K with respect to x1 , . . . , x6 and K decomposes G;
• G contains a tree covering x1 , . . . , xk .

This is algorithmic in the sense that we provide an algorithm that outputs the tree or the structure certifying that no such tree exists in time O(n4 ).
Proof. By Lemma 2.3, we can output a tree covering X or a k-structure of G in time O(n4 ). If a k-structure K is output, then, by Lemma 4.1, we can check whether K decomposes G (in which case no tree exists), or find a tree, or find a K4 -structure K .
In this last case, by Lemma 3.1, we can check whether K decomposes G or find a tree.
Theorem 5.2. Let k ≥ 3 be an integer. Let G be a connected graph of girth at least k and x1 , . . . , xk be vertices of G. Deciding whether G contains an induced tree covering x1 , . . . , xk can be performed in time O(n4 ).
Proof. This follows from Theorem 1.1 for k = 3, from Theorem 1.2 for k = 4 and from Theorem 5.1 for k ≥ 5.
Remark. In all the proofs above for k ≥ 5, we use very often that the input graph contains no triangle and no square.
Forbidding longer cycles is used less often. This suggests that the k-in-a-tree problem might be polynomial for graphs with no triangle and no square. We leave this as an open question.

W. Liu, N. Trotignon / Discrete Applied Mathematics 158 (2010) 1644–1649

1649

References
[1] M. Chudnovsky, P. Seymour, Excluding induced subgraphs, in: Surveys in Combinatorics, in: London Mathematical Society Lecture Notes Series, vol.
346, 2007, pp. 99–119.
[2] M. Chudnovsky, P. Seymour, The three-in-a-tree problem, Combinatorica (in press).
[3] N. Dehry, C. Picouleau, N. Trotignon, The four-in-a-tree problem in triangle-free graphs, Graphs Combin. 25 (2009) 489–502.
[4] A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
[5] B. Lévêque, D. Lin, F. Maffray, N. Trotignon, Detecting induced subgraphs, Discrete Appl. Math. 157 (2009) 3540–3551.