Graph Theoretic Detection of Ine ciencies in Network Models

Abstract

We present graph-theoretic characterisations of three notions of ine ciency arising in network models: edge-weakness in ow networks, node-weakness in depletable channels, and vulnerability in tra c networks. Our characterisations lead to three polynomial algorithms that check these forms of ine ciency. Furthermore, checking vulnerability also leads to an advancement on the subgraph homeomorphism problem.

-

Introduction

ciencies in Network Models In the following, we will always consider st-directed simple graphs, i.e., graphs without self-loops and parallel edges, equipped with a source node s (without incoming edges) and a target node t (without outgoing edges).

In the standard model of ow networks [ 1 ], edges are endowed with capacities and admissible ows can not exceed edge capacities. In the graph of Fig. 1(b), two ow units can go from s to t, provided that one of them takes the path s ! u ! t and the other one takes the path s ! v ! t. However, a ow of one s (a) : u # v >" t unit along the path s ! u ! v ! t would saturate the net (i.e., no more ow can be sent from s to t). This is ine cient, since not all possible ow is delivered. We call edge-weak those graphs that, as W in Fig. 1(a), admit non-maximum saturating ows for some capacity-to-edge assignments, as in Fig. 1(b).

In depletable channels [ 3 ], a model for energy consumption in wireless networks, each node u is equipped with an integer (u) 0 representing its depletable charge. Node charges constrain admissible ows: in the channel of Fig. 1(c) (built upon W), nodes are labelled with their charge (` ' stands for `unlimited'). As before, we can transmit two information units, or saturate the net with one unit only. We call node-weak those graphs (as W) that admit nonmaximum saturating ows for some charge-to-node assignment (Fig. 1(c)).

In tra c networks [ 2 ], edges are labelled with latency functions, that models agent delay along an edge in terms of its congestion, that is the ow on that edge. Autonomous sel sh users choose the faster path and the tra c stabilises to an equilibrium of a noncooperative game, (Wardrop equilibrium). The tra c network in Fig. 1(d) is built on top of W: two edges (u ! t and s ! v) cause a delay of 1 regardless the ow on them; the edge (u ! v) causes no delay; two edges (v ! t and s ! u) cause a delay linear in the ow on them. Sel sh users control a negligible part of tra c " and choose the quickest path p : s ! u ! v ! t, because there they experience a delay of 2 " instead of 1 + " experienced in other paths However, this leads to the congestion of p: in a ow of value 1, at the Wardrop equilibrium, all agents choose the path p and their delay is 2. This is an equilibrium, since agents have no interest in deviating from their choice. Paradoxically, if we remove the `ideal' edge u ! v, half of users will choose the path s ! u ! t and half the path s ! v ! t resulting in a delay of 3/2. This phenomenon has been known for a long time as Braess's paradox [ 2 ], that occurs when the equilibrium cost may be reduced by removing edges.

The property of a graph (as W in Fig. 1(a)) to lead, under some latency function (as the one in Fig. 1(d)), to the possibility of experiencing the Braess's paradox has been called vulnerability in [ 11 ]. 3

A Graph Theoretic Perspective We have characterised node-weakness [ 4 ] and edge-weakness [ 5 ] in terms of minimal separators, and vulnerability [ 6 ] in terms of subgraph embedding.

A minimal vertex separator (mvs for short) [ 10 ] of an st{graph is a minimal set of nodes whose removal disconnects s from t.

Theorem 1 ([ 4 ]). A directed st-graph G is node-weak if and only if there exists a path from s to t touching some mvs of G at least twice.

As discussed in Sect. 2, the graph W in Fig. 1(a) is node-weak: indeed, the mvs fu; vg is touched twice by the path s ! u ! v ! t. By contrast, the graph C in Fig. 2 is not node-weak, since its saturating ows have always value minf (v1) + (v2); (v3) + (v4)g: no st-path touches any of its mvs's twice.

Similarly, a minimal edge separator (mes for short) of an st{graph is a minimal set of edges whose removal disconnects s from t.

Theorem 2 ([ 5 ]). A directed st-graph G is edge-weak if and only if there exists a path from s to t touching some mes of G at least twice.

For example, the graph C in Fig. 2 is edge-weak, because if we assign capacity 0 to one of its two diagonal edges (v1 ! v4 or v2 ! v3) and 1 to all other edges, we essentially obtain a ow network with the same ows as that of Fig. 1(b). Indeed, the path s ! v1 ! v4 ! t touches twice the mes fs ! v1; v2 ! v3; v4 ! tg.

We have characterised vulnerable graphs as those graphs in which the pattern graph W can be embedded. An st-embedding of W into an st-graph G is a injective map from nodes of W to nodes of G such that: (1) for all edges u ! v of W, there exists a path from (u) to (v) in G, (2) (u) ; (v) and (u0) ; (v0) are node disjoint paths (apart for their extremes) whenever u 6= u0 or v 6= v0, and (3) there exist two (possibly empty) node-disjoint paths in G from its source to (s) and from (t) to its target.

Theorem 3 ([ 6 ]). A directed st-graph G is vulnerable i there is an stembedding of W into G. If G is vulnerable, then G is edge-weak.

The embedding of W into the graph C in Fig. 2 that maps source into source, target into target, u into v1, and v into v4 induces the following mapping of edges of W to disjoint paths of C (we denote sW and tW the source and target of W, and the same for sC and tC ): f(sW ! u; sc ! v1); (sW ! v; sc ! v2 ! v4); (u ! v; v1 ! v4); (u ! tW ; v1 ! v3 ! tC ); (v ! tW ; v4 ! tc)g. Here, the paths from sC to (sW ) and from (tW ) to tC are both empty.

As shown in Sect. 2, the graph W is edge-weak, node-weak, and vulnerable. Let us now consider graphs in Fig. 2. A is node-weak, because its mvs fug is touched twice by the path s ! u ! v ! u ! t. By contrast, A is not edge-weak (and so neither vulnerable): its only mes's are fs ! ug and fu ! tg and no path passes twice through them. The graph B is node-weak and edge-weak because of the path s ! u ! v ! u ! v ! t that touches twice both the mvs fug and the mes fu ! vg; however, it is not vulnerable, since there is no st-embedding of W into it. As said above, the graph C is vulnerable and thus edge-weak, but not node-weak. Finally, the graph D is not node-weak (its mvs's are f g s , fug, fvg, and ftg and no one of them is touched twice by a path) nor vulnerable (there is no st-embedding of W into it), but it is edge-weak, because the path s ! u ! x ! y ! x ! y ! v ! t passes twice through the mes fu ! v; x ! yg.

In the general case, the inclusion diagram is depicted top-left in Fig. 2; if we restrict our attention to directed acyclic graphs (DAG), the inclusion diagram is depicted top-right in Fig. 2, as a consequence of the following result. Theorem 4 ([ 5 ]). If an st-graph G is a DAG, then the following statements are equivalent: (1) G is vulnerable; (2) G is edge-weak; (3) G is not two{terminal series{parallel; (4) G contains a node-weak subgraph.

W / A v3 / v4

Node-Weak :% t

C s D

Vulnerable =

Edge-Weak / u x x / vO 8 y / t A

B

W

C

D Node-Weak

Edge-Weak / F u v / t s B / u f & v / t s C Detecting Braess-paradox in a tra c network is an NP -complete problem [ 11 ]. We proved [ 4, 3 ] that computing the minimum saturating ow in depletable channels is NP -hard (and the associated decisional problem is NP -complete). This result can be easily adapted to ow networks. Stemming from our results of Sect. 3, we succeeded in nding polynomial algorithms to check edge-weakness, node-weakness, and vulnerability.

A trivial algorithm to check if a graph G is node-weak is to generate all its mvs's [ 10 ] and, for each mvs S check if there exists a path between two nodes of S. However, the number of mvs's can be exponential in jV j. In [ 4 ], we present a polynomial algorithm that checks weakness by checking at worst O(jV j2) mvs. Theorem 5 ([ 4 ]). Checking whether an st-graph G = (V; E) is node-weak can be solved in time O(jV j2 jEj).

The same algorithm to detect node-weakness can be adapted to edgeweakness, by letting mes play the role of mvs, thus proving the following. Theorem 6 ([ 9 ]). Checking whether a directed st-graph G = (V; E) is edgeweak can be solved in time O(jEj3).

An st-graph is redundant if it contains redundant edges, i.e., edges that do not belong to any simple path from s to t. For example, the graph B in Fig. 2 is redundant because of the edge u ! v. Redundant edges play no role in Wardrop equilibria: removing a redundant edge from a graph G leads to a graph G0 that is vulnerable if and only if G is itself vulnerable.

In [ 7 ], it was proved that vulnerable and not redundant graphs coincide with two-terminal series-parallel graphs, and this implies the existence of e cient algorithms to check if a non-redundant st-graph is vulnerable [ 12 ]. However, we proved [ 6 ] that checking if a graph is redundant is itself NP -complete and thus, checking preconditions of the algorithm proposed by [ 7 ] is computationally hard.

In [ 6 ], we presented an algorithm that works on any directed st-graph G. At each main step, we analyse a cycle in G and either: (1) we remove a redundant edge, thus breaking a cycle; or (2) we nd an st-embedding of W. This process always ends nding an st-embedding of W or in a DAG G0 that is vulnerable i G is vulnerable; and the vulnerability of G0 can be checked in linear time. Theorem 7 ([ 6 ]). Checking whether a directed st-graph G = (V; E) is vulnerable can be solved in time O(jV j jEj2).

The algorithm for checking vulnerability can be adapted to the homeomorphic subgraph problem without node mapping. In general, this problem is NP complete [ 8 ], except when, as W, the pattern graph has all nodes with degree at most 3. In this case, some pattern graphs are known for which this problem is polynomial. We have added the pattern graph W to this family. Theorem 8 ([ 6 ]). Checking whether a directed graph G = (V; E) contains a subgraph homeomorphic to W can be solved in time O(jV j3 jEj2). 5

Open Problems We conclude by singling out some interesting open problems. First of all, it would be interesting to investigate if our graph theoretic characterisations and the corresponding polynomial algorithms can be extended to the multi-commodity model, where several source and target nodes are present.

Another issue is e ciency of our algorithms. Are they optimal? Which are lower-bounds of checking node-, edge-weakness, and vulnerability?

Finally, it would be interesting investigating a general algorithm for checking the subgraph homeomorphism problem for all pattern graphs with at most 3 as node degree, at least for patterns that are, as W, st-graphs.

References

1. R. Ahuja , T. Magnanti , and J. Orlin . Network Flows, theory, algorithms, and applications . Prentice-Hall, New Jersey, 1993 .

2. M. Beckmann , C. B. McGuire , and C. B. Winsten . Studies in the Economics of Transportation . Yale University Press, 1956 .

3. P. Cenciarelli , D. Gorla , and I. Salvo. Depletable channels: Dynamics and behaviour . In Proc. of FCT09 , volume 5690 of LNCS , pages 50 { 61 . Springer, 2009 .

4. P. Cenciarelli , D. Gorla , and I. Salvo. Depletable channels: Dynamics, behaviour, and e ciency in network design . Acta Informatica , 2018 . Accepted.

5. P. Cenciarelli , D. Gorla , and I. Salvo. Ine ciencies in network models: A graph theoretic perspective . Information Processing Letters , 131 : 44 { 50 , 2018 .

6. P. Cenciarelli , D. Gorla , and I. Salvo. A polynomial-time algorithm for checking the possibility of braess paradox in directed graphs . Algorithmica , 2018 . In press.

7. X. Chen , Z. Diao , and X. Hu . Network characterizations for excluding braess's paradox . Theory of Computing Systems , pages 1 { 34 , 2016 .

8. S. Fortune , J. Hopcroft , and J. Wyllie. The directed subgraph homeomorphism problem . Theoretical Computer Science , 10 ( 2 ): 111 { 121 , 1980 .

9. F. Granese . Polynomially recognising graphs where saturating ows are always maximum . BSc Thesis , Sapienza University of Rome., October 2017 .

10. T. Kloks and D. Kratsch . Listing all minimal separators of a graph . SIAM J. Comput. , 27 ( 3 ): 605 { 613 , 1998 .

11. T. Roughgarden . On the severity of Braess's Paradox: Designing networks for sel sh users is hard . J. Comput. Syst. Sci. , 72 ( 5 ): 922 { 953 , 2006 .

12. J. Valdes , R. Tarjan , and E. Lawler. The recognition of series-parallel digraphs . SIAM Journal of Computing , 11 : 298 { 313 , 1982 .