A Locally Connected Spanning Tree Can Be Found in Polynomial Time on Simple Clique 3-Trees? Tiziana Calamoneri, Matteo Dell’Orefice, and Angelo Monti Computer Science Department, “Sapienza” University of Rome, Italy calamo/monti@di.uniroma1.it, matteodellorefice@gmail.com Abstract. 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). Keywords: locally connected spanning tree, SC k-trees, 2-trees, chordal graphs, planar graphs. 1 Introduction 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 [3]. It is well known that an interconnection network can be modeled as a graph and, in this context, the existence of such a spanning tree ensures, in case of site failures, effective communication among operative sites as long as these failures are isolated [14]. Cai proved in [4] that the problem of determining whether a graph contains an LCST is NP-complete even when the input graph is restricted to be planar or split (and, a fortiori, chordal). So, researchers have looked for special classes of graphs for which the problem is polynomially solvable. ? Partially supported by the Italian Ministry of Education and University, PRIN project "AMANDA: Algorithmics for MAssive and Networked DAta" Copyright c by the paper’s authors. Copying permitted for private and academic pur- poses. V. Biló, A. Caruso (Eds.): ICTCS 2016, Proceedings of the 17th Italian Conference on Theoretical Computer Science, 73100 Lecce, Italy, September 7–9 2016, pp. 103–121 published in CEUR Workshop Proceedins Vol-1720 at http://ceur-ws.org/Vol-1720 104 T. Calamoneri, M. Dell’Orefice and A. Monti In particular, in [4] the problem has been proven to admit a linear solution on directed path graphs, a superclass of interval graphs; this result has been first generalized to the superclass of strongly chordal graphs [7] and then further extended to doubly chordal graphs [10]. Moreover, in [8] the authors present a linear time algorithm to solve the problem on circular arc graphs, a natural superclass of interval graphs. Finally, linear time algorithms for the LCST problem on cographs and co-bipartite graphs are provided in [10]. For a visual summary of the known results, see Figure 1. !"#$%&'( )'&*&$( .)'1/( %#+,'-( !"#$%&'( 67(84/$22.( 67(=4/$22.( 9:&;1:&'(#+/2$)'&*&$<( 9>)#''#*1&*(*2/?#$@.<( ./$#*0'-( !"#$%&'( %1$2!/2%( !1$!+'&$( )&/"( &$!( !#4 !#0$&)".( ,1)&$5/2( 1*/2$3&'( Fig. 1. The state of the art concerning the complexity of the LCST problem. The problem is NP-complete on black classes and linearly solvable on grey classes. White classes are studied in this paper, and for them a linear time algorithm is designed. 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 [9] - and we prove that the problem of finding an LCST is linearly solvable when restricted to them. We give an analogous result even for the case when the input graph is an SC 2-tree (i.e. a maximal outerplanar graph). 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. A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 105 2 Preliminaries 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. [9] Given a positive integer k, simple-clique k-trees (in short SC k-trees) are recursively defined as follows: – The complete graph with k + 1 nodes is an SC k-tree. – An SC k-tree with n + 1 nodes (n ≥ k + 1) can be constructed from an SC k-tree with n nodes by adding a node adjacent to all nodes of a k-clique not previously chosen in the existing SC k-tree, and only to these nodes. t u 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 [9] while SC 3-trees coincide with Apollonian networks [1], and are in fact equivalent to the intersection class of chordal and maximal planar graphs [9]. Hence, these two classes represent interesting subclasses of both chordal and planar graphs. Definition 2. [5] Given a graph G = (V, E) and two non-adjacent nodes u and v of V , a subset S ⊆ V \ {u, v} is an (u, v)-separator if the removal of S from G separates u and v into distinct connected components. 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. Proof. see Appendix. t u 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 [12] or in [11] for the more general class of k-trees. 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, 106 T. Calamoneri, M. Dell’Orefice and A. Monti (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. t u We now recall the following generalization of line graphs introduced in [6]. Definition 3. The k-line graph of a graph G, in short Lk (G), is defined as a graph whose nodes are the k-cliques in G. Two distinct such nodes are adjacent in the k-line graph if and only if they have k − 1 nodes in common in G. 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. t u The k-line graphs have been used to obtain the following characterization of SC k-trees: Theorem 1. [9] A k-tree G is an SC k-tree if and only if the (k + 1)-line graph Lk+1 (G) of G is a tree. 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 . Proof. see Appendix. A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 107 3 An Algorithm to Determine an LCST of an SC 2-Tree Cai [3] proved that a nontrivial graph contains an LCST if and only if it contains a spanning 2-tree T such that T does not contain as induced subgraph a 3-sun. The 3-sun graph is made of a central triangle, and three independent nodes, each adjacent to both ends of a single edge of the triangle. 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. Algorithm FindLCSTinSC2trees 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 x1 y1 be the edge in T for X1 ∩ X2 and xn−3 yn−3 be the edge in T for Xn−3 ∩ Xn−2 ; Add to T the two edges z1 x1 and zn−2 xn−2 ; return T . 108 T. Calamoneri, M. Dell’Orefice and A. Monti 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 . t u 4 An Algorithm to Determine an LCST of an SC 3-Tree 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 . Proof. see Appendix. 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 A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 109 then G is a 3-path and T is an LCST. Proof. see Appendix. 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   NT1 (u) if u ∈ AS̃ NT (u) = NT2 (u) if u ∈ BS̃ NT1 (u) ∪ NT2 (u) if u ∈ S̃  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. t u 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 110 T. Calamoneri, M. Dell’Orefice and A. Monti 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. Fig. 2. The three canonical partial solutions. The three outer nodes are in S, while the central node is in AS . We are now ready to describe the algorithm that, given an SC 3-tree, de- termines 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 A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 111 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 sep- arator 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(Y1 X) × L(Y2 X), that is the cartesian product of L(Y1 X) and L(Y2 X). We “decode” these labels in the corresponding canonical partial solution, which we combine, together with a subset of edges E 0 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. Algorithm Compute-Labels Input: An edge Xf (X) of L4 (G); Output: The set of labels L(Xf (X)) Sc G0 ← G[X ∪ f (X) ∪ i=1 Yi ]; L(Xf (X)) ← ∅; foreach (χ1v1 , ..., χcvc ) ∈ L(Y1 X) × ... × L(Yc X) do Let Hi be the canonical part. sol. of G0 [Yi ] associated to χivi , i = 1, ..., c; foreach subsetSE 0 ⊆ E(X) do c Sc H ← (X ∪ i=1 Yi , E 0 ∪ i=1 E(Hi )); Sc if H is a partial solution of G0 [X ∪ i=1 Yi ] w.r.t. separator Xf (X) then Add to L(Xf (X)) the label corresponding to H; return L(Xf (X)). 112 T. Calamoneri, M. Dell’Orefice and A. Monti Notice that, when c = 0, the cartesian product L(Y1 X) × ... × L(Yc X) 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, E 0 ) in every iteration of the inner cycle. Also, notice that when at least one of the L(Yi X)’s is empty, then L(Y1 X) × ... × L(Yc X) = ∅, 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(Y1 X)×...×L(Yc X) 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. Algorithm Decide-LCSTonSC3-trees 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-LCSTonSC3- trees returns “yes” if and only if the SC 3-tree in input has an LCST, in linear time. A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 113 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. t u 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 Conclusions and Open Problems 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 [2], we conjecture that the LCST problem remains linear for every class of SC k-trees, for any k; this result may be achieved by giving a generalization of Theorem 3 to the class of SC k-trees, k > 3. This generalization requires to: – extend Theorem 3, becoming: Let G be a SC k-tree, and T be a spanning tree of G. T is locally connected if and only if for every minimal separator S of G, and for every x ∈ S: 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. 114 T. Calamoneri, M. Dell’Orefice and A. Monti 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. References 1. J.S. Andrade, H.J. Herrmann, R.F.S. Andrade, L.R. da Silva, Apollonian Net- works: Simultaneously Scale-Free, Small World, Euclidean, Space Filling, and with Matching Graphs Phys. Rev. Lett. 94, 2005. Erratum in Phys. Rev. Lett. 102, 2009. 2. S. Arnborg, and A. Proskurowski, Linear Time Algorithms for NP-Hard Problems Restricted to Partial k-trees. Discrete Applied Mathematics 23, 11–24, 1989. 3. L. Cai, On spanning 2-trees in a graph. Discrete Applied Mathematics 74, 203–216, 1997. 4. L. Cai, The complexity of the locally connected spanning tree problem. Discrete Applied Mathematics 131, 63–75, 2003. 5. M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, 1980. 6. V.B. Le, Perfect k-line graphs and k-total graphs, J. Graph Theory 17, 65–73, 1993. 7. C.-C. Lin, G.J. Chang, G.-H. Chen, Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs. Discrete Mathematics, 307(2),208– 215, 2007. 8. C.-C. Lin, G.-H. Chen, G.J. Chang, A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs. Algorithmica, 66(2), 369–396, 2013. 9. L. Markenzon, C.M. Justel, and N. Paciornik, Subclasses of k-trees: Characteriza- tion and recognition. Discrete Applied Mathematics 154(5), 818–825, 2006. 10. B.S. Panda and D. Pradhan, Locally connected spanning trees in cographs, com- plements of bipartite graphs and doubly chordal graphs. Information Processing Letters, 110(23), 1067–1073, 2010. 11. A. Proskurowski, Separating Subgraphs in k-trees: Cables and Caterpillars. Discrete Mathematics 49, 275–285, 1984. 12. D.J. Rose, On simple characterizations of k-trees. Discrete Mathematics, 7, 317–322, 1974. 13. D.J. Rose, R.E. Tarjan, G. Luker, Algoritmic aspects of vertex elimination on graphs, SIAM J. Comput. 5, 266–283, 1976. 14. A. M. Farley, Networks immune to isolated failures, Networks, 11(3), 1981. A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 115 Appendix Proof of Lemma 1. 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]. t u Proof of Lemma 3. 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. t u Proof of Lemma 4. 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. 116 T. Calamoneri, M. Dell’Orefice and A. Monti (⇐ ) 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. t u Proof of Lemma 5. 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 [13] developed a method based on Lexicographic Breadth First Search (lex-BFS that produces a peo for chordal graphs (and obviously for SC k-trees) in linear time. Moreover in [12] Rose proved that the peo produced with this method for k-tree (and obviously for SC k-trees) has the property that the first k + 1 nodes in the order form a k + 1-clique and |P red(vi )| = k for each vi , k + 1 < i <≤ n. Once produced a peo v1 , v2 . . . vn with these properties it is easy to construct in linear time the tree Lk+1 (G). We start with a node X1 containing the nodes x1 , x2 , . . . xk+1 . Moreover we obtain the other nodes of Lk+1 (G) starting from the nodes vi , k + 1 < i ≤ n. More precisely for vi we create a node Xi containing the nodes {vi } ∪ P red(vj ), where vj is the last predecessor of vi , and we connect this new node Xi to the node Xj if j > k + 1, to X1 otherwise. It is easy to see that each of the n − k nodes of the resulting tree is a k + 1-clique and that, for each edge Xi Xj of the tree ,it holds |Xi ∩ Xj | = k (i.e. the tree is the the graph Lk+1 (G)). t u Proof of Lemma 6. 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. A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 117 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. t u Proof of Lemma 7. 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. t u Proof of Lemma 8. 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 . t u Proof of Lemma 9. 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 . t u Proof of Lemma 10. 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 , 1T≤ i ≤ 3 (cf. Lemma 4). In order to fix the ideas let t ∈ X be the node in i 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, 118 T. Calamoneri, M. Dell’Orefice and A. Monti 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   {x} if u = t NT (u) = NT 0 (x) ∪ {t} if u = x NT 0 (u) otherwise  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 A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 119 NT (y) = {x, a}. Thus again T is an LCST by noting that yt, xz and xa are edges of G. (b) S 0 = {a, x, y} is a minimal separator in K. AS 0 contains only t and z and T 0 = T [BS 0 ∪ S 0 ] is a spanning tree in G0 = G[BS 0 ∪ S 0 ] 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 {t} if u = z  NT (u) =   N T 0 (x) ∪ {t} if u=x NT 0 (u) otherwise  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) S 0 is a minimal separator in K and either S 0 = {a, y, z} or S 0 = {a, x, z}. Assume first that S 0 = {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 S 0 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 {t} if u = z  NT (u) =   {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 S 0 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}]. t u Proof of Lemma 12. 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. 0 Else, assuming 1 ≤ c ≤ 3, let ScE be the selected subset of E(X) such that H 0 is a partial solution of G [X ∪ 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 Sc solutions H i of G[Y i ], having label χivi , i = 1, ..., c. By Lemma 11, if (X, E 0 ∪ i=1 E(H i )) was not a S partial solution of G[X], then neither would H be a partial solution c of G0 [X ∪ i=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 120 T. Calamoneri, M. Dell’Orefice and A. Monti 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 Yi X with label χivi , so by structural induction L(Yi X) contains label χivi , i = 1, ..., c. Let Hi be the canonical partial Sc of G[Yi ] with solution Sc respect to separator Yi X. Then, by Lemma Sc 11, H = (X ∪ i=1 Yi , E 0 ∪ i=1 E(Hi )) is a partial solution of G0 [X ∪ i=1 Yi ] with respect to separator Xf (X), where E 0 = 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)). t u A Locally Connected Spanning Tree is in P on Simple Clique 3-Trees 121 Table used in Algorithm Decide-LCSTonSC3-trees label of {x, y, t} label of {x, z, t} label of {y, z, t} label of {x, y, z} αx - - αx (+yz), βz (+xz, yz), γy (+zt, xz) αy - - αy (+xz), βz (+xz, yz), γx (+yz) αt - - βx (+xz, zt), βy (+yz, zt) βx - - αz , βx (+xz), βy (+yz), γz (+tz) βy - - αz , βx (+xz), βy (+yz), γz (+tz) βt - - γy (+xz), γx (+yz) γx - - γy (+xz), γx (+yx) γy - - γy (+xz), γx (+yz), γt - - αz , βx (+xz), βy (+yz) αx αt - βz (+yz) αx βz - γy αt αx - βy (+yz) αt βz - βx αt γt - βx βx αz - αz , βy (+yz) βx γz - γz βx βx - βx βx βt - γz βy αx - γz βy αt - βx βt αz - γx (+yz) βt βx - γy γy βx - γy γt αt - βx αx αt βy βz αx βz βt γy αt αx βz βy αt βz αy βx βx αz αt βy βx βt αy γz βy αx βt γz βy αt αz βx βt αz βy γx βt βx αz γy Fig. 3. Table for the construction of the labels. Symbol ’-’ means that the corresponding child is not present in L4 . Notice that missing combinations do not lead to any feasible label for separator {x, y, z}.