Kateřina Böhmová

Jérémie Chalopin
email: jeremie.chalopin@lis-lab.fr

Matúš Mihalák
email: matus.mihalak@maastrichtuniversity.nl

Guido Proietti
email: guido.proietti@univaq.it

Peter Widmayer
email: widmayer@inf.ethz.ch

Sequence Hypergraphs: Paths, Flows, and Cuts

Keywords: Sequence hypergraphs, colored graphs, labeled problems, transportation lines, algorithms, complexity

We introduce sequence hypergraphs by extending the concept of a directed edge (from simple directed graphs) to hypergraphs. Specifically, every hyperedge of a sequence hypergraph is defined as a sequence of vertices (not unlike a directed path). Sequence hypergraphs are motivated by problems in public transportation networks, as they conveniently represent transportation lines. We study the complexity of several fundamental algorithmic problems, arising (not only) in transportation, in the setting of sequence hypergraphs. In particular, we consider the problem of finding a shortest st-hyperpath: a minimum set of hyperedges that "connects" (allows to travel to) t from s; finding a minimum st-hypercut: a minimum set of hyperedges whose removal "disconnects" t from s; or finding a maximum st-hyperflow: a maximum number of hyperedge-disjoint st-hyperpaths. We show that many of these problems are APX-hard, even in acyclic sequence hypergraphs or with hyperedges of constant length. However, if all the hyperedges are of length at most 2, we show that these problems become polynomially solvable. We also study the special setting in which for every hyperedge there also is a hyperedge with the same sequence, but in reverse order. Finally, we briefly discuss other algorithmic problems such as finding a minimum spanning tree, or connected components.

Introduction

Consider a public transportation network, e.g., a bus network, where every vertex corresponds to a bus stop, and where every bus line is specified as a fixed sequence An extended abstract of this paper appeared at WG 2016, and it was at a workshop of this lovely series on graph-theoretic concepts in computer science where the last author had the joy of meeting the jubilarian for the first time. of bus stops. One can travel in the network by taking a bus and then following the stops in the order that is fixed by the corresponding bus line. See Figure 1 for an illustration. Note that we think of a line as a sequence of stops in one direction only, since there might be one-way streets or other obstacles that cause that the bus can travel the stops in a single direction only. Then, interesting questions arise: How can one travel from s to t using the minimum number of lines? How many lines must break down, so that t is not reachable from s? Are there two ways to travel from s to t that both use different lines?

Bratislava

These kinds of questions are traditionally modeled and studied by algorithmic graph theory, but no model appears to capture all the necessary aspects of the problems above. We propose the following very natural way to extend the concept of directed graphs to hypergraphs.

A hypergraph H = (V, E) with an ordering of the vertices of every hyperedge is called a sequence hypergraph. Formally, the sequence hypergraph H consists of the set of vertices V = {v 1 , v 2 , . . . , v n }, and the set of (sequence) hyperedges E = {E 1 , E 2 , . . . , E k }, where each hyperedge E i = (v i1 , v i2 , . . . , v i l ) is defined as a sequence of vertices without repetition. We remark that this definition substantially differs from the commonly used definition of directed hypergraphs [START_REF] Ausiello | Directed hypergraphs: Problems, algorithmic results, and a novel decremental approach[END_REF][START_REF] Ausiello | Optimal traversal of directed hypergraphs[END_REF][START_REF] Gallo | Directed hypergraphs and applications[END_REF], where each directed hyperedge is a pair (From, To) of disjoint subsets of V. We note that the order of vertices in a sequence hyperedge does not imply any order of the same vertices in other hyperedges. Furthermore, the sequence hypergraph does not impose any global order on V.

There is another way to look at sequence hypergraphs coming from our motivation in transportation. For a sequence hypergraph H = (V, E), we construct a directed colored multigraph G = (V, E, c) as follows. The set of vertices V is identical to V, and for a hyperedge E i = (v i1 , v i2 , . . . , v i l ) from E, the multigraph G contains l -1 edges (v ij , v ij+1 ) for j = 1, . . . , l -1, all colored with color c(E i ), with c(E i ) = c(E i ) for i = i . Therefore, each edge of G is colored by one of the k = |E| different colors C = {c(E 1 ), c(E 2 ), . . . , c(E k ) | E i ∈ E}. Clearly, the edges of each color form a directed path in G. We refer to G as the underlying colored graph of H. We denote by m the number of edges of G.

In this article, we study several standard graph-algorithmic problems in the setting of sequence hypergraphs. In particular, we consider the problem of finding a shortest st-hyperpath: an st-path that uses the minimum number of sequence hyperedges; the problem of finding a minimum st-hypercut: an st-cut that uses Table 1. Summary of the complexities admitted by some classic problems in the setting of colored (labeled) graphs and sequence hypergraphs. The last row indicates whether the sizes of the maximum st-flow and the minimum st-cut equal in the considered setting. The cells in gray show our contribution. the minimum number of sequence hyperedges; and the problem of finding a maximum st-hyperflow: a maximum number of hyperedge-disjoint st-hyperpaths.

We show that the shortest st-hyperpath is NP-hard to approximate within a factor of (1 -ε) ln n, for any ε > 0, in general sequence hypergraphs, but can be found in polynomial time if the given sequence hypergraph is acyclic (Section 3). On the other hand, we show that both maximum st-hyperflow and minimum sthypercut are APX-hard to find even in acyclic sequence hypergraphs (Sections 4 and 5). We then consider sequence hypergraphs with sequence hyperedges of constant length, where the length of a hyperedge is the number of its vertices minus one. We note that the shortest st-hyperpath problem remains hard to approximate even with hyperedges of length at most 5, and we show that the maximum st-hyperflow problem remains APX-hard even with hyperedges of length at most 3. On the other hand, we show that if all the hyperedges are of length at most 2, all 3 problems become polynomially solvable (Section 6). We also study the complexity in a special setting in which for each hyperedge there also is a hyperedge with the same sequence, but in the opposite direction. We show that the shortest st-hyperpath problem becomes polynomially solvable, but both maximum st-hyperflow and minimum st-hypercut are NP-hard to find also in this setting, and we give a 2-approximation algorithm for the minimum st-hypercut problem (Section 7). Finally, we briefly study the complexity of other algorithmic problems, namely, finding a minimum spanning tree, or connected components, in sequence hypergraphs (Section 8). For a summary of the results see Table 1. The table also shows known results for the related labeled graphs (discussed below). The result on the APX-hardness of the shortest st-hyperpath problem (Theorem 1) appeared also, in a different context, in [START_REF] Böhmová | Computing and Listing st-Paths in Public Transportation Networks[END_REF].

Related Work

Recently, there has been a lot of research concerning optimization problems in (multi)graphs with colored edges, where the cost of a solution is measured by the number of colors used, e.g., one may ask for an st-path using the minimum number of colors. The motivation comes from applications in optical or other communication networks, where a group of links (i.e., edges) can fail simultaneously and the goal is to find resilient solutions. Similar situations may occur in economics, when certain commodities are sold (and priced) in bundles.

Formally, colored graphs or labeled graphs are (mostly undirected) graphs where each edge has one color, and in general there is no restriction on a set of edges of the same color. Note that some of the studies consider a slightly different definition of colored graphs, where to each edge a set of colors is associated instead of a single color. Since the computational complexity of some problems may differ in the two models, the transformations between the two models have been investigated [START_REF] Coudert | Combinatorial optimization in networks with Shared Risk Link Groups[END_REF].

The minimum label path problem, which asks for an st-path with a minimum number of colors, is NP-hard and hard to approximate [5-7, 16, 17, 22]. The 2 label disjoint paths problem, which asks for a pair of st-paths such that the sets of colors appearing on the two paths are disjoint, is NP-hard [START_REF] Hu | Diverse routing in optical mesh networks[END_REF]. The minimum label cut problem, which asks for a set of edges with a minimum number of colors that forms an st-cut, is NP-hard and hard to approximate [START_REF] Coudert | Shared risk resource group complexity and approximability issues[END_REF][START_REF] Zhang | Approximation and hardness results for label cut and related problems[END_REF]. The minimum label spanning tree problem, which asks for a spanning tree using edges of minimum number of colors, is NP-hard and hard to approximate [START_REF] Hassin | Approximation algorithms and hardness results for labeled connectivity problems[END_REF][START_REF] Krumke | On the minimum label spanning tree problem[END_REF]. application of a derived result they study the maximum number of edges of a so-called directed Sperner-hypergraph.

On the Shortest st-Hyperpath

In this section, we consider the shortest st-hyperpath problem in general sequence hypergraphs and in acyclic sequence hypergraphs.

Definition 1 (st-Hyperpath). Let s and t be two vertices of a sequence hypergraph H = (V, E). A set of hyperedges P ⊆ E forms a hyperpath from s to t if the underlying (multi)graph G of the subhypergraph H = (V, P ) contains an st-path, and P is minimal with respect to inclusion. We call such an st-path an underlying path of P. The length of an st-hyperpath P is defined as the number of hyperedges in P . The number of switches of an st-hyperpath P is the minimum number of changes between the hyperedges of P , when following any underlying st-path of P .

We note that each hyperpath may have multiple underlying paths. Also note that, even though the number of switches of an st-hyperpath P gives an upper bound on the length of P , the actual length of P can be much smaller than the number of switches of P (see Figure 2a). Proposition 1. Given a sequence hypergraph, and two vertices s and t, an st-hyperpath minimizing the number of switches can be found in polynomial time.

Such an st-hyperpath can be found, e.g., by a modified Dijkstra algorithm (starting from s, following the outgoing sequence hyperedges and for each vertex storing the minimum number of switches necessary to reach it).

Conversely, we show that finding a shortest st-hyperpath (minimizing the number of hyperedges) is hard to approximate. On the other hand, if the given sequence hypergraph is acyclic, we show that the shortest st-hyperpath problem becomes polynomially solvable.

Definition 2 (Acyclic Sequence Hypergraph). A set of hyperedges O ⊆ E

forms a hypercycle, if there are two vertices a = b such that O contains both a hyperpath from a to b, and a hyperpath from b to a. A sequence hypergraph without hypercycles is called acyclic.

s = v 0 v 6 = t x 1 x 2 x 3 x 4 x 5 x 6 v 1 v 2 v 3 v 4 v 5 X = {x 1 , x 2 , . . . , x 6 } S 1 = {x 1 , x 2 , x 5 } S 2 = {x 1 , x 3 , x 5 } S 3 = {x 2 , x 3 , x 6 } S 4 = {x 3 , x 4 , x 6 } S 5 = {x 4 , x 5 , x 6 }
Fig. 3. Finding a shortest st-hyperpath is at least as hard as the minimum set cover problem.

Observe that an st-hyperpath may also be a hypercycle (see Figure 2b).

Definition 3 (Edges of a Hyperedge)

.

Let E = (v 1 , v 2 , . . . , v k ) be a hyperedge of a sequence hypergraph H. We call the set of directed edges {e i = (v i , v i+1 )| i = 1, . . . , k -1} the edges of E.
The edges of E are exactly the edges of color c(E) in the underlying colored graph of H. The length of a hyperedge is defined as the number of its edges (which is the number of its vertices minus one). For a fixed order

V O = (v 1 , v 2 , . . . , v n ) of vertices V,
an edge e of a hyperedge E is called a forward edge with respect to V O if its orientation agrees with the order V O . Similarly, e is a backward edge if its orientation disagrees with V O . Theorem 1. Finding a shortest st-hyperpath in sequence hypergraphs is NP-hard to approximate within a factor of (1 -ε) ln n for any ε > 0, unless P = NP. The problem remains APX-hard even if every hyperedge has length at most 5.

Proof. We construct an approximation-preserving reduction from the set cover problem. The reduction is similar to that presented in [START_REF] Yuan | Minimum-color path problems for reliability in mesh networks[END_REF] for the minimum label path problem in colored graphs. An instance I = (X, S) of the set cover problem is given by a ground set X = {x 1 , . . . , x n }, and a family of its subsets S = {S 1 , . . . , S m }. The goal is to find a smallest subset S ⊆ S such that the union of the sets in S contains all elements from X. The set cover problem is known to be NP-hard to approximate within a factor of (1 -) ln n, unless P = NP [START_REF] Dinur | Analytical Approach to Parallel Repetition[END_REF]. Moreover, if each subset of S is of size at most 3, the problem remains APX-hard [START_REF] Crescenzi | A compendium of NP optimization problems[END_REF].

From I we construct a sequence hypergraph H = (V, E) as follows (cf. Figure 3 along with the construction). The set of vertices V = {v 0 , v 1 , . . . , v n } contains one vertex v i for each element x i of the ground set X, plus one additional vertex v 0 . Let V O be the order of vertices in V naturally defined by their indices. The set of sequence hyperedges E = {E 1 , . . . , E m } contains one hyperedge for each set in S. For a set S i ∈ S, consider the set of vertices that correspond to the elements in S i and order them according to V O , to obtain a sequence Q = (v i1 , v i2 , . . . , v ir ), where i 1 < i 2 < • • • < i r . First, let us consider the simplest case where none of the v ij and v ij+1 (for j = 1, . . . , r -1) are consecutive in the order V O , that is, i j + 1 = i j+1 . Then the sequence of the hyperedge E i corresponding to S i is (v ir-1 , v ir , v i (r-1) -1 , v i (r-1) , . . . , v i1-1 , v i1 ) (e.g., the hyperedge corresponding to S 2 in Figure 3). In other words, E i consists of forward edges: one forward edge (v ij -1 , v ij ) for each v ij in Q; and backward edges that connect the forward edges in the order opposite to Q. Now, for the more general case, if for some j, v ij and v ij+1 are consecutive vertices with respect to V O , i.e., i j + 1 = i j+1 , the sequence constructed as above would contain vertices repeatedly, which is not allowed (each sequence hyperedge has to be mapped to a path in the underlying graph). To avoid this, we construct E i as follows. For simplicity of the explanation, instead of describing the sequence of the hyperedge, we specify E i by listing the edges of the hyperedge and the path to which E i is mapped. The hyperedge E i consists of the same forward edges as before: one forward edge (v ij -1 , v ij ) for each v ij in Q. Whenever two or more vertices of Q are consecutive in V O , their corresponding forward edges form a path. Clearly, the forward edges of E i then determine a set of (non-overlapping) paths p 1 , p 2 , . . . , p r (uniquely ordered according to V O ). The backward edges of E i then connect these paths in the order opposite to V O into a single path (which specifies E i ). In particular, the last vertex of p r connects to the first vertex of p r -1 , the last vertex of p r -1 connects to the first vertex of p r -2 , . . . , and the last vertex of p 2 connects to the first vertex of p 1 .

Note that the length of each sequence hyperedge E i is bounded by 2|S i | -1, where |S i | is the size of the set S i ∈ S corresponding to E i . This follows from the fact that E i consists of |S i | forward edges and at most |S i | -1 backward edges to connect the forward edges. In particular, if each subset of S is of size at most 3, all the hyperedges are of length at most 5.

We set the source vertex s to v 0 , and the target vertex t to v n , and we show that a shortest st-hyperpath in H of length k provides a minimum set cover for I of the same size, and vice versa. First, notice that all the forward edges (with respect to V O ) of the hyperedges in E are of the form (v i , v i+1 ) for some i = 0, . . . , n -1. Together with the fact that t is smaller than s in the order V O , it follows that any path from s to t in the underlying graph of H goes via all the vertices, in the order V O . Thus, there is an underlying path p of the shortest st-hyperpath P in H, such that p does not use any backward edges of the hyperedges in E. Clearly, by choosing a hyperedge E i into the st-hyperpath P , one also chooses its forward edges and this way "covers" some sections of the underlying path of P . Since there is a one-to-one mapping between the hyperedges in E and the sets in S, by finding an st-hyperpath P of length k, one finds a set cover of size k for the given instance. On the other hand, each set cover of size k can be mapped, using the same direct one-to-one mapping in the opposite direction, to an st-hyperpath of length k.

Thus, the described reduction is approximation-preserving. By reducing from the general set cover problem we obtain the first part of the claim, and by reducing from the set cover problem with all subsets of size at most 3 we obtain the second part of the claim.

We complement the hardness result with a positive one.

Theorem 2. The problem of finding the shortest st-hyperpath in acyclic sequence hypergraphs can be solved in polynomial time.

Proof. Let H = (V, E) be an acyclic sequence hypergraph. Since H is acyclic, let V O be an order of the vertices V such that all the edges of each hyperedge are forward edges with respect to this order. This implies that for every sthyperpath, there is an underlying path where all the edges of each hyperedge appear consecutively (the last edge of a hyperedge E appearing in an underlying path is reachable by E from the first appearing edge of E). Therefore, finding the shortest st-hyperpath P in H is the same as finding a hyperpath minimizing the number of switches, which can be done in polynomial time by Proposition 1.

On the Maximum st-Hyperflow

We consider the problem of finding a number of hyperedge-disjoint st-hyperpaths. Capturing a similar relation as in graphs (between a set of k edge-disjoint st-paths and an st-flow of size k, when all the capacities are 1), for simplicity and brevity, we refer to a set of hyperedge-disjoint st-hyperpaths as an st-hyperflow.

Definition 4 (st-Hyperflow). Let s and t be two vertices of a sequence hypergraph

H = (V, E). Let F ⊆ 2 E be a set of pairwise hyperedge-disjoint st-hyperpaths F = {P 1 , . . . , P k }. Then, F is an st-hyperflow of size |F| = k.
We show that deciding whether a given sequence hypergraph contains an st-hyperflow of size 2 is NP-hard, and thus finding a maximum st-hyperflow is inapproximable within a factor of 2 -ε unless P = NP. This remains true even for acyclic sequence hypergraphs with all the hyperedges of length at most 3. Theorem 3. Given an acyclic sequence hypergraph H = (V, E) with all hyperedges of length at most 3, and two vertices s and t, it is NP-hard to decide whether there are two hyperedge-disjoint st-hyperpaths.

Proof. We construct a reduction from the NP-complete 3-Sat problem [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completeness[END_REF]. Let I be an instance of the 3-Sat problem, given as a set of m clauses C = {c 1 , . . . , c m } over a set X = {x 1 , . . . , x n } of Boolean variables. Recall that the goal of the 3-Sat problem is to find an assignment to the variables of X that satisfies all clauses of C.

From I we construct a sequence hypergraph H = (V, E) as follows (cf. Figure 4 along with the construction). The set V consists of 2+(m+1)+(n+1)+ ci∈C |c i | vertices: a source vertex s and a target vertex t; a vertex c i for each clause c i ∈ C and a dummy vertex c m+1 ; a vertex x j for each variable x j ∈ X and a dummy vertex x n+1 ; and finally a vertex x j c i for each pair (x j , c i ) such that x j ∈ c i , and similarly, x j c i for each x j ∈ c i . Let us fix an arbitrary order C O of the clauses in C. The set E consists of 4 + 2n + |I| hyperedges: There are 2 source hyperedges (s, c 1 ) and (s, x 1 ), and 2 target hyperedges (c m+1 , t) and (x n+1 , t). There are 2n auxiliary hyperedges (x i , x i c k ) and (x i , x i c k ) for i = 1, . . . , n, where c k , or c k is always the first clause (with respect to C O ) containing x i or x i , respectively. If there is no clause containing x i (or x i ), the corresponding auxiliary hyperedge is (x i , x i+1 ). Finally, there are |I| lit-in-clause hyperedges as follows.

c 1 c 1 c 2 c 2 c 3 c 3 c 4 x 1 + - x 1 x 2 + - x 2 x 3 + - x 3 x 4 + - x 4 x 5 s t x 1 c 1 x 2 c 1 x 3 c 1 x 1 c 2 x 2 c 2 x 1 c 3 x 3 c 3 x 4 c 2 Φ = ( x 1 ∨ x 2 ∨ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 4 ) ∧ ( x 1 ∨ x 3 )
Fig. 4. Deciding st-hyperflow of size 2 is at least as hard as 3-Sat.

For each appearance of a variable x j in a clause c i as a positive literal there is one lit-in-clause hyperedge (c i , c i+1 , x j c i , x j c k ), where c k is the next clause (with respect to C O ) after c i where x j appears as a positive literal (in case, there is no such c k , then the hyperedge ends in x j+1 instead). Similarly, if x j is in c i as a negative literal, there is one lit-in-clause hyperedge (c i , c i+1 , x j c i , x j c k ), where c k is the next clause containing the negative literal x j (or it ends in x j+1 ).

Clearly, each hyperedge is of length at most 3. We now observe that the constructed sequence hypergraph H is acyclic. All the hyperedges of H agree with the following order: the source vertex s; all the vertices c i ∈ C ordered according to C O , and the dummy vertex c m+1 ; the vertex x 1 followed by all the vertices x 1 c i ordered according to C O , and then followed by the vertices x 1 c i again ordered according to C O ; the vertex x 2 followed by all x 2 c i and then all x 2 c i ; . . . ; the vertex x n followed by all x n c i and then all x n c i ; and finally the dummy vertex x n+1 ; and the target vertex t.

We show that the formula I is satisfiable if and only if H contains two hyperedge-disjoint st-hyperpaths. There are 3 possible types of st-paths in the underlying graph of H: the first one leads through all the vertices c 1 , c 2 , . . . , c m+1 in this order; the second one leads through all the vertices x 1 , x 2 , . . . , x m+1 in this order and between x j and x j+1 it goes either through all the x j c * (here, and later, * is used as a wildcard) vertices or through all the x j c * vertices (this may differ for different j); and the third possible st-path starts the same as the first option and ends as the second one. Based on this observation, notice that there can be at most 2 hyperedge-disjoint st-hyperpaths: necessarily, one of them has an underlying path of the first type, while the other one has an underlying path of the second type.

From a satisfying assignment A to the variables of I we can construct the two disjoint st-hyperpaths as follows. The underlying path of one hyperpath leads from s to t via the vertices c 1 , c 2 , . . ., c m+1 , and to move from c i to c i+1 it uses a lit-in-clause hyperedge that corresponds to a pair (l, c i ) such that l is one of the literals that satisfy the clause c i in A. The second hyperpath has an underlying path of the second type, it leads via x 1 , x 2 , . . . , x n+1 , and from x j to x j+1 it uses the vertices containing only the literals that are not satisfied by the assignment A. Thus, the second hyperpath uses only those lit-in-clause hyperedges that correspond to pairs containing literals that are not satisfied by A. This implies that the two constructed st-hyperpaths are hyperedge-disjoint.

Let P and Q be two hyperedge-disjoint st-hyperpaths of H. Let P have an underlying path p of the first type and Q have an underlying path q of the second type. We can construct a satisfying assignment for I by setting to TRUE the literals opposite to those that occur in the vertices on q. Then, the hyperpath P describes how the clauses of I are satisfied by this assignment.

On the Minimum st-Hypercut

Quite naturally, we define an st-hypercut of a sequence hypergraph H as a set C of hyperedges whose removal from H leaves s and t disconnected.

Definition 5 (st-Hypercut). Let s and t be two vertices of a sequence hypergraph

H = (V, E). A set of hyperedges X ⊆ E is an st-hypercut if the subhypergraph H = (V, E \ X)
does not contain any hyperpath from s to t. The size of an st-hypercut X is |X|, i.e., the number of hyperedges in X.

For directed (multi)graphs, the famous MaxFlow-MinCut Duality Theorem [START_REF] Elias | A note on the maximum flow through a network[END_REF] states that the size of a maximum st-flow is equal to the size of a minimum st-cut. In sequence hypergraphs, this duality does not hold, not even in acyclic sequence hypergraphs as Figure 5 shows. But, of course, the size of any st-hyperflow is a lower bound on the size of any st-hypercut. We showed the maximum st-hyperflow problem to be APX-hard even in acyclic sequence hypergraphs (see Theorem 3). It turns out that also the minimum st-hypercut problem in acyclic sequence hypergraphs is APX-hard. Theorem 4. Minimum st-hypercut in acyclic sequence hypergraphs is NP-hard to approximate within a factor of 2 -ε under U GC, or within a factor 7/6 -ε unless P = NP.

Proof. We construct an approximation-preserving reduction from the vertex cover problem, which has the claimed inapproximability [START_REF] Khot | Vertex cover might be hard to approximate to within 2-epsilon[END_REF]. An instance of the vertex cover problem is an undirected graph I = (U, F ), with the vertex set U = {u 1 , . . . , u n } and the edge set F = {f 1 , . . . , f m }. The goal is to find a

s t v (1,1) v (1,2) v (1,3) u 1 p 1 v (2,1) v (2,2) v (2,3) u 2 p 2 v (3,1) v (3,2) v (3,3) u 3 p 3 v (4,1) v (4,2) v (4,3) u 4 p 4 f 1 f 2 f 3 f 4
Fig. 6. Minimum st-hypercut is at least as hard as minimum vertex cover.

smallest subset U ⊆ U such that U contains at least one vertex from each edge f ∈ F .

To construct from the instance I an instance I of the minimum st-hypercut problem in acyclic sequence hypergraphs, we fix an order of the vertices and edges of I as follows. Let U O = (u 1 , . . . , u n ) be an arbitrary order on the vertices of U . From every edge in F we create an ordered edge, where the vertices of the edge are ordered naturally according to U O . Let F denote the set of the created ordered edges, and let F O be the edges F ordered lexicographically according to U O . We construct the sequence hypergraph H = (V, E) of I as follows (cf. Figure 6 along with the construction). The set of vertices V consists of 3m + 2 vertices: a source vertex s, a target vertex t, and for each edge f i ∈ F O , i = 1, . . . , m, there are three vertices v (i,1) , v (i,2) , and v (i,3) . The set of hyperedges E consists of 2m + n hyperedges. There are m source hyperedges of the form (s, v (i,1) ), each of them connects s to one vertex v (i,1) . There are m target hyperedges of the form (v (i,3) , t), each of them connects one vertex v (i,3) to t. And finally, there are n vertex hyperedges, each corresponding to one of the vertices in U , and is constructed as follows.

For a vertex u ∈ U of I, we describe the sequence of vertices in the corresponding vertex hyperedge E u iteratively. We start with an empty sequence. We consider the edges F O in order, and for each edge f i ∈ F O that contains u we prolong the sequence of E u as follows. If f i contains u as the first vertex, we append v (i,1) and v (i,2) to E u . Otherwise, f i contains u as the second vertex, and we append v (i,2) and v (i,3) to E u . Now consider the edges of the obtained hyperedge E u and let us distinguish two types. First, there are edges of the form (v (i,1) , v (i,2) ) and (v (i,2) , v (i,3) ) for some i, and second, there are edges of the form (v (i,2) , v (j,1) ), (v (i,3) , v (j,2) ), and (v (i,3) , v (j,1) ) for some i < j. Note that, due to the fact that the edges in F O are ordered lexicographically, all the edges of the vertex hyperedge E u take one of the forms described above. Also note that, due to the direct correspondence between the vertices in U and vertex hyperedges, each tuple (v (i,j) , v (i,j+1) ) is part of (i.e., an edge of) exactly one of the hyperedges.

Clearly, by the construction, the sequence hypergraph is acyclic, since the ordering

V O = (s, v (1,1) , v (1,2) , v (1,3) , . . . , v (m,1) , v (m,2) , v (m,3) , t) is a topological sorting of the underlying graph G.
Let us now observe that there always exists a minimum st-hypercut that does not contain any source or target hyperedges. Notice that in the underlying graph G of H, the only outgoing edge from v (i,1) leads to v (i,2) , for i = 1, . . . , m, and similarly, the only incoming edge to v (i,3) comes from v (i,2) . Since for each i, the tuple (v (i,j) , v (i,j+1) ) is an edge of exactly one hyperedge, every source hyperedge (s, v (i,1) ) in an st-hypercut C can be substituted by the vertex hyperedge containing the edge (v (i,1) , v (i,2) ); and every target hyperedge (v (i,3) , t) can be substituted by the vertex hyperedge containing the edge (v (i,2) , v (i,3) ); and the resulting set is an st-hypercut of size equal or smaller than C. Thus, there exists an optimal solution that contains only vertex hyperedges. Now observe that any minimum st-hypercut C consisting of vertex hyperedges only, must for each i = 1, . . . , m "hit" either the edge (v (i,1) , v (i,2) ) or (v (i,2) , v (i,3) ) (i.e., one of those two edges is an edge of some hyperedge in C). Otherwise, the underlying graph of (V, E \C) would contain an st-path p i = s, v (i,1) , v (i,2) , v (i,3) , t.

We show that the described construction gives us an approximation-preserving reduction: for an st-hypercut of size k, we can construct a solution for the vertex cover problem of the same size, and vice versa. Let S ⊆ H be an optimal solution to the instance I that contains only vertex hyperedges. Recall that there is a direct one-to-one mapping between the vertex hyperedges and the vertices U of the instance I. There is also a direct mapping between each triple (v (i,1) , v (i,2) , v (i,3) ) and an edge from F . Since the solution S hits one of the edges (v (i,1) , v (i,2) ) or (v (i,2) , v (i,3) ) for each i, we can use the mapping to construct a solution S ⊆ U to the instance I of the original minimum vertex cover problem, such that |S| = |S |. On the other hand, every solution to the original vertex cover instance can be mapped, using the same direct one-to-one mapping in the opposite direction, to an st-hypercut of H of the same size.

Sequence Hypergraphs with Hyperedges of Length ≤ 2

We have seen that some of the classic, polynomially solvable problems in (directed) graphs become APX-hard in sequence hypergraphs. Note that this often remains true even if all the hyperedges are of constant length. In particular, Theorem 1 states that the shortest st-hyperpath is hard to approximate even if all the hyperedges are of length at most 5; Figure 4 illustrates that the duality between minimum st-hypercut and maximum st-hyperflow breaks already with a single hyperedge of length 3; and Theorem 3 yields that the maximum st-hyperflow is hard to approximate even if all hyperedges are of length at most 3.

It is an interesting question to investigate the computational complexity of the problems for hyperedge lengths smaller than 5 or 3. We show that, if all the hyperedges of the given sequence hypergraph are of length at most 2, the shortest st-hyperpath, the minimum st-hypercut, and the maximum st-hyperflow can all be found in polynomial time. Proof. Consider a shortest st-hyperpath P in a given sequence hypergraph with hyperedges of length at most 2. Clearly, whenever both edges of a hyperedge are part of an underlying path of P , they must appear consecutively on it. Thus, all the edges of each hyperedge appear consecutively on any underlying path of P . Therefore, the length of the shortest st-hyperpath P is again the same as the minimum number of switches of P , and such a shortest st-hyperpath can be found in polynomial time (Proposition 1).

Theorem 6. The maximum st-hyperflow problem in sequence hypergraphs with hyperedges of length at most 2 can be solved in polynomial time.

Proof. Let H = (V, E) be a sequence hypergraph with hyperedges of length at most 2, and let s and t be two of its vertices. Then, using standard graph algorithms we can find a maximum st-flow f in the underlying directed multigraph G of H with edge capacities 1. Thus, the flow f of size |f | gives us a set of |f | edge-disjoint st-paths p 1 , . . . , p |f | in G (note that any directed cycle in f can be easily removed). We iteratively transform p 1 , . . . , p |f | into a set of st-paths such that all the edges of each hyperedge appear on only one of these paths. Let E = (u, v, w) be a hyperedge that lies on two different paths (see Figure 7), i.e., (u, v) ∈ p i and (v, w) ∈ p j , for some i, j ∈ [|f |]. Then, p i consists of an su-path, edge (u, v), and a vt-path. Similarly, p j consists of an sv-path, edge (v, w), and a wt-path. Since all these paths and edges are pairwise edge-disjoint, by setting p i to consist of the su-path, edge (u, v), edge (v, w), and the wt-path, and at the same time setting p j to consist of the sv-path, and the vt-path, we again obtain two edge-disjoint st-paths p i and p j . However, now the hyperedge E is present only on p i . At the same time, since each hyperedge is of length at most 2, all the edges of any hyperedge appear on any st-path consecutively, and any hyperedge that was present on only one of p i or p j is not affected by the above rerouting and still is present on one of the two paths only.

Thus, the rerouting decreased the number of hyperedges present on more paths, and after at most |E| iterations of this transformation we obtain |f | hyperedge-disjoint st-paths, which gives us an st-hyperflow of size |f |. It is easy to observe that the size of the hyperflow is bounded from above by the size of the flow in the underlying multigraph. Thus, we obtain a maximum st-hyperflow in H.

Theorem 7. The minimum st-hypercut problem in sequence hypergraphs with hyperedges of length at most 2 can be solved in polynomial time.

Proof. Let H = (V, E) be a sequence hypergraph with hyperedges of length at most 2, and let s and t be two of its vertices. As in proof of Theorem 6, we find a maximum st-flow f (of size |f |) in the underlying directed multigraph G of H and obtain a maximum st-hyperflow F in H of the same size, i.e., |F | = |f |. Since in directed multigraphs the size of the minimum cut equals the size of the maximum flow [START_REF] Elias | A note on the maximum flow through a network[END_REF], it follows that we can find |F | edges e 1 , . . . , e |F | of G that form a minimum cut of G. Observe that each of these edges corresponds to exactly one hyperedge. Thus, we obtain a set C of at most |F | hyperedges that forms an st-hypercut. Since the size of any st-hypercut is bounded from below by the size of the hyperflow, C is a minimum st-hypercut.

Note that we proved Theorem 7 by first constructing an st-hyperflow and then finding an st-hypercut of the same size. Since this is always possible, it follows that the equivalent of the MaxFlow-MinCut Duality Theorem holds in this setting with hyperedges of length at most 2.

Sequence Hypergraphs with Backward Hyperedges

We consider a special class of sequence hypergraphs where for every hyperedge, there is the exact same hyperedge, but oriented in the opposite direction.

Definition 6 (Backward Hyperedges). Let

E = (v 1 , v 2 , . . . , v k ) be a hy- peredge of a sequence hypergraph H = (V, E). We say that E is a backward hyperedge 1 of E if E = (v k , . . . , v 2 , v 1
). If for every E of E, there is exactly one backward hyperedge in E, we refer to H as sequence hypergraph with backward hyperedges.

Such a situation arises naturally in urban public transportation networks, for instance most of the tram lines of the city of Zurich have also a "backward" line (which has the exact same stops as the "forward" line, but goes in the opposite direction). We study the complexities of shortest st-hyperpath, minimum sthypercut, and maximum st-hyperflow under this setting.

We show that, in this setting, we can find a shortest st-hyperpath in polynomial time. On the other hand, we show that minimum st-hypercut and maximum st-hyperflow remain NP-hard, and we give a 2-approximation algorithm for the minimum st-hypercut. Also observe in Figure 8 that the equivalent of the MaxFlow-MinCut Duality Theorem does not hold in sequence hypergraphs with backward hyperedges. The positive results in this section are based on existing algorithms for standard hypergraphs, the negative results are obtained by a modification of the hardness proofs given in Sections 4 and 5.

Theorem 8. The shortest st-hyperpath problem in sequence hypergraphs with backward hyperedges can be solved in polynomial time. s t Fig. 8. Sequence hypergraph with backward hyperedges with minimum st-hypercut of size 4, and only three hyperedge-disjoint st-hyperpaths. For every displayed hyperedge, there is also a backward hyperedge, which is for simplicity omitted from the figure .   Proof. Let H = (V, E) be a sequence hypergraph with backward hyperedges, and let s and t be two vertices of H. We construct a (standard) hypergraph H * = (V * = V, E * ) from H in such a way that for each sequence hyperedge E of E, E * contains a (non-oriented) hyperedge E * that corresponds to the set of vertices of E. Note that E and its backward hyperedge E consist of the same set of vertices, thus the corresponding E * and E * are the same. A shortest st-hyperpath2 P * in the (standard) hypergraph H * can be found in polynomial time. Observe that the size of P * gives us a lower bound |P * | on the length of the shortest path in the sequence hypergraph H.

In fact, we can construct from P * an st-hyperpath in H of size |P * | as follows. Let us fix p * to be an underlying path of P * . Let (s = v 1 , v 2 , . . . , v |P * |+1 = t) be a sequence of vertices, subsequence of p * , such that for each i = 1, . . . , |P * |, there is a hyperedge E * in P * that contains both v i and v i+1 , v i is the first vertex of E * seen on p * , and v i+1 is the last vertex of E * seen on p * . Since every hyperedge E * of E * corresponds to the set of vertices of some hyperedge E of E, there is a sequence of sequence hyperedges (E 1 , E 2 , . . . , E |P * | ), E i ∈ E, such that v i , v i+1 are vertices in E i . Since H is a sequence hypergraph with backward hyperedges, for every hyperedge E of E and a pair of vertices v i and v i+1 of E, there is a v i v i+1 -hyperpath in H of size 1, which consists of E or its backward hyperedge E . Therefore, there is an st-hyperpath of size |P * | in H.

Theorem 9. The maximum st-hyperflow problem in sequence hypergraphs with backward hyperedges is NP-hard.

Proof. We construct a reduction from the NP-complete 3-Sat problem [START_REF] Garey | Computers and intractability: a guide to the theory of NP-completeness[END_REF]. Let I be an instance of the 3-Sat problem, given as a set of m clauses C = {c 1 , . . . , c m } over a set X = {x 1 , . . . , x n } of Boolean variables.

From I we construct a sequence hypergraph H = (V, E) as follows (cf. Figure 9 along with the construction). The construction is very similar to that in the proof of Theorem 3, so we highlight the changes in bold. One major change is that now for every hyperedge there is a backward hyperedge. For simplicity, we divide all the sequence hyperedges into pairs of mutually backward sequence hyperedges, and we refer to one sequence hyperedge of each pair as forward hyperedge (and to the other as its backward hyperedge). For simplicity of the construction, we

c 1 c 1 c 2 c 2 c 3 c 3 c 4 x 1 + - x 1 x 2 + - x 2 x 3 + - x 3 x 4 + - x 4 x 5 s t x 1 c 1 x 2 c 1 x 3 c 1 x 1 c 2 x 2 c 2 x 1 c 3 x 3 c 3 x 4 c 2 ux 1 c 1 vx 1 c 1 ux 2 c 1 vx 2 c 1 ux 3 c 1 vx 3 c 1 ux 1 c 2 vx 1 c 2 ux 2 c 2 vx 2 c 2 ux 4 c 2 vx 4 c 2 ux 1 c 3 vx 1 c 3 ux 3 c 3 vx 3 c 3 Φ = ( x 1 ∨ x 2 ∨ x 3 ) ∧ ( x 1 ∨ x 2 ∨ x 4 ) ∧ ( x 1 ∨ x 3 )
Fig. 9. Maximum st-hyperflow in sequence hypergraphs with backward hyperedges is NP-hard.

describe explicitly only the forward hyperedges, and each of them implicitly defines a backward hyperedge.

Let |I| be the size of I (i.e., |I| = ci∈C |c i |). The set of vertices V consists of 2+(m+1)+(n+1)+3|I| vertices: a source vertex s and a target vertex t; a vertex c i for each clause c i ∈ C and a dummy vertex c m+1 ; a vertex x j for each variable x j ∈ X and a dummy vertex x n+1 ; and finally three vertices x j c i , ux j c i , and vx j c i for each pair (x j , c i ) such that x j ∈ c i , and similarly, x j c i , ux j c i , and vx j c i for each x j ∈ c i . Let us fix an arbitrary order C O of the clauses in C. The set of hyperedges E contains 4 + 2n + 3|I| forward hyperedges (plus the same amount of the corresponding backward hyperedges that we do not specify explicitly). There are 2 + |I| source hyperedges: (s, c 1 ) and (s, x 1 ); for each pair (x j , c i ), x j ∈ c i , there is (s, ux j c i ), and for each x j ∈ c i , there is (s, ux j c i ). There are 2 + |I| target hyperedges: (c m+1 , t) and (x n+1 , t); for each pair (x j , c i ), x j ∈ c i , there is (vx j c i , t), and for each x j ∈ c i , there is (vx j c i , t). There are 2n auxiliary hyperedges (x i , x i c k ) and (x i , x i c k ) for i = 1, . . . , n, where c k or c k is always the first clause (with respect to C O ) containing x i or x i , respectively. In case there is no clause containing x i (or x i ), the corresponding auxiliary hyperedge is (x i , x i+1 ).

Finally, there are |I| lit-in-clause hyperedges as follows. For each appearance of a variable x j in a clause c i as a positive literal there is one lit-in-clause hyperedge (vx j c i , ux j c i ,c i , c i+1 , x j c i , x j c k ), where c k is the next clause (with respect to C O ) after c i where x j appears as a positive literal (in case there is no such c k , the hyperedge ends in x j+1 instead). Similarly, if x j is in c i as a negative literal, there is one lit-in-clause hyperedge (vx j c i , ux j c i ,c i , c i+1 , x j c i , x j c k ), where c k is the next clause containing the negative literal x j (or the hyperedge ends in x j+1 ).

We show that the formula I is satisfiable if and only if the sequence hypergraph H contains 2+|I| hyperedge-disjoint st-hyperpaths. Since there are exactly 2+|I| source hyperedges, and no other hyperedge (including backward hyperedges) originates from the source vertex s, all these source hyperedges have to be used to get 2 + |I| hyperedge-disjoint st-hyperpaths. Similarly, all the target hyperedges have to be used. But then, each of the |I| vertices vx j c i or vx j c i has to be on one of the underlying st-paths. However, vx j c i can only be reached (unless passing via t) from ux j c i using a backward hyperedge of a lit-in-clause hyperedge. Similarly, vx j c i can only be reached from ux j c i using a backward hyperedge of a lit-in-clause hyperedge. This all implies that there can be 2 + |I| hyperedgedisjoint st-hyperpaths only if |I| of them are composed in one of the two following ways: a source hyperedge (s, ux j c i ), a backward hyperedge of some lit-in-clause hyperedge to get from ux j c i to vx j c i , and a target hyperedge (vx j c i , t); or a source hyperedge (s, ux j c i ), a lit-in-clause backward hyperedge to get from ux j c i to vx j c i , and a target hyperedge (vx j c i , t). Thus, the backward hyperedges of all |I| lit-in-clause hyperedges are used and cannot appear in the remaining st-hyperpaths. Also note that all other backward hyperedges are useless to reach t from s, since they lead only backwards. This implies a situation equivalent to that in the proof of Theorem 3. That is, the formula I is satisfiable if and only if the sequence hypergraph H contains 2 hyperedge-disjoint st-hyperpaths, when considering forward hyperedges only, without the |I| source and |I| target hyperedges already used above. Then, there are 3 possible types of st-paths in the underlying graph of H: the first one leads through all the vertices c 1 , c 2 , . . . , c m+1 in this order; the second one leads through all the vertices x 1 , x 2 , . . . , x m+1 in this order and between x j and x j+1 it goes either through all the x j c * vertices or through all the x j c * vertices (again, * is used here as a wildcart); and the third possible st-path starts the same as the first option and ends as the second one. Based on this observation, notice that there can be at most 2 hyperedge-disjoint st-hyperpaths: necessarily, one of them has an underlying path of the first type, while the other one has an underlying path of the second type.

From a satisfying assignment A of I we can construct the two disjoint sthyperpaths as follows. One hyperpath leads from s to t via the vertices c 1 , c 2 , . . ., c m+1 , and to move from c i to c i+1 it uses a lit-in-clause hyperedge that corresponds to a pair (l, c i ) such that l is one of the literals that satisfy the clause c i in A.

The second hyperpath has an underlying path of the second type, it leads via x 1 , x 2 , . . . , x n+1 , and from x j to x j+1 it uses the vertices containing only the literals that are not satisfied by the assignment A. Thus, the second hyperpath uses only those lit-in-clause hyperedges that correspond to pairs containing literals that are not satisfied by A. This implies that the two constructed st-hyperpaths are hyperedge-disjoint.

Let P and Q be two hyperedge-disjoint st-hyperpaths of H, considering only the forward hyperedges, without the source hyperedges that lead to vertices ux * c * or u x * c * . Let P have an underlying path p of the first type and Q has an underlying path q of the second type. We can construct a satisfying assignment for I by setting to TRUE the literals opposite to those that occur in the vertices on q. Then, the hyperpath P suggests how the clauses of I are satisfied by this assignment.

Theorem 10. The minimum st-hypercut problem in sequence hypergraphs with backward hyperedges is NP-hard.

Proof. We construct a reduction from the NP-hard vertex cover problem. Let I be an instance of the vertex cover problem, given as an undirected graph I = (U, F ), with the vertex set U = {u 1 , . . . , u n }, and the edge set F = {f 1 , . . . , f m }.

To construct from I an instance I of the minimum st-hypercut problem in acyclic sequence hypergraphs, we fix an order of the vertices and edges of I as follows. Let U O = (u 1 , . . . , u n ) be an arbitrary order on the vertices of U . From every edge in F we create an ordered edge, where the vertices of the edge are ordered naturally according to U O . Let F denote the set of the created ordered edges, and let F O be the edges F ordered lexicographically according to U O .

We construct the sequence hypergraph H = (V, E) of I as follows (cf. Figure 10 along with the construction). The construction is very similar to that in the proof of Theorem 4, so we highlight the changes in bold. One major change is that now for every hyperedge there is a backward hyperedge. For simplicity, we divide all the sequence hyperedges into pairs of mutually backward sequence hyperedges, and we refer to one sequence hyperedge of each pair as forward hyperedge (and to the other as its backward hyperedge). For simplicity of the construction, we describe explicitly only the forward hyperedges, and each of them implicitly defines a backward hyperedge.

The set of vertices V consists of 3m + 2 + 2n vertices: a source vertex s and a target vertex t; for each edge f i ∈ F O , i = 1, . . . , m, there are three vertices v (i,1) , v (i,2) , and v (i,3) ; and finally, for each vertex u k ∈ U O , k = 1, . . . , n, there are two vertices a k and b k . The set of hyperedges E contains 2m + 3n forward hyperedges (plus the same amount of the corresponding backward hyperedges that we do not specify explicitly). There are m type-1 source hyperedges of the form (s, v (i,1) ), each of them connects s to one vertex v (i,1) , and there are n type-2 source hyperedges of the form (s, a k ), connecting s to a k , for k = 1, . . . , n. There are m type-1 target hyperedges of the form (v (i,3) , t), each of them connects one vertex v (i,3) to t, and there are n type-2 hyperedges of the form (b k , t), connecting b k to t, for k = 1, . . . , n. And finally, there are n vertex hyperedges, each corresponds to one of the vertices in U , that are constructed as follows.

For a vertex u k ∈ U of the graph I, we describe the sequence of vertices in the corresponding vertex hyperedge E u k iteratively. We start with a sequence containing E u k = b k . We consider the edges F O in order, and for each edge f i ∈ F O that contains u k we prolong the sequence of E u k as follows. If f i contains u k as the first vertex, we append v (i,1) and v (i,2) to E u k . Otherwise, f i contains u k as the second vertex, and we append v (i,2) and v (i,3) to E u k . Once all edges containing u k have been considered, we append a k to E u k . We denote by E u k the corresponding backward vertex hyperedge. Now consider the edges of the obtained hyperedge E u k and note the form they can have. The first edge is an edge (b k , v (i,j) ) for some j ∈ {1, 2} and some i ∈ [m]. The last edge is an edge (v (i,j) , a k ) for some j ∈ {2, 3} and some i ∈ [m]. The remaining edges are of two main types: There are edges of the form (v (i,1) , v (i,2) ) and (v (i,2) , v (i,3) ) for some i ∈ [m], and there are edges of the form (v (i,2) , v (j,1) ), (v (i,3) , v (j,2) ), and (v (i,3) , v (j,1) ) for some i < j, i, j ∈ [m]. Note that, due to the fact that the edges in F O are ordered lexicographically, all the edges of the vertex hyperedge E u k take one of the forms described above. Also note that, due to the direct correspondence between the vertices in U and vertex hyperedges, each tuple (v (i,j) , v (i,j+1) ) is part of (i.e., an edge of) exactly one of the hyperedges.

s t v (1,1) v (1,2) v (1,3) u 1 p 1 v (2,1) v (2,2) v (2,3) u 2 p 2 v (3,1) v (3,2) v (3,3) u 3 p 3 v (4,1) v (4,2) v (4,3) u 4 p 4 q 4 q 3 q 2 q 1 f 1 f 2 f 3 f 4
Let us now observe that there always exists a minimum st-hypercut that does not contain any type-2 source hyperedges or type-2 target hyperedges. Clearly, none of the backward type-2 source hyperedges or type-2 target hyperedges are in a minimum st-hypercut, since each consists of a single edge that either leads to s or from t. Notice that in the underlying graph G of H, for each k = 1, . . . , n, there is only one outgoing edge from a k (other than to s), and this edge belongs only to the backward vertex hyperedge E u k . Similarly, there is only one incoming edge from b k (other than from t) and this edge belongs only to the backward vertex hyperedge E u k . Consequently, every forward type-2 source hyperedge or type-2 target hyperedge in an st-hypercut C can be substituted for a backward vertex hyperedge, and the resulting set is an st-hypercut of size equal to or smaller than C. Thus, there exists a minimum st-hypercut C which does not contain type-2 source or type-2 target hyperedges. Now observe that such an st-hypercut C has to contain all the backward vertex hyperedges, as otherwise, for some k, the underlying graph of (V, E \ C) would contain an st-path using the type-2 source hyperedge from s to a k , the backward vertex hyperedge E u k from a k to b k , and the type-2 target hyperedge from b k to t. Now we show that each type-1 source or type-1 target hyperedge in C can be substituted by a forward vertex hyperedge. Let B be the set of all backward vertex hyperedges. Notice that in the underlying graph of (V, E \ B), the only outgoing edges from v (i,1) lead to s or v (i,2) , for i = 1, . . . , m; and similarly, the only incoming edges to v (i,3) come from t or v (i,2) . (And clearly, the hyperedges (v (i,1) , s) and (t, v (i,3) ) are not part of any st-hyperpath.) Since for each i, the tuple (v (i,j) , v (i,j+1) ) is an edge of exactly one hyperedge, every type-1 source hyperedge (s, v (i,1) ) in an st-hypercut C can be substituted by the forward vertex hyperedge containing the edge (v (i,1) , v (i,2) ); and every type-1 target hyperedge (v (i,3) , t) can be substituted for the forward vertex hyperedge containing the edge (v (i,2) , v (i,3) ), and the resulting set is an st-hypercut of size equal to or smaller than C. Thus, there exists an optimum solution that contains only vertex hyperedges, and in particular, it contains all the backward vertex hyperedges. Now observe that any minimum st-hypercut C consisting of vertex hyperedges only must for each i = 1, . . . , m "hit" either the edge (v (i,1) , v (i,2) ) or (v (i,2) , v (i,3) ) (i.e., one of those two edges is an edge of some hyperedge in C). Otherwise, the underlying graph of (V, E \C) would contain an st-path p i = s, v (i,1) , v (i,2) , v (i,3) , t.

Let S ⊆ H be an optimum solution to the instance I that contains only vertex hyperedges. Since S contains all n backward vertex hyperedges, it contains |S |-n forward vertex hyperedges. Recall that there is a direct one-to-one mapping between the forward vertex hyperedges and the vertices U of the instance I. There is also a direct mapping between each triple (v (i,1) , v (i,2) , v (i,3) ) and an edge from F . Since the solution S hits one of the edges (v (i,1) , v (i,2) ) or (v (i,2) , v (i,3) ) for each i, we can use the mapping to construct a solution S ⊆ U to the instance I of the original minimum vertex cover problem, such that |S| = |S | -n. On the other hand, every solution of size k to the original vertex cover instance can be mapped, using the same direct one-to-one mapping in the opposite direction, to an st-hypercut of H of size k + n. Therefore, an optimum solution for I gives us an optimum solution for I. Theorem 11. The minimum st-hypercut problem in sequence hypergraphs with backward hyperedges can be 2-approximated.

s v 1 v 2 v 3 v 4 v 5 v 6 X = {x 1 , x 2 , . . . , x 6 } S 1 = {x 1 , x 2 , x 5 } S 2 = {x 1 , x 3 , x 4 } S 3 = {x 2 , x 3 , x 6 } S 4 = {x 3 ,

On Other Algorithmic Problems

We briefly consider some other standard graph algorithmic problems in sequence hypergraphs.

Definition 7 (Rooted Spanning Hypergraph)

. Let H = (V, E) be a sequence hypergraph. An s-rooted spanning hypergraph T is a subset of E such that for every v ∈ V, T is an sv-hyperpath. The size of T is |T |. Theorem 12. Finding a minimum s-rooted spanning hypergraph in acyclic sequence hypergraphs is NP-hard to approximate within a factor of (1 -ε) ln n, unless P = NP.

Proof. We construct an approximation-preserving reduction from the set cover problem, which has the claimed inapproximability [START_REF] Dinur | Analytical Approach to Parallel Repetition[END_REF]. Let I = (X, S) be an instance of the set cover problem, given by a ground set X = {x 1 , . . . , x n }, and a family of its subsets S = {S 1 , . . . , S m }.

We construct from I an instance I of the minimum s-rooted spanning hypergraph problem in sequence hypergraphs (see Figure 11 for an example). Let H = (V, E) be the following sequence hypergraph. The set of vertices V = {s, v 1 , . . . , v n } contains one vertex v i for each x i ∈ X, and a source vertex s. Let V O be an arbitrary fixed order on the vertices V. There are m hyperedges in E = {E 1 , . . . , E m }, one for each set in S. For a set S i ∈ S, let us take the vertices that correspond to the elements in S i and order them according to V O to obtain (v i1 , v i2 , . . . , v ir ). Then the sequence of the hyperedge E i corresponding to S i is simply (s, v i1 , v i2 , . . . , v ir ). The constructed sequence hypergraph is acyclic, as all the edges of its hyperedges agree with V O .

It remains to show that from a minimum s-rooted spanning hypergraph T for I a minimum set cover for I of the same size can be constructed. By definition, T is the smallest subset of E that allows to reach from s any other vertex in V. Moreover, since H is acyclic and each hyperedge starts at s, for each vertex v ∈ V, it is enough to choose one of the hyperedges in E (containing v) to reach v from s. This, together with the one-to-one correspondence between the hyperedges in E and sets in S, provides us with a prescription for a minimum set cover for I of size |T |. On the other hand, we can map any solution of the original minimum set cover instance to a minimum s-rooted spanning hypergraph of the same size.

Definition 8 (Strongly Connected Component)

. Let H = (V, E) be a sequence hypergraph. We say that a set C ⊆ E forms a strongly connected component if for every two vertices u, v ∈ V , with V being all the vertices of V present in C, the set C contains a uv-hyperpath. We say that the vertices in V are covered by C. We show NP-hardness of variant a) by a reduction from the APX-hard set cover problem [START_REF] Dinur | Analytical Approach to Parallel Repetition[END_REF]. Let I = (X, S) be an instance of the set cover problem, given by a ground set X = {x 1 , . . . , x n }, and a family of its subsets S = {S 1 , . . . , S m }. From I we construct a sequence hypergraph H = (V, E) as follows (see Figure 12 for an example). The set of vertices V = {s, t, v 1 . . . , v n , u 1 . . . , u n } contains one vertex v i and one vertex u i for each x i ∈ X, a source vertex s, and a target vertex t. Let X O be an arbitrary fixed order on the elements of X. The set of sequence hyperedges E consists of m + n + 1 hyperedges. There are n element hyperedges: for each element x i in X (i-th element of X in the order X O ), there is a hyperedge (v i , u i , u i-1 ), the hyperedge (v 1 , u 1 , s) corresponding to x 1 ends at s instead. There is one target hyperedge (t, u n ). Finally, there are m set hyperedges, one for each set in S defined as follows. For every set S i ∈ S, we take the vertices from {v 1 , . . . , v n } that correspond to the elements in S i and order them according to X O to obtain (v i1 , v i2 , . . . , v ir ). Then the sequence of the hyperedge E i corresponding to S i is simply (s, v i1 , v i2 , . . . , v ir , t).

It remains to show that a minimum set cover for I can be constructed from a minimum non-empty set of sequence hyperedges of H that form a strongly connected component. Let O be such a non-empty set of hyperedges. First observe that if O contains any set hyperedge, then O must contain all the element hyperedges and the target hyperedge. This follows from the fact that if O contains a set hyperedge, then s and t are covered by O, and O must contain a ts-hyperpath, but the only ts-hyperpath clearly consists of all element hyperedges plus the target hyperedge. Clearly, if O contains an element hyperedge or a target hyperedge, then either some v i or t is covered by O, and thus O must contain a hyperpath that leads to v i or t, respectively. However, the only sequence hyperedges that can reach v i or t are the set hyperedges. Therefore, O always contains at least one set hyperedge and all the element hyperedges and the target hyperedge. However, this implies that all the vertices have to be covered by O, which, in particular, implies that O must contain an sv i -hyperpath for each v i . Therefore, O consists of all element hyperedges, the target hyperedge, and the smallest subset of the set hyperedges that allows to reach from s any vertex v i ∈ V. In other words, for each vertex v i ∈ V, O must contain a set hyperedge that can reach v i from s. This, together with the one-to-one correspondence between the set hyperedges in E and sets in S, provides us with a prescription for a minimum set cover for I of size |O| -n -1. On the other hand, using the same mapping in the opposite direction, we can map any solution of the original minimum set cover instance to a minimum non-empty set of sequence hyperedges of H that form a strongly connected component. Theorem 14. Given a sequence hypergraph H = (V, E), finding a maximum number of hyperedges that form a strongly connected component C so that a) C is any non-empty set, or b) all the vertices in V are covered by C, is polynomial-time solvable.

Proof. As discussed above, for a given set of hyperedges, we can decide in polynomial time whether it forms a strongly connected component or not. Thus, in particular, we can check whether the set E forms a strongly connected component. In case it does, variant b) is solved trivially by taking all the hyperedges in E. Otherwise, this variant has no solution, because there is no strongly connected component covering all vertices in V.

To solve variant a), we start with te set of all hyperedges E and during the process, we iteratively remove those hyperedges that cannot be part of a feasible solution. Iteratively, we find strongly connected components in the underlying graph induced by the current set of hyperedges and remove all the sequence hyperedges that occur in two or more components (as these cannot be a part of a single strongly connected component), and repeat. Once no more hyperedges can be removed, we reached a situation, where of the remaining hyperedges is in exactly one strongly connected component. Thus, the solution is defined by the component that contains the maximum number of hyperedges.

Fig. 1 .

 1 Fig. 1. A bus line (actually, the career path of the jubilarian) in a transportation network, and the corresponding hyperedge.

Fig. 2 .

 2 Fig. 2.In both figures, the green-dotted curve and the red solid curve depict two sequence hyperedges. a) The length of the st-hyperpath is 2, but the number of switches is 7. b) The st-hyperpath consists of two sequence hyperedges that also form a hypercycle.

Fig. 5 .

 5 Fig. 5. Acyclic sequence hypergraph with minimum st-hypercut of size 2, and no two hyperedge-disjoint st-hyperpaths.

Fig. 7 .Theorem 5 .

 75 Fig. 7. Transforming st-paths into hyperedge-disjoint st-hyperpaths.

1 Fig. 10 .

 110 Fig. 10. Minimum st-hypercut in sequence hypergraphs with backward hyperedges is NP-hard.

Theorem 13 .

 13 Clearly, we can decide in polynomial time whether a given set of hyperedges C forms a strongly connected component as follows. Consider the underlying graph G of H induced by the set of sequence hyperedges C and find a maximum strongly connected component there. If this component spans the whole G, then C is a strongly connected component in H. Given a sequence hypergraph H = (V, E), it is NP-hard to find a minimum number of hyperedges that form a strongly connected component C so that a) C is any non-empty set, or b) all the vertices in V are covered by C.Proof. Variant b) is clearly NP-hard by a reduction from the Hamiltonian cycle problem: Consider a standard directed graph G = (V, E) and view it as a sequence hypergraph, where each sequence hyperedge is just an edge of G. Then, by finding a strongly connected component that covers all the vertices of V and uses the minimum number of sequence hyperedges (i.e., normal edges) we can solve the Hamiltonian cycle problem in G (either the component consists of |V | edges or more).

6 X 1 = {x 1 , x 2 , x 5 }S 2 = {x 1 , x 3 , x 4 }S 3 = {x 2 , x 3 , x 6 }S 4 = {x 3 , x 4 , x 6 }S 5 = {x 4 , x 5 , x 6 }Fig. 12 .

 61125213432364346545612 Fig.12. For a given sequence hypergraph, it is NP-hard to find a minimum non-empty set of sequence hyperedges that forms a strongly connected component.

  x 4 , x 6 } S 5 = {x 4 , x 5 , x 6 } Fig. 11. Minimum s-rooted spanning hypergraph is at least as hard as the minimum set cover problem.Proof. Let H = (V, E) be a sequence hypergraph with backward hyperedges, and let s and t be two vertices of H. Note that we can partition E into |E|/2 pairs of hyperedges (each pair contains a hyperedge and its backward hyperedge). We construct a (standard) hypergraph H * = (V * = V, E * ) from H in such a way that for each pair of mutually backward sequence hyperedges E and E of E, E * contains exactly one (non-oriented) hyperedge E * that corresponds to the set of vertices of E (and thus also E ). Note that E * may contain multiple hyperedges corresponding to the same set of vertices, and we get that E * contains exactly |E|/2 hyperedges.Next, we find a minimum st-hypercut X * in H * (this can be done in polynomial time by a transformation of H * into a directed graph and solving a maximum flow problem in it). Clearly, |X * | is a lower bound on the size of a minimum st-hypercut in H. Recall that every hyperedge in X * corresponds to 2 sequence hyperedges in H, thus, by removing all sequence hyperedges corresponding to hyperedges in X * , we obtain an st-hypercut in H of size 2 |X

* |.

Hassin et al.[START_REF] Hassin | Approximation algorithms and hardness results for labeled connectivity problems[END_REF] give a log(n)-approximation algorithm for the minimum label spanning tree problem and a √ n-approximation algorithm for the minimum label path problem, where n is the number of vertices of the input colored graph. Zhang et al.[START_REF] Zhang | Approximation and hardness results for label cut and related problems[END_REF] give a √ m-approximation algorithm for the minimum label cut problem, where m is the number of edges of the input colored graph. Fellows et al.[START_REF] Fellows | The parameterized complexity of some minimum label problems[END_REF] study the parameterized complexity of minimum label problems. Coudert et al.[START_REF] Coudert | Shared risk resource group complexity and approximability issues[END_REF][START_REF] Coudert | Combinatorial optimization in networks with Shared Risk Link Groups[END_REF] consider special cases when the span is 1, i.e., each color forms a connected component; or when the graph has a star property, i.e., the edges of every color are adjacent to one vertex.Note that since most of these results consider undirected labeled graphs, they provide almost no implications on the complexity of similar problems in the setting of sequence hypergraphs. In our setting, not only we work with directed labeled graphs, but we also require edges of each color to form a directed path, which implies a very specific structure that, to the best of our knowledge, has not been considered in the setting of labeled graphs.On the other hand, we are not the first to define hypergraphs with hyperedges specified as sequences of vertices. However, we are not aware of any work that would consider and explore this type of hypergraphs from an algorithmic graph theory point of view. In fact, mostly, these hypergraphs are taken merely as a tool, convenient to capture certain relations, but they are not studied further. We shortly list a few articles where sequence hypergraphs appeared, but we do not give details, since there is very little relation to our area of study. Berry et al.[START_REF] Berry | Graph drawing and manipulation with LINK[END_REF] introduce and describe the basic architecture of a software tool for (hyper)graph drawing. Wachman et al.[START_REF] Wachman | Learning from interpretations: a rooted kernel for ordered hypergraphs[END_REF] present a kernel for learning from ordered hypergraphs, a formalization that captures relational data as used in Inductive Logic Programming. Erdős et al.[START_REF] Erdős | Intersecting Sperner families and their convex hulls[END_REF] study Sperner-families and as an

Note, if E is a backward hyperedge of E, also E is a backward hyperedge of E .

An st-hyperpath P * and its underlying path are defined as in sequence hypergraphs.


Abderrahim Okba
email: aokba@laas.fr

Alexandru Takacs
email: atakacs@laas.fr

Hervé Aubert
email: aubert@laas.fr

900 MHz Miniaturized Rectenna

Keywords: energy harvesting, rectenna, wireless power transmission, flat dipole antenna

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Recently, Wireless Power Transfer (WPT) and electromagnetic Energy Harvesting (EH) have become an attractive solution for many industrial applications. The 3D indoor localization is one of these key applications. Nowadays, the 3D localization systems use batteryless tags and beacons in order to derive the position of tagged objects in a warehouse. Batteryless tags collect the power from the surrounding electromagnetic field generated by radiofrequency (RF) dedicated sources. Once enough power is harvested, tags wirelessly transmit their positions to beacons. The beacons communicate with each other through RF signals allowing the system to locate the objects. The RF sources generate the ambient electric field in the 868MHz -915MHz ISM frequency band. A compact rectenna composed of a Flat Dipole Antenna surrounded by a rectangular metallic ring and a rectifier with a single diode is used here to harvest the ambient electromagnetic energy in order to supply the batteryless tags.

In this paper, the broadband Flat Dipole Antenna is presented in section II while the rectifier is studied in section III. The compact rectenna is detailed in the section IV and obtained experimental results are finally discussed.

II. ANTENNA DESIGN AND RESULTS

A. Flat Dipole (FD) Antenna

Recently, broadband dipole antenna topologies have been reported for electromagnetic energy harvesting [START_REF] Kuhn | A Multi-Band Stacked RF Energy Harvester With RF-to-DC Efficiency Up to 84%[END_REF]- [START_REF] Assimonis | Sensitive and Efficient RF Harvesting Supply for Batteryless Backscatter Sensor Networks[END_REF]. The Flat Dipole shape is carried out by changing the geometry of a standard printed half-wavelength dipole. It is obtained by giving a round shape to the two constitutive quarterwavelength monopoles, as illustrated in Fig. 1. Contrary to the standard dipole where the current density flows along the dipole axis, the current in the shaped dipole flows by following different paths. As sketched in Fig. 1, the current density Js2 goes through a longer path than Js1. As a result, for the same physical length, the lower operating frequency of the antenna is smaller than one of the standard dipole and the antenna bandwidth is increased. In this work, the designed antenna covers the 868MHz-915MHz ISM frequency band. It was rigorously simulated by using the commercial software HFSS [START_REF]ANSYS HFSS[END_REF].

B. Miniaturization of the Flat Dipole Antrenna

The miniaturization of antennas can be performed from the use of dielectrics [START_REF] Volakis John | Small antennas: miniaturization techniques & applications[END_REF], magnetic materials [START_REF] Volakis John | Small antennas: miniaturization techniques & applications[END_REF], or metamaterials [START_REF] Ouedraogo | Miniaturization of Patch Antennas Using a Metamaterial-Inspired Technique[END_REF]. The modification of the antenna geometry may also be applied (see, e.g., by loading the radiating surface by slit [START_REF] Ghosh | Miniaturization of Slot Antennas Using Slit and Strip Loading[END_REF], by designing highly irregular antenna profiles [START_REF] Takacs | Height Reduction of the Axial-Mode Open-Ended Quadrifilar Helical Antenna[END_REF] or by using coupled ring resonators [8]). The miniaturization of the Flat Dipole Antenna (FDA) is performed here by adding a metallic rectangular ring around the antenna, as shown in Fig. 2. This allows reducing the physical length of the antenna of 25% while keeping the gain unchanged. Indeed, from appropriate design, the ring may favorably participate to the radiating field by increasing the antenna gain. Layout of the FDAs without rectangular metallic ring (purple) and with the rectangular ring (turquoise blue). The two antennas share the same lower frequency and gain.

The antenna is fabricated by using the lossy FR4 substrate (substrate thickness: 0.8mm, relative permittivity: 4.4 and loss tangent: 0.02). The size is of 10.5 x 6 cm². Fig. 3 displays the return loss with and without the rectangular ring. As expected, the ring allows increasing the antenna bandwidth and reducing the physical length of the antenna. The impedance matching is achieved between 840 MHz and 1.2 GHz. The radiation pattern is similar to one of the standard half-wavelength dipole with a maximum simulated gain of 2.8 dBi at 900 MHz (see Fig. 4). Simulated maximum gain of the FDA with the rectangular ring as a function of the frequency for θ=0° and φ=0°.

III. RECTIFIER DESIGN AND RESULTS

The rectifier was simulated using the commercial software ADS. It is composed by the HSMS2850 Schottky diode mounted in series configuration, a low-pass filter (100pF capacitor) used for the filtering of the fundamental and the harmonics and, an adjustable resistive load (0 -10kΩ potentiometer). The impedance matching circuit is composed of a shortcircuited stub bent, and a 30 nH inductance for matching the input impedance of the rectifier at 900 MHz. Fig. 5 displays the simulated return loss of the rectifier. A good input matching is obtained between 860 MHz and 910 MHz. The measured DC power is reported in Fig. 6 as a function of the frequency. The DC power of 12 µW is measured at 880 MHz with the 5 kΩ load (optimal load) and the input RF power of -15 dBm. An acceptable agreement is observed between simulation and measurement results.

The RF-to-DC conversion efficiency can be derived from the following expression:

𝜂(%) = 100 • 𝑃 𝐷𝐷 𝑃 𝑅𝑅 ( 1
)
where P DC is the measured DC power and P RF denotes the RF power injected at the rectifier input port. The measured and simulated efficiencies are reported in Fig. 7. The obtained maximum efficiency is of 38.6 % at 880 MHz. The experimental setup is shown in Fig. 9. The Anritsu MG3694B microwave generator is used for injecting the RF signal at the input of the transmitting (Tx) horn antenna (1-12 GHz) via a coaxial cable. The horn antenna illuminates the rectenna under test with a linearly-polarized E-field. An automatic acquisition routine is implemented in Labview software from National Instruments to speed-up the acquisition process. The harvested DC voltage is measured by using a standard DC multimeter. The DC power can be derived from the measured DC voltage as long as the load impedance is known. The measured insertion losses due to the coaxial cable are of 1dB in the entire frequency band of interest. where P DC is the harvested DC power, S is the incident RF power density, A eff is the antenna effective area, G R is the gain of the rectenna's radiating element, and λ is the free-space wavelength at the operating frequency. The RF power density (µW/cm2) can be determined from the E-field root mean square (rms) value E(V/m) on the antenna surface. This field is computed from the RF power Pt injected to the input of the transmitting horn antenna of gain G t located at the distance d from the rectenna. Consequently, the RF power density at the rectenna location is given by:

𝑆 = 𝐸 2 120. 𝜋 • 10 = 30. 𝑃 𝑡 . 𝐺 𝑡 𝑑 2 . 120. 𝜋 • 100 (3)
Fig. 10 shows the measured harvested DC power at the input port of the resistive load (RL = 5 kΩ) between 800MHz and 1 GHz for an incident power density ranging from 0.25 µW/cm² to 0.6 µW/cm². The DC power of 32.6 µW is measured at 900 MHz for the incident RF power density of 0.52 µW/cm². Measured DC power at the input port of the resistive load (RL=300Ω) as a function of the frequency

The optimal load impedance was also experimentally determined. Fig. 11 shows the DC harvested power as a function of the resistive load value at 900 MHz. It can be observed that the maximum DC power is obtained for R=5 kΩ. Rectenna efficiency (red dashed line) at 900 MHz and the harvested DC power (blue continuous line) as a function of illuminating RF power density

Using the load impedance of 10 kΩ, the harvested DC voltage exceeds 330mV (see Fig. 13) when the RF power density is at least of 0.25µW/cm² or equivalently, if the RF input power is higher than -14dBm at the rectifier input. Conse- Harvested DC voltage as a function of the incident RF power density with the load of 10kΩ

The Table I summarize key performances of the proposed FDA rectenna and of state-of-the-art rectennas operating at the same frequency. It can be observed that the FDA rectenna is the most compact while having a good efficiency for low incident RF power densities. Hence, it is a good candidate for achieving the best trade-off between compactness and efficiency. In this paper, a new rectenna based on a miniaturized Flat Dipole Antenna (0.05λ0²) is proposed. The miniaturization was performed by using a properly designed rectangular metallic ring. The measured efficiency of the fabricated rectenna exceeds 30% for a RF power density of 0.21 µW/cm² and reaches 47% for 2.1 µW /cm². Moreover, the rectenna may be used for powering-up a DC-DC boost converter for industrial applications.

Fig. 1 .

 1 Fig. 1. Sketch of two paths of the current density on the radiating surface of the Flat Dipole Antenna

Fig. 2 .

 2 Fig. 2.Layout of the FDAs without rectangular metallic ring (purple) and with the rectangular ring (turquoise blue). The two antennas share the same lower frequency and gain.

Fig. 3 .

 3 Fig. 3. Simulated return loss as a function of the frequency for the FDA without rectangular ring (red plot) and with rectangular ring (blue plot)

Fig. 5 .

 5 Fig. 5. Simulated return loss of the rectifier as a function of the frequency

Fig. 6 .

 6 Fig. 6.Measured (blue plot) and simulated (red plot) harvested DC powers as a function of the frequency.

Fig. 7 .

 7 Fig. 7. Measured (blue plot) and simulated (red plot) efficiencies of the rectifier as a function of the frequency

Fig. 9 .

 9 Fig. 9. Experimental setup used to characterize the rectennaThe efficiency of the rectenna can be derived from the following definition:

Fig. 10 .

 10 Fig. 10.Measured DC power at the input port of the resistive load (RL=300Ω) as a function of the frequency

Fig. 11 .

 11 Fig. 11.Measured DC power harvested by the rectenna as a function of the resistive load value at 900 MHz The conversion efficiency of the rectenna is derived from (2). Fig.12depicts the RF-to-DC conversion efficiency as a function of the RF power density illuminating the rectenna under test. The efficiency exceeds 30% for low input RF power densities and reaches 47% for a power density of 2.1 µW /cm².

Fig. 12 .

 12 Fig. 12.Rectenna efficiency (red dashed line) at 900 MHz and the harvested DC power (blue continuous line) as a function of illuminating RF power density

  proposed rectenna may power-up the BQ25504 DC-DC boost converter [9].

Fig. 13 .

 13 Fig.[START_REF] Palazzi | Novel Ultra-Lightweight Multiband Rectenna on Paper for RF Energy Harvesting in the Next Generation LTE Bands[END_REF].Harvested DC voltage as a function of the incident RF power density with the load of 10kΩ

TABLE I KEY

 I PERFORMANCES OF THE PROPOSED FD RECTENNA AND OF STATE-OF-THE-ART RECTENNAS OPERATING IN THE SAME FRE-QUENCY BAND

	Ref	Freq	PRF(dBm)	η(%)	Antenna
		(GHz)	S(µW/cm²)		surface
	[10]	0.915	1µW/cm²	37%	6 x 6 cm²
		2.45			0.33λ0²
	[11]	0.9	10dBm	33%	NR
	[12]	0.868	-20dBm	20%	NR
	[13]	0.9	0.1µW/cm²	16%	11 x 11 cm²
			1µW/cm²	40%	0.11λ0²
	In this	0.9	0.21µW/cm²	31%	11 x 6 cm²
	work		1µW/cm²	42%	0.05λ0²
	NR : Non Reported
			V. CONCLUSION


A Takacs
email: atakacs@laas.fr

A Okba #

H Aubert
email: aubert@laas.fr

Compact Planar Integrated Rectenna for Batteryless IoT Applications

Keywords: wireless power transmission, microwave energy harvesting, rectenna, internet of things. Rectenna Antenna Antenna

This paper addresses a new topology of compact rectennas in which the rectifier is integrated directly on the radiating surface. The rectenna is designed for wireless power transmission or microwave energy harvesting application in ISM 900 MHz band and exhibits a very good measured conversion efficiency (>25%) on a non-optimal load (10kΩ) for very low microwave power densities (>0.18 µW/cm 2 ). The measured DC voltage (>330 mV for microwave power density of at least 0.22 µW/cm 2 ) obtained from this planar rectenna is in the range of the cold turn-on/start-up voltage of modern commercial off-the-shelf DC-to-DC boost converters and power management units. The proposed rectenna is also very compact: its physical surface (10.5 x 6 cm 2 ) is only 5% of the square wavelength at the operating frequency (860 MHz).

I. INTRODUCTION

The rise of the Internet of Things (IoT) applications faces to a new challenge: how to power efficiently an enormous number of wireless sensors, intelligent tags, and devices? Nowadays, the use of a battery is almost a standard but, the topic of the self-powered/batteryless devices excites from longtime the scientific community and becomes recently an industrial reality for emerging innovative start-up and companies [1] [2]. One solution to implement self-powered and/or batteryless devices is to use a wireless power transmission approach: an intentionally microwave transmitter (energy shower) will energize at distance a rectenna module (rectifier + antenna). The energy shower should operate in the ISM bands and is then subject to regulations. ISM 868/915 MHz band provides a good trade-off in terms of free-space losses (fixing the maximum operating range of such a system) and wavelength (fixing the size of receiving antenna of the rectenna module). Many rectenna designs operating in the ISM 868/915 MHz band were proposed in the past with a focus mainly on the measured intrinsic performances (e.g., efficiency, harvested DC power, etc.) [START_REF] Kuhn | A Multi-Band Stacked RF Energy Harvester With RF-to-DC Efficiency Up to 84%[END_REF]- [START_REF] Assimonis | Sensitive and Efficient RF Harvesting Supply for Batteryless Backscatter Sensor Networks[END_REF]. From an industrial point of view, a successful rectenna design for IoT applications should be compact, low-profile and low-cost. The size of the rectenna module is determined mainly by the receiving antenna. Electronic devices should be also integrated with the antenna, e.g., the rectifier including its matching circuit, the Power Management Unit (PMU), the energy storage element, etc. But with the same goal in mind: keeping the overall structure as compact as possible.

This paper addresses the design in the ISM 868/915 MHz band of a compact rectenna using a miniaturized flat dipole antenna with the rectifier circuit directly integrated on the radiating surface of the antenna. To the authors' best knowledge, there are very few designs integrating the rectifier into radiating element at such low frequencies. In [START_REF] Popovic | Low-Power Far-Field Wireless Powering for Wireless Sensors[END_REF] the rectifier and the corresponding matching circuit are integrated in the ground plane of a patch antenna designed at 1.96 GHz but they are not integrated in the patch surface itself. Very recently, V. Palazzi et al. [START_REF] Palazzi | Novel Ultra-Lightweight Multiband Rectenna on Paper for RF Energy Harvesting in the Next Generation LTE Bands[END_REF] reported a compact rectenna using an annular slot with a wire-connected multibandrectifier positioned on the back-side of the antenna.

Our proposed innovative topology is described in Section II while the experimental results obtained with the manufactured prototype are presented and discussed in Section III.

II. RECTENNA TOPOLOGY AND DESIGN

A typical topology for an IoT compatible wireless sensor/tag is sketched in Fig. 1. From a practical point of view, if a compact planar structure is desired, the main design objective is to integrate all the functions/electronics (e.g., rectifier, PMU, energy storage, wireless sensor/tag, etc.) into the same Printed Circuit Board (PCB). The size of the overall structure is then mainly fixed by the size of the antenna operating at lowest frequency. As design requirements, we target a compact and fully planar rectenna with optimized performances in the ISM 868/915 MHz band. This rectenna should be able to power a standard DC-to-DC boost convertor and PMU (such as, e.g., BQ25504 device [8]) for incident electromagnetic (EM) power densities around 1 µW/cm 2 . Thus, the rectenna should provide an output DC voltage greater that the cold start-up voltage of such PMU (approximately 330 mV for the BQ25504 device) on a high impedance load (typically > 9kΩ, corresponding to the PMU input impedance) with the highest efficiency. The topology of the proposed 2D compact planar integrated rectenna is shown in Fig. 2 with the 3D rectenna topology. The rectenna consists of a flat dipole antenna (surrounded by a rectangular ring) integrated with a rectifier using a Schottky diode. The metal layer of the antenna is in (mechanical and electrical) contact with the bottom metal layer of the rectifier. The selected antennas in this frequency band are mainly based on dipole [3]- [START_REF] Assimonis | Sensitive and Efficient RF Harvesting Supply for Batteryless Backscatter Sensor Networks[END_REF] or annular slot topologies [START_REF] Palazzi | Novel Ultra-Lightweight Multiband Rectenna on Paper for RF Energy Harvesting in the Next Generation LTE Bands[END_REF]. The patch antennas are impractical in ISM 868/915 MHz band due to the large size. Flat dipole antennas topologies were selected in the past mainly for their broadband and/or multiband behavior [START_REF] Kuhn | A Multi-Band Stacked RF Energy Harvester With RF-to-DC Efficiency Up to 84%[END_REF]- [START_REF] Song | A high efficiency broadband rectenna for ambient wireless energy harvesting[END_REF]. We selected this topology here because of (i) its broadband behavior that allows operating efficiently in the ISM 868 MHz (Europe) and 915 MHz (USA/Japan) bands and, (ii) the large metal surface of the radiating element that allows integrating the rectifier and eventually other electronic devices. The flat dipole can be miniaturized (the size for operating at the targeted frequency is reduced compared with one of the standard flat dipoles) by adding an external ring/loop properly designed (see Fig. 2). In our case, the size was reduced by 25% (from to 14 x 6 cm 2 to 10.5 x 6 cm 2 ). The topology of the rectifier (with the dimensions of microstrip lines) and corresponding ADS simulation model are shown in Fig. 3. Fig. 3.

Rectifier topology and associated ADS simulation model

The rectifier is composed of a series HSMS2850 diode from Avago, a shunt capacitor (100pF) and a resistive load (10kΩ). This rectifier was previously designed, fabricated and characterized in our Laboratory in the framework of a research project with UWINLOC company [2]. An impedance matching circuit combining a short-circuited bend stub with a 30 nH inductance (Coilcraft) was used in order to match the impedance of the rectifier at 900 MHz. The rectifier was fabricated on Ro5870 substrate (thickness: 0.787 mm, relative permittivity: 2.3, dielectric loss tangent: 0.0012) and optimized to operate efficiently for low electromagnetic input power (less than -15 dBm).

III. EXPERIMENTAL AND SIMULATION RESULTS

The experimental setup positioned in an anechoic chamber (to prevent any interferences or undesirable multipath effects) shown in Fig. 4 was used to characterize the rectenna. A microwave signal generated from the Anritsu MG3694B generator is injected at the input of a transmitting (Tx) horn antenna through a coaxial cable. The horn antenna illuminates the rectenna under test, positioned in the far-field region of the Tx antenna, with a linearly-polarized E-field. An automatic acquisition routine is implemented in Labview software from National Instruments to speed-up the acquisition process. The harvested DC voltage is then measured by using a DC multimeter. The DC power can be derived from the measured DC voltage as long as the load is known. The efficiency η (in %) of the rectenna can be computed by using the following expression:

𝜂𝜂 = 𝑃𝑃 𝐷𝐷𝐷𝐷 𝑃𝑃 𝑅𝑅𝑅𝑅 • 100 = 𝑃𝑃 𝐷𝐷𝐷𝐷 𝑆𝑆 • 𝐴𝐴 𝑒𝑒𝑒𝑒𝑒𝑒 • 100 = 4 • 𝜋𝜋 • 𝑃𝑃 𝐷𝐷𝐷𝐷 𝑆𝑆 • 𝐺𝐺 𝑅𝑅 • 𝜆𝜆² • 100 (1)
where 𝑃𝑃 𝐷𝐷𝐷𝐷 is the harvested DC power, 𝑆𝑆 is the incident electromagnetic power density, 𝐴𝐴 𝑒𝑒𝑒𝑒𝑒𝑒 is the antenna effective area, 𝐺𝐺 𝑅𝑅 is the gain of the (rectenna's) antenna and 𝜆𝜆 is the free-space wavelength of the illuminating electromagnetic wave at the operating frequency. The electromagnetic power density S can be computed as a function of the E-field effective value 𝐸𝐸 (V/m) on the antenna surface. This value is derived from microwave power P t injected to the input port of the transmitting horn antenna (gain 𝐺𝐺 𝑡𝑡 ) positioned at a distance 𝑑𝑑 from the rectenna, as follows: The flat round antenna was fabricated on a low-cost FR4 substrate (substrate thickness: 0.8mm, relative permittivity: 4.4, dielectric loss tangent: 0.02). As shown in Fig. 5(a), the simulated (HFSS) -10 dB bandwidth of the antenna is between 845 MHz and 1.25 GHz and consequently, covers the ISM 868/915 MHz bands. For comparison purposes the reflection coefficient at the antenna input with and without the rectangular ring are depicted in Fig. 5(a).

𝑆𝑆 = 𝐸𝐸 2 120 • 𝜋𝜋 = 30 • 𝑃𝑃 𝑡𝑡 • 𝐺𝐺 𝑡𝑡 𝑑𝑑 2 • 120 • 𝜋𝜋 (2)
We can observe that the ring increases the bandwidth and allows reducing the size of the antenna. Electromagnetic simulations were performed in to optimize the rectangular ring. The ring perimeter (33 cm) and the distance between the ring and flat dipole antenna were adjusted in order to: (i) minimize the lowest operating frequency and (ii) increase the frequency bandwidth. The radiation pattern is close to one of the half-wavelength dipole with a simulated gain of 2.2 dBi in the -10 dB bandwidth (845 MHz-1.25 GHz). A prototype composed by a flat dipole antenna (enclosed by a rectangular metallic ring) and a compact printed taper were measured. The experimental results reported in Fig. 5(b) validate the frequency bandwidth predicted by the electromagnetic simulations.

The fabricated rectenna (see Fig. 2 d) was characterized by using the experimental setup shown in Fig. 4. The measured DC output voltage delivered by the manufactured rectenna on a non-optimal load of 10 kΩ is reported in Fig. 6. The maximum DC voltage (471 mV) is obtained at 860 MHz for an incident E-field E=1.28 V/m (0.44 µW/cm 2 ). At 868 MHz, the DC voltage is about 450 mV (0.44 µW/cm 2 ). Measured harvested DC voltage (V_DC) for the manufactured rectenna (incident E-field: 1.28 V/m, load: 10 kΩ) as a function of frequency.

The measured DC voltage and efficiency computed by using eq. (1) are given in Fig. 7 as a function of the incident E-field amplitude. A maximum efficiency of 37% (DC voltage: 1.13 V and DC power: 130µW) is obtained for E=2.88 V/m (2.2 µW/cm 2 ). As compared with the 3D rectenna [START_REF] Takacs | 900 MHz Miniaturized Rectenna[END_REF] shown in Fig. 2(a) the 2D rectenna exhibits a little bit lower efficiency, but it is more compact, planar and compatible with a multilayer fabrication process. A comparison with the recent state-of-art rectennas operating in the same frequency band is reported in Table 1. We selected only designs that use planar antennas and papers that reports experimental results for low-level of incident microwave power density. The state-of-art performances are reported as a function of the estimated microwave power on the rectifier input PRF or as a function of the incident microwave power density S. The size of the antennas/rectennas are reported in cm 2 as function of square wavelength ( 𝜆𝜆² ) allowing thus a fair comparison between designs operating at different frequencies. As reported in Table 1 the state-of-art designs use: (i) 3D topologies (the rectifier is interconnected with the antenna in a 3D manner as reported in [START_REF] Kuhn | A Multi-Band Stacked RF Energy Harvester With RF-to-DC Efficiency Up to 84%[END_REF]- [START_REF] Song | A high efficiency broadband rectenna for ambient wireless energy harvesting[END_REF]), (ii) planar but inline (IL) design that typically conducts to a 'large-size' design (e.g. [START_REF] Assimonis | Sensitive and Efficient RF Harvesting Supply for Batteryless Backscatter Sensor Networks[END_REF]) (iii) planar designs where the rectifier is integrated in the radiating element (this work) or connected by wire and positioned on the back-side of the antenna [START_REF] Palazzi | Novel Ultra-Lightweight Multiband Rectenna on Paper for RF Energy Harvesting in the Next Generation LTE Bands[END_REF] that lead to a more compact designs.

Table 1. Comparison with state-of-the-art designs.

NR : not reported in the paper * : rectifier connected to the antenna in an orthogonal/3D manner ** : rectifier connected to the antenna by an In Line (planar) connection *** a wire-connected multiband-rectifier is positioned on the back-side of the antenna It can be observed from Table 1 that the energy harvesting performances of the proposed rectenna are in the state-of-theart, but with a more compact structure: the antenna/rectenna surface is of 10.5 x 6 cm², that is, only 0.05𝜆𝜆² at 860 MHz. We note also that the efficiencies were measured for optimal loads while in this work, the load is non-optimal. As a matter of fact, the selected (non optimal) load of 10kΩ allows: (i) to maximize the DC output voltage required for the cold startup/wake-up of a commercial off-the-shelf DC-to-DC boost converter and, (ii) to simulate the input impedance of the same DC-to-DC boost converter. There is room on our antenna surface to integrate more electronic devices (the metal layer of flat dipole antenna is quite large) in order to obtain a miniaturized autonomous wireless sensor/tag. Moreover, depending on the targeted market, the overall structure can be manufactured either on a multilayer low cost (e.g., FR4) or on low loss (e.g., Ro5870) substrate.

IV. CONCLUSION An innovative compact rectenna (0.05λ² at 860 MHz) was proposed. It consists of a miniaturized flat dipole antenna with a rectifier which was optimized to operate at low microwave power densities. The rectifier is directly integrated into the surface of the radiating element. The large size of the metal layer of the flat dipole is very convenient for the eventual integration of additional electronic devices. A maximum efficiency of 37% is measured at 860 MHz for the manufactured rectenna with an illuminated electromagnetic power density of 2.2 µW/cm 2 only.

ACKNOWLEDGMENT

Fig. 1 .

 1 Fig. 1. Sketch of the typical topology of a wireless sensor/tag for an IoT scenario

Fig. 2 .

 2 Fig. 2. The manufactured rectennas: (a) the 3D version of the rectenna combining a flat dipole antenna (surrounded by a rectangular ring) with a rectifier; (b) top view of the rectifier before the mounting of the lumped devices; (c) bottom view of the rectifier; (d) top view of the 2D rectenna and (e) cross sectional view of this rectenna (the continuous blue line corresponds to the metal layer while the dotted red lines indicate the metallic parts of the rectifier.

Fig. 4 .

 4 Fig. 4.Experimental setup used to characterize the manufactured rectenna.

Fig. 5 .

 5 Fig. 5. (a) Simulated (HFSS) reflection coefficient (S11 in dB) as a function of the frequency for the flat dipole antenna enclosed by the rectangular ring (continuous blue line) and without ring (dotted red line); (b) Simulated reflection coefficient of the flat dipole antenna enclosed by the rectangular ring (continuous blue line) and the measured reflection coefficient of the fabricated prototype (dotted red line). The inset shows a photo of the manufactured antenna including the compact taper.

Fig. 6 .

 6 Fig.6.Measured harvested DC voltage (V_DC) for the manufactured rectenna (incident E-field: 1.28 V/m, load: 10 kΩ) as a function of frequency.

Fig. 7 .

 7 Fig. 7. Measured harvested DC voltage (V_DC: continuous blue line, values on vertical left axis) and efficiency (dotted red line, values in % on vertical right axis) as a function of incident E-field (frequency=860 MHz, load: 10kΩ)

  LAAS CNRS wishes to acknowledge UWINLOC company and the support of the French region OCCITANIE through the research project OPTENLOC.

	Ref	Freq	S (µW/cm²)	𝝶𝝶(%)	Antenna	Rectenna
		(GHz)	PRF (dBm)		Surface	Surface
	[3]	0.9	-15dBm	30	NR	NR/3D*
	[5]	0.868	0.1µW/cm 2	30	NR	NR/IL**
			1 µW/cm 2	44.8
	[10]	0.9	-10dBm	33	NR	NR
	[7]	0.9	0.1µW/cm 2	16	11x11cm 2	11x11cm 2
			1 µW/cm 2	40	0.11𝝀𝝀²	0.11𝝀𝝀² ***
	This	0.86	0.21µW/cm²	31	10.5x6cm²	10.5x6cm²
	work		1.1µW/cm²	35.5	0.05𝝀𝝀²	0.05𝝀𝝀²
			2.2µW/cm²	37