Frédéric Giroire

Frédéric Havet

Joanna Moulierac

Compressing Two-dimensional Routing Tables with Order *

Keywords: routing, routing tables, software defined networks, complexity, FPT, approximation algorithm, compact tables routage, tables de routage, software defined networking, complexité, FPT, algorithme d'approximation, tables compactes

A communication in a network is a pair of nodes (s, t). The node s is called the source source and t the destination. A communication set is a set of distinct communications, i.e. two communications might have the same source or the same destination, but they cannot have both same source and same destination. A routing of a communication (s, t) is a path in the network from s to t. A routing of a communication set is a union of routings of its communications. At each node, there is a set X of communications whose routing path goes through this node.

The node needs to be able to find for each communication (s, t) in X , the port that the routing path of (s, t) uses to leave it. An easy way of doing it is to store the list of all triples (s, t, k), where (s, t) ∈ X and k is the port used by the (s, t)-path to leave the node. Such triples are called communication triples. However, such a list might be very large. Motivated by routing in telecommunication network using Software Defined Network Technologies, we consider the problem of compacting this list using aggregation rules. Indeed, SDN routers use specific memory which is expensive and of small capacity. Hence, in addition, we can use some additional triples, called * -triples. As an example, a t-destination triple ( * , t, p), means that every communication with destination t leaves on port p. We carry out in this work a study of the problem complexity, providing results of NP-completeness, of Fixed-Parameter Tractability and approximation algorithms.

Introduction

Motivation. Software Defined Technology (SDN), e.g. OpenFlow [START_REF] Mckeown | Openflow: Enabling innovation in campus networks[END_REF] is a new promising approach to operate telecommunication networks. Its promise is to allow to take dynamic routing decisions by decoupling the control plane (the system making decisions) from the data plane (which forwards the packets). This way, a centralized controller receives the data monitored in the system (e.g. load, delay, ...) and then, based on this information, computes appropriate routing decisions. Each time a new flow arrives, the router contacts the controller and waits for the decisions to be pushed into its forwarding table. The routing tables thus are populated with flow-based rules with header informations (source IP, destination IP, ...) → exit port.

However, SDN hardware uses specific memory, e.g. TCAM memory [START_REF] Kang | Optimizing the "one big switch" abstraction in software-defined networks[END_REF][START_REF] Kanizo | Palette: Distributing tables in software-defined networks[END_REF], which is very expensive and of small size. Thus, the number of entries of the routing tables is limited to only a few thousands [START_REF] Narayanan | Macroflows and microflows: Enabling rapid network innovation through a split sdn data plane[END_REF][START_REF] Stephens | Past: Scalable ethernet for data centers[END_REF] and grows linearly with the number of flows passing through a router, causing a problem of scalability. It is thus an important area of research to obtain routing using only a limited number of rules per router. [START_REF] Cohen | On the effect of forwarding table size on SDN network utilization[END_REF] studies the problem of choosing routing with a limited number of entry per router using linear programming. Another way to compact the forwarding tables is to use aggregated rules. With such an aggregation, we can set routing entries such as "(*,destination)→ port" or "(source,*)→ port" or also a default entry such as "(*,*)→ port". For example, [START_REF] Giroire | Optimizing Rule Placement in Software-Defined Networks for Energy-aware Routing[END_REF] studies how to use default ports to reduce the size of routing tables. In this work, we consider the problem of compacting a routing table using aggregated rules.

We consider here bi-dimensional routing tables in which the routing decision is not done exclusively on the destination IP addresses, but on the source and destination IP address. Indeed, the commonly implemented destination-based routing has its limitations, especially in delivering quality of service which is a goal of SDN paradigm. One suggested remedy is to base the routing decision on additional fields in the packet header. One of the most important field is the source host. For instance, this would permit selective routing to provide a high bandwidth connection between two different sites of a company. Such refined forwarding is part of the next generation Internet design, and falls within the broader scope of layer four packet classification, where packets are routed using arbitrary fields of the packet header [START_REF] Hari | Detecting and resolving packet filter conflicts[END_REF], [START_REF] Eppstein | Internet packet filter management and rectangle geometry[END_REF], [START_REF] Tv Lakshman | High-speed policy-based packet forwarding using efficient multi-dimensional range matching[END_REF], [START_REF] Milind | Space decomposition techniques for fast layer-4 switching[END_REF]. Routers capable of packet classification can implement many advanced services, such as firewall access control, Virtual Private Networks, and quality of service routing, which are all promises of the SDN paradigm.

Modeling. A communication in a network is a pair of nodes (s, t). The node s is called the source source and t the destination. We use the source and destination fields in our examples, although our ideas apply to any two prefix fields in Internet protocol networks. A communication set is a set of distinct communications, i.e. two communications might have the same source or the same destination, but they cannot have both same source and same destination. A routing of a communication (s, t) is a path in the network from s to t. A routing of a communication set is a union of routings of its communications.

At each node, there is a set X of communications whose routing path goes through this node. The node needs to be able to find for each communication (s, t) in X , the port that the routing path of (s, t) uses to leave it. An easy way of doing it is to store the list of all triples (s, t, k), where (s, t) ∈ X and k is the port used by the (s, t)-path to leave the node. Such triples are called communication triples.

However, such a list might be very large. So we want to reduce it as much as possible using the * symbol. Hence, in addition, we can use some additional triples, called * -triples. There are two kinds of * -triples:

• t-destination triple ( * , t, p), meaning that every communication with destination t leaves RR n°8658 on port p.

• s-source triple (s, * , p), meaning that every communication with source t leaves on port p.

A routing list is an ordered list T 1 , . . . , T r of triples (either communication, or source, or destination ones). A communication is then assigned the port of the first triple in the list, that applies to it. It is crucial to remark that using * -triples introduces an order of the rules in the routing list.

Let C be a set of communication triples. A routing list R emulates C if each communication of C is assigned the same port by C and R. Observe that R may route more communications than C. For example, if the port of all triples of C have source s and port p, then the singleton list made of the global triple (s, * , p) emulates C, even if there is not a triple in C for all communications.

Problems. The problem is then to find the shortest routing list that emulates C. We denote by rmin(C) the minimum number of triples in a routing list emulating C.

Routing List:

Input: A set C of communication triples with at most k ports, and an integer r. Question: rmin(C) ≤ r?

The number of saved triples is sav(C) = |C|rmin(C). The complementary problem to Routing List is the following. Assume now that R contains a global triple, say τ . Let R τ be the set of triples of C that are routed by τ . Let R ′ be the list obtained from R by replacing τ by R τ (in any order). Clearly, R ′ emulates C and has no global triple. Hence

List Reduction

sav(C) ≥ |C| -|R ′ | = |C| -(|R| + |R τ | -1) = sav * (C) -(|R τ | -1). But, by definition, |R τ | ≤ M (C) -1. Thus sav * (C) ≤ sav(C) + M (C) -1.
Contributions. In this work, we first study the complexity of the above problems. We provide NP-completeness results in Section 3, Fixed Parameter Tractability in Section 4 and, finally approximation algorithms in Section5. [START_REF] Suri | Compressing two-dimensional routing tables[END_REF]. Similarly to us, the authors consider the problem of determining a compact routing table using aggregation rules that has the same behavior as the original routing table. The difference with our problem is that their goal is to find what they call a conflict-free routing table in which the rules can be taken in any order. On the contrary, as noted above, the order is crucial in our problems. We quote: "The filter compression problem with inconsistent filters [rules], where one uses priority to define best matching filter [rule], is open, and we conjecture that it is NP-complete."

Our work answers an open question of

Preliminaries

Standard and canonical routing lists

Let R = T 1 , . . . , T r be a routing list, possibly with a global triple. It is standard if there exists i such that T j is a * -triple if and only if j > i. The following lemma is easy and left to the reader. • putting all the communication triples of R at the beginning and all the * -triples of R at the end, keeping the same order as in R for the * -triples, also emulates C.

A routing list is canonical if it is the concatenation of sublist B 1 , . . . , B q , called blocks having the following properties for every 1 ≤ ℓ ≤ q:

(i) in B ℓ , there is a unique * -triple and it is the last one;

(ii) if the * -triple of B ℓ is an s-source triple (resp. t-destination triple), then all triples of B ℓ have source s (resp. destination t);

(iii) if ℓ = q, then B ℓ has no global triple.

Lemma 4. Let C be a set of communication triples and RT 1 , . . . , T r be a routing list emulating C. One can obtain from R a canonical routing list R ′ emulating C not longer than R by successive applications of the following operations:

• deleting some triple,

• replacing some communication triple (s, t, p) by the triple ( * , t, p),

• reordering the triples.

Proof. We shall use three operations described in the statement according to the following rules on a routing list L = T 1 , . . . , T r .

(R1) If there are triples after a global triple, then they are useless, so we delete them.

(R2) If the last triple is a communication triple (s, t, p), then we replace it by ( * , t, p).

(R3) Let i 1 , i 2 , . . . , i q be the indices in increasing order of the * -triples of L. If for some ℓ, T i ℓ is an s-source triple (resp. t-destination triple) and there is a communication triple T i with i ℓ -1 < i < i ℓ with source distinct from s (resp. destination distinct from t), then we move

T i after T i ℓ .
It is simple matter to check that if any of the above rules applies to a routing list emulating C, then we obtain a new routing list emulating C which is not longer that the original one.

Therefore starting from R, as long as one of the rules (R1), (R2) or (R3) applies, we do it. This process must end, because each rule can be applied only a finite number of times. Indeed (R1) decreases the size of the list, (R2) increases the number of * -triples, and (R3) decreases the vector (i 1 , i 2 , . . . , i q ) of the indices of * -triples in the lexicographic order.

Let R ′ = T ′ 1 , . . . , T ′ r be the routing list obtained at the end of the process. Note that at each time of the process, we have a routing list emulating C not longer than R by the above remark. In particular R ′ emulates C and |R ′ | ≤ |R|. Moreover, none of (R1), (R2), and (R3) applies. Let i 1 , i 2 , . . . , i q be the indices in increasing order of the * -triples of R ′ , and for 1 ≤ ℓ ≤ q, let B ℓ be the subsequence T i ℓ-1 +1 , . . . , T i ℓ (with i 0 = 0). By definition, the unique * -triple in B ℓ is its last triple. The concatenation B 1 , . . . , B q is R ′ for otherwise (R2) would apply. If ℓ = q, then B ℓ has no global triple, for otherwise (R1) would apply. Finally, if the * -triple of B ℓ is an s-source triple (resp. t-destination triple), then all triples of B ℓ have source s (resp. destination t), for otherwise (R3) would apply. Hence, R ′ is canonical.

The Direction-based Heuristic

Let C be a set of communication triples with destination set S and destination set T . Set n = |S| and m = |T |. For any port p, let C(p) be the set of triples of C with port p. For a source s (resp. destination t) and a port p, let C(s, p) (resp. C(s, t)) be the set of triples of C with source s (resp. destination t) and port p. For every source s, let M (s) := max p |C(s, p)| be the maximum number of triples in C with source s and same port, and for every destination t, let M (t) := max p |C(t, p)| Inria be the maximum number of triples in C with destination t and same port. Set

Z -(C) = s∈S (M (s) -1) = s∈S M (s) -n and Z | (C) = t∈T (M (t) -1) = t∈T M (t) -m.
Any routing list emulating C yields an upper bound on rmin(C). One such list can be obtained by routing source by source. One source s after another we route all triples of C with source s. This can be done by using the triple (s, * , p) for p a port such that there are M (s) triples with source s and port p after all triples with source s and port distinct from p. Doing so, we save M (s) -1 triples when routing the triples with source s. Hence, we obtain a routing list of size |C| -Z -(C). Such a list is called a source-based routing list.

Proceeding similarly according to the destinations, we obtain a routing list, called destinationbased of size |C| -Z | (C).

Setting

Z(C) = max{Z -(C), Z | (C)}, we have sav(C) ≥ Z(C) and rmin(C) ≤ |C| -Z(C). (1)
The algorithm consisting in computing a source-based routing list and a destination-based routing list and taking the shortest of the two, is called the Direction-based Heuristic. It provides a routing list emulating C of size Z(C). As we shall see in Corollary 25, the Direction-based Heuristic is a 2-approximation for List Reduction. Proof. Let C be a set of communication triples, all having the same port p. Let S and T be the set of sources and destinations, respectively, of C.

Complexity results

Solving 1-Port Routing List in polynomial time

Observe that a routing list with no global triples emulating C can always be transformed into a routing list with no global triples and no communication triples. Indeed each communication triple (s, t, p) can be replaced by the source triple (s, * , p) (or the destination triple ( * , t, p)). Therefore, we may only search for a shortest routing list with no global triples and no communication triples. Such a list is a set R of source triples and destination triples such that, for every triple (s, t, p) of C, either (s, * , p) ∈ R or ( * , t, p) ∈ R. This corresponds to finding a minimum vertex cover in the bipartite graph G defined as follows:

• V (G) = S ∪ T ; • E(G) = {st | (s, t, p) ∈ C}.
Recall that a vertex cover in G is a subset W of V (G) such that each edge e ∈ E(G) has an endvertex in W . Let ρ(G) be the size of a minimum vertex cover in G. A well-known theorem of Gallai [START_REF] Gallai | Maximum-minimum sätze über graphen[END_REF] asserts that |V (G)| = ρ(G) + µ(G), where µ(G) is the size of a maximum matching in G. Now, finding a maximum matching in a bipartite graph can be done in polynomial time, by the Hungarian Method for example. Hence 1-Port Routing List can be solved in polynomial time.

NP-hardness of 2-Port Routing List

C = {(s i , t j , 1) | a i b j ∈ A(D)} ∪ {(s i , t j , 0) | b j a i ∈ A(D)} ∪ {(s i , t ′ (m+1)i+r , 1) | 1 ≤ i ≤ n, 1 ≤ r ≤ m + 1} ∪ {(s ′ (n+1)j+r , t j , 0) | 1 ≤ j ≤ m, 1 ≤ r ≤ n + 1} Set r = n + m + k. We claim that rmin(C) ≤ r if and only if fas(D) ≤ k. Assume first that fas(D) ≤ k. Let σ = v 1 , .
. . , v n+m be an ordering of V (D) with at most k feedback arcs.

Let R be the routing list that is the succession of the sublists B 1 , . . . , B n+m defined as follows.

For ℓ = 1 to n + m, if v ℓ = a i then let B ℓ be a list consisting of the communication triples in {(s i , t j , 0) | b j ∈ N -(a i )} \ ℓ-1 ℓ ′ =1 B ℓ ′ (
in any order), followed by (s i , * , 1), and if v ℓ = b j then let B ℓ be a list consisting of the communication triples of {(s i , t j , 1)

| a i ∈ N -(b j )} \ ℓ-1 ℓ ′ =1 B ℓ ′ ,
followed by ( * , t j , 0). Intuitively, when v ℓ = a i , B l routes the communications with source s i that were not previously routed. The one with port 1 are routed by the source triple (s i , * , 1) while the ones with port 0 are routed by the preceding communication triples. Similarly, when v ℓ = b j , B l routes the communications with destination t j that were not previously routed.

Clearly, R emulates C. Let us now calculate its size. R contains n source triples and m destination triples.

Let us now compute the number of communication triples in each B

l . Assume that v ℓ = a i . A triple (s i , t j , 0) is in {(s i , t j , 0) | b j ∈ N -(a i )} \ ℓ-1 ℓ ′ =1 B ℓ ′ , if and only if, b j a i ∈ A(D) and a i precedes b j in σ. Hence (s i , t j , 0) is in B ℓ if and only if b j a i is a σ-feedback arc. Similarly, if v ℓ = b j , then (s i , t j , 1) is in B ℓ if
and only if a i b j is a σ-feedback arc. In both cases, the number of communication triples in B l is equal to the number of σ-feedback arcs with head v ℓ . Thus, the number of communication triples in R is equal to the number of σ-feedback arcs, and so it is at most k. Hence, adding the source triples and destination triples, the set R has size at most n + m + k.

Reciprocally, assume that rmin(C) ≤ r. Let R be a shortest canonical routing list that emulates C. Then |R| ≤ r.

Observe that R contains exactly n source triples, {(s i , * , 1)

| 1 ≤ i ≤ n}, and m destination triples {( * , t j , 0) | 1 ≤ j ≤ m}. Otherwise, assume that (s i , * , 1) ∈ R (The proof is similar if ( * , t j , 0) ∈ R.). This means that the communication triples {(s i , t ′ (m+1)i+r , 1) | 1 ≤ i ≤ n, 1 ≤ r ≤ m+1} ∈ C have to be routed by m+1 rules. If (s i , * , 0) ∈ R, we add the source triple (s i , * , 1)
and remove these m + 1 rules, saving m rules without changing the routing. If (s i , * , 0) ∈ R, we replace (s i , * , 0) by (s i , * , 1) and again remove the m + 1 rules. We have to add at most m rules to route all the communication triples with port 0 that were routed by (s i , * , 0). In both cases, we obtain a routing list emulating C of smaller size then R, a contradiction. Now R is canonical, so every communication triple (s, t, p) is either followed by an s-source triple or a t-destination triple. Therefore R can be decomposed into the blocks B 1 , . . . , B n+m , where each B ℓ , 1 ≤ ℓ ≤ n + m, is either a list of communication triples with source s i followed by (s i , * , 1) for some 1 ≤ i ≤ n, or a list of destination triples with destination t j followed by ( * , t j , 0) for some 1 ≤ j ≤ m.

Inria

Let σ = v 1 , . . . , v n+m be the ordering of V (D) where for 1 ≤ ℓ ≤ n + m, v ℓ = a i if all triples of B ℓ have source s i , and v ℓ = b j if all triples of B ℓ have destination t j . If an arc a i b j of D is not σ-feedback, then the block finishing with (s i , * , 1) precedes the one finishing with ( * , t j , 0). Therefore, the communication triple (s i , t j , 1) is routed by (s i , * , 1) and is not in R. Conversely, if an arc a i b j of D is σ-feedback, then the block finishing with ( * , t j , 0) precedes the one finishing with (s i , * , 1). Therefore, the communication triple (s i , t j , 1) must be routed before ( * , t j , 0) and thus is in R. Hence an arc a i b j is σ-feedback if and only if

(s i , t j , 1) is in R. Similarly, an arc b j a i is σ-feedback if and only if (s i , t j , 0) is in R.
Consequently, the number of σ-feedback arcs is equal the number of communication triples of R, which is at most rnm, because R contains n source triples and m destination triples as observed above. Thus fas(D) ≤ k.

NP-hardness of 2-Port With-global Routing List

Theorem 7. 2-Port With-global Routing List is NP-complete.
Proof. The proof is based on the one of Theorem 6.

Let D be a bipartite graph with bipartition (A, B). Let A = {a 1 , . . . , a n } and B = {b 1 , . . . , b m }. Consider the set of communication triples

C * = C ∪ {(s ′′ i , t ′′ i , 1) | 1 ≤ i ≤ 2nm + n + m + 3} ∪ {(s i , t 0 , 1) | 1 ≤ i ≤ n} ∪ {(s ′′′ i , t 0 , 0) | 1 ≤ i ≤ n + 1}
where C is the set of communication triples defined in the proof of Theorem 6. Set r = 1 + n + (m + 1) + k. We claim that rmin * (C * ) ≤ r if and only if fas(D) ≤ k.

Assume first that fas(D) ≤ k. We consider the routing list R * = R ( * , t 0 , 0) ( * , * , 1), where R is defined in the proof of Theorem 6. Clearly R * emulates C * and has a size 1 + n + (m + 1) + k.

Reciprocally, assume that rmin * (C * ) ≤ r. Let R * be a canonical shortest routing list that emulates C * .

Observe first that (s ′′ i , t ′′ i , 1), 1 ≤ i ≤ 2nm + n + m + 3, is the unique communication triple with source s ′′ i and the unique one with destination t" i . Therefore unless it is ( * , * , 1), the triple routing (s ′′ i , t ′′ i , 1) routes only that triple. Let us first prove that the global triple ( * , * , 1) ∈ R * . Suppose not. We have to use 2nm + n + m + 3 triples to route the communication triples of {(s ′′ i , t ′′ i , 1) | 1 ≤ i ≤ 2nm + n + m + 3}. Two cases may happen depending on whether the global triple ( * , * , 0) is in R * or not. In the second case, we add the global triple ( * , * , 1) and remove all triples routing {(

s ′′ i , t ′′ i , 1) | 1 ≤ i ≤ 2nm + n + m + 3} to R * ,
we save at least 2nm + n + m + 2 triples. In the first case, we replace the global triple ( * , * , 0) by ( * , * , 1), and remove the 2nm

+ n + m + 3 triples routing {(s ′′ i , t ′′ i , 1) | 1 ≤ i ≤ 2nm+n+m+3}
, and we add the communication triples that were routed by ( * , * , 0). There are at most nm + m(n + 1) + (n + 1) = 2nm + m + n + 1 such triples, because this is the total number of communication triples with port 0. Therefore, in both cases, we obtain a routing list emulating C * shorter than R * , a contradiction.

Let us now prove that R * contains the m + 1 destination triples {( * , t j , 0) | 0 ≤ j ≤ m}. Suppose not. Then there exists j such that ( * , t j , 0) ∈ R * . This means that the communication triples

{(s ′ (n+1)j+r , t j , 0) | 1 ≤ j ≤ m, 1 ≤ r ≤ n + 1} ∪ {(s ′′′ i , t 0 , 0) | 1 ≤ i ≤ n + 1} ∈ C * have
to be routed by n + 1 rules. If ( * , t j , 1) ∈ R * , we add the source triple ( * , t j , 0) and remove these n + 1 rules, saving n rules without changing the routing. If ( * , t j , 1) ∈ R * , we replace ( * , t j , 1) by ( * , t j , 0) and again remove the n + 1 rules. We have to add at most n rules to route all the communication triples with port 1 that were routed by ( * , t j , 1). In both cases, we obtain a routing list emulating C * shorter than R * , a contradiction.

We now denote by α the number of source triples (s i , * , 1) and by β the number of communication triples (s i , t 0 , 1), for 1 ≤ i ≤ n. We have α + β = n. Indeed, as ( * , t , 0) ∈ R * , on a line s i , the communication triples (s i , t 0 , 1) is necessary when (s i , * , 1) is not in R * , and superfluous in the opposite case. Now R * is canonical, so every communication triple (s, t, p) is either followed by an s-source triple or a t-destination triple or the global triple ( * , * , 1). Therefore R * can be decomposed into the blocks B 1 , . . . , B m+α+2 , where each B ℓ , 1 ≤ ℓ ≤ m + α + 1, is either a list of communication triples with source s i followed by (s i , * , 1) for some 1 ≤ i ≤ n, or a list of destination triples with destination t j followed by ( * , t j , 0) for some 1 ≤ j ≤ m. The last block B m+α+2 is a list of communication triples followed by the global triple ( * , * , 1).

We know show that there exists a canonical routing R ′′ emulating C * in which the rule ( * , t 0 , 0) is in the penultimate block, B m+α+1 . Note first that the rule ( * , t 0 , 0) appears after any source triple(s i , * , 1). Otherwise, we may switch the two corresponding blocks and save the communication triple(s i , t 0 , 1). To conclude, we know that two blocks corresponding to two destination triples can be switched without affecting the routing. Henceforth, in the following we assume that ( * , t 0 , 0) is the last triple of the block B m+α+1 .

Let σ = v 1 , . . . , v n+m be the ordering of V (D) where for 1 ≤ ℓ ≤ α + m, v ℓ = a i if all triples of B ℓ have source s i , and v ℓ = b j if all triples of B ℓ have destination t j . We then arbitrary assign the remaining vertices of A to the v ℓ , for α

+ m + 1 ≤ ℓ ≤ n + m.
If an arc a i b j of D is not σ-feedback, then the block finishing with (s i , * , 1) precedes the one finishing with ( * , t j , 0). Therefore, the communication triple (s i , t j , 1) is routed by (s i , * , 1) and is not in R * . Conversely, if an arc a i b j of D is σ-feedback, then the block finishing with ( * , t j , 0) precedes the one finishing with (s i , * , 1) if it exists, or the global triple ( * , * , 1). Therefore, the communication triple (s i , t j , 1) must be routed before ( * , t j , 0) and thus is in R * . Hence an arc a i b j is σ-feedback if and only if (s i , t j , 1) is in R * . Similarly, an arc b j a i is σ-feedback if and only if (s i , t j , 0) is in R * .

To summarize, the number of communication triples of R * is equal to the number of σfeedback arcs plus β, the number of communication triples of the column 0. R * contains m + 1 destination triples and α source triples, with α+β = n. Thus, rmin * (C * ) ≥ 1+n+(m+1)+fas(D). Since rmin * ≤ r, it follows fas(D) ≤ k.

Short routing list for full sets of communication triples

Recall that a communication set is full if it is of the form S × T , and that a set of communication triples is full if it is a set of communication triples on a full set of communications. Theorem 8. Routing List is NP-complete even if C is restricted to be a full set of communication triples.

Proof. Reduction from Routing List.

Let C be a set of communication triples. Let S be the set of sources of C and T be the set of destinations of C. Let Q be the set of communications of S × T not routed by C. For each communication (s, t) in Q, let p(s, t) be a port dedicated to this communication, and set C * = C ∪ {p(s, t) | (s, t) ∈ Q}. The set C * is a full set of communication. Moreover, in any shortest routing list emulating C * , for each (s, t) ∈ Q, there is a unique triple with port p(s, t), because it is only used for the communication (s, t). Therefore rmin(C * ) = |Q| + rmin(C).

Similarly to Theorem 8, one can prove the following.

Inria

Theorem 9. With-global Routing List is NP-complete even if C is restricted to be a full set of communication triples.

In the proof of Theorem 8, the number of ports is not bounded. However, we believe that the problem remain NP-complete as soon as they are at least two ports. Proof. Let us describe a kernelization algorithm that given an instance (C, z) of k-port List Reduction, returns either 'Yes' (or a small yes instance, e.g. (∅, 0)) only if sav(C) ≥ z, or an instance (C ′ , z) equivalent to C (that is such that sav(C) ≥ z if and only if sav(C ′ ) ≥ z) of size at most (4z -4)k.

A triple τ = (s, t, p) of C is source-linked (resp. destination-linked) is C contains another triple with port p and source s (resp. destination t). It is isolated, if it is neither source-linked nor destination-linked. Let τ be an isolated triple. Observe that whatever triple is used to route τ , it is the only one routed by this triple. Hence sav(C) = sav(C \ {τ }).

Therefore our kernelization algorithm removes all isolated triples of C. Let C ′ be the resulting set of communication triples. We then run the Direction-based Heuristic on C ′ to compute Z(C ′ ). If Z(C ′ ) ≥ z, then we return 'Yes', because sav(C) ≥ sav(C ′ ) ≥ Z(C ′ ). If not, then we return C ′ .

Clearly, the returned instance is equivalent to C. Let us now prove that it has size at most (4z -4)k. We know that Z -(C ′ ) ≤ z -1.

Let C -(resp. C | ) be the set of source-linked (resp. destination-linked) communication triples in C ′ . Because C ′ has no isolated vertices, we have C ′ = C -∪ C | . Let S ′ be the set of sources s such that M (s) ≥ 2. Observe that

|S ′ | ≤ s∈S ′ (M (s) -1) = Z -(C ′ ) ≤ z -1 (2)
and all source-linked communication triples have source in S ′ . But for a source s there are at most kM (s) triples with source s.

Hence |C -| ≤ k s∈S ′ M (s). Now s∈S ′ M (s) = s∈S ′ (M (s) - 1) + |S ′ | ≤ 2z -2 by Equation (2). Therefore |C -| ≤ (2z -2)k. Similarly, |C | | ≤ (2z -2)k, thus |C ′ | ≤ (4z -4)k.
Theorem 12. List Reduction parameterized by z admits a quadratic kernel, and so is FPT.

Proof. Let us describe a kernelization algorithm that given an instance (C, z) of List Reduction, returns either 'Yes' only if sav(C) ≥ z, or an instance (C ′ , z) equivalent to C (that is such that sav(C) ≥ z if and only if sav(C ′ ) ≥ z) of size at most z(4z -4).

We first remove all isolated triples of C, and denote the resulting set of communication triples C ′ . Let S ′ be the set of sources s such that M (s) ≥ 2, and T ′ be the set of destinations t such that M (t) ≥ 2. We have |S ′ | ≤ z -1 and |T ′ | ≤ z -1. For any source s, let P (s) be the set of ports such that do not appear on {s} × T ′ .

Assume that P (s) = ∅. Let M P (s) be the maximum number of triples with source s and same port in P (s), and let p 1 (s) be a port in P (s) appearing on M P (s) triples with source s. For any p ∈ P (s), let C ′ (p, s) be the set of triples of C ′ with source s and port p. Let R be a shortest routing list emulating C ′ . Suppose that (s, * , p) ∈ R for some p ∈ P (s) \ {p 1 (s)}. Necessarily, the triples of C ′ (p 1 (s), s) precede (s, * , p) in R. Hence replacing (s, * , p) by (s, * , p 1 (s)) and the M P (s) triples of C ′ (p 1 (s), s) by the ones of C ′ (p, s), we obtain a routing list R ′ emulating C ′ of length not smaller than R. By minimality of R, R ′ is also a shortest routing list emulating C ′ . Moreover all triples of C ′ (p, s) appear in R. Therefore

sav(C ′ ) = sav(C ′ \ C ′ (p, s)) for all p ∈ P (s) \ {p 1 (s)}. (3)
Similarly, for every destination t, we define P (t) as the set of ports such that do not appear on S ′ × {t}. We let M P (t) be the maximum number of triples with destination t and same port in P (t), and let p 1 (t) be a port in P (t) appearing on M P (t) triples with destination t. Finally, let for any p ∈ P (t), let C ′ (t, s) be the set of triples of C ′ with destination t and port p. A symmetrical argument as above shows

sav(C ′ ) = sav(C ′ \ C ′ (p, t)) for all p ∈ P (t) \ {p 1 (t)}. (4)
Let C ′′ be the the set of communication triples obtained from C ′ by removing C ′ (p, s)) for every source s ∈ S ′ and every port p ∈ P (s) \ {p 1 (s)}, and removing C ′ (p, t)) for all destination t ∈ T ′ and all port p ∈ P (t) \ {p 1 (r)}. Applying Equations 3 and 4 many times, we obtain sav(C ′ ) = sav(C ′′ ), i.e. C ′′ is equivalent to C ′ and so to C. By construction of C ′′ , for any s ∈ S ′ , there are at most z ports appearing on the triples with source s: at most z -1 on the triples with destination in T ′ and p 1 (s). Hence, there are at most

z s∈S ′ M (s) triples with source in S ′ . Since s∈S ′ M (s) ≤ |S ′ | + s∈S ′ (M (s) -1) ≤ 2z -2,
there are at most z(2z -2) triples of C ′′ with source in S ′ . Similarly, there are at most z(2z -2) triples of C ′′ with destination in T ′ . Thus, |C ′′ | ≤ z(4z -4). Hence, returning C ′′ yields the desired kernelization.

Problem 13. Does List Reduction parameterized by z admits a linear kernel? Theorem 14. For every k ≥ 1, k-port With-global List Reduction parameterized by z admits a linear kernel, and so is FPT.

Proof. Let (C, z) be an instance of k-port With-global List Reduction. If a port p appears at least z + 1 times in C, then sav * (C) ≥ z since we can first route each triple of C with a port distinct from p by itself, and then route all the triples with ports p with ( * , * , p). Therefore, we have the following easy kernelization algorithm. If a port appears at least z + 1 times, then we return 'Yes'. If not, we return C, which has size at most k • z.

Theorem 15. With-global List Reduction parameterized by z admits a cubic kernel, and so is FPT.

Proof. Let us describe a kernelization algorithm that given an instance (C, z) of With-global List Reduction, returns either 'Yes' only if sav * (C) ≥ z, or an instance (C ′ , z) equivalent to C (that is such that sav * (C) ≥ z if and only if sav * (C ′ ) ≥ z) of size at most 3z 3 .

We first check if a port appears at least z + 1 times in C. If yes, then we return 'Yes'. Henceforth, we may assume that every port appears at most z times.

A source s (resp. destination t) is rainbow if the communication triples of C with source s (resp. destination t) have pairwise distinct ports, that is if M (s) = 1. If C has more than z non-rainbow sources or more than z non-rainbow destinations, then we return 'Yes'. This is Inria valid because sav * (C) ≥ sav(C) ≥ Z(C). Henceforth we may assume that the numbers a and b of non-rainbow sources and non-rainbow destinations, respectively, are both less than z. Let S ′ = {s 1 , . . . , s a } be the non-rainbow sources, and T ′ = {t 1 , . . . , t b } be the set of non-rainbow destinations.

Let p be a port. It is loose there is no triple of C with source in S ′ , destination in T ′ and port p. For every source s (resp. destination t), we denote by C(s, p) (resp. C(t, p)) the set of triples of C with source s (resp. destination t) and port p. Let T (p) the set of triples of C with port p, source not in S ′ and destination not in T ′ . The trace of p is the (a + b + 1)-uple

(|C(s 1 , p)|, . . . , |C(s a , p)|, |C(t 1 , p)|, . . . , |C(t b , p)|, |T (p)|).
Note that if p is loose, then (C(s 1 , p), . . . , C(s a , p), C(t 1 , p), . . . , C(t b , p), T (p)) is a partition of C(p). As long as two loose ports p 1 and p 2 have the same trace, then we remove the triples with ports p 1 . This is valid according to the following claim whose proof is postponed to the end of this proof.

Claim. If two loose ports p 1 and p 2 have the same trace, then sav * (C) = sav * (C \ C(p 1 )).

We return the resulting set of communication triples C ′ . Observe that in C ′ loose ports have different traces. Now a + b + 1 ≤ 2z and every element of the trace is at most z.Therefore there are at most 2z 2 possible traces, so there are at most 2z 2 loose ports. Moreover, the number of non-loose ports is at most S ′ × T ′ ≤ z 2 . Thus there are at most 3z 2 ports appearing in C ′ . But each port appears at most z times in C and thus also in C ′ . Therefore |C ′ | ≤ 3z Let us now prove the opposite inequality. Let R be a shortest routing with global triples emulating C that contains the minimum number of * -triples with port p 1 .

Observe first that if R contains a source triple whose source is rainbow, then it routes a unique triple by which it can be replaced. Free to make such replacements, we may assume that the source of every source triple of R is in S ′ . Similarly, we may assume that the destination of every destination triple of R is in T ′ . Moreover, by Lemma 3, we can assume that in R all the * -triples are at the end.

Assume for a contradiction that R contains a source triple with port p 1 , say (s, * , p 1 ). Necessarily, s ∈ S ′ . Because p 1 and p 2 have the same trace, |C(s, p 1 )| = |C(s, p 2 )|. The triples of C(s, p 2 ) are routed by R. But since p 2 is loose, their destinations are not in T ′ , so they cannot be routed by a destination triple. Therefore C(s, p 2 ) ⊆ R. Furthermore, the destination of the triples of C(s, p 1 ) are not in T ′ . Thus there is no destination triple with their destination. Therefore no triple τ of C(s, p 1 ) appears in R, for otherwise R \ {τ } would also emulate C, a contradiction to the fact R is a shortest list emulating C. Consider the list R ′ obtained from R by replacing C(s, p 2 ) by C(s, p 1 ) and (s, * , p 1 ) by (s, * , p 2 ). Clearly, R ′ emulates C, |R ′ | = |R| and it has one * -triple with port p 1 less than R. This is a contradiction. Therefore R contains no source triple with port p 1 . Similarly, R contains no destination triple with port p 1 .

Assume for a contradiction that R contains the global triple ( * , * , p 1 ). We assert that there is no source or destination triple with port p 2 . Suppose there were one, say, without loss of generality, a source triple τ = (s, * , p 2 ). Necessarily, s ∈ S ′ . Consider now a triple (s, t, p 1 ) of C(s, p 1 ). Because p 1 is loose, its destination t is rainbow and thus there is no destination triple with destination t in R. Therefore (s, t, p 1 ) must be in R to route itself. Thus C(s, p 1 ) ⊆ R. Consider the concatenation R ′ of C(s, p 2 ) and R \ (C(s, p 1 ) ∪ {τ }). Any triple of C \ (C(s, p 1 ) ∪ C(s, p 2 )) is clearly assigned the same port by R ′ and R, and every elements of C(s, p 2 ) is assigned p 2 by itself. Let (s, t, p 1 ) ∈ C(s, p 1 ). There is no destination triple with destination t in R ′ because there were no in R, and there is no source triple with source s in R ′ because there the unique one of R was τ . Therefore R ′ assigns to (s, t, p 1 ) the port p 1 by ( * , * , p 1 ). Consequently, the routing list R ′ emulates C, and it is shorter than R, a contradiction. This proves our assertion.

This implies that C(p 2 ) ⊆ R. Now consider the routing list R ′′ which is the concatenation of C(p 1 ), R \ (C(s, p 2 ) ∪ {( * , * , p 1 )}), and ( * , * , p 1 ). As above for R ′ , one checks that R ′′ emulates C. But R ′′ has the same size as R and but one * -triple with port p 1 less than R, a contradiction.

Consequently, R has no * -triples with port R, hence C(p 1 ) ⊆ R. Now the routing list R\C(p 1 ) emulates C \ C(p 1 ), and so

sav * (C \ C(p 1 )) ≥ |C \ C(p 1 )| -R \ C(p 1 ) = |C| -|R| = sav(C).
This completes the proof of the claim, and that of the theorem.

Problem 16. Does With-global List Reduction parameterized by z admits a linear or quadratic kernel?

Routing List and variants

Theorem 17. Routing List parameterized by r admits a cubic kernel, and so is FPT.

Proof. Let us describe a kernelization algorithm that given an instance (C, r) of Routing List, returns either 'No' only if rmin(C) ≥ r, or an instance (C", r) equivalent to C (that is such that rmin(C) ≥ r if and only if rmin(C") ≥ r) of size at most 2r 3 + r 2 + r.

We first check whether there are sets S ′ ⊆ S and T ′ ⊆ T such that |S ′ | + |T ′ | ≤ r and for every triple (s, t, p) ∈ C either s ∈ S ′ or t ∈ T ′ . This is equivalent to decide whether there is a vertex cover of cardinality at most r in the bipartite graph G defined as follows:

• V (G) = S ∪ T ;

• E(G) = {st | there exists p such that(s, t, p) ∈ C}.

If no such sets S ′ , T ′ exist, then we return 'No'. This is valid because in a canonical list of size at most r, there are at most r blocks and all triples in a block have either same source or same destination.

Therefore, we may assume that we have two such sets S ′ and T ′ . (They can also be found in polynomial time.)

A source s ∈ S ′ (resp. destination t ∈ T ′ ) is forced if M (s) ≥ r + 1 (resp. M (t) ≥ r) and loose otherwise. Proof. We may assume that for each source s, R contains at most one source triple with source s, for otherwise the last source triple of source s is useless and can be deleted.

Observe that for a given source s, all triples of C(s) that are not routed by the (possibly inexistant) source triple with source s are routed by different triples of R.

Inria

Assume that s is a forced source. Let p s a port such that |C(s, p s )| ≥ r, then, by the above observation, (s, * , p s ) ∈ R. Moreover all triples of C(s) \ C(s, p s ) are routed by different triples. There are at most r -1 such triples, so |C(s) \ C(s, p s )| ≤ r -1. This proves (i).

Assume now that s is a loose source. If there is no * -triple with source s in R, then, by the above observation, all triples of C( Similarly, for a destination t ∈ T ′ , we define S 1 (t) as the set of destinations of the triples in C(s) \ C(t, p s ) if t is forced, and in C(t) if t is loose, and we set S 1 = t∈T ′ S 1 (t) and S 2 = S \ (S ′ ∪ S 1 ). The kernelization algorithm computes S 1 (t) for all t ∈ T ′ , and returns 'No' if |S 1 (t)| ≥ 2r. Henceforth, we may assume

|S 1 | ≤ (2r -1)|T ′ |.
Claim 17.2. Let R be a shortest routing list emulating C. There is no destination triple with destination in T 2 .

Proof. Suppose for a contradiction that a shortest routing list R emulating C contains a destination triple τ 2 with destination t 2 ∈ T 2 . Let R ′ be list obtained from R by deleting τ 2 . We shall prove that R ′ emulates C which implies that R is not a shortest routing list emulating C, a contradiction.

Since we only remove τ 2 from R it suffices to prove that all triples with destination t 2 are properly routed. Observe that since t 2 ∈ T 2 , all triples with destination t 2 are of the form (s, t 2 , p s ) for a forced source s. Now for such a source, the source triple (s, * , p s ) exists. Moreover, in R ′ , there is no destination triple with destination t 2 , because R was a shortest routing list containing τ 2 , and communication triple of the form (s, t 2 , p) for such a triple would have been useless in R. Therefore, R ′ properly routes (s, t 2 , p s ) using (s, * , p s ). ♦ Let C # be the set of communication triples of C with source in S \ S 2 and destination in T \ T 2 . Let S ′′ be a set of r + 1 sources disjoint from S \ S 2 and T ′′ be a set of r + 1 destinations disjoint from T \ T 2 . Set

C ′′ = C # ∪ {(s, t ′′ , p s ) | t ′′ ∈ T ′′ and
× T ′ | + |S ′ × T 1 | + |S 1 × T ′ | ≤ |S ′ | • |T ′ | + (2r -1)|S ′ | 2 + (2r -1)|T ′ | 2 ≤ (2r -1)r 2 , because |S ′ | + |T ′ | ≤ r. Thus |C ′′ | = |C # | + 2r(r + 1) ≤ 2r 3 + r 2 + r. Hence the algorithm returns C ′′ .
In order to keep the above proof simple, we made no attempt to make the size of C ′′ as small as possible. One can easily get smaller bounds than 2r 3 + r 2 + r, but we did not find a way to have a quadratic bound. This leaves the following question open. Problem 18. Does Routing List parameterized by r admits a linear or quadratic kernel? Theorem 19. With-global Routing List parameterized by r admits a cubic Turing kernel, and so is FPT.

Proof. Let us describe a kernelization algorithm that given an instance (C, r) of Routing List, returns either 'No' only if rmin(C) ≥ r, or an set of r instances (C i , r), 1 ≤ i ≤ r, of size at most ???r 3 , such that rmin(C) ≥ r if and only if rmin(C i ) ≥ r for some i.

Problem 20. Does With-global Routing List parameterized by r admits a linear or quadratic Turing kernel?

5 Approximation algortihms

Relationship between the problems with and without global triple

Lemma 21. If rmin * can be approximated with ratio α in polynomial time, then rmin can be approximated with ratio α + 1 in polynomial time.

Proof. Assume that there is an algorithm A * , that given a set of communication triples C, returns a list R * emulating C with global triples such that |R * | ≤ α rmin * (C).

Let A be the algorithm that does the following: It first runs A * to get a list R * emulating C such that |R * | ≤ α rmin * (C). If R * contains no global triple, then it returns R := R * . Then |R| ≤ α rmin * (C) ≤ α rmin(C). Assume now that R * contains a global triple. Free to delete, the useless triples after the first global triple, we may assume that R * has a unique global triple, and that it is the final one. Let τ = ( * , * , p) be this triple, and let C τ be the set of triples of C that are routed by it when routing according R * . By definition, all the triples of C τ have port p. Therefore, by Theorem 5, one can find in polynomial time a shortest routing list R τ emulating C τ . We then return the concatenation

R of R * \ τ and R τ . Now |R| ≤ |R * |+|R τ | ≤ α rmin * (C)+rmin(C τ )-1. But rmin * (C) ≤ rmin(C) and rmin(C τ ) ≤ rmin(C) because C τ ⊆ C. Hence |R| ≤ (α + 1) rmin(C) -1.
Lemma 22. If sav can be approximated with ratio α in polynomial time, then sav * can be approximated with ratio α + 1 in polynomial time.

Proof. Assume that there is an algorithm A, that given a set of communication triples C, returns a list R emulating C such that sav(C) ≤ α(|C| -|R|).

Let A * be the algorithm that does the following:

1. It first runs A to get a list R emulating C such that sav(C) ≤ α(|C| -|R|).
2. Next, it finds the port p that appears the most in C. Let C p be the set of triples of C with port p. It constructs a list R ′ made of all elements of C \ C p (in any order) followed by the global triple ( * , * , p).

3. It returns the list R * which is the shortest among R and R ′ .

Inria

Since A runs in polynomial time, so does A * , because the steps 2 and 3 above can trivially be performed in polynomial time. Let us now prove that A * gives an (α + 1)-approximate solution, that is sav

* (C) ≤ (α + 1)(|C| -|R * |). By Lemma 2, we have sav * (C) ≤ sav(C) + M (C) -1. But sav(C) ≤ α(|C| -|R|) ≤ α(|C| -|R * |),
M (s 1 ) ≥ M (s 2 ) ≥ • • • ≥ M (s n ) and M (t 1 ) ≥ M (t 2 ) ≥ • • • ≥ M (t m ).
The directed {0, 1, . . . , n} × {0, 1, . . . , m}-grid, denoted by G n,m is the digraph defined by

V (G n,m ) = {(i, j) | 0 ≤ i ≤ n and 0 ≤ j ≤ m} A(G n,m ) = {((i -1, j), (i, j)) | 1 ≤ i ≤ n and 0 ≤ j ≤ m} ∪ {((i, j -1), (i, j)) | 0 ≤ i ≤ n and 1 ≤ j ≤ m}.
For convenience, we set a h (i, j) = ((i -1, j), (i, j)) and a v (i, j) = ((i, j -1), (i, j)). The set A h (G n,m = {a h (i, j) | 1 ≤ i ≤ n and 0 ≤ j ≤ m} is the set of horizontal arcs, and the set A v (G n,m = {a v (i, j) | 0 ≤ i ≤ n and 1 ≤ j ≤ m} is the set of vertical arcs.

A edge-weighted digraph is a pair (G, w) where G is a digraph and w a weight function on its arcs, that is a function from A(D) into R. The length of a path U in an edge-weighted digraph (G, w) is the sum of the weights of its arcs: w(U ) = a∈A(U ) w(a).

Let w C be the weight function defined on A(G n,m ) by w C (a h (i, j)) = min{M (s i ), m -j} -1 and w C (a v (i, j)) = min{M (t j ), n -i} -1.

Let W (C) be the maximum length of a path in (G n,m , w C ). Observe that it is attained by a path from (0, 0) to one of the sides {n} × {0, 1, . . . , n} and {0, 1, . . . , n} × {n} because the weight of an arc is negative if and only if it is in Proof. Let R be a canonical routing list with no global triple that emulates C, and let B 1 , . . . , B q be the ordered list of its blocks. For 1 ≤ k ≤ q, let T ℓ k be the * -triple of B k , let r k be the number of triples of C routed by T ℓ k , and let i k (resp. j k ) be the number of source triples (resp. destination triples) with index at most ℓ k . We have

{a h (i, m) | 1 ≤ i ≤ n} ∪ {a v (n, j) | 1 ≤ j ≤ m}.
|R| = |C| -Σ with Σ = q k=1 (r k -1).
Let K s (resp. K t ) be the set of indices k such that T ℓ k is a source (resp. destination) triple. For k ∈ K s , s ′ k be the source of T ℓ k , and for k ∈ K t , t ′ k be the destination of T ℓ k . Assume k ∈ K s . When routing according to R, before considering the block B k , there are at most mj k triples of C with source s ′ k and at most M (s ′ k ) triples of C with source s ′ k . Therefore,

r k ≤ min{M (s ′ k ), m -j k }. Similarly, if k ∈ K t , then r k ≤ min{M (t ′ k ), n -i k }. Thus Σ ≤ k∈Ks (min{M (s ′ k ), m -j k } -1) + k∈Kt (min{M (t ′ k ), n -i k } -1).
Set u 0 = (0, 0) and u k = (i k , j k ) for 1 ≤ k ≤ q. Note that i k + j k = k for all 0 ≤ k ≤ q. The sequence U = u 0 , u 1 , . . . , u q can be seen as a path in the directed grid G n,m . Observe that if k ∈ K s then u k-1 u k is a horizontal arc and w From Theorem 23 we now derive that computing a source-based routing list and a destinationbased one, and taking the smaller one, yields a list reduces the list of at least one half of the optimum.

C (u k-1 u k ) = min{M (s i k ), m -j k } -1, and if k ∈ K t then u k-1 u k is a vertical arc and w C (u k-1 u k ) = min{M (t j k ), n -i k } -1. Hence w C (U ) = k∈Ks (min{M (s i k ), m -j k } -1) + k∈Kt (min{M (t j k ), n -i k } -1). Now since M (s 1 ) ≥ M (s 2 ) ≥ • • • ≥ M (s n ) and j 1 ≤ j 2 ≤ • • • ≤ j q , we have k∈Ks (min{M (s ′ k ), m- j k } -1) ≤ k∈Ks (min{M (s i k ), m -j k } -1). Similarly, k∈Kt (min{M (t ′ k ), n -i k } -1) ≤ k∈Kt (min{M (t j k ), n -i k } -1). Hence Σ ≤ w C (U ).
Theorem 24. Let C be a set of communication triples. Then Let us now prove W (C) ≤ 2Z(C). Let U be a longest path in (G n,m , w C ). We have

Z(C) ≤ sav(C) ≤ W (C) ≤ 2Z(C).
W (C) = w C (U ) = a h (i,j)∈A(U ) (min{M (s i ), m -j} -1) + a v (i,j)∈A(U ) (min{M (t j ), n -i} -1) ≤ a h (i,j)∈A(U ) (M (s i ) -1) + a v (i,j)∈A(U ) (M (t j ) -1)
Now for every 1 ≤ i ≤ n, U contains at most one arc in {a h (i, j) | 1 ≤ j ≤ m} and for every 1 ≤ j ≤ m, U contains at most one arc in {a v (i, j) | 1 ≤ i ≤ n}. Therefore

W (C) ≤ n i=1 (M (s i ) -1) + m j=1 (M (t j ) -1) ≤ Z -(C) + Z | (C) ≤ 2Z(C)
Since the source-based and destination-based routing lists can be computed in polynomial time, computing Z(C) Corollary 25. The Destination-based Heuristic is a 2-approximation for List Reduction.

Together with Lemma 22, this corollary immediately yields the following.

Corollary 26. There is a 3-approximation for With-global List Reduction.

Observe that W (C) is often smaller than 2Z(C). Therefore the Destination-based Heuristic often returns a routing list that saves more than a half of sav(C) triples. This leads to think that the approximation of 2 is not best possible.

Inria

For every M , the bound given by Theorem 28 is tight.

Proposition 29. For every integer M and n such that M ≤ n, there exists a set C of triples with n sources and n destinations such that (i) for every source, at most M communications with source s are assigned the same port, (ii) for every destination t, at most M of the communications with destination t are assigned the same port, and 6 Problem with two ports

(iii) rmin(C) = (n -M ) 2 + 2n -M . Proof. Let

Relation with the Feedback Arc Set problem

Let C be a set of communication triples, with source set S = {s 1 , . . . , s n }, destination sets T = {t 1 , . . . , t m } and port set {p 1 , p 2 }. We associate to C the n × m matrix A = A C defined by a i,j = 1 if (s i , t j , p 1 ) ∈ C, a i,j = -1 if (s i , t j , p 2 ) ∈ C, and a i,j = 0 otherwise. We also associate to C the bipartite digraph D C with vertex set S ∪ T in which for all s ∈ S and all t ∈ T , st is an arc if and only if (s, t, p 1 ) ∈ C, and ts is an arc if and only if (s, t, p 2 ) ∈ C. Hence, A C is the biadjacency matrix of the bipartite digraph D C .

Observe that C → A C is a one-to-one correspondence between the sets of communication triples, with source set S = {s 1 , . . . , s n }, destination sets T = {t 1 , . . . , t m } and port set {p 1 , p 2 }, and the {-1, 0, 1}-entry n × m matrices. Similarly, C → D C is a one-to-one correspondence between the sets of communication triples, with source set S = {s 1 , . . . , s n }, destination sets T = {t 1 , . . . , t m } and port set {p 1 , p 2 } and the labelled bipartite oriented graphs (an oriented graph is a digraph with no 2-cycles) with vertex set S ∪ T .

Let us make some easy observations on D C . In a digraph D, for any vertex v, we denote by A + D (v), or simply A + (v) when D is clear from the context, the set of arcs leaving v. Similalry, we denote by by A - D (v), or simply A -(D), the set of arcs entering v. Proof. Since in the operations described in Lemma 4 to obtain a canonical routing list, no communication triple is added, it suffices to prove the results for canonical routing lists. Moreover, if R contains a global triple ( * , * , p), then we can replace it by the (s, * , p) for all sources s of R without increasing the number of We prove the result by induction the sum of the numbers of sources and destinations of C, the result vacuously true if C is empty.

Let C be a non-empty set of communication triples and set D = D C . Let R be a canonical routing list with no global triple emulating C and let R ′ be the set of communication triples of R. For each block B i of R, let T i be the last triple of

B i . Set B ′ i = B 1 ∩ R ′ . We have B ′ i = B i \ {T i }.
Suppose that T 1 is a source triple, say (s, * , p). Set p ′ = {p 1 , p 2 } \ {p}. Then all the communication triples with source s and port p ′ must be routed before T 1 , and thus belong to

B 1 . Hence if p ′ = p 1 then A + D (s) ⊆ B ′ 1 , and if p ′ = p 2 then A - D (s) ⊆ B ′ 1 .
In particular, there is no cycle through s in D \ B ′ 1 . Let C ′ be the set of triples obtained from C by removing the triples with source s.

Then D ′ = D C ′ is the digraph D -s and R \ B 1 emulates C ′ . By the induction hypothesis, R ′ \ {B ′ 1 }, which is the set of communication triples of R \ B 1 corresponds to a feedback arc set in D -s. Therefore, R ′ is a feedback arc set in D.
Similarly, we get the result if T 1 is a destination triple.

The following lemma is a kind of reciprocal to Lemma 31.

Lemma 32. Let C be a set of communication triples with n sources and m destinations. If D C is acyclic, then there is a routing list emulating C containing at most n + m -1 source or destination triples and no other triples.

Proof. By induction on n + m, the result holding trivially when C has one source and one destination. Suppose that C is a set of communication triples with n sources and m destinations, where n + m ≥ 3. If D C is acyclic, then it contains a vertex v with in-degree 0. If this vertex is a source (resp. destination), then all the communication triples with source (resp. destination) v have port p 1 (resp. p 2 ). Hence using first the triple (v, * , p 1 ) (resp. ( * , v, p 2 )), all communication triples of C with source (resp. destination) v are routed. Therefore, the set C ′ of communication triples that remain to be routed has one source or destination less than C. Moreover D C ′ is D Cv, so it is acyclic. Thus, by the induction hypothesis, there is a routing list emulating C ′ containing n + m -2 source or destination triples. and no other triples. The concantenation of (v, * , p 1 ) (resp. ( * , v, p 2 )) with this list gives the desired routing list emulating C. Corollary 45. sc(D) is equal to the optimal solution of the fractional relaxation of the ILP (6) and thus can be computed in polynomial time using linear programming.

Remark 46. In fact, Theorem 44 derives from the fact that {x | Ax ≥ b, x ≥ 0} is an integral polyhedron. This implies in particular that an integral optimal solution can be found in polynomial time.

Polynomial-time algorithm when the associated digraph is acyclic

Theorem 47. There is a polynomial-time algorithm that computes rmin C when D C is acyclic.

The proof of Theorem 47 is based on the following integer linear programming formulation.

Minimize

x (s,t,p) + x ( * ,t,p) + x (s, * ,p) Subject to:

x (s,t,p) + x ( * ,t,p) + x (s, * ,p) ≥ 1 for all (s, t, p) ∈ C p x ( * ,t,p) ≤ 1 for all t ∈ T p x (s, * ,p) ≤ 1 for all s ∈ S x (s,t,p) , x ( * ,t,p) , x (s, * ,p) ∈ {0, 1}

(x + v + x - v )
Subject to:

x uv + x + u + x - v ≥ 1 for all uv ∈ A(D) x + v + x - v ≤ 1 for all v ∈ V (D) x a , x + v , x - v ∈ {0, 1} (8)
Let us prove that this ILP computes rmin(C) if D C is acyclic.

Proposition 48. If D C is acyclic, then the ILP (7) computes rmin(C).

Proof. Let x * be an optimal solution of the ILP [START_REF] Giroire | Optimizing Rule Placement in Software-Defined Networks for Energy-aware Routing[END_REF] for C and let r * be the optimal value of the objective function. Let R be a shortest routing list with no global triples emulating C. Let x R be the characteristic function of R, that is x R τ = 1 if the the triple τ ∈ R, and x R τ = 0 otherwise. For all (s, t, p) ∈ C, the triple is routed by R so x R (s,t,p) + x R ( * ,t,p) + x R (s, * ,p) ≥ 1. Now since R is a shortest list, there is at most one destination triple per destination t, so for all t ∈ T , p x R ( * ,t,p) ≤ 1. Similarly, there is at most one source triple per source s, so for all s ∈ S, p x R (s, * ,p) ≤ 1. Therefore, x R satisfies the constraints of [START_REF] Giroire | Optimizing Rule Placement in Software-Defined Networks for Energy-aware Routing[END_REF]. Moreover, by definition |R| =

x R (s,t,p) + x R ( * ,t,p) + x R (s, * ,p) . Therefore r * ≤ |R| = rmin(C). Reciprocally, let us construct a routing list R * with no global triples emulating C from x * . Let C ′ be the set of communication triples (s, t, p) such that x * (s,t,p) = 1, let R ′ be any list over C ′ , and set C ′′ = C \ C ′ . Since D C was acyclic, D C ′′ is also acyclic. Moreover. the set Z of destination and source triples τ such that x * τ = 1 corresponds to a star cover of D C ′′ . Indeed, the first constrainst implies that for every arc uv of D C ′′ , u ∈ V + or v ∈ V -because x * (s,t,p) = 0, and the second and third constraints imply that two stars have distinct centres. Hence, as in Lemma 39, there is a convenient routing list R ′′ of size |Z| emulating C ′′ . The concatenation of R ′ and R ′′ is then a routing list with no global triples emulating C. Hence

Conclusion

We studied the complexity of several variants Routing List and of List Reduction. We provide results of NP-completeness, of Fixed-Parameter Tractability and approximation algorithms.

We leave several questions as open problems:

• We describe several kernels for our problems. Is it possible to find smaller kernels? In particular, we obtained a quadratic kernel for List Reduction parameterized by z.

Problem 13. Does List Reduction parameterized by z admits a linear kernel?

• The Destination-based Heuristic is a 2-approximation for List Reduction. However, observe that the heuristic often returns a routing list that saves more than a half of sav(C) triples. This leads to think that the approximation of 2 is not best possible.

Problem 27. What is the best approximation ratio for List Reduction?

• We proved the NP-Completeness of Routing List by a reduction to Feedback Arc Set. Knowing that Feedback Arc Set is APX-complete, Problem 37. Is Routing List also APX-complete? For which approximation ratio?

  Input: A set C of communication triples and an integer z Question: sav(C) ≥ z? We shall also consider a variation of the problem in which another kind of triples, called global triples, may be used. Such a triple is of the form ( * , * , p) and mean that all communications leave on port p. Hence, given a set of communication triples C, the problem is to find the shortest routing list with global triples that emulates C. Let us denote by rmin * (C) the minimum number of triples in a routing list with global triples emulating C, and let sav * (C) = |C|rmin * (C). We study the following variations of Routing List and List Reduction. With-global Routing List: Input: A set C of communication triples with at most k ports, and an integer r. Question: rmin * (C) ≤ r? With-global List Reduction Input: A set C of communication triples and an integer z Question: sav * (C) ≥ z? Note that rmin and rmin * (resp. sav and sav * ) are closely related parameters, in the sense of the two following lemmas. Lemma 1. Let C be a set of communication triples in which n sources appear. rmin * (C) ≤ rmin(C) ≤ rmin * (C) + n -1. Proof. Clearly, rmin * (C) ≤ rmin(C). Let R be a shortest routing list with global triples. Trivially, R contains at most one global triple, because all communication triples are routed by a global triple. Let s 1 , . . . , s n be the sources appearing in C. If R has a global triple ( * , * , p), then it can be replaced by the n source triples (s i , * , p), 1 ≤ i ≤ n, to obtain a routing list with no global triples. Hence, rmin(C) ≤ rmin * (C) + n -1. Inria Let M (C) be the maximum number of triples of C with the same port. Lemma 2. Let C be a set of communication triples. sav(C) ≤ sav * (C) ≤ sav(C) + M (C) -1. Proof. Clearly, sav(C) ≤ sav * (C). Let us now prove that sav * (C) ≤ sav(C) + M (C) -1. Let R be a shortest routing list with global triples. We have |R| = |C|sav * (C). Trivially, R contains at most one global triple. If R contains no global triple then sav(C) ≥ |C| -|R|, and so sav * (C) ≤ sav(C).

Lemma 3 .

 3 Let C be a set of communication triples and R be a routing list emulating C. Then the routing list R ′ obtained from R by • deleting the useless communication triples (the ones that route no triples),

Theorem 5 . 1 -

 51 Port Routing List can be solved in polynomial time.

Theorem 6 . 2 -

 62 Port Routing List is NP-complete. Proof. We use a reduction from the Feedback Arc Set problem. Let D be a bipartite graph with bipartition (A, B). Let A = {a 1 , . . . , a n } and B = {b 1 , . . . , b m }. Consider the set of communication triples

Conjecture 10 .

 10 For every k ≥ 2, k-Port Routing List and k-Port With-global Routing List are NP-complete even if C is restricted to be a full set of communication triples. 4 Parameterized complexity 4.1 List Reduction and variants Theorem 11. For every k ≥ 1, k-port List Reduction parameterized by z admits a linear kernel, and so is FPT.

3 .

 3 It remains to prove the claim. Clearly, sav * (C) ≥ sav * (C \ C(p 1 )).

Claim 17 . 1 .

 171 Assume that a routing list R emulating C has size at most r.(i) If s is a forced source, then there is a unique port p s such that |C(s, p s )| ≥ r. Moreover (s, * , p s ) ∈ R and at most r -1 triples of C have source s and port different from p s . (ii) If s is a loose source, then |C(s)| ≤ 2r -1.

  s) are routed by different triples, so |C(s)| ≤ r. If there is a triple (s, * , p) in R, then all triples of C(s) \ C(s, p) are routed by different triples, so |C(s) \ C(s, p)| ≤ r -1, and so |C(s)| ≤ 2r -1 because |C(s, p)| ≤ r since s is a loose source. This proves (ii). ♦ Let s be a source in S ′ . Let T 1 (s) be the set of destinations of the triples in C(s) \ C(s, p s ) if s is forced, and in C(s) if s is loose. Set T 1 = s∈S ′ T 1 (s) and T 2 = T \ (T ′ ∪ T 1 ). The kernelization algorithm computes T 1 (s) for all s ∈ S ′ . If a source s is forced and |T 1 (s)| ≥ r, then by Claim 17.1-(i), rmin(C) > r, and we return 'No'. In the same way, If a source s is forced and |T 1 (s)| ≥ 2r, then by Claim 17.1-(ii), rmin(C) > r, and we return 'No'. Henceforth, we may assume that |T 1 (s)| ≤ 2r -1 for every s ∈ S ′ and so |T 1 | ≤ (2r -1)|S ′ |.

  and by definition, |C| -|R * | ≥ |C| -|R ′ | = M (C) -1. It follows that sav * (C) ≤ (α + 1)(|C| -|R * |).

5. 2

 2 Approximate upper bounds on sav and sav * Let C be a set of communication triples with destination set S and destination set T . Set n = |S| and m = |T |. We can order S and T by decreasing order according to the function M . That is

Theorem 23 .

 23 sav(C) ≤ W (C) and rmin(C) ≥ |C| -W (C), for all set of communication triples C.

  Thus Σ ≤ W (C), and so sav(C) ≤ W (C) and |R| ≥ |C| -W (C).

Proof.

  By Equation (1) and Theorem 23, we have Z(C) ≤ sav(C) ≤ W (C).

Fact 30. 1 . 2 . 3 .

 123 The communication triples of C are in one-to-one correspondence to the arcs of D C . 2. If s ∈ S, then A + (s) corresponds to the set of communication triples with source s and port p 1 and A -(s) corresponds to the set of communication triples with source s and port p If t ∈ T , then A + (t) corresponds to the set of communication triples with destination t and port p 1 and A -(s) corresponds to the set of communication triples with destination t and port p 2 . Inria In view of Fact 30.1, for sake of clarity, we often identify the arcs of D C with their corresponding communication triples. Lemma 31. Let C be a set of communication triples and R be a routing list of C. The set of communication triples in R corresponds to a feedback arc set in D C .

  The previous two lemmas implies that rmin * (C) and rmin(C) are closely related to fas(D C ). Corollary 33. If C be a set of communication triples with n sources and m destinations, then fas(D C ) + 1 ≤ rmin * (C) ≤ rmin(C) ≤ fas(D C ) + n + m -1. Proof. Let R be a canonical routing list emulating C. By Lemma 31, there are at least fas(D C ) communication triples in R. Moreover, R contains at least one * -triple because it is canonical. Hence |R| ≥ fas(D C ) + 1. Therefore, rmin * (C) ≥ fas(D C ) + 1. Let C 0 be the set of communication triples corresponding to a minimum feedback arc set F of D C . Set C ′ = C \ C 0 . The digraph D ′ C is D C \ F and so is acyclic. Therefore, by Lemma 32, Theorem 44 (Hoffman and Kruskal [10]). If A is totally unimodular and b is an integral vector, then the linear programme Minimize c T x subject to : Ax ≥ b x ≥ 0 has an integral optimal solution (if it has one).

  This translates in the following ILP on D = D C , which extends[START_REF] Giroire | Minimizing routing energy consumption: from theoretical to practical results[END_REF]

  rmin(C) ≤ |R ′ | + |R ′′ | = |C ′ | + |C ′′ | = |C|.Lemma 49. ILP (7) can be solved in polynomial time.Proof. Let M D be the matrix associated to ILP[START_REF] Giroire | Optimizing Rule Placement in Software-Defined Networks for Energy-aware Routing[END_REF]. Then M D = [I A D ]. Since A D is totally unimodular, M D is also totally unimodular. Thus, by Theorem 44, ILP (7) can be solved in polynomial time.Proof of Theorem 47. It follows directly from Proposition 48 and Lemma 49.

  s forced source of C} ∪ {(s ′′ , t, p t ) | s ′′ ∈ S ′′ and t forced destination of C} Claim 17.3. rmin(C) ≤ r if and only if rmin(C ′′ ) ≤ r. Proof. C and C ′′ coincide on C # , and, by construction of C ′′ , they have the same forced sources and destinations. Moreover, by Claim 17.2, for a shortest routing list emulating C (resp. C ′′ ) the triples not in C # are routed by the source or destination triples of the forced sources and destinations. Therefore a shortest routing list emulating C is also a routing list emulating C ′′ (provided it has size at most r), and vice versa. ♦ Claim 17.3 states that C and C ′′ are equivalent. Now C # has size at most |S ′

  C be the set of triples (s, t, p(s, t)) for 1 ≤ s ≤ n and 1 ≤ t ≤ n such that Conditions (i) and (ii) are clearly satisfied. Consider now the routing list R which is the concatenation of {(s, t, p(s, t)) | 2 ≤ s ≤ n and 2 ≤ t ≤ n}, {( * , t, p(1, t) | 2 ≤ t ≤ n} and{(s, * , p(s, 1) | 1 ≤ s ≤ n}. One can check that R emulates C and |R| = (n -M ) 2 + 2n -M . Thus rmin(C) ≤ (n -M ) 2 + 2n -M , and so by Theorem 28, rmin(C) = (n -M ) 2 + 2n -M .

	p(s, t) =	s M	+	t M	mod	n M	.

RR n°8658

route des Lucioles -BP 93 06902 Sophia Antipolis Cedex Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

* This work has been partially supported by ANR project Stint under reference ANR-13-BS02-0007, ANR program Investments for the Future under reference ANR-11-LABX-0031-01, ANR VISE, ANR Skyflow, CNRS-FUNCAP project GAIATO, the associated Inria team AlDyNet, the project ECOS-Sud Chile and Paca Region.

Problem 27. What is the best approximation ratio for List Reduction?

In addition, W (C) can be computed in polynomial time. Indeed the longest path from a vertex u to a set X of vertices in a edge-weighted acyclic digraph (D, w) can be computed as follows. First we find a topological order of D, that is an order v 1 , . . . , v n such that if v i v j ∈ A(D) then i < j. We initialize p(u) = 0 and p(v) = -∞ for all v ∈ V (D) \ {u}. Then for i = 1 to n, we compute p(v i ) := max{p(v j ) + w(v j v i ) | v j v i ∈ A(D)} and we return max{p(x), x ∈ X}. Finding a topological order of an acyclic digraph can be done in linear time, that is in time O(|V (D)| + |A(D)|). Thus the above algorithm computes the longest path from u to X in linear and thus can be used to compute W (C) in O(n + m) time. Therefore computing the ratio W (C)/Z(C) gives in polynomial an upper bound on the approximation ratio of the above heuristic for each C.

Theorem 23 is also useful because we can sometimes estimate W (C) and thus obtain good lower bounds on rmin. Forthwith is an example.

Theorem 28. Let S be a set of n sources, T be a set of n destinations. Let C be a set of communication triples for S × T . If for every source, at most M communications with source s are assigned the same port, and for every destination t, at most M of the communications with destination t are assigned the same port, then rmin(C) ≥ (n -M ) 2 + 2n -M and rmin * (C) ≥ (n -M ) 2 + n -M + 1.

Proof. We shall prove rmin(C) ≥ (n -M ) 2 + 2n -M . By Lemma 1, this implies rmin * (C) ≥ (n -M ) 2 + n -M + 1.

Since |C| = n 2 , by Theorem 23, it suffices to prove that

Let k 0 be the greater index such that i k0 ≤ n -M and j k0 ≤ n -M . By symmetry of this edge-weighted digraph, we may assume that i k0+1 = n -M + 1. Let us prove that U has the following properties.

(a) U contains no subpath (i, j), (i + 1, j), (i + 1, j + 1) for n -M ≤ i ≤ n and 1 ≤ j < n -M .

(b) U does not end with the subpath (n -M, j), . . . , (n, j) for 1 ≤ j < n -M .

(c) U does not end with the subpath (i, j), (i, j +1), (i+1, j +1), . . . , (n, j +1) for n-M ≤ i ≤ n

and n -M ≤ j ≤ n -1.

If U has a subpath (i, j), (i + 1, j), (i + 1, j + 1) for some i and j such that n -M ≤ i ≤ n and 1 ≤ j < n -M , then the path U ′ obtained from U by replacing (i, j), (i + 1, j), (i + 1, j + 1) by (i, j), (i, j + 1), (i + 1, j + 1) satisfies w C (U ′ ) = w C (U ) + 1, a contradiction to the maximality of w C (U ). This proves (a).

If U ends with the subpath (n -M, j), . . . , (n, j) for some j such that 1 ≤ j < n -M , then the sequence U ′ obtained from U by replacing (n -M, j), . . . , (n, j) by (n -M, j), (n -M, j + 1), . . . , (n, j + 1) satisfies w C (U ′ ) = w C (U ) + n -M , a contradiction to the maximality of w C (U ).

This proves (b).

If U ends with the subpath (i, j), (i, j + 1), (i + 1, j + 1), . . . , (n, j + 1) for some a and b such that n -M ≤ i ≤ n and n -M ≤ j ≤ n -1, then the path U ′ obtained from U by replacing (i, j), (i+1, j), (i+1, j +1), . . . , (n, j +1) by (i, j), (i+1, j), . . . , (n, j) satisfies w C (U ′ ) = w C (U )+1, a contradiction to the maximality of w C (U ). This proves (c). Now (a) and (b) imply that u k0 = (n -M, n -M ) = u 2n-2M and (c) implies that U ends with (n -M, n -M ), . . . , (n -M, n). In particular, the path U has 2n -M arcs. Moreover, each arc of U has weight M -1.

there is a list R ′ of size at most n + m -1 emulating C ′ . Now the list C 0 , R ′ has size at most fas(D C ) + n + m -1 and emulates R. Proof. Let R be a canonical routing list with no global triple. Since a block routes only the communication with a single source or communication with a single column, the number of blocks is at most max{n, m} communications. Since the set of communications is full, there are nm communications. Hence, there must be at least nm/ max{n, m} = min{n, m} blocks. Since a blocks contains a * -triple, they are at least min{n, m} * -triples in R. As they are at least fas(D C ) communication triples in R. Hence R s of size at least fas(D C ) + min{n, m}.

Deriving approximation algorithms

Van Zuylen [START_REF] Van Zuylen | Linear programming based approximation algorithms for feedback set problems in bipartite tournaments[END_REF] gave a 4-approximate polynomial-time algorithm for Feedback Arc Set in complete bipartite tournaments.

We can use this approximation algorithm for Feedback Arc Set to build polynomial-time approximation algorithms for some sets ofcommunication triples. We can also derive approximation algorithms for almost full sets of communication triples. For convenience, we present the result when the number of sources equals the number of destinations. They can easily be extended to the case when those numbers differ.

Theorem 36. Let α be a positive real number. There is a polyomial-time max{4, 2 + 2α}approximate algorithm for Routing List with no global triple restricted to the sets of at least n 2α • n communication triples with n sources, n destinations and two ports.

Proof. Let C be a set of at least n 2 -α•n communication triples with n sources and n destinations and two ports.

Let D 1 (resp. D 2 ) be the digraph obtained by adding an arc st (resp. ts) for each communication (s, t) not appearing in C. Observe that D i corresponds to the set of communication triples obtained from C by routing all missing communications to the port p i . Both D 1 and D 2 are bipartite tournaments.

Consider a minimum feedback arc set S of D C , and let σ = v 1 , . . . , v 2n be an ordering such that S is σ-feedback. For each missing communication (s, t) in C, the arc st is backward if s = v i , t = v j and j < i, otherwise it is forward. Observe that st is forward (resp. backward) if and only if ts is backward (resp. forward). Let B 1 = {st | st is backward} and Problem 37. Can we derive from the fact that Feedback Arc Set is APX-complete, that our problem is also APX-complete? For which approximation ratio?

The complementary problem to Feedback Arc Set is the following. Maximum Acyclic Subdigraph: Arora et al. [START_REF] Arora | A new rounding procedure for the assignment problem with applications to dense graph arrangement problems[END_REF] proved that Maximum Acyclic Subdigraph admits a polynomial-time approximation scheme on dense instances. A dense digraph is one in which the number of arcs is Ω(n 2 ).

Theorem 38 (Arora et al. [START_REF] Arora | A new rounding procedure for the assignment problem with applications to dense graph arrangement problems[END_REF] ). Maximum Acyclic Subdigraph has an n O(1/ǫ 2 ) time approximation scheme on dense graphs.

Relation with the Star Cover problem

A routing list is convenient if it contains only source triples and destination triples. By Lemmas 31 and 32, there is a convenient routing list emulating a set of communication triples C if and only if D C is acyclic.

In view of the results of Subsection 6.1, a general method to compute a routing list emulating a given set of communication triples C is to first compute a set R ′ of communication triples corresponding to a feedback arc set of D C , and then to compute a convenient routing list for C ′ = C \ R ′ . The concatenation of R ′ and R ′′ would then be a routing list emulating C. In fact, the approximation algorithm described in Subsection 6.2 use this approach. But they use a non-optimal algorithm for finding the convenient routing list in the second phase.

In this subsection, we show how to optimize the second phase. That is, once the first phase is done, and we are left with the routing list C ′ , find a shortest convenient routing list emulating C ′ .

Convenient Routing List:

Input: A set C of communication triples with two ports, such that D C is acyclic. Find: a convenient routing list emulating C with minimum size?

We first show how this problem is equivalent to the Star Cover Problem for D C . We then show how to solve the Star Cover Problem for an arbitrary graph in polynomial time.

An out-star is a digraph consisting of one vertex, called the centre, dominating all the others. An in-star is the converse of an out-star, that is a digraph consisting of one vertex, called the centre, dominated by all the others. A star is either an out-star or an in-star. A star cover of a digraph D is a set of stars S with disjoint centres such that A(D) = S∈S A(S).

We are interested in finding the minimum size of a star cover of D, denoted by sc(D), and a minimum star cover of D, that is a star cover with sc(D) stars.

Star Cover

Input: a digraph D. Find: a minimum star cover.

Observe that if S is a star cover, then the pair (V + , V -), where V + and V -is the set of centres of out-stars and in-stars, respectively, in S, satisfies the following property:

For every arc uv, either u ∈ V + or v ∈ V -. (⋆) Reciprocally, assume that (V + , V -) is a pair of disjoint sets of vertices satisfying (⋆). For every vertex v, let S + v be the out-stars with centre v and arcs A + (v), and S - v be the in-star with centre v and arcs

Therefore, for convenience, we shall consider that a star cover is pair (V + , V -) of disjoint sets of vertices satisfying (⋆).

Lemma 39. Let C be a set of communication triples such that D C is acyclic. There is a convenient routing list of size r emulating C if and only if D C has a star cover of size r.

Proof. Let R be a convenient routing list emulating C. Set

Let st be an arc of D C with s ∈ S and t ∈ T . The communication triple (s, t, p 1 ) of C is routed by R. So either (s, * , p 1 ) or ( * , t, p 1 ) is in R. Hence either s ∈ V + or t ∈ V -. Similarly, if ts is an arc of D C with s ∈ S and t ∈ T , then either t ∈ V + or s ∈ V -. Therefore, (V + , V -) is a star cover of D C .

Reciprocally, let (V + , V -) be a star cover of D C . Set

Futhermore, because D C is acyclic, we can order R + in such a way that a triple (s, * , p 1 ) is in front of (resp. goes after) ( * , t, p 2 ) whenever (s, t, p 1 ) ∈ C (resp. (s, t, p 2 ) ∈ C). It suffices to take the triples of R + according to a linear ordering v 1 , . . . , v n+m of the vertices of D C with no arcs vjv i with i < j in D. Similarly, we can order R -in such a way that a triple (s, * , p 2 ) is in front of (resp. goes after) ( * , t, p 1 ) whenever (s, t, p 2 ) ∈ C (resp. (s, t, p 1 ) ∈ C). Now it is easy to check that the concatenation of R + and R -is a convenient routing list of size |V + | + |V -| that emulates C.

Solving Star Cover by a purely combinatorial algorithm

Lemma 40. Let D be a digraph and (V + , V -) a star cover of D. Let P be a path in D. If the initial vertex of P is in V -, then all vertices of P are in V -.

Inria

Proof. By induction on the length of P , the result holding trivially if it has length 0. Let (v 0 , . . . , v p ) be a path of length p ≥ 1 such that v 0 ∈ V -. By the induction hypothesis applied to the path (v 0 , . . . , v p-1 ),

If u and v are two vertices, then a (u, v)-path is a path with initial vertex u and terminal vertex v. If U is a set and v a vertex, then a a (U, v)-path is a path with initial vertex in U and terminal vertex v. A digraph is strongly connected or strong, if for any pair (u, v) of vertices, there is a Proof. Let (V + , V -) be a star cover of D.

Assume that V -contains a vertex u. For any vertex v of D, there is a (u, v)-path, because D is strong. Thus, by Lemma 40, v ∈ V -. Hence V -= V (D).

By directional duality, if V + is not empty, then

The transitive closure of an acyclic digraph D is the digraph T D with vertex set V (D) and arcs the pairs (u, v) of distinct vertices such that there exists a (u, v)-path in D. A stable set in a digraph is a set of pairwise non-adjacent vertices. The stability number of a digraph D, denoted α(D), is the maximum size of a stable set.

Proof. Let D be an acyclic digraph.

Let (V + , V -) be a minimum star cover of D. Set U = V (D) \ (V + ∪ V -). We claim that U is a stable set in T D . Indeed, suppose for a contradiction, that U is not a stable set. Then there are two vertices u and v in U such that (u, v) is an arc in T D . Hence, by definition of transitive closure, there is a (u, v)-path P in D. Let w be the second vertex of P . Since u is in U , vertex w must be in V -. But in D, there is a (w, v)-path, namely Pu. So, by Lemma 40, v ∈ V -, a contradiction. This proves our claim that U is a stable set of T D .

Hence

Reciprocally, let U be a maximum stable set in T D . Since U is maximal, in T D , every vertex v of V (D) \ U is either dominated by a vertex of U or dominates a vertex of U . Let V + (resp. V -) be the set of vertices of V (D) \ U that dominates (resp. is dominated by) a vertex of U in T D .

We first claim that V + and V -are disjoint. Indeed, assume for a contradiction that a vertex v is in V + ∩ V -. Then there is a vertex u 1 in U dominating v in T D , and a vertex u 2 in U dominated by v (possibly u 1 = u 2 ). In D, there is a (u 1 , v)-path P 1 and a (v, u 2 )-path. The concatenation of P 1 and P 2 contains a (u 1 , u 2 )-path in D, which contradicts the fact that U is a stable set in D if u 1 = u 2 , or that D is acyclic if u 1 = u 2 . This proves our first claim.

We also claim that if uv is an arc of D, then either u ∈ V + or v ∈ V -. Indeed, if u / ∈ V + , then u ∈ U ∪ V -. Thus there is a (U, u)-path from U to u in D (reduced to the vertex u when u ∈ U ). Adding the arc uv to this path we obtain a (U, v)-path in D. So v ∈ V -. This proves our second claim.

The two claims shows that (

It is well-known that the transitive closure of any acyclic digraph corresponds to a strict partial order. Therefore, the underlying graph of a transitive closure is a comparability graph. Comparability graphs are perfect, so a maximum stable set can be found in polynomial time in such graphs. Hence, for a given acyclic digraph D, a maximum stable set of T D can be computed in polynomial time, and so by Lemma 42 (and its proof), one can find in polynomial time a minimum star cover.

Theorem 43. Star Cover is polynomial-time solvable.

Proof. Let us present a procedure star-cover(D), that given a digraph D returns a minimum star cover of D. The idea is to reduce to the case when D is acyclic. When D is acyclic, the procedure runs as we just explained, so we only detail here how to reduce to this case.

We first compute the strong components of D. If D is not acyclic, one of these components, say C, is not trivial. Let U + (resp. U -) be the set of vertices of V (D -C) having an outneighbour (resp. in-neighbour) in C. Let D 1 be the digraph obtained form D -C by adding all the arcs from U + to U -.

Let (V + , V -) be a star cover of D. By Corollary 41,

In the first case, all arcs entering C must have their tail in V + , so U + ⊆ V + . In the second case, U + ⊆ V -. In both cases, it implies that every arc from U + to U -has its tail in V + or its head in V + . Hence (V + \ V (C), V -\ V (C)) is a star cover of D 1 .

Reciprocally, assume that S 1 = (V - 1 , V + 1 ) is a star cover of D. Then necessarily

) is a star cover of D. To summarize, the mapping θ that associates to each star cover S = (V + , V -) of D, the pair (V -∩ V (C), V + ∩ V (C)) is a surjection into the set of star covers of D 1 . Moreover, S| = |θ(S)| + |C|.

Therefore the algorithm makes a recursive call to star-cover(D 1 ), which returns a minimum star cover of (V - 1 , V + 1 ) of D 1 . If U + ⊆ V + 1 , then it returns (V + 1 ∪ V (C), V - 1 ), otherwise it returns (V + 1 , V - 1 ∪ V (C)).

Solving Star Cover via linear programming

The Star Cover problem can be formulated as the following ILP.

Minimize

v∈V (D)

Subject to:

Let A D be the matrix associated to this ILP, and let B D be the bipartite graph defined by

After multiplying the rows of A D corresponding to the second constraint by -1, the resulting matrix A ′ D is the incidence matrix of B D . It is well known that the incidence matrix of a bipartite graph is totally unimodular. Thus A ′ D is totally unimodular and so is A D .

Inria