Emmanuelle Anceaume
email: emmanuelle.anceaume@irisa.fr

Yann Busnel
email: yann.busnel@univ-nantes.fr

Sébastien Gambs
email: sebastien.gambs@irisa.fr

Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes

Keywords: Uniform sampling, unstructured peer-to-peer systems, ergodicity, Byzantine adversary

come

Introduction

We consider the problem of uniform sampling in large scale open systems with adversarial (Byzantine) nodes. Uniform sampling is a fundamental primitive guaranteeing that any individual in a population has the same probability to be selected as sample. This property is of utmost importance in systems in which the population is continuously evolving and where it is impossible to capture the full complexity of the network through global snapshots. By collecting random subsets of information over the network, one can infer at almost no cost some global characteristic of the whole population (such as its size, its topological organization, its resources, . . . ). Therefore uniform sampling finds its root in many problems such as data collection, dissemination, load balancing, and datacaching [START_REF] Jelasity | Gossipbased Peer Sampling[END_REF][START_REF] Bertier | On Gossip and Populations[END_REF][START_REF] Karger | Simple Efficient Load Balancing Algorithms for Peer-to-Peer[END_REF][START_REF] Lv | Search and Replication in Unstructured Peer-to-Peer Networks[END_REF].

Providing unbiased (i.e., uniform) sampling in these open systems is a challenging issue. First, this primitive must cope with the continuous change of the network structure caused by nodes departures and arrivals. Nevertheless, it has been shown through simulations [START_REF] Jelasity | Gossipbased Peer Sampling[END_REF][START_REF] Massoulié | Peer Counting and Sampling in Overlay Networks: Random Walk Methods[END_REF] and analytic studies [START_REF] Busnel | A Formal Characterization of Uniform Peer Sampling Based on View Shuffling[END_REF][START_REF] Gurevich | Correcness of Gossip-Based Membership under Message Loss[END_REF][START_REF] Bakhshi | An Analytical Model of Information Dissemination for a Gossip-based Protocol[END_REF] that simply maintaining a partial and small local view of node identifiers (ids) is sufficient to provide near uniform sampling. This can be achieved through gossip-based algorithms [START_REF] Jelasity | Gossipbased Peer Sampling[END_REF][START_REF] Karp | Randomized Rumor Spreading[END_REF][START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF] or through random walks [START_REF] Massoulié | Peer Counting and Sampling in Overlay Networks: Random Walk Methods[END_REF][START_REF] Stutzbach | On Unbiased Sampling for Unstructured Peer-to-Peer Networks[END_REF][START_REF] Bollobás | Random Graphs -2nd Edition[END_REF][START_REF] Zhong | Non-uniform Random Membership Management in Peer-to-Peer Networks[END_REF]. Gossip-based algorithms mainly consist, for each node v in the system, in periodically selecting some other node w in v's local view and exchanging information. Information can either be pushed to other nodes or pulled from other nodes. Over time, information spreads over the system in an epidemic fashion allowing each node to continuously update its local view with fresh node ids. On the other hand, a random walk on a network (which can be represented as a graph) is a sequential process, starting from an initial node v, which consists in visiting a node in v's neighborhood according to some randomized order. In its simpler form, the next node is chosen uniformly at random among the neighbors, while more sophisticated choices are implemented to cope with the bias introduced towards high degree nodes (for instance, through the Metropolis-Hastings algorithm [START_REF] Awan | Distributed Uniform Sampling in Unstructured Peer-to-Peer Networks[END_REF]).

An important issue that seriously hampers the feasibility of uniform sampling in open and large scale systems is the unavoidable presence of malicious nodes. Malicious (or Byzantine) nodes typically try to manipulate the system by exhibiting undesirable behaviors [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF]. In our context, they try to subvert the system by launching targeting attacks against nodes in the aim of biasing uniformity by isolating honest nodes within the system. This is quickly achieved by poisoning local views of honest nodes with malicious node ids. For instance in unstructured graphs, a number of push operations logarithmic in the size of local views is sufficient to fully eclipse honest nodes from the local view of a node [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF], while in structured graphs, a linear number of join operations is required [START_REF] Awerbuch | Group Spreading: A Protocol for Provably Secure Distributed Name Service[END_REF]. Recent works have been proposed to detect and exclude these adversarial behaviors [START_REF] Jesi | Secure Peer Sampling[END_REF][START_REF] Singh | Eclipse Attacks on Overlay Networks: Threats and Defenses[END_REF][START_REF] Liu | Detecting Malicious Beacon Nodes for Secure Location Discovery in Wireless Sensor Networks[END_REF] by observing that malicious nodes try to get an in-degree much higher than honest nodes in order to isolate them. Extensive simulations [START_REF] Jesi | Secure Peer Sampling[END_REF] have shown that this approach is only highly effective for a very small number of malicious nodes (i.e., in O(log |S|) where |S| is the size of the network S), otherwise detection mechanisms may boil down to false positive detection (i.e., detection of honest nodes).

On the other hand, when the system is harmed by a large number of malicious peers (i.e., a linear proportion of the nodes of the system), which is definitively a realistic assumption in peer-to-peer systems [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF][START_REF] Douceur | The Sybil Attack[END_REF], additional mechanisms are required to prevent targeted attacks from succeeding. Specifically, in structured peer-to-peer systems, analytical studies have shown that applying the "induced churn" principle allows to defend the system against adversarial behaviors, either through competitive induced churn strategies [START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF], or through global induced churn [START_REF] Anceaume | Analytical Study of Adversarial Strategies in Cluster-based Overlays[END_REF]. Briefly, this principle states that, by forcing nodes to periodically change their position in the graph, malicious peers cannot predict the evolution of the state of the system after a given sequence of join and leave operations. By taking advantage of the properties of structured graphs, the authors of both papers have shown that, with high probability, any node is equally likely to appear in the local view of each other honest node in a number of rounds polynomial in the size of the system. Unfortunately, in unstructured peer-to-peer systems, nodes cannot rely on the topological nature of structured graphs to reject new node ids that do not conform to the imposed distance function (contrary to structured networks [START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF][START_REF] Anceaume | Analytical Study of Adversarial Strategies in Cluster-based Overlays[END_REF]). To circumvent this issue, Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] rely on the properties of min-wise independent permutations, which are fed by the streams of gossiped node ids, to eventually converge towards uniform sampling on the node ids. More precisely, these authors have derived an upper bound on the expected time T s to converge towards unbiased (uniform) samples. However, by construction, this convergence is definitive in the sense that once a random sample has been locally observed it is kept as a local sample forever. As a consequence, beyond the time limit T s , no other node ids received in the input stream can ever appear in the random sample. The property of a sampler to guarantee that each received node id infinitely often has a non-null probability to locally appear as a sample is called the ergodic sampling property (this property is formally defined later in the paper).

Intuitively, this lack of adaptivity seems to be the only defense against adversarial behavior when considering bounded resources (memory and bandwidth). This paper is devoted to the formal analysis of the conditions under which uniform and ergodic sampling is feasible or not. More precisely, the main contribution of this paper is to show necessary and sufficient conditions under which uniform and ergodic sampling is achievable in unstructured peer-to-peer systems potentially populated with a large proportion of Byzantine nodes. Specifically, let S represent the wide collection of nodes in the system, and k < 1 the proportion of malicious nodes in S. Let δ m be the number of (not necessarily unique) malicious node ids gossiped by malicious nodes during a time interval T s , and Γ denote the local memory of any honest node u in S. In this context, we prove the following assertions:

-If the number δ m of (non-unique) malicious ids received at node u during a given period of time T s is strictly greater than T s -|S|(1k) then, neither uniform sampling nor ergodic sampling can be achieved; -If δ m ≤ T s -|S|(1k) and the size of the memory Γ is greater than or equal to |S| then, both uniform and ergodic sampling can be achieved; -If δ m ≤ T s -|S|(1k), and |Γ | < |S| then, uniform and ergodic sampling cannot be achieved.

Briefly, these conditions show that if the system cannot provide the means to limit the number of messages an adversary can periodically send, then solving either uniform sampling or ergodic sampling is impossible. On the other hand, if this assumption holds and if all honest nodes in the system have access to a very large memory (in the size of the network) then, the problem becomes trivially solvable. Unfortunately, as will be shown, both conditions are necessary and sufficient to solve the uniform and ergodic sampling problem. Clearly, these strong conditions highlight the damage that adversarial behavior can cause in large-scale unstructured systems.

To the best of our knowledge, we are not aware of any previous work that has specified the conditions for which uniform and ergodic sampling is reachable in presence of adversarial behaviors.

The outline of this paper is the following. In the next section, we describe the model of the system and how it is vulnerable to malicious nodes. Afterwards in Section 3, we define uniform and ergodic sampling, while in Section 4, related work is presented. Finally, Section 5 identifies the two conditions for which uniform and ergodic sampling is achievable, before concluding in Section 6.

System Model

An overlay network is a logical network built on top of a physical network. We consider an overlay network S populated with nodes labelled through a system wide identifier. We assume that a unique and permanent identifier is assigned to each node. In the following, nodes identifiers are abbreviated by node ids. Nodes communicate among each other along the edges of the overlay by using the communication primitives provided by the underlying network (e.g., IP network service). Nodes are free to join and leave the overlay at any time. The particular algorithms use by nodes to choose their neighbors and to route messages induce the resulting overlay topology. In particular, the topology of unstructured overlays conforms with that of random graphs (i.e. relationships among nodes are mostly set according to a random process).

Adversary

A fundamental issue faced by any practical open system is the inevitable presence of nodes that try to manipulate the system by exhibiting undesirable behaviors [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF]. Such nodes are called malicious or Byzantine nodes. Malicious nodes can simply display behaviors such as simply dropping or re-routing messages towards other malicious nodes, or they can devise more complex strategies such as mounting eclipse attacks (also called routing-table poisoning [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF][START_REF] Castro | Secure Routing for Structured Peer-to-peer Overlay Networks[END_REF]) by having honest nodes redirecting outgoing links towards malicious ones. Moreover, they can magnify the impact of their attacks by colluding and coordinating their actions. In our work, we do not consider Sybil attacks [START_REF] Douceur | The Sybil Attack[END_REF], which mainly consist in flooding the system with numerous fake identifiers. We assume the existence of some external mechanism for solving this problem (for instance an off-line certification authority, cf. Section 2.2). We model malicious behaviors through a strong adversary that fully controls these malicious nodes. The adversary has the ability to inspect the whole overlay and strategizes on the time at which malicious nodes operations must be issued. We assume that the adversary cannot control more than a fraction k < 1 of malicious nodes in the overlay. A node which always follows the prescribed protocols is called honest. Note that honest nodes cannot a priori distinguish honest nodes from malicious ones, which would otherwise render the problem trivial.

Security Mechanisms

We assume the availability of a signature scheme that enables to verify the validity of a signature on a message (i.e. the authenticity and integrity of this message with respect to a particular node). Recipients of a message ignore any message that is not signed properly. Nodes ids and keys (private and public) are acquired via a registration authority [START_REF] Castro | Secure Routing for Structured Peer-to-peer Overlay Networks[END_REF] and it is assumed that honest nodes never reveal their private keys to other nodes. We also assume the existence of private channels (obtained through cryptographics means) between each pair of nodes preventing an adversary from eavesdropping and unnoticeably tampering with the content of a message exchanged between two honest nodes through this channel. However of course, a malicious node has complete control over the messages it sends and receives.

Uniform and Ergodic Sampling

In this section, we describe the terminology and assumptions used in this paper and then define uniform and ergodic sampling.

Assumptions and Terminology

Similarly to Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF], we consider the following assumptions. There exists a time T 0 such that from time T 0 onwards, the churn of the system ceases.

This assumption is necessary to make the notion of uniform sample meaningful. Thus from T 0 onwards, the population of the system S is composed of |S| nodes, such that at least (1k)|S| of them are honest and no more than k|S| of them are controlled by the adversary (for k < 1). The subset of honest nodes in the overlay is denoted by N and we assume that all the nodes in N are weakly connected from time T 0 onwards.

Each node u ∈ N has locally access to a sampling component4 as presented in Figure 1. The sampling component implements a strategy s and has uniquely access to a data structure Γ u , referred to as the sampling memory. The size of the sampling memory Γ u is bounded and is denoted by |Γ u |. The sampling component S s u is fed with (non unique) node ids that correspond to the node ids periodically received (either through gossip algorithms or through random walks). This stream of node ids may contain repetition of the same node id, which can be particularly frequent for malicious node ids, as discussed later. At each time t, the following three steps are executed: the first element of the stream, say node id v, is given as input to the sampler component. The sampling component S s u reads v, and removes it from the stream. According to its strategy s, S s u may store or not v in Γ u (for example, the strategy s may consist in storing v if Γ u is not full or in substituting v for a randomly chosen node id in Γ u ), and outputs at most one node id v ′ . The output at time t is denoted S s u (t). The produced node id v ′ is chosen among the node ids in Γ u according to the strategy s (for instance, strategy s may choose the smallest node id in Γ u or the smallest node id under a given min-wise permutation [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF]). Note that these three steps are atomically done. The maximum finite hitting time needed for the sampling component S s u to reach a uniform sample is denoted by T s . Clearly T s depends on the strategy s implemented by the sampling component and also on the stream of node ids the sampling component has access to. Finally, δ m represents the number of malicious node ids received (possibly multiple times) in the stream of node ids at node u during the time interval T s .

Sampling Properties

We consider the problem of achieving an unbiased (uniform) and ergodic sampling in large scale unstructured peer-to-peer systems subject to adversarial attacks. A strategy s that solves this problem has to meet the following two properties: i) Uniformity, which states that any node in the overlay should have the same probability to appear in the sample of honest nodes in the overlay, and ii) Ergodicity, which states that any node should have a non-null probability to appear infinitely often in the sample of any honest nodes in the overlay. More formally, strategy s should guarantee: Property 1 (Uniformity). Let N be a weakly connected graph from time T 0 onwards, then for any time t ≥ T s , for any node u ∈ S, and for any node v ∈ N ,

P[u ∈ S s v (t)] = 1 |S| .
Property 2 (Ergodicity). Let N be a weakly connected graph from time T 0 onwards, then for any time t ≥ T 0 , for any node u ∈ S, and for any node v ∈ N ,

P [{t ′ |t ′ > t ∧ u ∈ S s v (t ′ )} = ∅] = 0,
where ∅ represents the empty set. In the following, Properties 1 and 2 are respectively denoted U and E.

Remark 1. Uniformity by itself does not imply ergodicity and conversely, ergodicity by itself does not imply uniformity. Indeed, Property 1 guarantees that any node (honest or not) has an equal probability to be sampled by any honest node in the system. Nonetheless, once convergence to a random sample locally holds, this property does not say that this sample must change over time to provide a fresh and random node id (this is definitively important for data-caching applications which continuously require fresh node id). Guaranteeing this dynamicity is formalized by Property 2 which states that each node has a non-null probability to be selected as a sample at any time, guaranteeing the access of new sample graphs.

Related Work

In the literature, different approaches have been proposed to deal with malicious behaviors, each one focusing on a particular adversarial strategy.

With respect to eclipse attacks, a very common technique, called constrained routing table, relies on the uniqueness and impossibility of forging nodes identifiers. It consists in selecting as neighbors only the nodes whose identifiers are closer to some particular points in the identifier space [START_REF] Castro | Secure Routing for Structured Peer-to-peer Overlay Networks[END_REF]. Such an approach has been successfully implemented into several overlays (e.g., CAN, Chord, Pastry). More generally, to prevent messages from being misrouted or dropped, the seminal works of Castro et al. [START_REF] Castro | Secure Routing for Structured Peer-to-peer Overlay Networks[END_REF] and Sit and Morris [START_REF] Sit | Security Considerations for Peer-to-Peer Distributed Hash Tables[END_REF] on distributed hash tables based overlays combine routing failure tests and redundant routing as a solution to ensure robust routing. Their approach has then been successfully implemented in different structured-based overlays (e.g., [START_REF] Hildrum | Asymptotically Efficient Approaches to Faulttolerance in Peer-to-Peer Networks[END_REF][START_REF] Fiat | Making Chord Robust to Byzantine Attacks[END_REF][START_REF] Anceaume | PeerCube: an Hypercubebased P2P Overlay Robust against Collusion and Churn[END_REF]). In all these previous works, it is assumed that at any time, and anywhere in the overlay, the proportion of compromised nodes is bounded and known, allowing powerful building blocks such as Byzantine tolerant agreement protocols to be used among peers subsets [START_REF] Fiat | Making Chord Robust to Byzantine Attacks[END_REF][START_REF] Anceaume | PeerCube: an Hypercubebased P2P Overlay Robust against Collusion and Churn[END_REF]. When such an assumption fails, additional mechanisms are needed. For instance, Awerbuch et al. [START_REF] Awerbuch | Towards a Scalable and Robust Overlay Network[END_REF] propose the Cuckoo&flip strategy, which consists in introducing local induced churn (i.e., forcing a subset of nodes to leave the overlay) upon each join and leave operation. This strategy prevents malicious nodes from predicting what is going to be the state of the overlay after a given sequence of join and leave operations. Subsequently to this theoretical work, experiments have been conducted to verify the practical feasibility of global induced churn, which consists in having all the nodes of the overlay periodically leaving their positions. These experiments assume that the overlay is populated by no more than k = 25% of compromised nodes [START_REF] Condie | Induced Churn as Shelter from Routing-Table Poisoning[END_REF]. Authors of [START_REF] Anceaume | Analytical Study of Adversarial Strategies in Cluster-based Overlays[END_REF] have analyzed several adversarial strategies, and show that an adversary can very quickly subvert DHT-based overlays (DHT for Distributed Hash Tables) by simply never triggering leave operations. They also show that when all nodes (honest and malicious ones) are imposed a limited lifetime, the system eventually reaches a stationary regime where the ratio of corrupted clusters is bounded, independently from the initial amount of corruption in the system.

Jesi et al. [START_REF] Jesi | Secure Peer Sampling[END_REF] propose a random sampling algorithm that deals with malicious nodes. Their solution assumes that the ultimate goal of the malicious nodes is to mutate the random graph in a hub-based graph, hub for which malicious nodes gain the lead. Once this goal is reached, malicious nodes can very quickly and easily subvert the whole overlay by performing denial-of-service attacks. Conducting a hub attack mainly consists for malicious nodes in increasing their in-degree. Jesi et al. [START_REF] Jesi | Secure Peer Sampling[END_REF] propose to detect highly popular nodes by extending classic node sampling services with a module that identifies and blacklists nodes that have an in-degree much higher than the other nodes of the overlay. This approach, also adopted in several structured based overlays [START_REF] Singh | Eclipse Attacks on Overlay Networks: Threats and Defenses[END_REF] through auditing mechanisms, or in sensor networks [START_REF] Liu | Detecting Malicious Beacon Nodes for Secure Location Discovery in Wireless Sensor Networks[END_REF], is effective only if the number of malicious nodes is very small with respect to the size of the overlay, typically of O(log |S|).

Recently, Bortnikov et al. [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF] have proposed a uniform sampling algorithm that tolerates up to a linear number of malicious nodes. Their sampling mechanism exploits the properties offered by min-wise permutations. Specifically, the sampling component is fed with the stream of node ids periodically gossiped by nodes, and outputs the node id whose image value under the randomly chosen permutation is the smallest value ever encountered. Thus eventually, by the property of min-wise permutation, the sampler converges towards a random sample. By limiting the number of requests malicious nodes can periodically issue, their solution requires a single node id to be stored in the local memory. Nevertheless, their solution does not satisfy the ergodicity property as convergence toward a random sample is permanent. It is worth noting that our results complement two previous results [START_REF] Busnel | A Formal Characterization of Uniform Peer Sampling Based on View Shuffling[END_REF][START_REF] Gurevich | Correcness of Gossip-Based Membership under Message Loss[END_REF], in which both papers propose an analysis of the class of uniform and ergodic sampling protocols. Each paper provides a complete analytical proof of a gossip-based protocol that reaches both U and E. However, in contrast to the present work, adversarial behaviors were not considered.

Finally, taking a completely different approach from the previously mentioned papers, which are based on gossip algorithms or on distance function properties, the techniques presented in [START_REF] Yu | SybilGuard: Defending against Sybil Attacks via Social Networks[END_REF][START_REF] Yu | SybilLimit: A Near-Optimal Social Network Defense against Sybil Attacks[END_REF] rely on social network topologies to guard against Sybil attacks. Both protocols take advantage of the fact that Sybil attacks try to alter the fast mixing property of social networks to defend against these attacks. However, in presence of malicious nodes with a high degree, performance of both protocols degrade drastically.

Note that the analysis presented in this paper is independent from the way the stream of node ids at each node u has been generated. That is, it may result from the propagation of node ids through gossip-based algorithms (namely through push, pull or push-pull mechanisms initiated by u and its neighbors), from the node ids received during random walks initiated at u, or even from the induced churn imposed in structured-based overlays.

Characterization of the Uniform and Ergodic Sampling Problem

We start our characterization by showing that the adversary can bias the input stream in such a way that neither uniform nor ergodic properties can be met. This is achieved by flooding the input stream with sufficiently many malicious node ids. Specifically, Lemma 1 states that for any strategy s, if the number δ m of non unique malicious node ids that appear in the input stream of node u ∈ N during T s time units exceeds a given threshold then it is impossible for any node in the overlay to equally likely appear as a sample of node u, and this holds forever. Let (C 1 ) be a condition on δ m value

δ m ≤ T s -(1 -k)|S|. (C 1 )
Condition (C 1 ) characterizes the fact that for any honest node v ∈ N , during the time interval T s , v has a non-null probability to appear in the input stream.

We have

Lemma 1. ¬(C 1 ) =⇒ ¬ U ∧ ¬E.
Proof. Let v ∈ N . Suppose that Condition (C 1 ) does not hold, namely it exists an adversarial behavior such that

δ m > T s -(1 -k)|S|.
In this case, the number of honest node ids in the input stream at v (i.e., T s -δ m ) is strictly lower than (1k)|S|, which means formally that

T s -δ m < (1 -k)|S|.
By assumption (cf. Section 3.1) the overlay is populated by (1k)|S| honest nodes. Thus, as the adversary manages to flood the input stream at v, there exists at least one node id u ∈ S that will never appear in the stream. Therefore, whatever the strategy s, v's sampling component can never output u. Thus,

∀t > T 0 , P[u ∈ S v (t)] = 0, (1)
which clearly violates Property U.

Equation (1) can be rewritten as ∃t > T 0 , ∃u ∈ S, ∀t ′ > t, P[u ∈ S v (t ′ )] = 0, which has for consequence that the set of instants t ′ for which u can be sampled by v is empty. Formally,

P[{t ′ |t ′ > T 0 ∧ u ∈ S v (t ′ )} = ∅] = 1,
which violates Property E, and completes the proof of the lemma.

⊓ ⊔

We now assume that Condition (C 1 ) holds. The second lemma states that if the size of the sampling memory is large enough, then whatever the constrained adversarial behavior, the sampling component succeeds in exhibiting uniform and ergodic samples. This makes a sufficient condition to solve our problem. Specifically, let (C 2 ) be defined as follows

|Γ | < |S|. (C 2 )
Condition (C 2 ) characterizes the fact that nodes cannot maintain the full knowledge of the population overlay (essentially for scalability reasons). Then,

Lemma 2. (C 1 ) ∧ ¬(C 2 ) =⇒ U ∧ E.
Proof. Proof of the lemma is straightforward. By Condition (C 1 ), any node u ∈ S has a non-null probability to appear in the input stream of any node v ∈ N .

By assumption of the lemma, |Γ v | ≥ |S|. Consider the basic strategy s of v's sampling component that consists in storing into Γ v , any new id read from the input stream. Then eventually, all the node ids will be present into Γ v , and thus any node u is equally likely to be chosen in Γ v , which guarantees Property U.

Moreover, v has the possibility to return infinitely often any node id u present in Γ v . Thus for any time t, the set of instants t ′ , with t ′ > t, such that u is chosen has a zero probability to be empty, which provides Property E and completes the proof.

⊓ ⊔

The following Lemma completes the characterization of the problem, specifically:

Lemma 3. (C 1 ) ∧ (C 2 ) =⇒ ¬(U ∧ E).
Proof. Suppose that both Conditions (C 1 ) and (C 2 ) hold. Proving that ¬(U ∧ E) is equivalent to showing that (¬E ∨ ¬ U) holds, and thus, that (E =⇒ ¬ U) holds. Suppose that (C 1 ) ∧ (C 2 ) ∧ E is met, we now show that U cannot hold. Consider any node v ∈ N (the set of honest nodes) and let Γ v (t) denote the content of v's sampling memory at the instant t. From Condition (C 2 ),

∀t ′ ≥ T 0 , ∃u ∈ S, u ∈ Γ v (t ′ ). (2)
In particular, Equation ( 2) is true for t ′ = T s . Let node w ∈ S be such that w / ∈ Γ v (T s ), then by assumption, Property E holds. Thus Suppose that d = 0, then ∀t ′′ ≥ t, w ∈ Γ v (t ′′ ), the state (w ∈ Γ v ) is absorbing. Suppose that the overlay contains only two nodes, v and w. By assumption, at least one of the two nodes is honest (k < 1). Let us assume that v is honest (the proof is similar for w). Then, by Condition (C 2 ), we have |Γ v | = 1 (the case |Γ v | = 0 trivially leads to impossibility). By assumption, we have ∀t ′′ ≥ t, w ∈ Γ v (t ′′ ) and as |Γ v | = 1, we also have ∀t ′′ ≥ t, Γ v (t ′′ ) = {w}. As a consequence, whatever the strategy s implemented in v's sampling component,

∃t > T s , w / ∈ Γ v (T s ) ∧ w ∈ Γ v (t). ( 3
) w ∈ Γ v w ∉ Γ v d a b c
∀t ′′ ≥ t, P[v ∈ S s v (t ′′ )] = 0 =⇒ P[{t ′′ |t ′′ > t ∧ v ∈ S s v (t ′′ )} = ∅] > 0,
contradicting E, and thus contradicting the assumption of the lemma. Thus d > 0 and, a fortiori, b < 1, and no state is absorbing. Suppose now that U holds. We prove the lemma by contradiction. Consider again the case where the overlay is populated by only two nodes, v and w. As above suppose that node v is honest and that |Γ v | = 1. The evolution of the sampling memory at node v can be modeled by a Markov chain as represented in Figure 3. By assumption, E holds, thus infinitely often, and successively, both v and w appear in Γ v . Moreover also by assumption, U holds, that

is, ∀t ≥ T s , P[w ∈ S s v (t)] = P[v ∈ S s v (t)] = 1 2 .
As a consequence, w has the same probability as v to be in Γ v , whatever the number of times w and v appear in the stream before time T s . Suppose now that node w is malicious. By Condition (C 1 ), node id w can appear in v's stream no more than T s -1 times during any sliding window of T s time units. As |Γ v | = 1, a single node id can be stored, and beyond this node id, no other additional information can be stored. We show that whatever the strategies s implemented by v's sampling component, they all lead to a contradiction. Blind replacement. At any time t, the sampling component reads the first node id in the stream, and stores it in Γ v in place of the previous one. By construction, any strategy has to select its output among the elements stored in Γ v , thus the output of the sampling component follows the same probability distribution as the one observed in the stream. As the adversary can flood the stream with up to T s -1 malicious node ids, this means that property U cannot be met. No replacement. Similarly to the blind replacement strategy, node ids are read from the stream, and stored in Γ v up to time t, where t is the first time at which a specific node id is read. From time t onwards, this specific node id is kept in Γ v , independently from the node ids read from the stream after t, leading to an absorbing state of the Markov chain. For instance, this specific node id can be the smallest image value under a random min-wise independent function, such as the min-wise permutation [START_REF] Bortnikov | Brahms: Byzantine Resilient Random Membership Sampling[END_REF]. Clearly, this strategy violates property E. Probabilistic replacement. This strategy consists in substituting the current node id in Γ v with the next one read from the stream according to a given probability law. To guarantee that ∀t, P[w ∈ S s v (t)] = P[v ∈ S s v (t)] = 1 2 , then either both v and w have an equal probability to appear in the stream or the sampling component must be able to remember the node ids it has seen in the past to guarantee that, at any time t, each node id has the same probability to be chosen as sample. The former case does not hold as by assumption, the adversary can flood the stream with up to T s -1 malicious ids. Moreover, the latter case is impossible as by assumption |Γ v = 1|, and thus a single information can be stored which prevents to store more than a single piece of information (e.g., it is impossible to store both a node id and a counter), therefore property U cannot hold. Proof. This result follows directly from the statements of Lemma 2 and 4.

Γ v = {v} Γ v = {w}
⊓ ⊔

Conclusion

In this paper, we have investigated the sampling problem of large-scale unstructured peer-to-peer systems in adversarial environments. We have first shown that, if the system cannot provide the means to limit resources of an adversary, then solving either uniform sampling or ergodic sampling is impossible. We have then demonstrated that, if this assumption holds and if all honest nodes in the system have access to a very large memory (in the size of the system) then, the problem becomes trivially solvable but not yet realistic. Unfortunately, we have shown that both conditions are necessary and sufficient ingredients to solve the uniform and ergodic sampling problem in potentially adversarial environments.

Clearly, these strong conditions highlight the damage that adversarial behavior can cause in large-scale unstructured systems.

As future work, first we intend to study to which extent the adversary model needs to be weaken to achieve uniform and ergodic sampling in a setting where the nodes themselves have limited ressources (for instance in terms of memory). Second, we plan to investigate an approximate version of the sampling primitive to achieve near uniform and/or near ergodic sampling despite the presence of a strong adversary. Both studies should have a positive impact for applications exhibiting different requirements in terms of resources (i.e. memory, computational power and communication complexity) and for settings in which probabilistic guarantees on samples are sufficient.

Fig. 1 .

 1 Fig. 1. Sampling component of node u ∈ N .

Fig. 2 .

 2 Fig. 2. Markov chain that represents the evolution of w's presence in the sampling memory Γv of node v ∈ N .

Fig. 3 .

 3 Fig. 3. Markov chain that represents the state of the local memory Γv of v.

Thus (C 1 )

 1 ∧ (C 2 ) =⇒ ¬(U ∧ E), which concludes the proof of the lemma. ⊓ ⊔The last lemma reformulates the necessary condition of the problem characterization by combining Lemmata 1 and 3.

Lemma 4 . 4 )

 44 U ∧ E =⇒ (C 1 ) ∧ ¬(C 2 ).Proof. The contrapositive form of writing Lemma 3 is U ∧ E =⇒ ¬((C 1 ) ∧ (C 2 )), and thus, by distributivity,U ∧ E =⇒ ¬(C 1 ) ∨ ¬(C 2 ).(On the other hand, the contraposition of Lemma 1 leads toU ∨ E =⇒ (C 1 ). As (U ∧ E ⇒ U ∨ E), we have U ∧ E =⇒ (C 1 ).(5)By combining Equations 4 and 5, the following holdsU ∧ E =⇒ (C 1 ) ∧ (¬(C 1 ) ∨ ¬(C 2 )). Thus, U ∧ E =⇒ ((C 1 ) ∧ ¬(C 1 )) ∨ ((C 1 ) ∧ ¬(C 2 )) .Due to the principle of contradiction, (C 1 ) ∧ ¬(C 1 ) cannot hold, leading toU ∧ E =⇒ (C 1 ) ∧ ¬(C 2 ),which completes the proof.⊓ ⊔The Uniform and Ergodic Sampling Problem defined in Sections 2 and 3 is completely characterized by the following theorem: Theorem 1. (C 1 ) ∧ ¬(C 2 ) is a necessary and sufficient condition for Uniform and Ergodic Sampling Problem to hold.

Although malicious nodes have also access to a sampling component, we cannot impose any assumptions on how they feed it or use it as their behavior can be totally arbitrary.

Acknowledgements

We are very grateful to the anonymous reviewers for their constructive comments that have help us to improve the quality of this paper.


Vincent Jost
email: vincent.jost@lix.polytechnique.fr.

Guyslain Naves
email: naves@math.mcgill.ca.

The graphs with the max-Mader-flow-min-multiway-cut property

We are given a graph G, an independant set S ⊂ V (G) of terminals, and a function w : V (G) → N. We want to know if the maximum w-packing of vertex-disjoint paths with extremities in S is equal to the minimum weight of a vertex-cut separating S. We call Mader-Mengerian the graphs with this property for each independant set S and each weight function w. We give a characterization of these graphs in term of forbidden minors, as well as a recognition algorithm and a simple algorithm to find maximum packing of paths and minimum multicuts in those graphs.

Introduction

Given a graph G = (V, E), a set S ⊂ V with |S| ≥ 2 and inducing a stable set is called a set of terminals. An S-path is a path having distinct ends in S, but inner nodes in V \ S. A set P of S-paths, is a packing of vertex-disjoint S-paths (since there is no risk of confusion, we will use the shorter term packing of S-paths within this paper), if two paths in P do not have a vertex in common in V \ S. We are looking for a maximum number ν(G, S) of S-paths in a packing.

An S-cut is a set of vertices in V \ S that disconnect all the pairs of vertices in S (that is a blocker of the S-paths). We are looking for an S-cut with a minimum number κ(G, S) of vertices.

The following inequality holds for any graph G and any S ⊆ V (G): ν(G, S) ≤ κ(G, S), as any S-path intersects any S-cut. Note that if |S| = 2 the equality always holds, being Menger's vertex-disjoint undirected (s, t)-paths theorem. This paper deals with graphs for which ν(G, S) = κ(G, S), for any set S of terminals. Actually, we try to characterize a stronger property associated with a weighted version of these two optimization problems. Consider the following system with variables x ∈ R V \S + :

x(P ) ≥ 1 for every S-path P

Figure 1: The net.

An integral vector x minimizing wx over ( 1) is necessarily a 0, 1-vector and is the characteristic vector of a minimum S-cut. Dually, an integral vector y optimum for the dual of minimizing wx over (1) is necessarily a maximum w-packing of S-paths. Hence, if (1) is a TDI system, we have that the minimum w-capacity of an S-vertex-cut is equal to the maximum w-packing of S-paths.

As an example, consider the graph of Figure 1, called net. Let S be the square vertices. A maximum integral packing of S-paths (w = 1) contains only one path, while any S-cut must contain at least two vertices. Precisely, there is a fractional packing of S-paths of value 3 2 (by taking each S-path of length 3 with value 1 2 ), and a fractional S-cut with the same value (by taking x(v) = 1 2 for all v / ∈ S). Motivated by the following property, we call Mader-Mengerian the graphs for which the system (1) is TDI for every set S of terminals.

Property 1. Given a graph G and a set of terminal S, the following conditions are equivalent: 1. The system (1) is TDI, 2. The polyhedron defined by (1) is integral, 3. The optimum value of maximizing w T x subject to (1) is integral (if finite) for all w ∈ V {0,1,+∞} .

The proof of this property is postponed to section 3 where the stronger Lemma 8 is proved. We already know that the long claw is not Mader-Mengerian.

Our main result (Theorem 9) is a description of the Mader-Mengerian graphs in terms of forbidden minors. However we do not use the usual minor operations (edge deletion and edge contraction), but ad-hoc operations on vertices. Our proof implies an algorithm (Lemma 8) to find maximal w-packing of paths in Mader-Mengerian graphs and minimum vertex multicuts for a given set of terminals. We also give a characterization of the pairs (G, S) for which the system (1) is TDI (Theorem 14).

One of our most surprising results is that G is Mader-Mengerian if and only if the system (1) is TDI for every independant set S of cardinality 3. This implies (with Lemma 8) a polynomial algorithm to recognize Mader-Mengerian graphs.

Finding a minimum S-cut is an NP-complete problem, even if |S| = 3 [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF]. In fact, [START_REF] Dahlhaus | The complexity of multiterminal cuts[END_REF] deals with edge-cuts (that is, sets of edges disconnecting S), but one may observe that S-edge-cut in a graph G correspond to vertex-cut in the line-graph of the graph obtained from G by adding one leaf to each vertex in S.

Finding maximal packing of disjoint paths is a classical problem in graph theory, even if it was mainly studied for edge-disjoint (or arc-disjoint) paths. Menger [START_REF] Menger | Zur allgemeinen kurventheorie[END_REF] gave the first significant result, stating that when |S| = 2, the maximum number of disjoint S-paths is equal to the minimum cardinality of an (s, t)-cut, both in edge-disjoint and vertex-disjoint cases. This result was further developped by Ford and Fulkerson [START_REF] Ford | Maximal flow through a network[END_REF], into what became the network flow theory. When there is more than two terminals, the results are however closer to matching theory than to network flows. Gallai [START_REF] Gallai | Maximum-minimum Sätze und verallgemeinerte Faktoren von Graphen[END_REF] first proved a min-max theorem for packing of fully-disjoint S-paths (that is even the ends of the paths must be disjoint), and his result was then strengthened by Mader [START_REF] Mader | Über die Maximalzahl kreuzungsfreierH-Wege[END_REF] for inner-disjoint paths with ends in different parts of a partition of the terminals. Mader's theorem implies the following: Theorem 1 [START_REF] Mader | Über die Maximalzahl kreuzungsfreierH-Wege[END_REF]. Let G be a graph and S an independant set of G. Then,

ν(G, S) = min |U 0 | + k i=1 b U 0 (U i ) 2
where the minimum ranges over all the partitions U 0 , . . . , U k of V \ S , such that each S-path intersects either U 0 or E(U i ) for some

1 ≤ i ≤ k. Here, b U 0 (X) := |{v ∈ X : N (v) \ (X ∪ U o ) = ∅}|.
In the light of Mader's theorem, we are looking for graphs that admit a much simpler characterization: ν(G, S) = min |U | where the minimum ranges over sets U such that each Spath intersects U . A practical reason for looking for these graphs is that Mader's theorem relies on matching theory, while our result will only use Menger's theorem, that is flow theory. As a consequence, algorithms for finding an optimal packing of S-paths in Mader-Mengerian graphs are simpler and more efficient than those for general graphs.

Mader's theorem has been recently extended by Chudnovsky et al. [START_REF] Chudnovsky | Packing Non-Zero A-Paths In Group-Labelled Graphs[END_REF], and by Gyula Pap [START_REF] Pap | Packing Non-Returning A-Paths[END_REF].

Let us mention a similar result for edge-disjoint paths, that was proved by Cherkasky [START_REF] Cherkasky | A solution of a problem of multicommodity flows in a network[END_REF] and Lovász [START_REF] Lovász | On some connectivity properties of Eulerian graphs[END_REF]: Lovász, 1977). For any inner Eulerian graph G, then the maximum number of edge-disjoint S-paths is equal to 1 2 s∈S λs, where λs is the minimum cardinality of a cut between s and Ss.

Theorem 2 (Cherkasky,
This has been later extended by Karzanov and Lomonosov [START_REF] Karzanov | Systems of flows in undirected networks[END_REF], who proved the Locking Theorem. These results explains when the maximum packing of edge-disjoint S-paths has a characterization in terms of minimal cuts.

Vertex minors and skew minors

Given a graph G = (V, E) and v ∈ V , deleting v in G means considering the graph G-v induced by V -v, that is: G -v := (V -v, E \ δ G (v))
Contracting v means considering the graph G/v obtained by removing v and replacing its neighborhood by a clique:

G/v := (V -v, E ∪ {wx|w, x ∈ N G (v)} \ δ G (v))
For e = xy ∈ E contracting e means considering the graph G/e obtained by identifying the end-nodes x and y of e.

G/e := (V,

E ∪ {xz|z ∈ N G (y)} ∪ {yz|z ∈ N G (x)} \ e)
A graph obtained from G by any sequence of vertex deletions and vertex contractions is a vertex-minor of G. A graph obtained from G by any sequence of vertex deletions, vertex contractions and edge contractions is a skew-minor of G.

Vertex-minors can also be described in the following way:

Proposition 3.
Let G be a graph, and G ′ be a vertex-minor of G. Let D be the vertices deleted and C be the vertices contracted to get G ′ from G. Then, u, v ∈ V (G ′ ) are adjacent in G ′ if and only if there is a path with extremities u and v in G and whose inner nodes are in C.

This immediately implies:

Lemma 4. Vertex-deletions and vertex-contractions commute.

By definition, for a class of graph, being closed under skew minors implies being closed under vertex minors, which in turn implies being closed under induced subgraphs. Several important classes of graphs are closed under skew minors. Among them: Definition 5.

-The interval graphs are the graphs of intersection of intervals of the real line.

-The chordal graphs are the graphs of intersection of subtree of a tree. Equivalently, a graph is chordal if each of its cycles of length at least 4 has a chord. -The cocomparability graphs are the graphs whose complement is the underlying graph of a partially ordered set.

-The Asteroidal-Triple-free (AT-free) graphs are the graphs without asteroidal triple. A stable set S of cardinality 3 is an asteroidal triple of G if there is no

x ∈ S such that S -x is contained in a connected component of G -(x ∪ N (x)
). -The P k -free graphs, for k ∈ N, are the graphs with no induced path of length at least k.

The following proposition is left as an exercise: Proposition 6. Interval graphs, chordal graphs, co-comparability graphs, AT-free graphs, P kfree graphs are closed under skew minors.

The following lemma explains why we are interested in the vertex-minor operations.

Lemma 7. Given a graph G and a set of terminal S, if the system (1) is TDI, then it is also TDI for any vertex-minor of G.

Proof. Deleting v ∈ V \ S corresponds to setting w v = 0. Contracting v ∈ V \ S corresponds to setting w v = +∞.

Integrality of the blocker of S-paths

For a given graph G and a set S of terminal, we construct an auxiliary graph G S as follows. First, note that if a non-terminal vertex v is adjacent to two terminals s and t, we may assume that the maximum packing for a weight function w contains w(v) times the 2-length paths sv, vt, and the minimal S-cut contains v. Hence, we first delete every non-terminal vertex adjacent to two or more terminals.

We may also assume that no S-path of a maximum packing contains two vertices of N G (s) for some terminal s (by taking chordless paths). Therefore if G -N G (s) contains a component disjoint from S, we can delete all its vertices.

From now, we will always suppose that:

(i) G has no vertices adjacent to two distinct terminals.

(ii) for each s ∈ S, every component of G -N G (s) intersects S.

(iii) G has no edge whose ends are both adjacent to the same terminal.

Then we consider the set N = N G (S) of vertices adjacent to S. N is the vertex set of G S . We delete the terminals, and contract the vertices in V -(N ∪ S). Then we remove all the edges whose ends are adjacent to the same terminal in G (the contraction of a path of a maximum packing would not use these edges) . This gives G S . By construction, this graph is |S|-partite, each part being the neighborhood of one terminal.

Note that a, b ∈ N are adjacent in G S if a and b are not adjacent to a common terminal, and there is an (a, b)-path in G whose inner vertices are outside S ∪ N G (S). Proof. Assume that G S is not bipartite. Let C * be an induced odd cycle of G S . We define a weight vector w ∈ V (G) {0,1,+∞} as follows:

w v :=    1 if v ∈ C * 0 if v ∈ V (G S ) \ C * +∞ otherwise (2)
To every edge uv of C * , we can associate an S-path of G intersecting N exactly in u and v. Then a maximum fractional w-packing of S-paths is given by taking 1/2 for each of these paths and a minimum fractional S-cut of G is given by 1/2 on every node of C * , and 1 on other vertices of N . The optimum value of the corresponding pair of dual linear programs is then |V (C * )|/2, hence the polyhedron defined by (1) is not integer.

Suppose now that G S is bipartite, with bipartition (A, B).

Let H be the graph obtained by deleting S and add two new non-adjacent vertices s a and s b , adjacent to respectively A and B.

Let P be a chordless (s a , s b )-path in H. Let {a, b} := N ∩ V (P ). We can associate a unique path P of G to P , by replacing its extremities by terminals of G (because each vertex of N is adjacent to a unique terminal). We show that P cannot be a cycle. Let Q = V ( P ) \ (S ∪ N ). If Q is empty, P is clearly not a cycle because in H, the neighborhood of a terminal is a stable set.

Else

Q is contained in a component C of G \ (N ∪ S). C is adjacent to N G (s)
and N G (t) for two distinct terminals s and t by condition (ii). We can suppose that a ∈ N G (s). P is a cycle only if b ∈ N G (s). But if this was the case, then for c ∈ N G (t) adjacent to C, a, c, b would be a path in H, hence a and b would be in the same part of the bipartition (A, B), contradiction. P is not a cycle, it is an S-path.

By applying the vertex-disjoint version of Menger's theorem to H, ν(G, w, S) = κ(G, w, S) for any w ∈ Z V \S .

A forbidden minor characterization

In this section, we find a characterization of Mader-Mengerian graphs by excluded vertex-minors. We start from the proof of Lemma 8, where we showed that if a graph is not Mader-Mengerian, its auxiliary graph has an odd cycle. In the auxiliary graph construction, we perform vertexminor operations plus deletion of edges between two vertices adjacent to the same terminal. It follows that a graph that is not Mader-Mengerian contains a vertex-minor G of the following form.

G is a graph obtained by taking an odd cycle C and the terminals adjacent to C. Each vertex of C is adjacent to exactly one terminal, called the representant of this vertex. We color the vertices depending on their representants: each representant gets a distinct color, each other vertex has the color of its representant. A color is thus a set of vertices adjacent to some terminal, plus this terminal. Two consecutive vertices of the odd cycle have distinct colors, while the extremities of each chord share the same color. Let A n be the class of graphs obtained in this way with n terminals.

One path of lemmas and proofs to obtain the following result is presented in the Appendix.

Theorem 9. Let G be a graph.The system (1) is TDI for every stable set S if and only if G does not contain a vertex minor in A 3 .

Proof. Direct consequence of Lemmas 18, 20 and 24.

Corollary 10. System (1) is TDI for every stable set S of G if and only if it is TDI for every stable set S of cardinality 3 of G.

This gives a polynomial-time recognition algorithm for the related class of graphs, in combination with Lemma 8: we only have to check for each independant subset of three vertices whether the associated auxiliary graph is bipartite. Another important consequence is that the class of graphs for which system (1) is TDI for every stable set is large. Indeed, it contains at least the asteroidal-triple-free graphs:

Corollary 11. For every asteroidal-triple-free graph, the system (1) is TDI.

Proof. Follows from Theorem 9 and Proposition 6, as every graph in A 3 contains an asteroidal triple, namely the set of terminals.

To conclude this section on vertex-minors, we prove that there is an infinite number of minimal graphs to exclude. Let U ′ , V ′ and W ′ be the color classes of u, v and w respectively in G ′ . Every vertex adjacent to u in G ′ must be in the same color class U ′ as u in G ′ , proving that U \ (D ∪ C) ⊂ U ′ . Because color classes are a partition of the vertex set, we have equality,

U ′ = U \ (C ∪ D) and similary for V ′ and W ′ . Suppose C is not empty, let x ∈ C. We may assume x ∈ U . If x is the representant of U , then G ′ = G -(D + x)/(C -x).
Else, if x is not the representant of U , x has exactly two neighbors y and z outside U . Because u, v and w must be at distance 3 of each other in G ′ , y, z must be in D. Then we also have that

G ′ = G -(D + x)/(C -x). Hence G ′ = G -(C ∪ D).
But then, as the set of edges between colors of G ′ must be a cycle, G ′ = G, proving that G is minimal.

Minimal skew-minors exclusion

A skew-minor of a graph G is any graph obtained from G via the following operations: vertex deletion, vertex contraction and edge contraction.

Note that Mader-Mengerian graphs are not closed under edge contraction since by inflating one of the central vertex of the net we get a Mader-Mengerian graph. However, we can get a simple sufficient condition for the integrality of system (1) based on skew-minors: Theorem 13. Any graph G is either Mader-Mengerian or contains a net or a rocket as a skew minor.

When the set of terminals is fixed

Our arguments apply when we want to find the pairs (G, S), S ⊂ V (G), for which the system (1) is TDI. Up to now, we have only looked at graphs G for which we have TDIness for every set of terminals. To deal with a fixed set of terminals, we define another notion of vertex-minor, the signed vertex-minor, defined on pairs (G, S). Signed vertex-minor are defined like vertex-minor, except that the set of terminals of the minor must be a subset of the terminals of the original graph. More precisely, (H, S ′ ) is a signed vertex-minor of (G, S) if H is a vertex-minor of G and S ′ ⊆ S.

Recall that A 3 is the class of graphs built from a three-colored odd cycle, by adding a terminal for each color, and chords with extremities of the same color. We define similarly the class A 3 of signed vertex-minor (G, S), where G ∈ A 3 , and S is the set of the three terminals in the construction of G.

This setting does not affect Lemma 8, and then the following theorem, close to Theorem 9, can be deduced by the same proof. Indeed, the proofs in Section 4 never create new terminals when considering vertex-minors, and hence are still valid for signed vertex-minors.

Theorem 14. Let G be a graph and S a set of terminal in G. The system (1) is TDI if and only if (G, S) does not have a signed vertex-minor in A 3 .

Corollary 15. The system (1) is TDI for (G, S) if and only if it is TDI for every (G, S ′ ), with S ′ ⊆ S, |S| = 3. Moreover, all the graphs of A 3 are minimal graphs by signed vertex-minors for which system (1) is not TDI. Indeed, a potential minor would have the same set of terminals. Moreover, if we contract a vertex, then its two consecutive vertices in the odd cycle become adjacent to two terminals, hence must be deleted. Hence, the minor must be obtained without vertex contraction, and the minimality follows easily.

Conclusion

We studied the pairs (G, S) of (graphs, subsets of terminals) for which the cost of an S-vertexcut is equal to the maximum packing of S-paths. We proved that this property for a given S is polynomially checkable as it reduces to the bipartiteness of an auxiliary graph. Moreover if this property is true, the minimal S-cut and maximum path-packing problems can be solved by finding a maximum vertex-capacitated flow in a smaller graph.

We proved that if (G, S) does not satisfy this property, then there exists S ′ ⊆ S with |S ′ | = 3 such that (G, S ′ ) does not satisfy it either. Moreover, each signed vertex-minor in A 3 is a minimal signed vertex-minor obstruction.

Concerning the graphs satisfying the min-max formula for any S, we proved that they can be recognized in polynomial time, that the list of vertex-minor obstructions is infinite, but we r(u 1 ) 4, a), let G ′ be the graph obtained by contracting u and r(u) and by deleting all the vertices except r(u 1 ), r(u 2 ), u 1 , u 2 and v. G ′ is a net (Figure 4,b). 4, c), we may assume v ′ u 1 ∈ E(C). Let G ′ be the graph obtained from G by contracting u, v and r(u) and deleting every other vertex except v ′ , r(v ′ ), r(u 1 ), r(u 2 ), u 1 and u 2 . Then G ′ is a net (Figure 4,d).

u 1 u 2 u 3 r(v 1 ) r(v 2 ) r(v 3 ) v 1 v 2 v 3 v 1 v 2 v 3 r(v 1 ) r(v 2 ) r(v 3 ) (a) (b)
If d C (v ′ , u) = 2 (Figure
Now suppose that d C (u, v) = 2. We may assume that u 1 is adjacent to v. Then the graph obtained from G by contracting r(u) and deleting every vertex except u, v, u 1 , u 2 , v ′ and r(u 1 ), is a net. Lemma 17. Every color is adjacent to at most two other colors, or G contains a net vertexminor.

Proof. Let R be any color. By applying iteratively Lemma 16, if there is a vertex of color R whose two consecutive vertices have distinct colors, then either G contains a net, or R is adjacent to exactly two colors.

Otherwise, each vertex in C is consecutive to two vertices of the same color. Suppose that there are three vertices u 1 , u 2 , u 3 in C of color R, such that their neighbors have three different colors. let v 1 , v 2 and v 3 be the vertices following u 1 , u 2 , u 3 respectively in C (Figure 5, a). Then, by contracting u 1 , u 2 , u 3 , r(u 1 ) and deleting all the vertices except v 1 , v 2 , v 3 and their representants, we obtain a net (Figure 5,b).

From now, we suppose that G does not have a net minor. We define the graph of colors, whose vertices are the colors, by the adjacency relation introduced above. By Lemma 17, the graph of color has maximum degree two. By connexity, it is either a cycle or a path. We index the colors from 1 to n, following the order defined by the path or the cycle. Thus, each edge of C has extremities of colors i and i + 1, or 1 and n. We have the following immediate consequence. Proof. By contradiction. Let u be a bicolored vertex, of color 1, and v its bicolored neighbor of color 2. Let w be a bicolored vertex of color 4. Then, the graph obtained by contracting vertices of colors 3 and 5, and deleting all the vertices of colors 1, 2 and 4, except u, v, w and their representants, is a net.

Lemma 22. Suppose G is net-free. The number of edges between any two color classes is zero or odd.

Proof. Choose two adjacent colors, and remove from C every edge between these two colors. Every path thus obtained has its both extremities in the same color class, or in the two chosen colors. So every path has an even length. As C is odd, this proves that we removed an odd number of edges.

Lemma 23. Suppose G is net-free. If n = 5, there is a maximal sequence of consecutive edges in C between any two given adjacent colors of length 2k + 1, for some k ≥ 1.

Proof. Consider the subpaths of C obtained by keeping only the edges between colors 1 and 2. Either there is a net minor or each of these paths has length at least 2 by Lemma 21. Then, by Lemma 22, there is a path of odd length, proving the lemma.

Lemma 24. If n = 5, then G is not a minimally excluded graph by vertex minor.

Proof. If G contains a net minor, it is clearly not minimal. Suppose it does not.

Figure 2 :

 2 Figure 2: A graph G and the auxiliary graph G S .

Lemma 12 .Figure 3 :

 123 Figure 3: The rocket

Figure 5 :

 5 Figure 5: Illustration for Lemma 17.

Figure 7 :

 7 Figure 7: Illustration for Lemma 20. The representant of each color is drawn as a square.

were unable to provide an explicit description of this list. We believe that this list is hard to obtain, and somehow ugly. We also proved that this class of graphs is interesting as it contains the asteroidal-triple-free graphs.

Figure 4: Illustration for Lemma 16.

Appendix to section 4

The distance in C between two vertices u and v is the minimum number of arcs in one of the two (u, v)-paths in C. We denote d C (u, v) this minimum. We say that u and v are consecutive if d C (u, v) = 1. We denote r(u) the representant of a vertex u. We say that a vertex of C is bicolored if its two neighbors in C have distinct colors. Two colors are adjacent if there is an edge in C whose ends have these two colors. Note that the net is a forbidden minor of Mader-Mengerian graphs, and is minimal. We try to find other forbidden minors that do not have a net as vertex-minor. For a graph H, we say that G is H-free if H is not a vertex minor of G.

Lemma 16. Let u be a bicolored vertex. Let v be a vertex of the same color as u. Then, either G contains a net, or every vertex consecutive to v has the color of a vertex consecutive to u.

Proof. Let u 1 and u 2 be adjacent to u in C, v ′ is adjacent to v, and u 1 , u 2 and v ′ have distinct Lemma 18. Let G be net-free. The number n of colors is odd, and the graph of colors is a cycle.

Proof. Suppose not. Then C has a proper 2-coloring (following the parity of the colors), thus is even, contradicting the assumption.

Lemma 19. Let G be net-free. Every color contains a bicolored vertex.

Proof. Without loss of generality, it is sufficient to prove that there is a bicolored vertex of color 1. Let U be the vertices of color 1 adjacent to a vertex of color n and U ′ be the other vertices of color 1. Let W the vertices of C having an odd color minus U ′ , and B its complement in V (C)(see Figure 6). B does not contain two consecutive vertices of C, and (W, B) cannot be a proper two coloring of C. Thus there is an edge in C with both extremities in W . But this can only be an edge between U and color n, hence there is a bicolored vertex in U .

Lemma 20. If G is net-free, the number n of colors is at most 5.

Proof. By contradiction. Let u, v and w be bicolored vertices of colors 1, 3 and 5 respectively (see Figure 7). Contract every vertex of other colors, and delete every remaining vertex except u, v, w and their representants. If n > 5, the 6-vertices graph obtained by this way is a net. Let u 1 , v 1 , u 2 , . . . u k , v k be a maximum subpath of C of odd length between colors 1 and 2. By Lemma 23, we have k ≥ 2. Let w be the vertex of color 5 adjacent to u 1 , and w ′ the vertex of color 3 adjacent to v k . Let s be a bicolored vertex of color 4 (see Figure 8,a).

Consider the graph obtained by contracting vertices of colors 3 and 5, and deleting all the other vertices except u 1 , v 1 , u 2 , . . . u k , v k , s, r(u 1 ), r(u 2 ) and r(s). This graph (Figure 8,b) is composed of a cycle of length 2k + 1 plus three terminals r(u 1 ), r(u 2 ) and r(s). It obviously checks the condition for being an excluded graph. Thus G is not minimal.