, we provide recursive formulas to compute the number of leaves in fully leafed induced subtrees appearing in series-parallel graphs. As a byproduct, the problem FLIS is polynomial for this family of graphs.
t
We are particularly interested in the problem of enumerating fully leafed induced subtrees, i.e., induced subtrees whose number of leaves is maximal with respect to all induced subtrees of the same size [BCGLNV17]. These combinatorial objects were studied both in the general case [BCGLNV17] and in the particular context of tree-like polyforms and polycubes [BCGS17]. Unfortunately, the problem of nding fully leafed induced subtrees is NP-hard in general [BCGLNV17]. One possible approach to tackle such problems consists of nding a natural parameter that allows xed parameter tractable algorithms.
We consider the case of series-parallel graphs (SP-graphs), for which the problem becomes polynomial. We believe that the ideas presented below are an important step in designing a parametrized algorithm for solving the problem in general. Additionally, since our algorithm is derived from recursive formulas, it also yield useful insights on the shape of fully leafed induced subtrees in series-parallel graphs. 2
We brie y recall some de nitions from graph theory. See [Die10] for more details. Unless otherwise stated, all graphs considered in this text are undirected.
A graph is an ordered pair G = (V; E), where V is its set of vertices and E is its set of edges. Given a vertex u, we denote by NG(u) the set of neighbors of u in G, i.e., NG(u) = fv 2 V j fu; vg 2 Eg. When the context is clear, we omit the index G and write simply N (u). The degree of u is de ned by deg(u) = jN (u)j. The size of G, denoted by jGj, is the total number jV j of vertices. For U V , the subgraph of G induced by U , denoted by G[U ], is the graph G[U ] = (U; E \ P2(U )), where P2(U ) is the set of all subsets of size 2 of U .
A graph is called a tree if it is both connected and acyclic. A vertex u 2 V is called a leaf of T if deg(u) = 1. The number of leaves of T is denoted by jT jl. We say that G[U ] is an induced subtree of G if the graph induced by U is a tree. Forests and induced subforests are de ned similarly by keeping the \acyclic" property and removing the \connected" one.
A two-terminal graph is a quadruple G = (V; E; s; t), where (V; E) is a graph and s; t 2 V , s 6= t, we call s the source and t the sink of G. A two-terminal graph G = (V; E; s; t) is called a series-parallel graph (or simply SP-graph) if one of the following three conditions is satis ed: (i) (Basic SP-graph) V = fs; tg and E = ffs; tgg; (ii) (Series composition) There exist two SP-graphs G1 = (V1; E1; s1; t1) and G2 = (V2; E2; s2; t2) such that V = V1 [ V2, V1 \ V2 = ft1g = fs2g, E = E1 [ E2, E1 \ E2 = ;, s = s1 and t = t2. In this case, we write G = G1 ./ G2. (iii) (Parallel composition) There exist two SP-graphs G1 = (V1; E1; s; t) and G2 = (V2; E2; s; t), where at least one graph among G1, G2 is non basic, such that V = V1 [ V2, V1 \ V2 = fs; tg, E = E1 [ E2 and E1 \ E2 = ;.
In this case, we write G = G1 k G2.
Examples of SP-graphs are depicted in Figure 1. Series-parallel graphs have been studied since the 19th century. Their enumeration was investigated in 1890 by MacMahon [Mac90] and can be found in OEIS as sequence A000084. A few years later, Riordan and Shannon [RS42] provided a formal proof of the recursive (a) (b) (c) formula given by MacMahon. From there, several papers have been published on their combinatorial properties (see for instance [Fin03] and references therein). 3
As mentioned in the introduction, we are interested in induced subtrees of series-parallel graphs and in particular those with several leaves. We rst recall a de nition introduced in [BCGLNV17].
De nition 3.1 (Leaf function, [BCGLNV17]). Given a nite or in nite graph G = (V; E), let TG(i) be the family of all induced subtrees of G with exactly i vertices. The leaf function of G, denoted by LG, is the function with domain f0; 1; 2; : : : ; jGjg de ned by
LG(i) = maxfjT jl : T 2 TG(i)g; with the convention max ; = jT jl = LG(i).
1. An induced subtree T of G with i vertices is called fully leafed when Problem 3.2 (Leaf Induced Subtree Problem, [BCGLNV17]). Given a simple graph G and two positive integers i and `, does there exist an induced subtree of G with i vertices and ` leaves? Example 3.3. Let G be the SP-graph illustrated in Figure 2. Positive instances of Problem 3.2 are identi ed in (a) and (b). It is not hard to prove that both subtrees are fully leafed. More precisely, one can show that (7; `) is a negative instance of Problem 3.2 for any ` > 5. Similarly, (11; `) is a negative instance of Problem 3.2 for any ` > 6. Notice that the adjective \induced" is important. For example, the blue subgraph illustrated in Figure 2(c) is a subtree, but it is not induced for otherwise the dashed edge would have to be included, therefore creating a cycle. Exhaustive inspection of all induced subtrees show that the leaf function of G is given by Table 1. 4
Let G be any SP-graph. We are interested in computing the leaf function LG of G. An important observation is that induced subtrees of SP-graphs obtained by a parallel composition could be obtained by \merging" an induced subforest with an induced subtree, i.e., a subtree in a graph and a forest in the other, which is not intuitive. Fortunately, such a subforest factor has a very speci c shape: it always has two connected components and it must include both the source and the sink of the SP-graph in which it lives. Hence, we can restrict our attention to those two types of induced subgraphs. Moreover, the following lemma, whose proof is omitted due to lack of space, is key in describing the recursive formulas. where where Lemma 4.1. Let G be a parallel or series composition of two SP-graphs G1 and G2. If T = T1 [ T2 is a fully leafed induced subtree or subforest of G, where T1 G1 and T2 G2, then T1 and T2 are fully leafed induced subtrees or subforests of G1 and G2 respectively.
Hence, by Lemma 4.1, we only need to keep track of the induced subtrees obtained by series or parallel compositions and encode their status (leaf or inner vertex and proximity) with respect to the source and the sink.
De nition 4.2. Let G = (V; E; s; t) be an SP-graph and i an integer, with 2 i jGj. We denote by L(G; i; ; ) the maximum number of leaves that can be realized by an induced subtree T of size i of G, such that = 8 0; if s 2 T; degT (s) > 1; > >< 1; if s 2 T; degT (s) = 1; > 2; if s 2= T; jN (s) \ T j 6= 0; >: 3; if s 2= T; jN (s) \ T j = 0; and = 8 0; if t 2 T; degT (t) > 1; > >< 1; if t 2 T; degT (t) = 1; > 2; if t 2= T; jN (t) \ T j 6= 0; >: 3; if t 2= T; jN (t) \ T j = 0: Similarly, let F (G; i; ; ) be the maximum number of leaves that can be realized by an induced subforest of size i whose two connected components Ts and Tt containing s and t respectively are such that = 0; if degTs (s) > 1; 1; if degTs (s) = 1; and = 0; if degTt (t) > 1; 1; if degTt (t) = 1:
max L(G; i; ; ); 0 ; 3 (1) for i = 2; 3; : : : ; jGj. Therefore, it is su cient to describe how to compute recursively L(G; i; ; ) and F (G; i; ; ) to solve Problem 3.2 in the case of series-parallel graphs.
There are two additional useful de nitions that we need to introduce. First, let DistN = f2; 3g f2; 3g [ f0; 1g f3g[f3g f0; 1g. Intuitively, when ( ; ) 2 DistN, we are guaranteed that the composition of the induced subtrees/subforests involved will not create a cycle because their respective vertices are \distant". Moreover, for (a; b) 2 f0; 1g f0; 1g, let ` be the leaf loss function de ned by `(a; b) = a + b which indicates the number of leaves that are lost after a composition. For the remainder of this section, we study the di erent cases, according to the type of composition, in the case of induced subtrees as well as induced subforests. 4.1
Series composition Assume that G = G1 ./ G2, where G = (V; E; s; t), G1 = (V1; E1; s1; t1), G2 = (V2; E2; s2; t2). Also, let T be a fully leafed induced subtree of G. There are three cases to consider.
(ST1) T is included in G1. Then we de ne ST1(G; i; ; ) as the number of leaves of T : (ST2) T is included in G2. Then we de ne ST2(G; i; ; ) as the number of leaves of T : = =
ST1(G; i; ; ) = L(G1; i; ; 1); (2; if fs; tg 2 E2 and 1 2 f0; 1g;
3; otherwise.
ST2(G; i; ; ) = L(G2; i; 2; ) (2; if fs; tg 2 E1 and 2 2 f0; 1g;
3; otherwise.
(ST3) T is included neither in G1 nor G2. Then there exist a fully leafed induced subtree T1 of G1 and a fully leafed induced subtree T2 of G2 such that T = T1 [ T2 and T1 \ T2 = ft1g = fs2g. Therefore, the number of leaves of T is
1; 22f0;1g ST3(G; i; ; ) = (i1;mi2)a`xi+1 fL(G1; i1; ; 1) + L(G2; i2; 2; ) `( 1; 2)g 1; 22f0;1g 1; 22f0;1g 1; 22f0;1g ( 1; 2)2DistN
1; 22f0;1g ( 1; 2)2DistN
L(G; i; ; ) = j2mf1a;2x;3gfSTj(G; i; ; )g The parallel composition is more intricate, but all cases can be covered using a similar reasoning. Assume that G = G1 k G2, where G = (V; E; s; t), G1 = (V1; E1; s1; t1), G2 = (V2; E2; s2; t2).
As in the last subsection, we rst consider the subtree case. Let T be a fully leafed induced subtree of G. We distinguish six cases.
(PT1) T is included in G1. Then the number of leaves of T is (PT2) T is included in G2. In that case, we obtain
P T1(G; i; ; ) = L(G1; i; ; )
P T2(G; i; ; ) = L(G2; i; ; ) In the following cases T lives both in G1 and G2.
(PT3) s 2 T and t 2= T . Then we have = 0, since s is an internal vertex of T . Therefore, the number of leaves in that case is
P T3(G; i; 0; ) = (i1;i2)`i+1 fL(G1; i1; 1; 1) + L(G2; i2; 2; 2) `( 1; 2)g
max where = minf 1; 2g (PT4) s 2= T and t 2 T . This case is analogous to (PT3), but now we have = 0 and P T4(G; i; ; 0) = (i1;i2)`i+1 fL(G1; i1; 1; 1) + L(G2; i2; 2; 2) `( 1; 2)g
max where = minf 1; 2g
(PT5) T can be decomposed in a forest F1 included in G1 and a tree T2 included in G2. In this case, observe that s; t 2 F1; T2, which implies = 0 and = 0. Therefore, the number of leaves of T is (PT6) T can be decomposed in a tree T1 included in G1 and a forest F2 included in G2. This case is analogous to (PT5) and we obtain
Finally, assume that F is a fully leafed induced forest of G = G1 k G2 and write F = F1 [ F2 (F1 and F2 possibly empty), where F1 is included in G1 and F2 is included in G2.
There are nine cases. (PF1) F2 = ;. Then the number of leaves of F is (PF2) F1 = ;. Then (PF3) F1 is a subforest, F2 a subtree and s 2 F2. Then
P F1(G; i; ; ) = F (G1; i; ; )
P F2(G; i; ; ) = F (G2; i; ; ) 1; 22f0;1g 1; 22f0;1g 1; 22f0;1g 1; 22f0;1g (PF4) F1 is a subforest, F2 a subtree and t 2 F2. Then (PF5) F1 is a subtree, F2 a subforest and s 2 F1. Then
P F3(G; i; 0; ) = (i1;mi2)a`xi+1 fF (G1; i1; 1; ) + L(G2; i2; 2; 3) `( 1; 2)g
P F4(G; i; ; 0) = (i1;mi2)a`xi+1fF (G1; i1; ; 1) + L(G2; i2; 3; 2) `( 1; 2)g (PF6) F1 is a subtree, F2 a subforest and t 2 F1. Then (PF7) Both F1 and F2 are subtrees, s 2 F1 and t 2 F2. Then
P F5(G; i; 0; ) = (i1;mi2)a`xi+1 fL(G1; i1; 1; 3) + F (G2; i2; 2; ) `( 1; 2)g
P F6(G; i; ; 0) = (i1;mi2)a`xi+1fL(G1; i1; 3; 1) + F (G2; i2; ; 2) `( 1; 2)g (PF8) Both F1 and F2 are subtrees, s 2 F2 and t 2 F1. Then
P F7(G; i; ; ) =
max fL(G1; i1; ; 3) + L(G2; i2; 3; )g (i1;i2)`i ; 2f0;1g P F8(G; i; ; ) =
max fL(G1; i1; 3; ) + L(G2; i2; ; 3)g (i1;i2)`i ; 2f0;1g (PF9) Finally, Both F1 and F2 are subforests. Then
P F9(G; i; 0; 0) =
fF (G1; i1; 1; 1) + F (G2; i2; 2; 2) s
t
L(BT ; i; ; ) = (2; if i = 2 and =
= 1; 1; otherwise.
L(G; 2; 1; ) = L(G; 2; ; 1) = 2 for any ; 2 f0; 1; 2; 3g.
Finally, let BF be the SP-graph of 5 vertices depicted in Figure 3 and F the induced subforest higlighted in blue. Then
F (BF ; i; ; ) = (4; 1 if i = 4 and otherwise.
=
= 1; F (G; i; ; ) = 1 Hence, for any SP-graph G 6= BF of size at most 5, for all i 2 f2; 3; : : : ; jGjg and ; 2 f0; 1g, we have 5
The recursive formulas presented in this paper can be easily translated into a program that generates all fully leafed induced subtrees of a given SP-graph. In the future, we are interested in investigating the enumerative combinatorics of induced subtrees of SP-graphs. [Die10]
R. Diestel. Graph theory. Graduate Texts in Mathematics, 173, Springer-Verlag Berlin Heidelberg 2014. [Epp92] D. Eppstein. Parallel recognition of series-parallel graphs. Information and Computation, 98(1):41{55, 1992. [ESS86] P. Erd}os, M. Saks and V. T. Sos. Maximum induced trees in graphs. Journal of Combinatorial Theory.
Series B, 41(1):61{79, 1986. [Fin03] S. Finch. Series-parallel networks. Technical report. Harvard University, 2003. [KW91] D. J. Kleitman and D. B. West. Spanning trees with many leaves. SIAM Journal on Discrete Mathematics., 4(1):99{106, 1991. [Kur30] C. Kuratowski. Sur le probleme des courbes gauches en Topologie.
15(1):271{283, 1930.
Fundamenta Mathematicae, (5) (6) (7) (8)
M. J. Zaki. E ciently Mining Frequent Trees in a Forest. Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '02, pp. 71{80. ACM, 2002.