David Callan

A Determinant of Stirling Cycle Numbers Counts Unlabeled Acyclic Single-Source Automata

Keywords: Stirling cycle number, unlabeled acyclic automaton, column-marked subdiagonal path, sign-reversing involution

We show that a determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata. The proof involves a bijection from these automata to certain marked lattice paths and a sign-reversing involution to evaluate the determinant. We also give a formula for the number of acyclic automata with a given set of sources.

Introduction

The chief purpose of this paper is to show bijectively that a determinant of Stirling cycle numbers counts unlabeled acyclic single-source automata. Specifically, let A k (n) denote the kn × kn matrix with (i, j)

entry ⌊ i-1 k ⌋+2 ⌊ i-1
k ⌋+1+i-j , where i j is the Stirling cycle number, that is, the number of permutations on [i] := {1, 2, . . . , i} with j cycles. For example,

A 2 (5) =                
1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 3 2 0 0 0 0 0 0 0 0 1 3 2 0 0 0 0 0 0 0 0 1 6 11 6 0 0 0 0 0 0 0 1 6 11 6 0 0 0 0 0 0 0 1 10 35 50 24 0 0 0 0 0 0 1 10 35 50 0 0 0 0 0 0 0 1 15 85 0 0 0 0 0 0 0 0 1 15

                .
As evident in the example, A k (n) is formed from k copies of each of rows 2 through n + 1 of the Stirling cycle triangle, arranged so that the first nonzero entry in each row is a 1 and, after the first row, this 1 occurs just before the main diagonal; in other words, A k (n) is a Hessenberg matrix with 1s on the infra-diagonal.

Main Theorem. The determinant of A k (n) is the number of unlabeled acyclic single-source automata with n transient states on a (k + 1)-letter input alphabet.

Section 2 reviews basic terminology for automata and recurrence relations to count finite acyclic automata, and includes a new formula for the number of acyclic automata with a given set of sources. Section 3 introduces column-marked subdiagonal paths, which play an intermediate role, and a way to code them. Section 4 presents a bijection from these column-marked subdiagonal paths to unlabeled acyclic singlesource automata. Finally, Section 5 evaluates det A k (n) using a sign-reversing involution and shows that the determinant counts the codes for column-marked subdiagonal paths.

Automata

A (complete, deterministic) automaton consists of a set of states and an input alphabet whose letters transform the states among themselves: a letter and a state produce another state (possibly the same one). A finite automaton (finite set of states, finite input alphabet of, say, k letters) can be represented as a k-regular directed multigraph with ordered edges: the vertices represent the states and the first, second, . . . edge from a vertex give the effect of the first, second, . . . alphabet letter on that state. A finite automaton cannot be acyclic in the usual sense of no cycles: pick a vertex and follow any path from it. This path must ultimately hit a previously encountered vertex, thereby creating a cycle. So the term acyclic is used in the looser sense that only one vertex, called the sink, is involved in cycles. This means that all edges from the sink loop back to itself (and may safely be omitted) and all other paths feed into the sink.

A non-sink state is called transient. The size of an acyclic automaton is the number of transient states. An acyclic automaton of size n thus has transient states which we label 1, 2, . . . , n and a sink, labeled n+1. Liskovets [START_REF] Liskovets | Exact enumeration of acyclic deterministic automata[END_REF] uses the inclusion-exclusion principle (also used below) to obtain the following recurrence relation for the number a k (n) of acyclic automata of size n on a k-letter input alphabet (k ≥ 1):

a k (0) = 1; a k (n) = n-1 j=0
(-1) n-j-1 n j (j + 1) k(n-j) a k (j), n ≥ 1.

A source is a vertex (state) with no incoming edges. A finite acyclic automaton has at least one source because a path traversed backward v 1 ← v 2 ← v 3 ← . . . must have distinct vertices and so cannot continue indefinitely. An interior vertex is one that is neither the sink nor a source. An acyclic automaton with 6 states and input alphabet a, b is represented below as a multigraph with the vertices (states) on a horizontal line. It has two sources, 1 and 4; the interior states are 2,3, 5 and the sink is 6. Observe that the vertices are so arranged that all edges point to the right. This is always possible for a finite acyclic automaton (see Corollary 4 below).

Proposition 1

The number b k (n, j) of acyclic automata of size n on a k-letter input alphabet with source set {1, 2, . . . , j}

(1 ≤ j ≤ n) is given by b k (n, j) = n-j i=0 (-1) n-i+j n -j i (i + 1) k(n-i) a k (i)
Remark For the case j = 1, this formula is a bit more succinct than the recurrence in [1, Theorem

⊆ [j + 1, n], let f (X) = # automata in A whose set of non-principal sources includes X, g(X) = # automata in A whose set of non-principal sources is precisely X. Then f (X) = Y : X⊆Y ⊆[j+1,n] g(Y )
and by Möbius inversion [START_REF] Van Lint | A Course in Combinatorics[END_REF] on the lattice of subsets of

[j + 1, n], g(X) = Y : X⊆Y ⊆[j+1,n] µ(X, Y )f (Y ) where µ(X, Y ) is the Möbius function for this lattice. Since µ(X, Y ) = (-1) |Y |-|X| if X ⊆ Y , we have in particular that g(∅) = Y ⊆[j+1,n] (-1) | Y | f (Y ). (1)
Let us evaluate the sum in (1) by the size of

Y ; | Y | ranges from 0 to n -j. For | Y | = n -i with j ≤ i ≤ n, there are n-j n-i = n-j i-j choices for Y . The vertices in [n + 1
]\Y together with their incident edges form an acyclic automaton with i transient states in which {1, 2, . . . , j} are sources; clearly, there are (ij + 1) kj a k (ij) such automata because the graph obtained by deleting the vertices 1, 2, . . . , j and their incident edges is a subautomaton of size ij. Also, all edges from the ni vertices comprising Y go directly into the set

[j + 1, n + 1]\Y : (i -j + 1) k(n-i) choices. Thus f (Y ) = (i -j + 1) kj a k (i -j)(i -j + 1) k(n-i) . Hence, g(∅) = n i=j (-1) n-i n -j i -j (i -j + 1) k(n-i+j) a k (i -j). (2)
Now, by definition, g(∅) is the number of automata in A for which 1, 2, . . . , j are the only sources, that is, g(∅) = b k (n, j) and thus the Proposition follows from (2) by a change in summation index. ✷

A standard j-source automaton is one with precisely j sources labelled 1, 2, . . . , j. Let B k (n, j) denote the set of standard j-source acyclic automata of size n, that is, the acyclic automata on a k-letter input alphabet with sources 1, 2, . . . , j, interior vertices j + 1, j + 2, . . . , n and sink n + 1. The two-line representation of an automaton in B k (n, j) is the 2 × kn matrix whose top row lists the vertices in order and whose columns then list the edges from each vertex in order. For example, B = 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 2 4 6 6 6 6 6 6 6 3 5 3 2 2 6

is in B 3 (5, 1) (here 1 is the only source) and the source-to-sink paths in B include 1

a → 2 a → 6, 1 b → 4 c → 3 a → 6, 1 b → 4 b → 5 b → 2 b → 6
, where the alphabet is {a, b, c}. An unlabeled standard j-source automaton is an equivalence class of standard j-source automata under relabeling of the interior vertices. Liskovets notes [START_REF] Liskovets | Exact enumeration of acyclic deterministic automata[END_REF] that, when j = 1, B k (n, j) has no nontrivial automorphisms, that is, each of the (nj)! relabelings of the interior vertices of B ∈ B k (n, j) produces a different automaton. We prove this for general j below. It follows that unlabeled standard j-source automata of size n on a k-letter alphabet are counted by 1 (n-j)! b k (n, j) and, in particular, the formula for b k (n, j) in Prop. 1 always gives a number divisible by (nj)!. The next result establishes a canonical representative in each relabeling class.

Proposition 2 Each equivalence class in B k (n, j) under relabeling of interior vertices has size (nj)! and contains exactly one standard j-source automaton with the "last occurrences increasing" property: the last occurrences of the interior vertices-j + 1, j + 2, . . . , n-in the bottom row of its two-line representation occur in that order.

Proof:

The first assertion follows from the fact that the interior vertices of an automaton B ∈ B k (n, j) can be distinguished intrinsically, that is, independent of their labeling. To see this, first mark the sources, namely 1, 2, . . . , j, with marks (new labels) v 1 , v 2 , . . . , v j and observe that there exists at least one interior vertex whose only incoming edge(s) are from a source (the only currently marked vertices) for otherwise a cycle would be present. For each such interior vertex v, choose the last edge from a marked vertex to v where edges are in the left-to-right order of the two-line representation. This determines an order on these vertices; mark them in order v j+1 , v j+2 , . . . , v ℓ . If there still remain unmarked interior vertices, at least one of them has incoming edges only from a marked vertex or again a cycle would be present. For each such vertex, use the last incoming edge from a marked vertex, where now edges are arranged in order of the subscript on the initial vertex with the built-in order breaking ties, to order and mark these vertices v ℓ+1 , v ℓ+2 , . . .. Proceed similarly until all interior vertices are marked. For example, with j = 1 and B = 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 2 4 6 6 6 6 6 6 6 3 5 3 2 2 6 , there is only one source and so v 1 = 1. There is just one interior vertex, namely 4, whose only incoming edge is from the source, and so v 2 = 4 and 4 becomes a marked vertex. Now all incoming edges to both 3 and 5 are from marked vertices and the last such edges (built-in order comes into play) are 4 b → 5 and 4 c → 3 putting vertices 3, 5 in the order 5, 3. So v 3 = 5 and v 4 = 3. Finally, v 5 = 2. This proves the first assertion.

By construction of the vs, relabeling each interior vertex with the subscript of its corresponding v produces an automaton in B k (n, j) with the "last occurrences increasing" property and is the only relabeling that does so. The example yields 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 5 2 6 4 3 4 5 5 6 6 6 6 6 6 6 .

✷ Proposition 3

In a standard j-source finite acyclic automaton with the "last occurrences increasing" property, every edge a → b satisfies a < b.

Proof: Suppose to the contrary that a < b and b → a is an edge. Then the "last occurrences increasing" property implies that there is an occurrence of b to the right of a in the bottom row of the two-line representation as sketched.

(n) = | B k (n) |. Also, let C k (n) denote the subset of B k (n) representing unlabeled automata canonically as in Prop. 2; thus | C k (n) | = 1 (n-1)! b k (n).
Henceforth, we identify an unlabeled automaton with its canonical representative.

Column-Marked Subdiagonal Paths

A subdiagonal (k, n, p)-path is a lattice path of steps E = (1, 0) and N = (0, 1), E for east and N for north, from (0, 0) to (kn, p) that never rises above the line y = 1 k x. Let C k (n, p) denote the set of such paths. For k ≥ 1, it is clear that C k (n, p) is nonempty only for 0 ≤ p ≤ n and the generalized ballot theorem (see, for example, [3, Theorem 3B]) implies that

| C k (n, p) | = kn -kp + 1 kn + p + 1 kn + p + 1 p . A path P in C k (n, n) can be
y = -1 y = 1 2 x A path in C * 2 (4, 4)
A marked path

P * in C * k (n, n) can be coded by a sequence of pairs (a i , b i ) kn i=1
where (b i ) kn i=1 is the code for the underlying path P and a i ∈ [1, b i ] gives the position of the * in the ith column. The example is coded by (1, 1), (1, 1), (1, 2), (2, 2), (1, 2), [START_REF] Narayana | Lattice Path Combinatorics With Statistical Applications[END_REF][START_REF] Narayana | Lattice Path Combinatorics With Statistical Applications[END_REF], [START_REF] Liskovets | Exact enumeration of acyclic deterministic automata[END_REF][START_REF] Narayana | Lattice Path Combinatorics With Statistical Applications[END_REF], [START_REF] Van Lint | A Course in Combinatorics[END_REF][START_REF] Narayana | Lattice Path Combinatorics With Statistical Applications[END_REF].

An explicit sum for | C * k (n, n) | is | C * k (n, n) | = 1≤b1≤b2≤...≤b kn , bi ≤ ⌈i/k⌉ for all b 1 b 2 . . . b kn ,
because the summand b 1 b 2 . . . b kn is the number of ways to insert the ' * 's in the underlying path coded by (b i ) kn i=1 . In the next section we exhibit a bijection from C * k (n, n) to C k+1 (n). This bijection implies, in particular, that the number of unlabeled single-source acyclic automata on a 2-letter alphabet is given by

| C 2 (n) | = | C * 1 (n, n) | =

Bijection from Paths to Automata

In this section we exhibit a bijection from

C * k (n, n) to C k+1 (n).
Using the path illustrated in the previous section as a working example with k = 2 and n = 4, first construct the top row of a two-line representation consisting of k + 1 each 1s, 2s, . . . , n s and number them left to right for reference: We have det A

(n) = σ sgn σ n i=1 a i,σ(i) = σ sgn σ n i=1 i+1
2i-σ(i) , and so

det A(n) = c (-1) # 0s in c n i=1 i + 1 i + 1 -c i , (3)
where the sum is restricted to padded compositions c of n with c i ≤ i for all i (counted by A002083) because i+1 i+1-ci = 0 unless c i ≤ i. Henceforth, let us write all permutations in standard cycle form whereby the smallest entry occurs first in each cycle and these smallest entries increase left to right. Thus, with dashes separating cycles, 154-2-36 is the standard cycle form of the permutation ( 1 2 3 4 5 6 5 2 6 1 4 3 ). We define a nonfirst entry to be one that does not start a cycle. Thus the preceding permutation has 3 nonfirst entries: 5,4,6. Note that the number of nonfirst entries is 0 only for the identity permutation. We denote an identity permutation (of any size) by ǫ.

By definition of Stirling cycle number, the product in (3) counts lists (π i ) n i=1 of permutations where π i is a permutation on [i+1] with i+1-c i cycles, equivalently, with c i ≤ i nonfirst entries. This observation motivates us to define L n to be the set all lists of permutations π = (π i ) n i=1 where π i is a permutation on [i + 1], # nonfirst entries in π i is ≤ i, π 1 is the transposition (1,2), each nonidentity permutation π i is immediately followed by c i -1 ǫ's where c i ≥ 1 is the number of nonfirst entries in π i (so the total number of nonfirst entries is n). Assign a weight to π ∈ L n by wt(π) = (-1) # ǫ's in π . Then

det A(n) = π∈Ln wt(π).
We now define a weight-reversing involution on (most of) L n . Given π ∈ L n , scan the list of its component permutations π 1 = (1, 2), π 2 , π 3 , . . . left to right. Stop at the first one that either (i) has more than one nonfirst entry, or (ii) has only one nonfirst entry, b say, and b > maximum nonfirst entry m of the next permutation in the list. Say π k is the permutation where we stop (assuming that we do stop).

In case (i) decrement (i.e. decrease by 1) the number of ǫ's in the list by splitting π k into two nonidentity permutations as follows. Let m be the largest nonfirst entry of π k and let ℓ be its predecessor. Replace π k and its successor in the list (necessarily an ǫ) by the following two permutations: first the transposition (ℓ, m) and second the permutation obtained from π k by erasing m from its cycle and turning it into a singleton. Here are two examples of this case (recall permutations are in standard cycle form and, for clarity, singleton cycles are not shown). The reader may readily check that this sends case (i) to case (ii). In case (ii), π k is a transposition (a, b) with b > maximum nonfirst entry m of π k+1 . In this case, increment the number of ǫ's in the list by combining π k and π k+1 into a single permutation followed by an ǫ as follows: in π k+1 , b is a singleton; delete this singleton and insert b immediately after a in π k+1 (in the same cycle). The reader may check that this reverses the result in the two examples above and, in general, sends case (ii) to case (i). Since the map alters the number of ǫ's in the list by 1, it is clearly weight-reversing. The map fails only for lists that both consist entirely of transpositions and have the form

.Corollary 4

 4 . . b . . . c . . . . . . a . . . b . . . The edge c → b coming into this b necessarily has b < c and, iterating, we would get an infinite sequence of vertices a < b < c < . . .. ✷ For every finite acyclic automaton there is an ordering of the transient states with the sources coming first such that, when the vertices are arranged horizontally in this order, every edge points to the right. ✷ An automaton is single-source (or initially connected) if it has only one source. Let B k (n) := B k (n, 1) denote the set of single-source acyclic automata on a k-letter input alphabet with vertices 1, 2, . . . , n + 1 where 1 is the source and n + 1 is the sink, and set b k

  coded by the heights of its E steps above the line y = -1; this gives a sequence (b i ) kn i=1 subject to the restrictions 1 ≤ b 1 ≤ b 2 ≤ . . . ≤ b kn and b i ≤ ⌈i/k⌉ for all i. A column-marked subdiagonal (k, n, p)-path is one in which, for each i ∈ [1, kn], one of the lattice squares below the ith E step and above the horizontal line y = -1 is marked, say with a ' * '. Let C * k (n, p) denote the set of such marked paths.

  1≤b1≤b2≤...≤bn bi ≤ i for all i b 1 b 2 . . . b n = (1, 3, 16, 127, 1363, . . .) n≥1 , sequence A082161 in [4].

(a 1

 1 , b 1 ), (a 2 , b 2 ), . . . , (a n , b n ) with b 1 ≤ b 2 ≤ . . . ≤ b n . Such lists have weight 1. Hence det A(n) is the number of lists (a i , b i ) n i=1 satisfying 1 ≤ a i < b i ≤ i + 1 for 1 ≤ i ≤ n, and b 1 ≤ b 2 ≤ . . . ≤ b n . After subtracting 1 from each b i , these lists code the paths in C * 1 (n, n) and, using §4, det A(n) = | C * 1 (n, n) | = | C 2 (n) |.

  3.2]. Consider the set A of acyclic automata with transient vertices [n] = {1, 2, . . . , n} in which the sources include {1, 2, . . . , j}. Call {1, 2, . . . , j} the principal sources. For X

	Proof:

1365-8050 c 2008 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

The last step in the path is necessarily an N step. For the second last, third last,. . . N steps in the path, count the number of steps following it. This gives a sequence i 1 , i 2 , . . . , i n-1 satisfying 1 ≤ i 1 < i 2 < . . . < i n-1 and i j ≤ (k + 1)j for all j. The example yields (i j ) 3 j=1 = (1, 5, 9). Circle the positions i 1 , i 2 , . . . , i n-1 in the two-line representation and then insert (in boldface) 2, 3, . . . , n in increasing order in the second row in the circled positions: .

These will be the last occurrences of 2, 3, . . . , n in the second row. Working from the last column in the path back to the first, fill in the blanks in the second row left to right as follows. Count the number of squares from the * up to the path (including the * square) and add this number to the nearest boldface number to the left of the current blank entry (if there are no boldface numbers to the left, add this number to 1) and insert the result in the current blank square. In the example the numbers of squares are respectively 2,3,1,2,1,2,1,1 yielding This will fill all blank entries except the last. Note that * s in the bottom row correspond to sink (that is, to n + 1) labels in the second row. Finally, insert n + 1 into the last remaining blank space to give the image automaton:

1 1 1 2 2 2 3 3 3 4 4 4 2 4 5 3 3 5 4 5 4 5 5 5 .

This process is fully reversible and the map is a bijection. ✷

Evaluation of det A k (n)

For simplicity, we treat the case k = 1, leaving the generalization to arbitrary k as a not-too-difficult exercise for the interested reader. Write A(n

. From the definition of det A(n) as a sum of signed products, we show that det A(n) is the total weight of certain lists of permutations, each list carrying weight ±1. Then a weight-reversing involution cancels all -1 weights and reduces the problem to counting the surviving lists. These surviving lists are essentially the codes for paths in C * 1 (n, p), and the Main Theorem follows from §4. To describe the permutations giving a nonzero contribution to det A(n) = σ sgn σ × n i=1 a i,σ(i) , define the code of a permutation σ on [n] to be the list c = (c i ) n i=1 with c i = σ(i) -(i -1). Since the (i, j) entry of A(n), i+1 2i-j , is 0 unless j ≥ i -1, we must have σ(i) ≥ i -1 for all i. It is well known that there are 2 n-1 such permutations, corresponding to compositions of n, with codes characterized by the following four conditions: (i) c i ≥ 0 for all i, (ii) c 1 ≥ 1, (iii) each c i ≥ 1 is immediately followed by c i -1 zeros in the list, (iv) n i=1 c i = n. Let us call such a list a padded composition of n: deleting the zeros is a bijection to ordinary compositions of n. For example, (3, 0, 0, 1, 2, 0) is a padded composition of 6. For a permutation σ with padded composition code c, the nonzero entries in c give the cycle lengths of σ. Hence sgn σ, which is the parity of "n -# cycles in σ", is given by (-1) # 0s in c .


Tomáš Masopust
email: masopust@fit.vutbr.cz

Jiří Techet
email: techet@fit.vutbr.cz

Leftmost Derivations of Propagating Scattered Context Grammars: A New Proof

Keywords: formal languages, propagating scattered context grammars, leftmost derivations, generative power

In 1973, V. Virkkunen proved that propagating scattered context grammars which use leftmost derivations are as powerful as context-sensitive grammars. This paper brings a significantly simplified proof of this result.

Introduction

Propagating scattered context grammars, introduced in [START_REF] Greibach | Scattered context grammars[END_REF], represent an important type of semi-parallel rewriting systems. Since their introduction, however, the exact relationship of the family of languages they generate to the family of context-sensitive languages is unknown. The language family generated by these grammars is included in the family of context-sensitive languages; on the other hand, the question of whether this inclusion is proper represents an open problem in formal language theory. There have been several attempts to modify the definition of propagating scattered context grammars to obtain the family of context-sensitive languages (see [START_REF] Fernau | Scattered context grammars with regulation[END_REF][START_REF] Gonczarowski | Scattered versus context-sensitive rewriting[END_REF][START_REF] Meduna | Maximal and minimal scattered context rewriting[END_REF][START_REF] Milgram | A note on scattered context grammars[END_REF][START_REF] Virkkunen | On scattered context grammars[END_REF]). The approach discussed in [START_REF] Virkkunen | On scattered context grammars[END_REF] allows the productions to be applied only in a leftmost way and, thereby, obtain the family of context-sensitive languages generated by these grammars. This result is of some interest as the use of context-free, contextsensitive, and unrestricted productions in a leftmost way in the corresponding grammars of the Chomsky hierarchy does not have any impact on their generative power.

The proof in [START_REF] Virkkunen | On scattered context grammars[END_REF] consists of two parts; first, two preliminary lemmas (Lemma 2 and Lemma 3) are given and then the main result, stated in Theorem 2, is presented as a straightforward corollary of these two lemmas. In Lemma 2 it is demonstrated how any sentence of some context-sensitive language can be derived by a propagating scattered context grammar which uses leftmost derivations. Every sentence generated in such a way contains, however, some additional symbols. Lemma 3 shows how these symbols can be removed. Together, the proof consists of six-page-long construction part and not even one-pagelong basic idea of the construction which makes it extremely hard to follow. A more formal proof of the correctness of the construction is missing.

This paper aims to present the proof of this result in a much simpler and more readable way. The main difference of our proof lies (1) in the way how the symbols to be rewritten are selected and (2) the way how context-sensitive productions are simulated. Furthermore, the proof is based on a single construction instead of two. All this leads to a significantly simpler and more transparent construction.

Preliminaries and definitions

We assume that the reader is familiar with formal language theory (see [START_REF] Salomaa | Formal Languages[END_REF]). For an alphabet V , |V | denotes the cardinality of V . V * represents the free monoid generated by V . The unit of V * is denoted by ε. Set V + = V * -{ε}. For w ∈ V * , |w| and alph(w) denote the length of w and the set of symbols occurring in w, respectively.

A grammar is a quadruple G = (V, T, P, S), where V is the total alphabet, T ⊂ V is the set of terminals, P is a finite set of productions of the form x → y, where x ∈ V * (V -T )V * , y ∈ V * , and

S ∈ V -T is the start symbol of G. If u = z 1 xz 2 , v = z 1 yz 2 ,
and x → y ∈ P , where z 1 , z 2 ∈ V * , then G makes a derivation step from u to v according to x → y, symbolically written as u

⇒ G v [x → y] or, simply, u ⇒ G v. Let ⇒ +
G and ⇒ * G denote the transitive closure of ⇒ G and the reflexive and transitive closure of ⇒ G , respectively. If S ⇒ * G w, where w ∈ T * , S ⇒ * G w is said to be a successful derivation of G. The language of G, denoted by L(G), is defined as

L(G) = {w ∈ T * : S ⇒ * G w}. If each production of G is of the form xAy → xuy, where x, y ∈ V * , A ∈ V -T , u ∈ V + , then G is a context-sensitive grammar.
The family of context-sensitive languages is denoted by L (CS). If each production of G is of one of the following forms: AB → CD, A → BC, A → a, where A, B, C, D ∈ V -T , and a ∈ T , then G is a grammar in the Kuroda normal form.

Lemma 1 ([4]) For every context-sensitive grammar there exists an equivalent grammar in the Kuroda normal form.

A scattered context grammar (see [START_REF] Fernau | Scattered context grammars with regulation[END_REF][START_REF] Gonczarowski | Scattered versus context-sensitive rewriting[END_REF][START_REF] Greibach | Scattered context grammars[END_REF][START_REF] Masopust | Scattered context grammars can generate the powers of 2[END_REF][START_REF] Meduna | Canonical scattered context generators of sentences with their parses[END_REF][START_REF] Meduna | Maximal and minimal scattered context rewriting[END_REF][START_REF] Meduna | Reduction of scattered context generators of sentences preceded by their leftmost parses[END_REF][START_REF] Milgram | A note on scattered context grammars[END_REF][START_REF] Virkkunen | On scattered context grammars[END_REF]) is a quadruple G = (V, T, P, S), where V is the total alphabet, T ⊂ V is the set of terminals, S ∈ V -T is the start symbol of G, and P is a finite set of productions such that each production has the form

(A 1 , A 2 , . . . , A n ) → (x 1 , x 2 , . . . , x n ), for some n ≥ 1, where A i ∈ V -T , and x i ∈ V * , for all 1 ≤ i ≤ n. If each production (A 1 , A 2 , . . . , A n ) → (x 1 , x 2 , . . . , x n ) ∈ P satisfies x i ∈ V + for all 1 ≤ i ≤ n, then G is a propagating scattered con- text grammar. If (A 1 , A 2 , . . . , A n ) → (x 1 , x 2 , . . . , x n ) ∈ P , u = u 1 A 1 u 2 A 2 . . . u n A n u n+1 , and v = u 1 x 1 u 2 x 2 . . . u n x n u n+1 , where u i ∈ V * for all 1 ≤ i ≤ n + 1, then G makes a derivation step from u to v according to p = (A 1 , A 2 , . . . , A n ) → (x 1 , x 2 , . . . , x n ), symbolically written as u ⇒ G v [p] or, simply, u ⇒ G v. In addition, if A i / ∈ alph(u i ) for all 1 ≤ i ≤ n, then the direct derivation is leftmost, and we write u lm ⇒ G v [p]; if A i / ∈ alph(u i+1 ) for all 1 ≤ i ≤ n,

Main Results

The following theorem and its proof, which represent the main result of this paper, demonstrate that propagating scattered context grammars which use leftmost derivations are equivalent to context-sensitive grammars.

Theorem 1 L (PSC, lm) = L (CS).

Proof: As propagating scattered context grammars do not contain erasing productions, their derivations can be simulated by linear bounded automata. As a result, L (PSC, lm) ⊆ L (CS). In what follows, we demonstrate that also L (CS) ⊆ L (PSC, lm) holds true by demonstrating that for every grammar in the Kuroda normal form there exists an equivalent propagating scattered context grammar which uses leftmost derivations. Let G = (V, T, P, S) be a grammar in the Kuroda normal form. Set

N 1 = (V -T ) ∪ {ā : a ∈ T } (suppose that (V -T ) ∩ {ā : a ∈ T } = ∅), N1 = { Â : A ∈ N 1 }. Let n = |N 1 |; then, we denote the elements of N 1 as {A 1 , A 2 , . . . , A n }. Define the homomorphism α from V * to N * 1 as α(A) = A for each A ∈ V -T , and α(a) = ā for each a ∈ T . Set N ′ 2 = {A ′ : A ∈ V -T }, N 3 = { ab : a, b ∈ V }, N ′ 4 = { Aa ′ : A ∈ V -T, a ∈ V }, and
N 5 = { a, 0 , ab, 0 : a, b ∈ V } ∪ { a, i, j : a ∈ V -T, 1 ≤ i ≤ 3, 1 ≤ j ≤ n} ∪ { ab, 4 : a, b ∈ T }.
Without loss of generality, assume that the sets N 1 , N1 , N ′ 2 , N 3 , N ′ 4 , N 5 , { S, X}, and T are pairwise disjoint. Define the propagating scattered context grammar In short, productions introduced in (1) initiate the derivation, productions from (2) are used to select the nonterminal to be rewritten, productions from (3), (4), and ( 5) simulate G's productions of the form A → a, A → BC, and AB → CD, respectively, and, finally, productions from (6) finish the derivation. In the following paragraphs, we describe the derivation of Ḡ in greater detail. Every derivation starts either by a production introduced in (1a) to generate sentences a ∈ L(G), where a ∈ T , or by a production introduced in (1b) to generate sentences x ∈ L(G), where |x| ≥ 2. As S does not occur on the right-hand side of any production, productions from (1) are not used during the rest of the derivation. Consider G's sentential form a 1 a 2 . . . a k , where a 1 , a 2 , . . . , a k ∈ V , for some k ≥ 2. In Ḡ, this sentential form corresponds to

Ḡ = (N 1 ∪ N1 ∪ N ′ 2 ∪ N 3 ∪ N ′ 4 ∪ N 5 ∪ { S,
∈ P , a ∈ V , E ∈ N 3 ∪ N ′ 4 , F ′ ∈ {B ′ , Ba ′ }, 1 ≤ i ≤ n, and 1 ≤ j ≤ n -1, add (a) ( AB, 0 ) → ( CD, 0 ), (b) i. ( A, 0 , B, X) → ( A, 1, 1 , B ′ , A 1 ), ii. ( A, 0 , Ba , X) → ( A, 1, 1 , Ba ′ , A 1 ), (c) i. ( A, 1, i , A i ) → ( A, 2, i , Âi ), ii. ( A, 2, i , F ′ , Âi ) → ( A, 3, i , F ′ , A i ), iii. ( A, 3, j , E, A j ) → ( A, 1, j + 1 , E, A j+1 ), (d) i. ( A, 3, n , B ′ , E, A n ) → ( C, 0 , D, E, X), ii. ( A, 3, n , Ba ′ , A n ) → ( C, 0 ,
b 1 b 2 . . . b r-1 a r , 0 b r+1 b r+2 . . . b k-2 a k-1 a k X, where b i = α(a i ) for all i ∈ {1, 2, . . . , r -1, r + 1, r + 2, . . . , k -2}, for some 1 ≤ r ≤ k -2, or to b 1 b 2 . . . b k-2 a k-1 a k , 0 X,
where b i = α(a i ) for all 1 ≤ i ≤ k -2 (observe that every right-hand side of a production from (1b) represents a sentential form of this kind). To simulate a G's production, the leftmost nonterminal from its left-hand side has to be selected in the sentential form of Ḡ. This is done by appending 0 to the symbol to be selected by productions from [START_REF] Gonczarowski | Scattered versus context-sensitive rewriting[END_REF]. Specifically, for a symbol a ∈ V , (2a) selects the leftmost symbol a immediately following the currently selected symbol and (2b) selects the leftmost symbol a preceding the currently selected symbol. Productions from (2c) and (2d) are used to select and unselect the penultimate nonterminal in Ḡ's sentential form which is composed of two symbols from V . Observe that in this way, any symbol (except for the final X) in every sentential form of Ḡ can be selected. Further, observe that during a derivation, always one symbol is selected.

After the nonterminal is selected, the use of the G's production can be simulated. Productions of the form A → a are simulated by (3a) for every selected nonterminal a 1 , a 2 , . . . , a k-2 and by (3b), (3c) if the penultimate nonterminal (which contains a k-1 , a k ) of the Ḡ's sentential form is selected. Analogously, productions of the form A → BC are simulated by productions from [START_REF] Kuroda | Classes of languages and linear-bounded automata[END_REF].

Productions from (5a) are used to simulate an application of productions of the form AB → CD within the penultimate nonterminal of Ḡ's sentential form. In what follows, we demonstrate how productions from (5b), (5c), and (5d) are used if this production is simulated within a 1 a 2 . . . a k-2 . Suppose that the sentential form in Ḡ is of the form

b 1 b 2 . . . b r-1 a r , 0 b r+1 b r+2 . . . b k-2 a k-1 a k X
and we simulate the application of a r a r+1 → c r c r+1 ∈ P . Recall that N 1 = {A 1 , A 2 , . . . , A n } denotes the set of all symbols which may appear in b r+1 b r+2 . . . b k-2 . First, to select b r+1 = α(a r+1 ), the production

( a r , 0 , b r+1 , X) → ( a r , 1, 1 , b ′ r+1 , A 1 ) from (5(b)i) is applied in a successful derivation, so b 1 b 2 . . . b r-1 a r , 0 b r+1 b r+2 . . . b k-2 a k-1 a k X lm ⇒ Ḡ b 1 b 2 . . . b r-1 a r , 1, 1 b ′ r+1 b r+2 b r+3 . . . b k-2 a k-1 a k A 1 .
Observe that if b r+1 does not immediately follow a r , 0 , the leftmost b ∈ alph(b r+2 b r+3 . . . b k-2 ) satisfying b = b r+1 is selected by the production from (5(b)i). The purpose of productions from (5c) is to verify that the nonterminal immediately following a r , 0 has been selected. First, the production

( a r , 1, 1 , A 1 ) → ( a r , 2, 1 , Â1 ) from (5(c)i) is applied to tag the first A 1 following a r , 1, 1 , so b 1 b 2 . . . b r-1 a r , 1, 1 b ′ r+1 b r+2 b r+3 . . . b k-2 a k-1 a k A 1 lm ⇒ Ḡ b 1 b 2 . . . b r-1 a r , 2, 1 b ′ r+1 y 1 a k-1 a k d 1 ,
where either

y 1 = b r+2 b r+3 . . . b m-1 Â1 b m+1 b m+2 . . . b k-2 , d 1 = A 1 , satisfying A 1 / ∈ alph(b r+2 b r+3 . . . b m-1 ), for some 1 ≤ m ≤ k -2, or y 1 = b r+2 b r+3 . . . b k-2 , d 1 = Â1 ,
Observe that in order to simulate a production of the form AB → CD within a k-2 a k-1 , productions from (5(b)ii) and (5(d)ii) have to be used instead of productions from (5(b)i) and (5(d)i) in the simulation described above. The details are left to the reader. Finally, consider a G's sentence a 1 a 2 . . . a k ∈ T + . This corresponds to ā1 ā2 . . . ār-1 a r , 0 ār+1 ār+2 . . . āk-2 a k-1 a k X, or ā1 ā2 . . . āk-2 a k-1 a k , 0 X in Ḡ after finishing the simulation. To enter the final phase in Ḡ, we need the sentential form to be in the second above described form. This can be achieved by applying a production from (2c) to the first sentential form. The rest of the derivation can be expressed as

ā1 ā2 . . . āk-2 a k-1 a k , 0 X lm ⇒ Ḡ ā1 ā2 . . . āk-2 a k-1 a k , 4 X [p 6a ] lm ⇒ k-2 Ḡ a 1 a 2 . . . a k-2 a k-1 a k , 4 X [Ξ 6b ] lm ⇒ Ḡ a 1 a 2 . . . a k-2 a k-1 a k [p 6c ],
where p 6a and p 6c are productions introduced in steps (6a) and (6c), respectively, and Ξ 6b is a sequence of k -2 productions from (6b). As a result, x ∈ L( Ḡ, lm) if and only if x ∈ L(G). Therefore, L (CS) ⊆ L (PSC, lm).

As L (PSC, lm) ⊆ L (CS) and L (CS) ⊆ L (PSC, lm), we obtain L (PSC, lm) = L (CS), so the theorem holds. ✷

Next, we state the following corollary.

Corollary 1 L (PSC, rm) = L (CS).

Proof: This corollary can be proved by a straightforward modification of the proof of Theorem 1 and its proof is, therefore, left to the reader. ✷

  then the direct derivation is rightmost, and we write u rm ⇒ G v [p]. The language of G, denoted by L(G), is defined as L(G) = {w ∈ T * : S ⇒ * G w}. A propagating scattered context grammar G = (V, T, P, S) uses leftmost or rightmost derivations if its language is defined as L(G, lm) = {w ∈ T * : S lm ⇒ * G w} or L(G, rm) = {w ∈ T * : S rm ⇒ * G w}, respectively. The family of languages generated by propagating scattered context grammars which use leftmost or rightmost derivations is denoted by L (PSC, lm) or L (PSC, rm), respectively.

2 . 3 . 4 . 5 .

 2345 X} ∪ T, T, P , S), where P is constructed as follows: 1. (a) For each a ∈ L(G), where a ∈ T , add ( S) → (a) to P ; (b) For each S ⇒ G ab, where a, b ∈ V , add ( S) → ( ab, 0 X) to P ; For each a, b, c ∈ V , add (a) ( a, 0 , α(b)) → (α(a), b, 0 ), (b) (α(a), b, 0 ) → ( a, 0 , α(b)), (c) ( a, 0 , bc ) → (α(a), bc, 0 ), (d) (α(a), bc, 0 ) → ( a, 0 , bc ) to P ; For each A → a ∈ P and b ∈ V , add (a) ( A, 0 ) → ( a, 0 ), (b) ( Ab, 0 ) → ( ab, 0 ), (c) ( bA, 0 ) → ( ba, 0 ) to P ; For each A → BC ∈ P and a ∈ V , add (a) ( A, 0 ) → (B C, 0 ), (b) ( Aa, 0 ) → (B Ca, 0 ), (c) ( aA, 0 ) → (α(a) BC, 0 ) to P ; For each AB → CD

6 .

 6 Da , X) to P ; For each a, b, c ∈ T , add (a) ( ab, 0 ) → ( ab, 4 ), (b) (c, ab, 4 ) → (c, ab, 4 ), (c) ( ab, 4 , X) → (a, b) to P .

† Supported by the Czech Ministry of Education under the Research Plan No. MSM 0021630528. ‡ Supported by the Czech Grant Agency project No. 102/05/H050. 1365-8050

Tomáš Masopust and Jiří Techet

satisfying A 1 / ∈ alph(y 1 ). Then, the production

from (5(c)ii) is applied to untag the first symbol Â1 following b ′ r+1 , so

This means that if A 1 occurs between a r , 2, 1 and b ′ r+1 , it is tagged by the production from (5(c)i) but it cannot be untagged by any production from (5(c)ii), so the derivation is blocked. Finally, the production

and the same verification continues for A 2 . This verification proceeds for all symbols from N 1 so this part of the derivation can be expressed as

, where p i1 , p i2 , and p j3 are productions from (5(c)i), (5(c)ii), and (5(c)iii), respectively, for all 1 ≤ i ≤ n, 1 ≤ j ≤ n -1, and either


Joel Spencer
email: spencer@cs.nyu.edu

C R Subramanian

On the size of induced acyclic subgraphs in random digraphs

Keywords:

Let D ∈ D(n, p) denote a simple random digraph obtained by choosing each of the `n 2 ´undirected edges independently with probability 2p and then orienting each chosen edge independently in one of the two directions with equal probability 1/2. Let mas(D) denote the maximum size of an induced acyclic subgraph in D. We obtain tight concentration results on the size of mas(D). Precisely, we show that mas(D) ≤ 2 ln(1 -p) -1 (ln np + 3e) almost surely, provided p ≥ W/n for some fixed constant W . This combined with known and new lower bounds shows that (for p satisfying p = ω(1/n) and p ≤ 0.5)

This proves a conjecture stated by Subramanian in 2003 for those p such that p = ω(1/n). Our results are also valid for the random digraph obtained by choosing each of the n(n -1) directed edges independently with probability p.

Introduction

Given a simple digraph H = (V, F ), let mas(H) denote the maximum size (|V ′ |) of a subset V ′ ⊆ V such that the induced subgraph H[V ′ ] is acyclic. By "simple", we mean that there is at most one arc (directed edge) between any unordered pair of vertices. Self-loops are not allowed. Throughout, we mean vertex induced subgraphs whenever we use the term subgraphs. The associated algorithmic problem of deciding, given an arbitrary H and k, if mas(H) ≥ k is N P -complete [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. The optimization version of 1365-8050 c 2008 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France this algorithmic problem is not polynomial-time approximable even within a multiplicative ratio of O(n ǫ ) for some ǫ > 0 unless P = N P [START_REF] Lund | The Approximation of Maximum Subgraph Problems[END_REF].

Suppose D is a a random digraph drawn from the model D(n, p) defined below. Throughout, we assume that V = {1, . . . , n}. Also, p ≤ 0.5 is a positive real number.

Model D ∈ D(n, p) : Choose each undirected edge {u, v} joining distinct elements of V independently with probability 2p. For each chosen {u, v}, orient it in one of the two directions {u → v, v → u} in D with equal probability (=0.5). The choices of arcs are independent for different chosen unordered pairs. This results in a simple digraph where each arc is chosen with probability p. When p = 0.5, there is an arc between every pair of vertices resulting in a random tournament.

The range of mas(D) has been analyzed for D ∈ D(n, p) and the following upper and lower bounds were obtained by Subramanian in [START_REF] Subramanian | Finding induced acyclic subgraphs in random digraphs[END_REF]. While the above-mentioned upper and lower bounds are asymptotically the same (upto constant multiplicative factors) for large values of p, they differ significantly for very small values of p. In particular, if p = n -1+o (1) and hence ln np = o(ln n), then the lower bound 2p -1 (ln np) is asymptotically much smaller than the upper bound 2p -1 (ln n). In [START_REF] Subramanian | Finding induced acyclic subgraphs in random digraphs[END_REF], it was conjectured that the upper bound can be improved further and also that lower and upper bounds are the same (upto negligible (asymptotically) additive terms). In this paper, we partially prove this by improving the upper bound and bring it closer to the lower bound and also show that they are asymptotically the same when p is not too small and obtain tight concentration results on the value of mas(D). Formally, we obtain the following

Theorem 1.1 ([7]) Let D ∈ D(n, p), p ≤ 0.5. Then, almost surely, mas(D) ≤ min 2 (ln n) ln(1 -p) -1 + 1, n .
Theorem 1.3 Write w = np.
There is a sufficiently large constant W such that : If p satisfies w ≥ W , then, almost surely,

mas(D) ≤ 2 ln(1 -p) -1 (ln w + 3e) .
The lower bound of Theorem 1.2 requires that p = o(1). One can obtain a lower bound for larger values of p also. This bound is precisely stated in Theorem 1.5 given below.

Let G ∈ G(n, p) denote the simple undirected random graph on V where each edge is chosen independently with probability p. Let α(G) denote the maximum size of an independent set in G. The following lemma (Lemma 2.1) of [START_REF] Subramanian | Finding induced acyclic subgraphs in random digraphs[END_REF] relates lower bounds on mas(D) and α(G). For p ≥ (ln n) -1 , Bollobas and Erdős [START_REF] Bollobas | Cliques in random graphs[END_REF] and Matula [START_REF] Matula | The largest clique size in a random graph[END_REF] (see also Chapter 7 of [START_REF] Janson | Random Graphs[END_REF]) obtained the following lower bound on α(G).

Theorem 1.4 ([1], [START_REF] Matula | The largest clique size in a random graph[END_REF]) Write w = np. Let p be such that (ln n) -1 ≤ p ≤ 0.5. Then, almost surely,

α(G) ≥ 2 ln(1 -p) -1 (ln w -ln ln w -O(1)) .
Applying Lemma 1.1 to the previous theorem, we obtain Theorem 1.5 Write w = np. Let p be such that p ≥ (ln n) -1 . Then, almost surely,

mas(D) ≥ 2 ln(1 -p) -1 (ln w -ln ln w -O(1)) .
Combining the lower and upper bounds mentioned in Theorems 1.2, 1.5 and 1.3, we obtain the following corollary which provides a tight estimate of the range of mas(D).

mas(D) = 2(ln w) ln(1 -p) -1 (1 ± o(1)) .
Here, o( 1) is with respect to n.

Proof: If p ≤ 1/(ln n), then we apply the lower bound of Theorem 1.2 and also use the fact that ln(1p) -1 ≥ p for each p < 1 to get the desired result. Otherwise, we can apply the lower bound of Theorem 1.5 to obtain the corollary. ✷ Note 1 : The lower bound of Theorem 1.2 has a factor of p -1 which is better than the factor 1/(ln(1p) -1 ) used by the bound of Theorem 1.5. This improvement is marginal since Theorem 1.2 is applicable only for small (p = o(1)) values of p. But the improvement is significant for higher values of p, if possible. For example, when p = 1/2, 2p -1 = 4 but 2/(ln(1 -p) -1 ) = 2/(ln 2) ≈ 2.886. But such an improvement for higher values of p is ruled out by the upperbound of Theorem 1.3.

Note 2 : By a constructive lower bound of (1 -ǫ)(ln w)/(ln(1 -p) -1 ) on the size of any maximal induced acyclic subgraph obtained by Subramanian in [START_REF] Subramanian | Finding induced acyclic subgraphs in random digraphs[END_REF], we notice that, for any p, a simple greedy heuristic produces a solution whose size is almost surely within a ratio of 2 + δ for any positive δ. Thus, for random digraphs, one can obtain a constant factor approximation to the optimal solution.

The results (theorems and corollaries) stated in this section hold true if D is a random graph obtained by choosing each potential directed edge independently with probability p. See Section 3 for further details.

Proof of Theorem 1.3

We use q to denote the expression ln(1 -p) -1 . The following fact will be used in the proof. For p = 0, we take the limit.

q p = ln(1 -p) -1 p = -ln(1 -p) p ≤ 1.5 for 0 ≤ p ≤ 0.5. (1)
Let u be any positive integer and let A ⊆ V be a set of size u such that D[A] is acyclic. Then, there exists an ordering σ : {1, . . . , u} → A of A such that each arc in D[A] is of the form σ(i) → σ(j) for some 1 ≤ i < j ≤ u. This implies that, for any 1 ≤ k ≤ u, there is an ordered partition of A into k subsets A 1 , . . . , A k such that

• |A i | = u i = ⌈u/k⌉ for i ≤ r and |A i | = u i = ⌊u/
k⌋ for i > r where r = u mod k.

• For each 1 ≤ i < j ≤ k, there is no arc in D[A] from any element in A j to any element in A i .

Note 3:

We shall carefully choose k below to give nearly optimal results. The case k = 2 was first explored by the authors. Already this gives mas(D) = O(p -1 ln(np)) and the technical calculations below are considerably simpler. Now, choose u to be the integer u = q -1 (ln w)(2 + δ) where δ is determined by the requirement that u = ⌊q -1 (ln w)(2 + 6e(ln w) -1 )⌋. It is sufficient to prove that, almost surely, the subgraph induced by any A of size u is not acyclic. Fix a subset A of size u. Using the above mentioned observation about such acyclic subsets and also the inequality of Lemma 2.1 (given later),

Pr( D[A] is acyclic ) ≤ u u 1 , . . . , u k (1 -p) P i<j uiuj ≤ u u 1 , . . . , u k (1 -p) ( k 2 )(u/k) 2 -k/8 ≤ k u e -qu 2 (k-1)/2k (1 -p) -k/8 = k u e -u(ln w)(2+δ)(k-1)/2k (1 -p) -k/8 = k e (ln w)(2+δ)(k-1)/2k u (1 -p) -k/8
This bound holds for any fixed A of size u. There are n u ≤ en u u sets of size u. This gives us

Pr( ∃A, |A| = u, D[A] is acyclic ) ≤ enk ue (ln w)(2+δ)(k-1)/2k u (1 -p) -k/8 = ewk (2 + δ)(ln w)w (2+δ)(k-1)/2k • q p u (1 -p) -k/8
Now choose k to be the integer nearest to 2(ln w)(3e) -1 + 2. By choosing W sufficiently large, we can ensure that k ≤ 3(ln w)(3e) -1 . Thus, we have 2(ln w)(3e) -1 + 1 < k ≤ 3(ln w)(3e) -1 . It then follows that 2/(k -1) < (3e)(ln w) -1 or equivalently that 2k/(k -1) = 2 + 2/(k -1) < 2 + (3e)(ln w) -1 . This implies that k -

1 2k (2 + δ) ≥ k -1 2k 2 + (3e)(ln w) -1 > 1. = r (a -b + 1) 2 -(a -b) 2 + k (a -b) 2 -a 2 = r (1 + 2a -2b) + k b 2 -2ab = r (1 + 2a -2b) + r (b -2a) = r (1 -b) = r(k -r) k ≤ k 2 4k = k 4
The lemma now follows. ✷

Non-simple random digraphs

Consider the other model which does not force the random digraph to be simple and allows cycles of length 2.

Model D ∈ D 2 (n, p) : Choose each directed edge u → v joining distinct elements of V independently with probability p.

Consider D ∈ D 2 (n, p). For each unordered pair {u, v} of distinct vertices, the 2-cycle u, v, u fails to be present in D with probability 1 -p 2 . Hence,

Pr( D has no 2-cycle ) = (1 -p 2 ) ( n 2 ) ≤ e -n(n-1)p 2 /2
Hence if np → ∞, then D has a 2-cycle almost surely. In fact, for any f (n) = ω(p -1 ), for each sufficiently large n, if A is any fixed subset of V of size f (n), then the probability that A has a 2-cycle approaches 1. In particular, this is true for f (n) = Ω(p -1 (ln np)). Still, as stated in Theorem 3.1 given below, almost surely, there are induced acyclic subgraphs of size f (n) in D and hence mas(D) = Ω(p -1 (ln np)). This may seem paradoxical but does not seem so once we notice that the number of subsets of size f (n) is so large that some subset A manages to be devoid of not only 2-cycles but also of all cycles despite the low probability of this happening for any fixed set. Precisely, we obtain the following Here, o(1) is with respect to n.

Theorem 1 . 2 (

 12 [START_REF] Subramanian | Finding induced acyclic subgraphs in random digraphs[END_REF]) Write w = np. For each fixed ǫ > 0, there exists a sufficiently large positive constant w ǫ such that : If p is such that w ǫ ≤ w = o(n), then, almost surely, mas(D) ≥ 2 p (ln w -ln ln w -ln 2 + 1 -0.5ǫ).

Lemma 1 . 1 (

 11 [START_REF] Subramanian | Finding induced acyclic subgraphs in random digraphs[END_REF]) Let D ∈ D(n, p) and G ∈ G(n, p). For any positive integer b,Pr( mas(D) ≥ b ) ≥ Pr( α(G) ≥ b ).

Corollary 1 . 1

 11 Write w = np. If p satisfies w = ω(1), then almost surely,

Theorem 3 . 1

 31 Let D ∈ D 2 (n, p) with p ≤ 0.5. The lower and upper bounds stated in Theorems 1.2, 1.3 and 1.5 hold true (with respective assumptions) for D ∈ D 2 (n, p) also. Proof: One can verify from the proof of Lemma 1.1 that it holds true also when D is drawn using the D 2 (n, p) model. Hence the lower bounds follow from applying this lemma to lower bounds on α(G) for G ∈ G(n, p). For the upper bounds, one can verify that the proof arguments that worked for D ∈ D(n, p) work for D ∈ D 2 (n, p) also. ✷ As a corollary, we obtain Corollary 3.1 Let D ∈ D 2 (n, p). Write w = np. If p satisfies w = ω(1), then almost surely, mas(D) = 2(ln w) ln(1 -p) -1 (1 ± o(1)) .

Also, since p ≤ 0.5, we have (1 -p) -1 ≤ 2 and hence (1 -p) -k/8 ≤ e k/8 ≤ e 3(ln w)/8(3e) = w 3/8(3e) . Applying these in the probability estimate derived above, we get

Note that F P = (4/3) -u w 1/8e = w (1/8e)-(ln 4/3)(2+δ)/q ≤ w ( ln 2 8e -(ln 4/3)(2+δ))/q is inversely polynomial in w and is inversely exponential in 1/q. Also, as n → ∞, the quantity max{1/q, w} approaches ∞ for all choices of p. Hence, using our assumption w ≥ W , we notice that F P → 0 as n → ∞. This establishes that, almost surely, mas(D) ≤ 2q -1 (ln w + 3e).

It remains to prove the following lemma.

with u i = ⌈u/k⌉ for i ≤ r and u i = ⌊u/k⌋ for i > r, be an ordered partition of u into k positive parts. Then

Similarly, we have

Comparing the two equations, we get

Note 4: Note that the requirement p ≤ 0.5 can be relaxed to p being upper limited by any positive constant strictly less than 1.

Further work

For p satisfying w = np = ω(1), Corollary 1.1 provides a tight estimate of mas(D). However, the lower and upper bounds still differ by an additive term which is in O( ln ln w ln(1-p) -1 ). We believe that the two bounds can be brought even closer to each other.

Similarly, in the case of D ∈ D 2 (n, p), there is scope for tightening and reducing the gap of O( ln ln w ln(1-p) -1 ) between the lower and upper bounds on mas(D) derived in this paper. We believe this can also be reduced further and it is worth exploring. Corollary 1.1 affirmatively settles the conjecture of [START_REF] Subramanian | Finding induced acyclic subgraphs in random digraphs[END_REF] for p = ω(1/n). It would be interesting to extend the result to all p ≥ c/n for some absolute constant c > 0.


Gruia Cȃlinescu

Cristina G Fernandes

On the k-restricted structure ratio in planar and outerplanar graphs

Keywords: planar graphs, outerplanar graphs, approximation algorithms

A planar k-restricted structure is a simple graph whose blocks are planar and each has at most k vertices. Planar k-restricted structures are used by approximation algorithms for Maximum Weight Planar Subgraph, which motivates this work.

The planar k-restricted ratio is the infimum, over simple planar graphs H, of the ratio of the number of edges in a maximum k-restricted structure subgraph of H to the number edges of H. We prove that, as k tends to infinity, the planar k-restricted ratio tends to 1/2. The same result holds for the weighted version.

Our results are based on analyzing the analogous ratios for outerplanar and weighted outerplanar graphs. Here both ratios tend to 1 as k goes to infinity, and we provide good estimates of the rates of convergence, showing that they differ in the weighted from the unweighted case.

Introduction

We provide insight on approximation algorithms for MAXIMUM WEIGHT PLANAR SUBGRAPH and related problems. MAXIMUM WEIGHT PLANAR SUBGRAPH is the NP-hard problem [START_REF] Liu | On the deletion of nonplanar edges of a graph[END_REF]; [START_REF] Yannakakis | Node-and edge-deletion NP-complete problems[END_REF] of finding a heaviest planar subgraph in an edge-weighted simple graph G = (V, E, w), where w : E → Q + . That is, the objective is to find a set of edges F ⊆ E such that (V, F ) is a planar graph, and which maximizes w(F ) = e∈F w(e). In the unweighted version, called MAXIMUM PLANAR SUBGRAPH, the goal is to find a planar subgraph of G with maximum number of edges -that is, all edges of G have weight 1.

A planar k-restricted structure is a graph whose blocks (2-connected components) are planar and each has at most k vertices. As we are only interested in planar graphs, from now on we omit the word "planar" -all our k-restricted structures are planar. The best known approximation algorithms for MAXIMUM PLANAR SUBGRAPH [START_REF] Cȃlinescu | A better approximation algorithm for finding planar subgraphs[END_REF] and MAXIMUM WEIGHT PLANAR SUBGRAPH [START_REF] Cȃlinescu | A new approximation algorithm for finding heavy planar subgraphs[END_REF] are based on 3-restricted structures.

Note that a 2-restricted structure is a forest, and finding a maximum weight forest is a classical problem with polynomial-time algorithms (see, for example, [START_REF] Cormen | Introduction to Algorithms[END_REF]). It is known how to find a maximum 3-restricted structure [START_REF] Lovász | Matching Theory[END_REF]; [START_REF] Gabow | Efficient algorithms for graphic matroid intersection and parity[END_REF]; [START_REF] Szigeti | On the graphic matroid parity problem[END_REF] and an ǫ-approximation for a maximum weight 3-restricted structure (implicit in [START_REF] Camerini | Random pseudo-polynomial algorithms for exact matroid problems[END_REF]). For k > 3, several approximation algorithms, originally devised for the Steiner tree problem, produce approximate maximum weight planar k-restricted structures [START_REF] Berman | Improved approximations for the Steiner tree problem[END_REF]; [START_REF] Zelikovsky | Better approximation bounds for the network and Euclidean Steiner tree problems[END_REF]. When applied to MAXIMUM WEIGHT PLANAR SUBGRAPH, the approximation ratio of these algorithms depends on the planar k-restricted structure ratio ρ k , defined below. The running time of these algorithms is a polynomial in n k , where n = |V |.

For a simple graph H, denote by ms k (H) the maximum number of edges in a subgraph of H whose blocks have size at most k. Define ρ k as the infimum, over planar simple graphs H, of ms k (H)/|E(H)|. When H is edge-weighted, denote by ms ′ k (H) the maximum weight of edges in a subgraph of H whose blocks have size at most k. Define ρ ′ k as the infimum, over edge-weighted planar graphs H, of ms ′ k (H)/w(E(H)). In this paper we prove that lim k→∞ ρ k = lim k→∞ ρ ′ k = 1/2. Similar ratios have been extensively studied for the Steiner tree problem [START_REF] Du | On better heuristic for Euclidean Steiner minimum trees[END_REF]; [START_REF] Promel | A new approximation algorithm for the Steiner tree problem with performance ratio 5/3[END_REF]; [START_REF] Robins | Improved Steiner tree approximation in graphs[END_REF]; [START_REF] Zelikovsky | An 11/6-approximation algorithm for the network Steiner problem[END_REF], and are used in the analysis of most approximation algorithms for Steiner tree. The ratios ρ k and ρ ′ k play a similar role with respect to MAXIMUM PLANAR SUBGRAPH. Our results are based on analyzing β k and β ′ k , defined as ρ k , but for outerplanar and edge-weighted outerplanar simple graphs. Precisely, we prove that there exist positive constants c 1 and c 2 such that

1 -c 1 lg k k ≤ β k ≤ 1 -c 2 lg k k , and that there exist positive constants c ′ 1 and c ′ 2 such that 1 -c ′ 1 1 lg k ≤ β ′ k ≤ 1 -c ′ 2 1 lg k . Hence lim k→∞ β k = lim k→∞ β ′ k = 1.
We use only base 2 logarithms in this paper. Our proofs are constructive, that is, they consist of explicit examples and deterministic algorithms.

Previous works show that ρ 2 = ρ ′ 2 = 1/3 [START_REF] Dyer | Analysis of heuristics for finding a maximum weight planar subgraph[END_REF], [START_REF] Cȃlinescu | A new approximation algorithm for finding heavy planar subgraphs[END_REF], that β 2 = β ′ 2 = 1/2, and et al. (1998, 2003). It is also known that a planar simple graph can have its edge set partitioned into two outerplanar graphs Gonc ¸alves (2005). Thus

ρ 3 = 4/9 Cȃlinescu et al. (1998), 1/3 + 1/72 ≤ ρ ′ 3 ≤ 5/12
β 3 = β ′ 3 = 2/3 Cȃlinescu
lim k→∞ ρ k ≥ 1 2 lim k→∞ β k = 1 2 and lim k→∞ ρ ′ k ≥ 1 2 lim k→∞ β ′ k = 1 2 . Note that it is trivial that ρ k ≥ ρ ′ k and β k ≥ β ′ k , and also ρ k ≥ ρ k-1 , ρ ′ k ≥ ρ ′ k-1 , β k ≥ β k-1 , and β ′ k ≥ β ′ k-1 .
Our results indicate that for β k > β ′ k for large values of k. As in [START_REF] Cȃlinescu | A new approximation algorithm for finding heavy planar subgraphs[END_REF], it is possible to prove that the approximation ratio of Berman and Ramaiyer's algorithm [START_REF] Berman | Improved approximations for the Steiner tree problem[END_REF] with blocks of size at most k, when applied to MAXI-MUM WEIGHT PLANAR SUBGRAPH, is at least

ρ ′ 2 - ρ ′ 2 -ρ ′ 3 2 - ρ ′ 3 -ρ ′ 4 3 -• • • - ρ ′ k-1 -ρ ′ k k -1 = (1) ρ ′ 2 1 2 + ρ ′ 3 1 2 - 1 3 + ρ ′ 4 1 3 - 1 4 + • • • + ρ ′ k-1 1 k -2 - 1 k -1 + ρ ′ k 1 k -1 . ( 2
)
This is a convex combination in ρ ′ j , for 2 ≤ j ≤ k. Our results do not improve the approximation ratio for MAXIMUM PLANAR SUBGRAPH or MAXIMUM WEIGHT PLANAR SUBGRAPH. They do lead immediately to an alternative proof of the main result of [START_REF] Cȃlinescu | A new approximation algorithm for finding heavy planar subgraphs[END_REF]: an approximation algorithm with ratio strictly greater than 1/3, by using a large k in Berman-Ramaiyer's formula of the previous paragraph, the fact that ρ ′ j ≥ ρ ′ j-1 ≥ 1 3 for all j ≥ 3, and that lim k→∞ ρ ′ k = 1/2. Note that the restriction of working on simple graphs is natural. Indeed dealing with multigraphs in the unweighted case is similar to dealing with weighted simple graphs. Therefore, from now on, our graphs are simple unless otherwise specified.

We continue this note as follows. In the next section we give examples for the upper bounds of the limits, and construct the machinery we use for outerplanar graphs. Then we prove the lower bounds for the limits for both weighted and unweighted outerplanar graphs. For the sake of simplicity we do not present here our best c 1 and c ′ 1 ; they do not equal our c 2 and c ′ 2 . We leave open finding the exact formulas for β k and β ′ k for all k; such formulas are known for Steiner trees in graphs [START_REF] Borchers | The k-Steiner ratio in graphs[END_REF].

Upper bounds

Outerplanar graphs

We continue with notions useful when working with outerplanar graphs, notions previously used in [START_REF] Cȃlinescu | A new approximation algorithm for finding heavy planar subgraphs[END_REF]. Let H be a maximal outerplanar graph (no edge can be added without violating outerplanarity); then it is immediate that the boundary of the exterior face of H is a Hamiltonian cycle C and each interior face is triangular (Harary, 1972, p. 106).

Let E be the edge set of H, b be the exterior face of H, F be the set of faces of H, and The "dual" construction is also possible: given any undirected tree whose all internal vertices have degree three, one can obtain a maximal outerplanar graph by embedding the tree in the plane, collapsing all the leaves into a single vertex, obtaining a plane multigraph, and taking the planar dual of this multigraph (Bondy and Murty, 1976, Sec. 9.2).

F ′ = F \
The next lemma appears in [START_REF] Cȃlinescu | A new approximation algorithm for finding heavy planar subgraphs[END_REF], but we include its proof for the sake of completeness.

Lemma 2 D ′ is a tree all of whose internal nodes have degree three.

Proof: First, let us prove that D ′ has no cycle. It is enough to show that any cycle in D contains b. A cycle in D corresponds to a cut in H (Bondy and Murty, 1976, p. 143, ex. 9.2.3). Because C is a Hamiltonian cycle in H, any cut in H contains at least two edges in C, which correspond to arcs incident to b in D.

Therefore, any cycle in D contains at least two arcs incident to b, so it contains b.

Second, let us prove that D ′ is connected. If D ′ were not connected, there would be two nodes u and v in different components of D ′ . Let us argue that we can choose u and v to be nodes in V (D). If u were Fig. 1: An outerplanar graph (solid lines) and the tree D ′ (white vertices and dotted lines) obtained from its dual. not a node in V (D), then it would be a node that originated from the subdivision of an arc incident to b, and thus it would have degree one in D ′ . Change u to its unique neighbor in D ′ . Do the same for v. Note that the new u and v must still be in different components of D ′ , since they are in the same component as the initial u and v, respectively. So we can assume u and v are nodes of D. And because D is connected, there is a path in D between u and v. For this path not to exist in D ′ , it has to go through node b. But this implies that b would be a cut node in D. If b were a cut node in D, then there would be a minimal cut in D containing exactly a proper subset of the arcs incident to b (consider the set of arcs going from b to one of the components of D after the removal of b). A minimal cut in D corresponds to a cycle in H (Bondy and Murty, 1976, p. 143, ex. 9.2.3). This implies that there would be a cycle in H whose edges are a proper subset of the edges of C, a contradiction (a proper subset of the edges of any cycle induces an acyclic graph, since it is enough to remove one edge of a cycle to be left with a path, which is acyclic).

Therefore D ′ is indeed a tree. Recall that all nodes of D but b have degree three. Before removing b, we subdivided all of the arcs incident to b. The new nodes have degree one in D ′ , and all others have the same degree as in D, i.e., three. ✷

A k-restricted structure K, subgraph of H, is also outerplanar, so its blocks with more than two vertices have each a Hamiltonian cycle. Thus having blocks of size at most k is equivalent, for outerplanar graphs, to having cycles of length at most k.

Let e be an edge of H. We use e to denote also the corresponding arc in D or D ′ . A cycle C in H (seen as a set of arcs) is a minimal cut in D (Bondy and Murty, 1976, p. 143, ex. 9.2.3). So C disconnects D. See Figure 2.1 for an example. Recall that F ′ is the set of nodes of D other than b. Since C is minimal, the nodes of D are partitioned into exactly two connected components, given by the set of nodes with exactly one endpoint in F 0 is exactly one more than the number of arcs of D ′ (or D) with exactly one endpoint in F 0 \ {u}: we have two new arcs, from u to its children, and we miss the arc from u to its parent. Immediate induction gives that

F C 1 ∋ b (outside C) and F C 0 ⊆ F ′ (inside C), so that C is
|C| = |F 0 | + 2.
The statement of the next lemma is a bit technical, so we give some intuition before stating it. Let S be a k-restricted structure on an outerplanar graph H. Consider the embedding of S induced by H. If we add to S an edge of H that lies on a non-external face of S, then the resulting graph is still outerplanar. See Figure 2.1 for an illustration. Lemma 3 Let H = (V, E) be a maximal outerplanar graph and K ⊆ E be such that (V, K) is a krestricted structure. Let Q = E \ K and e ∈ Q. Consider the duals D and D ′ described above and consider e as an arc of D and D ′ . If there is no path in D ′ with only arcs of Q starting from an endpoint of e to a leaf, then (V, K ∪ {e}) is a k-restricted structure.

Proof: For a contradiction, suppose that (V, K) is a k-restricted structure, (V, K∪{e}) is not a k-restricted structure, and there is no path in D ′ with only arcs of Q starting from an endpoint of e to a leaf. So there is also no path in D with only arcs of Q from an endpoint of e to b.

Let C be a cycle in (V, K ∪ {e}) of length greater than k. As (V, K) is a k-restricted structure, it has no cycle of length greater than k. So e ∈ C. Let F 0 = F C 0 and F 1 = F C 1 be defined as above. The arcs in D with exactly one endpoint in F 0 correspond exactly to the edges in C, and thus are in K, except for e.

Let v ∈ F be the endpoint of e in F 1 . Let R be the set of nodes reachable in D from v using only arcs of Q \ {e}. By assumption, b is not in R. Also, all arcs in D, except for e, with exactly one endpoint in R are in K, as they are not in Q. Besides, there is at least one such arc f . Let M be the set of arcs in D with exactly one endpoint in F 0 ∪ R. From the two paragraphs above, M ⊆ K. Note that F 0 ∪ R induces a connected subgraph of D ′ . Indeed, the subgraph of D ′ induced by F 0 is connected and all vertices in R are connected to v in (the subgraph of D ′ induced by) R, and v is adjacent through e to a vertex of F 0 . Also, F 0 ∪ R contains no leaves of D ′ , as b ∈ F 0 ∪ R. Therefore M is a minimal cut in D and thus, according to (Bondy and Murty, 1976, p. 143, ex. 9.2.3), is also a cycle in H.

As D without b is a tree, e is the only edge in D between F 0 and R. So f is not in C, and is in M . Also, M contains all edges in C but e. Therefore the cycle M , which is in (V, K), has more than k arcs, a contradiction, because (V, K) is a k-structure. ✷

Theorem 4 There exists a constant c 2 > 0 such that

β k ≤ 1 -c 2 lg k k for all k ≥ 4.
Proof: Let us describe a triangulated outerplanar graph H k , simply denoted H here. We describe the tree D ′ . Then D can be deduced from D ′ by collapsing leaves, while H is constructed from D by planar duality.

Consider balanced binary trees T 1 , T 2 , T 3 (all interior nodes have two children, and all the leaves are on the same level), each with between k and 2k nodes, add one more node r and make it adjacent to the roots of T 1 , T 2 , and T 3 . This is the tree D ′ , and when convenient, we assume D ′ is rooted at r. Also, let D = (F, E) and H = (V, E) be constructed as above. See Figure 2.1 for an illustration. We have that 3k ≤ |E| ≤ 6k.

Let Q be a minimal set of edges such that (V, E \ Q) is a k-restricted structure. It is enough to show that |Q| ≥ 6c 2 lg k, for a constant c 2 which we choose later.

We know that (V, E \ Q) is a k-restricted structure, and therefore it cannot have cycles longer than k. The edges in Q correspond to arcs in D ′ .

Assume first that one arc e incident to r is in Q. By the minimality of Q, we have that (V, (E \Q)∪{e}) is not a k-restricted structure. Thus, by Lemma 3, Q contains a path from r to a leaf of D ′ , and since T 1 , T 2 , and T 3 are balanced with at least k nodes, this path must have at least lg(k -1) nodes.

Consider now the second case, when the three arcs incident to r are not in Q. Let the set R of nodes of F ′ (recall that these are the interior faces of H) be constructed recursively as follows: r ∈ R, and if a non-leaf node u has a parent in R and all its (three) incident arcs are not in Q, then add u to R. Observe that all arcs that have exactly one endpoint in R are not in Q. Hence one cycle of (V, E \ Q) is given by the minimal cut of D which has R on one side. This cycle has |R| + 2 edges/arcs. As (V, E \ Q) is a r Fig. 4: The example for k = 4 in Theorem 4.

k-restricted structure, |R| < k. If Q were empty, R = F ′ . But |F ′ | > 3⌊k/2⌋ (the interior nodes of T 1 , T 2 , and T 3 ), so we get a contradiction. Thus, we may assume Q is non-empty.

As Q is minimal, Lemma 3 assures that there is a path in Q from each arc in Q to a leaf in D ′ . Let P be such a path with, say, j arcs. Note that r is not in P , as in this second case no arc incident to R is in Q. If a node u is the highest node of F ′ touched by P , then only the nodes in the balanced subtree rooted at u (including u) are not included in R because of P .

We decompose Q in ℓ such paths P 1 , P 2 , . . . , P ℓ for some ℓ ≥ 1. Thus the number of nodes of

F ′ not in R cannot exceed 2 |P1| + 2 |P2| + • • • + 2 |P ℓ | .
This number, given |Q|, is maximized when ℓ = 1 (one single long path), and it must exceed k/2 since |F ′ | > 3⌊k/2⌋ and |R| < k. We conclude that |Q| ≥ lg(k/2), in the second case.

In both cases |Q| ≥ lg(k/2) ≥ 1 2 lg k, so we can pick c 2 = 1/12, finishing the proof. ✷

Theorem 5 There exists a constant c ′ 2 > 0 such that

β ′ k ≤ 1 -c ′ 2 1
lg k for all k ≥ 4.

Proof:

The example graph H = H k is a triangulated outerplanar graph. We describe D ′ , and D can be deduced from D ′ by collapsing leaves, while H is constructed from D by planar duality. Consider a balanced binary tree T 1 with between 4k +1 and 8k nodes; add one more node r and make it adjacent to the root of T 1 . This is D ′ , and we root it at r for convenience. The graphs D = (F, E) (r is also considered to be a leaf here) and H = (V, E) are constructed as above. See Figure 5 for an illustration. Let n be the number of nodes in D ′ . Note that n = 2 h for some integer h. Also, 4k + 2 ≤ n ≤ 8k + 1, so lg k < h ≤ lg k + 4 ≤ 3 lg k. Assign to each arc e of D ′ a weight as follows: if the higher node of e is at level i (with r at level 0), then w(e) = 1/2 i . Then w(H) = h.

Let Q be a set of edges such that (V, E \ Q) is a k-restricted structure. We proceed to show that w(Q) ≥ 1/8.

We know that (V, E \ Q) is a k-restricted structure, and therefore it cannot have cycles longer than k. Again, the edges in Q correspond to arcs in D ′ . Let r ′ be the neighbor of r in D ′ . If some arc incident to r ′ is in Q, then this arc has weight 1 or 1/2, and we are done proving that w(Q) ≥ 1/8. Assume in the following that Q does not contain any arc incident to r ′ .

Let the set R of nodes of F ′ (the interior faces of H) be constructed recursively as follows: r ′ ∈ R, and if a non-leaf node u has a parent in R and all its (three) incident arcs are not in Q, then add u to R. One cycle of (V, E \Q) is given by the minimal cut of D which has R on one side; this cycle has |R|+2 edges. Thus we have that |R| < k. If Q was empty, R = F ′ and |F ′ | ≥ 2k, since T 1 has at least 4k + 1 nodes and thus at least 2k interior nodes. But this is a contradiction, so we may assume that Q is non-empty.

An interior node u of D ′ at level i (with r at level 0) has, including itself, 2 h-i -1 descendants which are interior nodes of D ′ . The lightest edge incident to u has weight 1/2 i . Thus at a cost (weight) of 1/2 i one can prevent at most 2 h-i vertices from F ′ to enter R. The cost per vertex removed is at least

1/2 h = 1/n ≥ 1/(8k + 1). The edges of Q must prevent at least k + 1 nodes from F ′ to enter R (since |R| < k and |F ′ | ≥ 2k) and therefore w(Q) ≥ k+1 8k+1 ≥ 1 8 . Thus we proved that w(Q) ≥ 1/8 for any set Q of edges such that (V, E \ Q) is a k-restricted structure.
It follows that a maximum weight k-restricted structure in H has weight at most h -1/8. Thus

β ′ k ≤ (h -1/8) w(E(H)) = h -1/8 h = 1 - 1 8 1 h ≤ 1 - 1 24 1 lg k , (3)
as h ≤ 3 lg k. Putting c ′ 2 = 1/24 completes the proof. ✷

Lower bounds

Theorem 6 There exists a constant c 1 > 0 such that

β k ≥ 1 -c 1 lg k k for all k ≥ 4.
Proof: Let H = (V, E) be an outerplanar graph, and add an edge set E ′ such that

H ′ = (V, E ∪ E ′ ) is a maximal outerplanar graph. Construct D and D ′ for H ′ ; both D and D ′ have arc set E ∪ E ′ .
We give an algorithm to construct a set of edges Q ⊆ E such that (V, E \ Q) is a k-restricted structure, and |Q| ≤ c 1 (|E|/k) lg k, for a constant c 1 to be chosen later. For a tree T and a non-root node u in T , denote by T u the subtree of T rooted at u plus the parent of u and the arc from u to its parent in T .

To construct Q, the algorithm iteratively builds a sequence of sets of edges Q 0 , Q 1 , . . . , Q ℓ and a sequence of rooted trees D 0 , D 1 , . . . , D ℓ . It starts with j = 0, Q j = ∅, and D j = D ′ , rooted at an arbitrary leaf. If D j has at most k arcs of E, the algorithm outputs

Q = Q 0 ∪ Q 1 ∪ • • • ∪ Q j .
Else, increment j and find in D j-1 the lowest node u j such that T uj , for T = D j-1 , has more than k arcs of E; such a u j must exist since the unique child of the root of D j-1 is a valid candidate. Construct in T uj a path P j as follows: set u = u j and do the following until u becomes a leaf of D j-1 . Find u ′ , a child of u such that T u ′ has at most as many edges of E as T u ′′ , where u ′′ is the other child of u. Put in P j the edge {u, u ′ }, make u = u ′ , and resume constructing P j . Of course P j may contain edges/arcs from E ′ . Define Q j = P j ∩ E and D j = D j-1 -Z j , where Z j is the set of proper descendants of u j in D j-1 (that is, without u j itself). Note that u j is a leaf in D j . Go back to the checking of the number of arcs of E in D j . Denote by ℓ the final value of j.

Immediate induction gives that, for j = 1, . . . , ℓ, each D j is a rooted almost-binary tree (the root has only one child, while any other non-leaf node has two children). By the choice of u j , the subtrees rooted at both children of u j have at most k edges of E. Therefore P j contains at most 1 + lg k arcs of E and thus It remains to prove that

|Q j | ≤ 1 + lg k ≤ 2 lg k. If we let E j be E ∩ E(D j ), then |E j+1 | ≤ |E j | -k,
K = (V, E \ Q) is a k-restricted structure. Define Q ′ = ∪ ℓ i=1 P j \ E. If ℓ = 0, then |E| ≤ k,
and no cycle of K can have more than k edges. Thus we assume in the following that ℓ > 0. Note that u 1 is connected to a leaf of D ′ by the path P 1 . For 2 ≤ i ≤ ℓ, each u i is connected by the path P i to either a leaf of D ′ or a previous u i ′ (1 ≤ i ′ < i). Therefore by immediate induction each

u i , with 1 ≤ i ≤ ℓ, is connected to a leaf of D ′ by a path contained in Q ∪ Q ′ .
Assume for a contradiction that K is not a k-restricted structure. Let C be a cycle of K with more than k edges. Recall that F C 0 , or simply F 0 , is a set of nodes of D and b ∈ F 0 . Consider F 0 as a set of nodes in D ′ and recall also that F 0 induces a connected subgraph of D ′ . We claim that F 0 ∩ {u 1 , u 2 , . . . , u ℓ } = ∅. Indeed, next we prove this by induction on ℓ, by looking at the algorithm above, that picked u 1 , u 2 , . . . , u ℓ .

When ℓ = 1, we reason as follows: as F 0 induces a connected subgraph of D ′ , we have that either

u 1 ∈ F 0 , or F 0 ⊆ A 1 , the set of proper descendants of u 1 , or F 0 ⊆ V (D ′ ) \ (A 1 ∪ {u 1 }). If u 1 ∈ F 0 ,
we are done. So we analyze the two other possibilities. Assume that F 0 ⊆ V (D ′ ) \ (A 1 ∪ {u 1 }). Since ℓ = 1, the whole tree induced by V (D ′ ) \ A 1 has at most k edges from E, and all the edges with exactly one endpoint in F 0 are in this induced tree (as in this case u 1 ∈ F 0 ), contradicting |C| > k. So it is not possible that F 0 ⊆ V (D ′ ) \ (A 1 ∪ {u 1 }). Assume now that F 0 ⊆ A 1 . Let u ′ and u ′′ be the children of u 1 . Then F 0 does not contain u 1 and, as it is connected, F 0 must lay entirely in the subtree rooted at either u ′ or u ′′ . Say, by symmetry, it is contained in the subtree rooted at u ′ . By our choice of u 1 (with lowest level in the tree D ′ = D 0 ), the subtree T u ′ has at most k edges/arcs of E. Noting that F 0 does not contain leaves of D ′ , we conclude that all the arcs of D ′ with exactly one endpoint in F 0 must be in T u ′ , and therefore |C| ≤ k, a contradiction. Now assume ℓ > 1. The argument above gives that F 0 cannot be a subset of A 1 . Unless u 1 ∈ F 0 , in which case we are done, we must have that F 0 is a subset of V (D 1 ) that does not contain leaves of D 1 . Then we can apply the same arguments to u 2 as we did to u 1 , with D 1 instead of D 0 . This continues for u 3 and so forth until we conclude that, unless F 0 ∩ {u 1 , u 2 , . . . , u ℓ-1 } = ∅, we must have u ℓ ∈ F 0 .

We proved that, assuming |C| > k, we have F 0 ∩ {u 1 , u 2 , . . . , u ℓ } = ∅. So let i, with 1 ≤ i ≤ ℓ, be such that u i ∈ F 0 . We know that u i is connected by a path P contained in Q ∪ Q ′ to a leaf of D ′ ; this path must have an edge e with exactly one endpoint in F 0 , since no leaf of D ′ is in F 0 . By the way

F 0 is defined, e ∈ C. However, e ∈ Q ∪ Q ′ ⊆ Q ∪ E ′ , and C ⊆ E(K) = E \ Q. That is, e ∈ E ∩ E ′ = ∅, a contradiction. We conclude that K is indeed a k-restricted structure, completing the proof. ✷ Theorem 7 There exists a constant c ′ 1 > 0 such that β ′ k ≥ 1 -c ′ 1 1 lg k for all k ≥ 4.
Proof: The idea of the proof comes from Lemma 25 of [START_REF] Cȃlinescu | A new approximation algorithm for finding heavy planar subgraphs[END_REF], where the case k = 3 is Let u be the highest node of F 0 in D ′ . Then u is not a leaf of D ′ and thus is not the root of the rooted D ′ . All the nodes of F 0 are in the subtree of D ′ rooted at u. Thus we may assume without loss of generality that i = j. Let the arc from u to its parent be colored i ′ , and the arc from u to its right child u ′′ be colored i ′′ . By construction, i ′ = i ′′ . Also, as no node in F 0 is adjacent to an arc in E j , we have that i ′ = j and i ′′ = j.

We claim that the number of nodes of F 0 is at most 2 j-i ′′ -1 if i ′′ > i ′ , and at most 2 j-i ′′ -2 j-i ′ -1 -1 if i ′′ < i ′ . The proof is by induction on 2j -3i ′′i ′ . Note that our coloring ensures that the edge from u to its left child u ′ is colored i ′ .

The induction has two base cases: i ′′ = j -1 and i ′ = j -2, or i ′′ = j -2 and i ′ = j -1. In the first case, both u ′ and u ′′ , unless they are leaves (in which case they cannot be in F 0 ), have one incident arc colored j and they cannot be in F 0 . Thus |F 0 | = 1 as desired. In the second case, u ′′ , unless a leaf, has edges incident colored as follows: j -2 to the parent, and j -1 to the right child. This is the first case, and therefore none of the children of u ′′ can be in F 0 . Unless u ′ is a leaf, the edge going from u ′ to its right child has color j, and therefore u ′ ∈ F 0 . We conclude that F 0 ⊆ {u, u ′′ } and therefore |F 0 | ≤ 2, as desired.

Consider now the general induction step. We have three case. In the first case, i ′ < i ′′ . Then u ′ , unless a leaf, has the arc going to its right child colored i ′′ + 1. If i ′′ = j -1, then u ′ ∈ F 0 ; else by induction at most 2 j-(i ′′ +1) -1 nodes in the subtree rooted at u ′ can be in F 0 . Unless it is a leaf, u ′′ has arcs incident to it colored i ′′ , to its left child, and i ′′ + 1, to its right child. Thus if i ′′ = j -1, we have that u ′′ ∈ F 0 ; otherwise, by induction, at most 2 j-(i ′′ +1) -1 nodes in the subtree rooted at u ′′ can be in F 0 . In all subcases (i ′′ = j -1 or not), the number of nodes of F 0 in the subtrees rooted at u ′ or at u ′′ is at most 2 j-i ′′ -1 -1. Then the number of nodes of F 0 in the subtree rooted at u cannot exceed one (for u) plus the number of nodes of F 0 in the subtrees rooted at u ′ and u ′′ . This number is 2 j-i ′′ -1 -1 + 2 j-i ′′ -1 -1 + 1 = 2 j-i ′′ -1, completing this induction case.

The second case is when i ′′ = i ′ -1. Unless it is a leaf, u ′′ has the arc going to its right child colored i ′′ + 1 = i ′ , and to its left child colored i ′′ . Induction gives 2 j-i ′ -1 as the maximum number of nodes of F 0 in the subtree rooted at u ′′ . Unless it is a leaf, u ′ has the arc going to its right child colored i ′ + 1 and the arc going to its left child colored i ′ . Induction gives 2 j-(i ′ +1) -1 as the maximum number of nodes of F 0 in the subtree rooted at u ′ . Then the total number of nodes of F 0 in the subtree rooted at u cannot exceed 1 + 2 j-i ′ -1 + 2 j-i ′ -1 -1 = 2 j-i ′ + 2 j-i ′ -2 j-i ′ -1 -1

(5) = 2 j-i ′ +1 -2 j-i ′ -1 -1 (6) = 2 j-i ′′ -2 j-i ′ -1 -1,

as desired. In the third case, i ′′ < i ′ -1. Unless it is a leaf, u ′′ has the arc going to its right child colored i ′′ + 1, and to its left child colored i ′′ . Induction gives 2 j-(i ′′ +1) -1 as the maximum number of nodes of F 0 in the subtree rooted at u ′′ . Unless it is a leaf, u ′ has the arc going to its right child colored i ′′ + 1 and the arc going to its left child colored i ′ . Note that i ′′ + 1 < i ′ . Induction gives that the subtree rooted at u ′ has at most 2 j-(i ′′ +1) -2 j-i ′ -1 -1 nodes of F 0 . Combining and adding u, we obtain that the total number of nodes in the subtree rooted at u cannot exceed 1 + 2 j-i ′′ -1 -1 + 2 j-i ′′ -1 -2 j-i ′ -1 -1 = 2 j-i ′′ -2 j-i ′ -1 -1, (8) as desired.

Thus the maximum number of nodes of F 0 is obtained when i ′′ = 1 and i ′ = 2, and is 2 j-1 -2 j-3 -1. Hence the cycle C has size |F 0 | + 2 ≤ 2 j-1 . To ensure that |C| ≤ k, we pick j = ⌈lg k⌉ ≥ lg k. With this value of j, each G i , for i = 1, 2, . . . , j, is a k-restricted structure.

We pick c ′ 1 = 1 at this moment. Thus we showed that H has a k-restricted structure G i with

w(E(G i )) ≥ (1 -1/j)w(E) ≥ 1 - 1 lg k w(E), (9)
finishing the proof. ✷

The proofs of Theorems 6 and 7 give the more precise bounds of β k ≥ 1 -⌊lg(k+1)⌋

  {b}. Let D be the dual undirected multigraph of H. Let us call the vertices of D (which are faces of H) nodes, and the edges of D, arcs. All nodes of D but b have degree three. Also, the edges in the Hamiltonian cycle C correspond to the arcs incident to b in D. Let D ′ be the graph obtained from D by subdividing each arc incident to b, and then removing b. See Figure 2.1 for an example.

Fig. 2 :

 2 Fig. 2: The dark edges show a cycle C in H and the gray edges show the corresponding cut in D. The black nodes indicate F0 and the white nodes, F1.

Fig. 3 :

 3 Fig. 3: The dark edges indicate a 4-restricted structure S. The dashed dark edge is inside some non-external face of S, and could be added to S with the result still being a 4-restricted structure.

Fig. 5 :

 5 Fig. 5: An example for Theorem 5. (a) A tree D ′ . (b) The corresponding graph H.

  as at most one arc of T uj remains in E j+1 : the arc from u j to its parent in D ′ . Hence it is immediate by induction on ℓ that |E| ≥ ℓk and |Q| ≤ ℓ i=1 |Q i | ≤ 2ℓ lg k. We conclude that indeed |Q| ≤ 2(|E|/k) lg k, and we now set c 1 = 2.

  3+lg(k-1)⌋ . We conjecture thatβ k = 1γ d k +lg k k and β ′ k = 1γ ′ 1 d ′ k +lg k ,with γ and γ ′ positive constants, d k = o(lg k) and d ′ k = o(lg k). Besides, it maybe the case that γ = γ ′ = 1 and d k and d ′ k are bounded by a constant. However we do not believe that d k or d ′ k are zero.

  Consider the following planar graph G. It has p + 2 vertices x, y, v 1 , v 2 , . . . , v p , and 2p edges: {x, v i } and {y, v i } for each 1 ≤ i ≤ p. Let S be an arbitrary k-restricted structure of G. Any block in S with t vertices, where t > 2, must contain x and y (and t -2 vertices v i ).

	Theorem 1 For any positive integer k, ρ k ≤ 1/2.
	Proof: Two blocks cannot
	have two common vertices, and thus S has at most one block with more than two vertices; this block
	can have at most 2(k -2) edges. Thus the maximum number of edges in a k-restricted structure of G is
	2(k -2) + (p -(k -2)) = p + k -2. Making p very large compared to k shows that ρ k cannot exceed
	1/2.	✷

† Research supported in part by NSF grant CCF-0515088. 1365-8050

considered. Let H = (V, E, w) be a weighted outerplanar graph, and add an edge set E ′ such that H ′ = (V, E ∪E ′ ) is a maximal outerplanar graph. Set w(e) = 0 for all e in E ′ . We have that w(E ∪E ′ ) = w(E) and thus without loss of generality we may construct a k-restricted structure in H ′ instead of H. Construct D and D ′ for H ′ ; both D and D ′ have arc set E ∪ E ′ .

The proof idea consists of picking a value j ≥ lg k c ′

1

(with c ′ 1 > 0 to be picked later) and color each arc of D ′ with one color from the set {1, 2, . . . , j} so that, if E i is the set of edges/arcs colored i, then the graph

which is what we want to prove. Consider j ≥ 3. Root D ′ at an arbitrary leaf. The resulting rooted tree is almost binary -every node but the root has two children. For convenience, assume the root has a right child only. Color the arc incident to the root 1. Traverse the tree in preorder, going right first, processing every non-leaf node u as follows. Let v be the parent of u, u ′ be the left child of u and u ′′ be the right child of u. Also, assume the arc {v, u} has color i, where 1 ≤ i ≤ j. Color the arc {u, u ′ } with color i. If u is the right child of v, color the arc {u, u ′′ } with color (i mod j) + 1. (That is, if i = j, then color 1, else color i + 1.) If u is the left child of v, and the arc from v to its other child is colored i ′ , then use for {u, u ′′ } color (i ′ mod j) + 1 if (i ′ mod j) + 1 = i, otherwise use for {u, u ′′ } color (i mod j) + 1. See the example in Figure 3. Now we analyze the size of some arbitrary cycle C in G i . As before, C is given by the arcs of D ′ with exactly one endpoint in F 0 = F C 0 , where F 0 induces a connected component of D ′ and does not contain leaves of D ′ .

We claim that F 0 cannot contain a node adjacent to an arc in E i . Indeed, if u is a node of F 0 adjacent to an arc in E i , then it is immediate from the way E i is constructed that there is a path P from u to a leaf of D ′ with all of its arcs in E i : just follow the arcs downwards in D ′ going left only. Since F 0 does not contain leaves in D ′ , by following P from u downwards we find an arc of D ′ with only one endpoint in F 0 . Thus there is an arc of E i which is an edge in C; however G i does not contain edges from E i . Thus no node of F 0 is adjacent to E i .