A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that for each node its neighborhood in T induces a connected subgraph in G. The problem of determining whether a graph contains an LCST or not has been proved to be NP-complete, even if the graph is planar or chordal. The main result of this paper is a linear time algorithm that, given an SC 3-tree (i.e. a maximal planar chordal graph), determines in linear time whether it contains an LCST or not, and produces one if it exists. We give an analogous result even for the case when the input graph is an SC 2-tree (i.e. a maximal outerplanar graph).
A locally connected spanning tree (LCST) T of a graph G is a spanning tree of
G such that for each node its neighborhood in T induces a connected subgraph
in G [
Cai proved in [
In particular, in [
%#+,'-( !"#$%&'( ./$#*0'-( !"#$%&'( %1$2!/2%( )&/"( 1*/2$3&'( !"#$%&'(
)'&*&$( .)'1/( !1$!+'&$( &$!( 67(84/$22.( 9:&;1:&'(#+/2$)'&*&$<( 67(=4/$22.( 9>)#'#*1&*(*2/?#$@.<( !#0$&)".(
!#4 ,1)&$5/2(
In this paper we consider the SC 3-trees (i.e. maximal planar chordal graphs)
- an interesting and naturally defined subclass of k-trees introduced in [
The rest of this paper is organized as follows: Section 2 is devoted to recall some known notions and to state some preliminary results that will be useful in the successive two sections. Section 3 is devoted to give a linear time algorithm for finding an LCST on an SC 2-tree; it is preliminary to Section 4, where the idea provided in the previous section is generalized and refined in order to prove that an LCST of an SC 3-tree can be found in linear time, if it exists. Finally, Section 5 concludes the paper addressing some open problems.
In this section we recall some known notions, and state some preliminary lemmas for SC k-trees that will be useful in the main part of this paper restricted to k = 2, 3.
Definition 1. [
In this paper we deal with the two classes of SC 2-trees and SC 3-trees. SC
2-trees coincide with maximal outerplanar graphs [
Definition 2. [
Let S be an (u, v)-separator of G. S is a minimal (u, v)-separator if no proper subset of S separates u from v. More generally, S is a minimal separator if it is a minimal (u, v)-separator, for some pair (u, v) of non adjacent nodes.
Given a set of nodes V 0 ⊆ V of a graph G, we denote by G[V 0] the subgraph induced in G by the nodes in V 0.
We now give some properties of a minimal separator of an SC k-tree. Due to lack of space, the proofs are deferred to the Appendix.
Lemma 1. Let G be an SC k-tree, and S be a minimal separator in G, then the graph G[V \ S] has exactly two connected components AS and BS and the two graphs G[AS ∪ S] and G[BS ∪ S] are SC k-trees.
tu tu
From now on, fixed a minimal separator S, we will continue to call AS and BS the two connected components of G \ S.
In the following lemma we recall some simple properties of SC k-trees that can
be proved by induction on the number of nodes in G and that have been stated
either in [
Lemma 2. Let G be an SC k-tree, then (i) G has (k + 1)-cliques but no (k + 2)-cliques, (ii) every minimal separator of G is a k-clique, (iii) G is a chordal graph, (iv) For each k-clique K in G there exists a node t such that K ∪ {t} induces a (k + 1)-clique in G.
Lemma 3. Let G be an SC k-tree, then for any minimal separator S in G there are two nodes a and b, such that S is an (a, b)-separator; moreover S ∪ {a} and S ∪ {b} are (k + 1)-cliques in G.
Proof. see Appendix. tu
We now recall the following generalization of line graphs introduced in [
In the following, for a node X in Lk(G), with a small abuse of notation, we will denote by X also the set of nodes of G that are in the the k-clique corresponding to X.
Lemma 4. Let G be an SC k-tree, then a k-clique S in G is a minimal separator if and only if there exist two adjacent nodes X1 and X2 in Lk+1(G) such that S = X1 ∩ X2.
Proof. see Appendix. tu
The k-line graphs have been used to obtain the following characterization of
SC k-trees:
Theorem 1. [
An SC k-tree whose (k + 1)-line graph Lk+1(G) is a path is called k-path.
Since our algorithms exploit the (k +1)-line graph, we are interested to output Lk+1(G) in linear time from an SC k-tree input graph G; this is possible, as shown by the following result.
Lemma 5. Let G be an SC k-tree; then tree Lk+1(G) can be computed in linear time.
Proof. see Appendix.
Given a graph G, and one of its spanning trees T , for each node v of G, NT (v) represents the set of the nodes of G that are adjacent to v in T ; these nodes will be called T -neighbors of v. The next lemma states a necessary condition that an LCST of a SC k-tree satisfies. As we will see later, 3 states the sufficiency of this condition for the case k = 3.
Lemma 6. Let G be an SC k-tree, k ≥ 2, S be one of its minimal separators and T be an LCST in G. We have that: (i) if T [S] contains an isolated node, then its T -neighbors completely lie either in AS or in BS . (ii) G[S] contains at least one edge of T .
Cai [
Corollary 1. An SC 2-tree G contains an LCST if and only if G does not contain as induced subgraph a 3-sun.
From the characterization above, we deduce the structure of the subclass of SC 2-trees admitting an LCST (i.e. 2-paths, in Lemma 7 and Corollary 2), and from there we look for the actual edges of the existing LCST (Lemma 8). Lemma 7. Let G be an SC 2-tree. Its 3-line graph L3(G) has nodes of degree 3 if and only if G contains a 3-sun as induced subgraph.
Proof. see Appendix.
Now, since an SC k-tree G is a k-path if and only if Lk+1(G) is a path, from the above two results we have: Corollary 2. An SC 2-tree G contains an LCST if and only if L3(G) is a path.
Now we give a characterization of LCSTs of 2-paths. This characterization allows us to design an algorithm that finds an LCST of a 2-path in linear time. Lemma 8. Let G be a 2-path, and T be one of its spanning trees. T is an LCST if and only if, for each minimal separator S = {x, y} of G the edge xy is in T . Proof. see Appendix.
From the above results it is easy to obtain a linear time algorithm that, given an n node SC 2-tree G, return an LCST of G if it exists, returns ’no’ otherwise.
Input: an n node SC 2-tree G; Output: an LCST of G if it exists, NO otherwise.
Compute tree L3(G); if L3(G) is not a path then return no; Let X1, X2, . . . Xn−2 be a linear order of the nodes of the path L3(G); T ← ∅; if L3(G) consists of a single node X1 then
insert in T any two edges of the 3-clique X1 and return T ; for i = 1 to n − 3 do
add to T the edge in the minimal separator Xi ∩ Xi+1; Let Xj = {xj, yj, zj} for j ∈ {1, n − 2}; Let x1y1 be the edge in T for X1 ∩ X2 and xn−3yn−3 be the edge in T for Xn−3 ∩ Xn−2; Add to T the two edges z1x1 and zn−2xn−2; return T . Theorem 2. (Correctness and Complexity) Algorithm FindLCSTinSC2trees determines an LCST of a given SC 2-tree if and only if it exists and runs in linear time.
Proof. If L3(G) is not a path the algorithm, in agreement with Lemma 2, correctly returns "no".
It remains to show that the tree T constructed by the algorithm visiting the path L3(G) is an LCST of G. This easily follows noting that the algorithm constructs the LCST T exploiting the characterization in Lemma 8 and selects all edges induced by each minimal separator of G. Note that, after the selection in T of the n − 2 minimal separators of G, it remains to connect to T the only two nodes of degree 2, z1 and zn−2, that occur in G. The node z1 is connected in T to a node of the minimal separator X1 ∩ X2 while the node zn−2 is connected in T to a node of of the minimal separator Xn−3 ∩ Xn−2. It is easy to see that the resulting spanning tree of G is an LCST.
For what concerns the time complexity, observe that L3(G) can be computed in linear time (cf. Lemma 5) and the same asymptotic time is sufficient also to traverse the n − 2 nodes of the path L3(G) to gather the edges of T . tu 4
In the previous section, we have seen that it is easy to determine an LCST of an SC 2-tree G, if it exists, exploiting its L3(G). Unfortunately, when we move to SC 3-trees, things seem to be not so easy anymore. Nevertheless, we will show that it is possible to determine an LCST of an SC 3-tree G, if it exists, exploiting its L4(G), in linear time. This is the aim of this section. Lemmas 9 and 10 are technical statements needed for the proof of Theorem 3, which gives a necessary and sufficient condition for the existence of an LCST in an SC 3-tree.
In the following statement, the graph 2K2 is the disjoint union of two copies of K2.
Lemma 9. Let G be an SC 3-tree and T be one of its spanning trees. If, for each minimal separator S = {x, y, z} of G, one of the following is true: (i) T contains exactly two edges of G[S] (ii) T contains exactly one edge of G[S] (w.l.o.g. this edge is xy) and either
NT (z) ⊆ AS or NT (z) ⊆ BS then, for each node X in L4(G) it holds T [X] 6= 2K2.
Lemma 10. Let G be an SC 3-tree and T be one of its spanning trees. If, for each minimal separator S = {x, y, z} of G, the following is true: (ii) T contains exactly one edge of G[S] (w.l.o.g. this edge is xy) and either NT (z) ⊆ AS or NT (z) ⊆ BS then G is a 3-path and T is an LCST.
Theorem 3. Let G be an SC 3-tree, and T be one of its spanning trees. T is an LCST if and only if, for each minimal separator S = {x, y, z}, one of the following is true: (i) T contains exactly two edges of G[S]; (ii) T contains exactly one edge of G[S] (w.l.o.g. this edge is xy) and either
NT (z) ⊆ AS or NT (z) ⊆ BS .
Proof. We prove the two implications separately.
(⇒) Let T be an LCST, and let us prove that either (i) or (ii) hold on S.
First, notice that from item (ii) of Lemma 2, G[S] is a 3-clique, so it cannot contain three edges of T , otherwise a cycle would occur in T ; so, in view of Lemma 6, G[S] contains either one or two edges of T . If it contains exactly two edges of T , then (i) holds and we have done. If, on the contrary, G[S] contains exactly one edge xy of T then, by Lemma 6, NT (z) has an empty intersection either with AS or with BS , that is (ii) holds.
(⇐) Let us now assume that S satisfies either (i) or (ii), and let us prove that T is an LCST. The proof proceeds by induction on the number n of nodes of G. For n = 4 ( the basis of the induction) G is a 4-clique and each spanning tree of G is an LCST and the claim is trivially true since no separator exists. Assume now that G has n > 4 nodes and the claim is true for every SC 3-tree with less than n nodes. If all the minimal separators of G satisfy (ii), by Lemma 10 we have that G is a 3-path and T is an LCST.
It remains to consider the case in which there exists a separator S˜ of G that satisfies (i). Consider graphs G1 = G[AS˜ ∪ S˜] and G2 = G[BS˜ ∪ S] and the ˜ spanning trees T1 = T [AS˜ ∪ S˜] of G1 and T2 = T [BS˜ ∪ S˜] of G2. In view of Lemma 1, graphs G1 and G2 are SC 3-trees and each separator of one of these two graphs is in fact a separator of G hence, for each separator S of Gi, 1 ≤ i ≤ 2, the tree Ti satisfies either (i) or (ii). By inductive hypothesis, it follows that T1 and T2 are LCSTs of G1 and G2, respectively. Moreover, we have For each u not in S˜, we already know that its T -neighbors are connected in G \ {u} (since T1 is an LCST of G1 and T2 in an LCSTs of G2); for each u in S˜, its T -neighbors are partially in AS˜ (and they are connected in AS˜ ∪ S˜), partially in AS˜ (and they are connected in BS˜ ∪ S˜), and partially in S˜ (through which all the T -neighbors of u are connected since S˜ is a 3-clique in G). It follows that T is an LCST of G. tu
The next three definitions aim to introduce the concept of partial solution and their labels, which will be the crucial operating principle of the algorithm. A partial solution is simply a “piece" of LCST of a peripheral portion of the graph in input, and those solutions are combined together at each iteration, if possible. Definition 4. Let S = {x, y, z} be a minimal separator of an SC 3-tree G. Let G0 be the graph obtained from G by substituting set BS with the single node {b} connected to all the three nodes in S. A partial solution on AS ∪ S w.r.t. S, HAS∪S , is a spanning forest of AS ∪ S such that there exists an LCST T of G0 such that HAs∪S = T [AS ∪ S].
In the following we will call simply H a partial solution when S and AS ∪ S are clear from the context.
Theorem 3, characterizing LCSTs in SC 3-trees, suggests that partial solutions fall in exactly three distinct categories, depending on how many edges of H are induced in S, and depending on the presence or not of an isolated node in H. The next definition formalizes this fact.
Definition 5. Let S = {x, y, z} be a minimal separator of an SC 3-tree G. Let H be a partial solution on AS ∪ S w.r.t. S. We say that H has label: – αx if yz is an edge of H and x is isolated in H; – βx if xy and xz are both in H; – γx if yz is an edge of H, xy and xz are not in H, and x is not isolated in
H.
Analogous definitions can be given for labels αy, βy and γy, and αz, βz and γz. Definition 6. Let S be a minimal separator in G, and assume |AS | = 1. The canonical partial solutions of G[AS ∪ S] associated to label χv (with χ ∈ {α, β, γ} and v ∈ S) are depicted below.
We are now ready to describe the algorithm that, given an SC 3-tree, determines an LCST if it has one. We highlight that, in order not to overburden the exposition, we focus on the decisional problem. It is not difficult, given the information gathered in the decisional version of the algorithm, to find the edges of the LCST, as will be explained later.
From now on, we assume L4(G) to be rooted in a degree 1 node, R. For any node X 6= R, we denote by f (X) its parent, that is the first node encountered on the unique path from X to R; by X¯ we denote the set of nodes of L4(G) in the subtree rooted at X. To not clutter the exposition we will sometimes denote with X¯ also the corresponding set of nodes in G, that is {x ∈ V (G) : x ∈ Y and Y ∈ X¯ }.
Since we established the equivalence between minimal separators of G and edges of L4(G) (cf. Lemma 4), in the following we will identify a minimal separator S = X ∩ f (X) of G with the corresponding edge Xf (X) of L4(G); moreover, we define the set of labels of edge Xf (X) as L(Xf (X)) = {χv : ∃ a partial solution on X w.r.t. X ∩ f (X) with label χv}.
The very high level idea of the algorithm consists in traversing L4(G) in post-order; when visiting a node X, we compute the set L(Xf (X)) of labels using the sets of labels of the children of X, Y1, ..., Yc, which have already been computed. This is done with the aim of extending the partial solutions of Yi, combining them in a partial solution of X. It is clear that G contains an LCST if and only if L(Y R) 6= ∅, where Y is the only child of root R.
We now focus on the issue of assigning to an edge Xf (X) its set of labels L(Xf (X)). First of all, notice that if X is a leaf, then the partial solutions of X are exactly the nine canonical partial solutions, so in this case L(Xf (X)) contains all nine labels, that is L(Xf (X)) = {χv|χ ∈ {α, β, γ}, v ∈ X ∩ f (X)}. Otherwise, assume for example that X has two children Y1, and Y2. By brute force we test every pair of 2 labels, each one from the set L(Y1X) × L(Y2X), that is the cartesian product of L(Y1X) and L(Y2X). We “decode” these labels in the corresponding canonical partial solution, which we combine, together with a subset of edges E0 of E(X), in a subgraph H of G[X ∪ Y1 ∪ Y2]. If this subgraph is a partial solution of G[X ∪ Y1 ∪ Y2 ∪ f (X)] w.r.t. separator X ∩ f (X), then we add the corresponding label to L(Xf (X)); the following algorithm does the job, and its correctness is proved below.
Input: An edge Xf (X) of L4(G); Output: The set of labels L(Xf (X))
G0 ← G[X ∪ f (X) ∪ Sic=1 Yi]; L(Xf (X)) ← ∅; foreach (χ1v1 , ..., χcvc ) ∈ L(Y1X) × ... × L(YcX) do
Let Hi be the canonical part. sol. of G0[Yi] associated to χivi , i = 1, ..., c; foreHac←hs(uXbs∪etSEic=01⊆YEi,(EX0 )∪dSoc
i=1 E(Hi)); if H is a partial solution of G0[X ∪ Sic=1 Yi] w.r.t. separator Xf (X) then
return L(Xf (X)).
Notice that, when c = 0, the cartesian product L(Y1X) × ... × L(YcX) is by definition equal to the set containing the empty tuple {()}; so, when X is a leaf, the external cycle is executed exactly once, the Hi’s do not exist, and H = (X, E0) in every iteration of the inner cycle. Also, notice that when at least one of the L(YiX)’s is empty, then L(Y1X) × ... × L(YcX) = ∅, so the outer cycle is never executed, and the output L(Xf (X)) is the empty set.
Before proving the correctness of Algorithm Compute-Labels, we highlight that its time complexity is constant, since the cardinality of L(Y1X)×...×L(YcX) is always at most 93, there are a constant number of subsets of E(X), and the “if” condition can be verified in constant time since G0 has size O(c) = O(1). Notice that Compute-Labels may be substituted by a constant size look-up table, if one is interested in the overall efficiency of the algorithm (see Figure 3 in Appendix).
The following lemma is needed in the proof of the correctness of algorithm Compute-Labels. Since it is an immediate consequence of the definition of partial solution, its proof is omitted.
Lemma 11. Let G be a SC 3-tree, Xf (X) be an edge of L4(G). Let G0 = G[(V \ X) ∪ X]. Assume G has a LCST T such that T [X] is a partial solution with label χv. Then, G0 has a LCST T 0 such that T 0[X] is the canonical partial solution associated to label χv.
Lemma 12. After the execution of Algorithm Compute-Labels on input Xf (X), L(Xf (X)) contains label χv, (χ ∈ {α, β, γ} and v ∈ X ∩ f (X)) if and only if there exists a partial solution of G[X] having label χv.
Proof. see Appendix.
We are ready to give the pseudocode of the algorithm deciding whether an SC 3-tree has an LCST or not.
Input: An n node SC 3-tree G; Output: yes if an LCST of G exists, no otherwise. if n = 4 then return yes; Compute L4(G); Root L4(G) in a degree 1 node R; Let Y be the only child of R; foreach node X 6= R of L4(G) in postorder do
L(Xf (X)) ← Compute-Labels(Xf (X)); if L(Y R) 6= ∅ then return no; else return yes.
Theorem 4. (Correctness and Complexity) Algorithm Decide-LCSTonSC3trees returns “yes” if and only if the SC 3-tree in input has an LCST, in linear time. Proof. If n = 4, then obviously any spanning tree of G is locally connected, and the algorithm returns "yes". Otherwise, by Lemma 12, we have that L(Y R) is nonempty if and only if there exists a partial solution H of G[Y ] with respect to the minimal separator Y R. It is easy to see that H can be extended to a LCST of G adding a single edge.
Moreover, the algorithm is linear. Indeed, L4(G) can be computed in linear time (cf. Lemma 5), and algorithm Compute-Labels is called O(n) times, and, as already noted, has constant cost. tu
In this extended abstract there is no space to detail how to reconstruct an LCST from the labels assigned in the algorithm, so here we will give only an overview. We can traverse again L4(G), this time in a pre-order fashion; starting from the edge incident to the root, we arbitrarily choose one label; this label implies a certain canonical partial solution, so we add the corresponding edges to the current LCST. At the general iteration, we proceed visiting the children of the current node having already chosen a label of the separator corresponding to the edge connecting it with its father; this label came up from precise labels on the edges connecting this node to its children, so we are forced to choose exactly those labels, and we add in the LCST the corresponding edges of G. 5
We have proved that the problem of finding an LCST is linearly solvable on
the classes of SC 3-trees; an analogous result holds for the case when the input
graph is an SC 2-tree. Even supported by the results in [
NT (x) ∩ S = ∅ ⇒ NT (x) ⊆ AS or NT (x) ⊆ BS ; – increase the number of labels and specify their description; – generalize Algorithm Compute-Labels.
A minor modification of this algorithm would allow the enumeration of all LCSTs of an SC k-tree, still running in polynomial time, for any fixed k. Indeed, the algorithm would have polynomial delay and the number of LCSTs in an SC k-tree is upper bounded by nf (k), where f is the number of possible labels (f is exponential in k or worse). This follows from the fact that an SC k-tree has at most n minimal separators, and that an LCST can behave in at most f (k) different ways on a minimal separator.
Moreover, we highlight that the result by Cai characterizes the SC 2-trees not admitting an LCST by means of a forbidden configuration, i.e. the 3-sun graph. For what concerns the SC 3-trees, we know that some of them do not admit an LCST (for example the one whose L4(G) has one node of degree 4 and three of the adjacent nodes have degree 4; all the other nodes are leaves); we wonder whether, also in this case, it is possible to characterize them by means of certain forbidden configurations.
Proof. Proceed by induction on the number n of nodes in G = (V, E). If n = k+1, then G is a (k + 1)-clique and the claim is trivially true because no separator exists. Assume now that the claim is true for each SC k-tree with less than n > k + 1 nodes and let G be an SC k-tree with n nodes. In view of the recursive definition of the SC k-trees, there is a node t in G and a k-clique K such that G0 = G[V \ {t}] is an SC k-tree with n − 1 nodes and K is the set of neighbors of t in G. Note that the separators of G are all the separators of G0 plus the separator K. Let S be a separator of G. Two cases can arise.
– S is the k-clique K. In this case let AS = V \ (S ∪ {t}) and BS = {t} and the claim follows since G[AS ∪ S] is the SC k-tree G0 and G[BS ∪ S] is the SC- k tree given by the k-clique K. – S is also a separator in G0. By the inductive hypothesis there exist two sets A0S and BS0 satisfying the claim in G0. Note that it cannot be both A0S ∩K 6= ∅ and BS0 ∩ K =6 ∅ (otherwise S would not be a separator). W.l.o.g. assume BS0 ∩ K = ∅ and consider AS = A0S ∪ {t} and BS = BS0. Note that AS is a connected component in G (since A0S is a connected component in G0 and t is connected to at least a node in A0S). Moreover G[AS ∪ S] is the SC k-tree obtained connecting the node t to the k-clique K in the SC k-tree G0[A0S ∪ S] and G[BS ∪ S] is the SC k-tree G0[BS0 ∪ S].
Proof. Proceed by induction on the number n of nodes in G. If n = k + 1, then G is a (k + 1)-clique and the claim is trivially true because no separator exists. Assume now that the claim is true for each SC k-tree with less than n nodes and let G be an SC k-tree with n nodes. In view of the recursive definition of the SC k-trees, there is a node a in G and a k-clique K such that G0 = G − {a} is an SC k-tree with n − 1 nodes and K is the set of neighbors of a in G. Note that K is a (a, b)-minimal separator for G where b is a node in G0 connected to all the nodes in K (the existence of such a node is ensured by item (iv) of Lemma 2). Thus the separator K of G satisfies the claim. Moreover all the others separators in G are also separators in G0 thus the claim follows by inductive hypothesis.
Proof. We prove the two implications separately.
(⇒ ) Since S is a minimal separator in G, by Lemma 3 there are in G two nodes a and b such that S is an (a, b)-separator and S ∪ {a} and S ∪ {b} are k + 1-cliques in G. Let X1 and X2 be the two nodes in Lk+1(G) corresponding to the k + 1-cliques S ∪ {a} and to S ∪ {b} respectively. By definition of Lk+1(G), these nodes are adjacent and the claim follows. tu tu (⇐ ) We will show that the k-clique S = X1 ∩ X2 in G is a minimal (a, b)separator where a = X1 \ S and b = X2 \ S.
Suppose, by contradiction, that a and b are connected in the subgraph G0 induced by the nodes V \ S. Note that a and b not are adjacent in G (otherwise we have in G a (k + 2)-clique induced by nodes of X1 ∪ X2 against item (i) in Lemma 2) and let P =< a, t1, . . . ti, b >, with i ≥ 1, be a shortest path from a to b in G0. We will prove that each node of P must be connected to all the nodes in the set S, so leading to a contradiction since set {t1} ∪ X1 forms a (k + 2)-clique in G.
To prove that each node ti in P must be adjacent to all the nodes in the set S, let us assume, by contradiction that there is a node tj in P and a node u in S such that ti and u are not adjacent. Let t be the first node adjacent to u we meet along the path P from tj to a and let t0 be the first node adjacent to u we meet along the path P from ti to b. Now consider in G the cycle consisting of the nodes in P from t to t0 and the node u. This cycle contains at least 4 nodes (i.e. t, tj, t0 and u) and is cordless (since P is a minimal path from a to b). Thus we have a contradiction in view of item (iii) in Lemma 2. tu
Proof. A perfect elimination ordering (peo) of G is an order v1, v2 . . . vn of its nodes such that the set P red(vi) , 1 ≤ i ≤ n, of the nodes that are adjacent to vi in G and that precede vi in the order, form a clique.
Rose and al. in [
Proof. Let x be an isolated node in T [S]. By contradiction, assume that NT (x) has a non empty intersection both with AS and with BS. Let a and b be the T -neighbors of x such that a ∈ AS and b ∈ BS; since T is an LCST, a and b must be connected in G by either an edge or a path not passing through any other node of S, and this is a contradiction since S is a separator.
In order to prove the second assertion, assume by contradiction that subgraph G[S] does not contain any edge of T . By the first assertion, each node in S has its T -neighbors either all in AS or all in BS. But in this case, for each node a ∈ A and b ∈ B it cannot exists a path in T connecting a to b. Thus T is not a spanning tree. tu
Proof. If G contains a 3-sun, then there are three 3-cliques all having an edge in common with the same (central) 3-clique, hence L3(G) has a node of degree at least 3. Vice-versa let X = {x, y, z} be a node of degree 3 in L3(G). Let Y1 = {x, y, a}, Y2 = {x, z, b} and Y3 = {y, z, c} be the three neighbors of X, then the six nodes {x, y, z, a, b, c} induce a 3-sun in G. tu
Proof. We prove the two implications separately.
(⇒ ) If T is an LCST, the claim immediately follows from property (ii) in Lemma 6.
(⇐ ) Proceed by induction on the number n of nodes in G. If n = 3 the claim trivially holds, because no separator exists. If n > 3 there exists at least a separator S = {x, y}. In view of Lemma 1 and by definition of k-paths, G[AS ∪ S] and G[BS ∪ S] are 2-paths and hence they satisfy the inductive hypothesis, implying that T [AS ∪ S] and T [BS ∪ S] are LCSTs. Merging together T [AS ∪ S] and T [BS ∪ S] we get a tree T that is a LCST because edge xy belongs to T . tu
Proof. Suppose, by contradiction, that there exists a 4-clique X = {x, y, z, t} in G = (V, E) such that T [X] = 2K2. This implies that, for each minimal separator S ⊂ X of G, it holds (ii). Let S = {x, y, z} be any of these separators and let z be the isolated node in T [S]. Without loss of generality let BS be the component of G[V \ S] containing NT (z). In graph T [AS ∪ S] node z is hence isolated. The above reasoning applies to any other separator in X. Thus the path in T connecting the two edges of the 2K2 must be in X and this contradicts the assumption that T [X] = 2K2. tu
Proof. First we show that G is a 3-path. By contradiction assume that tree L4(G) is not a path. Let X = {x, y, z, t} be a node of L4(G) with three neighbors Y1, Y2 and Y3. Consider now the three minimal separators Si = X ∩ Yi, 1 ≤ i ≤ 3 (cf. Lemma 4). In order to fix the ideas let t ∈ X be the node in Ti Yi and S1 = {x, y, t}, S2 = {x, z, t} and S3 = {z, y, t}. In each graph T [Si], 1 ≤ i ≤ 3, there is a single isolated node, if this node is t for all the three graphs, then xy, xz and yz are in T . Thus the set {x, y, z} is a cycle in T , a contradiction. Hence there is a minimal separator Si,1 ≤ i ≤ 3, such that t is not isolated in T [Si], w.l.o.g. let it be S1 and let xt ∈ E(T ). This implies that y is the only isolated node in T [S1], z is the only isolated node in T [S2] and the edges xy, ty, xz and tz are not in T . This in turn implies that yz is the only edge in T [S3]. Summarizing, we have that the edges xt and yz form a 2K in the 4-clique X, a contradiction to Lemma 9.
Now we show that T is an LCST. We proceed by induction on the number n of nodes in the 3-path G = (V, E). If n = 4, then G is a 4-clique and the claim is trivially true because any spanning tree of a 4-clique is locally connected. Assume now that the claim is true for every 3-path with less than n > 4 nodes and let G be a 3-path with n nodes. Let t be the last node added to G in its recursive definition and consider the separator S = {x, y, z} identified by the neighbors of t in G. Observe that G0 = G[V \ {t}] is a 3-path with n − 1 nodes since L4(G0) can be obtained by L4(G) by cutting the leaf containing t. Moreover, for all the separators of G0 (note that these separators are also separators of G) T 0 = T [V \ {t}] satisfies (ii) in G0. Since T satisfies (ii) for the separator S in G, t cannot be adjacent in T to both x and y (otherwise a cycle is introduced in a tree), so the degree of t in T is at most 2. We will examine the two cases. 1. |NT (t)| = 1: T 0 is a spanning tree for G0 and, by inductive hypothesis, it is an LCST of G0. Moreover, since T is connected it must be either xt ∈ T or yt ∈ T (remember that S satisfies (ii)). W.l.o.g. assume that xt ∈ T . For each u ∈ V , it holds Now, using the fact that T 0 is an LNCS for G0 and that yt ∈ E and y ∈ NT 0 (x), it is easy to see that T is an LCST for G. 2. |NT (t)| = 2: Without loss of generality assume that NT (t) = {x, z}. Note that NT (z) = {t} since S satisfies (ii) in T . Let a be a node in G connected to all nodes in S (such a node there exists by Lemma 3). Since G is a 3-path, any induced 4-clique (in particular, K = {a, x, y, z}) contains at most 2 minimal separators, so besides {x, y, z}, at most one among {x, y, a}, {x, z, a} and {y, z, a} is a minimal separator contained in K. There are three cases to consider. (a) S is the only minimal separator in K. In this case G has only five nodes (the nodes {a, x, y, z, t}). The node a in T can be connected only to x or to y.
In the first case (where ax is in T ), we have NT (x) = {y, t, a} and NT (t) = {x, z}. Moreover x and t are the only nodes in T having degree greater than one. Thus we conclude that T is an LCST by noting that ay, yt and xz are edges of G.
In the second case ( where ay is in T ), x, t and y are the only nodes in T having degree greater then one and NT (x) = {y, t}, NT (t) = {x, z} and NT (y) = {x, a}. Thus again T is an LCST by noting that yt, xz and xa are edges of G. (b) S0 = {a, x, y} is a minimal separator in K. AS0 contains only t and z and T 0 = T [BS0 ∪ S0] is a spanning tree in G0 = G[BS0 ∪ S0] that satisfies (ii) on every minimal separator, hence -by inductive hypothesis - G0 is a 3-path and T 0 is an LCST. Summarizing, for each u ∈ V , it holds {z, x} if u = t NT (u) = {t} if u = z
NNTT 00 ((xu)) ∪ {t} iofthue=rwxise Now, using that T 0 is an LCST of G0, zx ∈ E, y ∈ NT 0 (x) and yt ∈ E, it is easy to see that T is a LCST of G. (c) S0 is a minimal separator in K and either S0 = {a, y, z} or S0 = {a, x, z}.
Assume first that S0 = {a, y, z}. Note that T 0 obtained by adding edge xz to T [V \ {t}] is a spanning tree of G0 = G[V \ {t}] and it satisfies (ii). Thus, by inductive hypothesis, T 0 is an LCST of G0. Note that S0 satisfies (ii) on T and since NT (z) = {t} it must be ay ∈ E(T ). Summarizing, for each u ∈ V , it holds
{z, x} if u = t NT (u) = {t} if u = z {y, t} if u = x NT 0 (u) otherwise Now, using that T 0 is an LCST of G0, and zx and yt are edges of G, it is easy to see that T is an LCST of G.
The reasoning is similar if we assume that the minimal separator S0 is {a, x, z}. In this case we can consider the spanning tree T 0 of G0 obtained by adding the edge yz to T [V \ {t}]. tu
Proof. (⇒) If X is a leaf, that is c = 0, then the canonical partial solution on G[X] = G[X] corresponding to label χv satisfies the statement.
Else, assuming 1 ≤ c ≤ 3, let E0 be the selected subset of E(X) such that H is a partial solution of G0[X ∪ Sc
i=1 Yi] w.r.t. separator Xf (X), for which label χv was added to L(Xf (X)). By structural induction, there are partial solutions Hi of G[Y i], having label χivi , i = 1, ..., c. By Lemma 11, if (X, E0 ∪ Sc i=1 E(Hi)) was not a partial solution of G[X], then neither would H be a partial solution of G0[X ∪ Sic=1 Yi], a contradiction. Finally, notice that G[X] has the same label of H, that is χv.
(⇐) If X is a leaf, then G[X] = G[X] admits all nine possible canonical partial solutions. Since c = 0, the outer cycle is executed exactly once on the empty tuple (), and the inner cycle will find a partial solution for each possible label. Assume now that 1 ≤ c ≤ 3. Assume there exists a partial solution H of G[X] with respect to separator Xf (X). Then, notice that H[Y i] is a partial solution of G[Y i] with respect to separator YiX with label χivi , so by structural induction L(YiX) contains label χivi , i = 1, ..., c. Let Hi be the canonical partial solution of G[Yi] with respect to separator YiX. Then, by Lemma 11, H = (X ∪ Sic=1 Yi, E0 ∪ Sic=1 E(Hi)) is a partial solution of G0[X ∪ Sic=1 Yi] with respect to separator Xf (X), where E0 = E(H[X]) is found by brute force by the inner cycle, and the corresponding label (that is the same as H) is added to L(Xf (X)). Table used in Algorithm Decide-LCSTonSC3-trees label oααααfββββββββγγγααααβββγγxyyxxxxxyyyxxxttyttt{ttttx, y, t} label oααααβββfββαααγβγ---------zxxxzzxxtzzt{tttx, z, t} label of------------------------{y, z, t} αxααα(yzz+(,,β+ββyαxzxxx(z)γ((γγz+,++,yy)yββ(x,((xxzα+xβ++zzz((zz,βxβγ+))xx+,(z,,xyzzzz+βxtββx((())))βββββγγγγγγyz+++,yyzx,,,(yyyzzzxxxxxγ,(()γγβzyy+yy++,xxx,yzzzβz(yy(((yy)))+)y+++zzzz,())y))yγy+y,,,zxyzzγγγy)()),xzz,z+z((()t+++z)tytt,zzzx)))z) label of {x, y, z} βz γy βy βx βy γz γz βx γx γy