=Paper=
{{Paper
|id=Vol-2243/paper8
|storemode=property
|title=Graph Theoretic Detection of Inefficiencies in Network Models
|pdfUrl=https://ceur-ws.org/Vol-2243/paper8.pdf
|volume=Vol-2243
|authors=Ivano Salvo,Daniele Gorla,Pietro Cenciarelli
|dblpUrl=https://dblp.org/rec/conf/ictcs/SalvoGC18
}}
==Graph Theoretic Detection of Inefficiencies in Network Models==
https://ceur-ws.org/Vol-2243/paper8.pdf
Graph Theoretic Detection
of Inefficiencies in Network Models
Ivano Salvo, Daniele Gorla, and Pietro Cenciarelli
Sapienza University of Rome, Dpt. of Computer Science
Abstract. We present graph-theoretic characterisations of three notions
of inefficiency arising in network models: edge-weakness in flow networks,
node-weakness in depletable channels, and vulnerability in traffic net-
works. Our characterisations lead to three polynomial algorithms that
check these forms of inefficiency. Furthermore, checking vulnerability also
leads to an advancement on the subgraph homeomorphism problem.
1 Introduction
In this paper, we summarise a bunch of works [4, 3, 6, 5, 9] devoted to graph-
theoretically characterise three notions of inefficiency arising in three network
models: flow networks, depletable channels, and traffic networks.
In the standard model of flow networks, where flows are constrained by
edge capacities, and in depletable channels, where flows are constrained by node
charges, inefficiency is related to the existence of non-maximum saturating flows.
Thus, a directed graph is said to be edge-weak (resp. node-weak) if there exists a
capacity (resp. charge) assignment to edges (resp. nodes) such that the resulting
flow network (resp. depletable channel) admits non-maximum saturating flows.
In the traffic network model for selfish routing, inefficiency is related to the
fact that removing edges can lead to networks with a lower latency for agents at
the Nash equilibrium (usually referred to as Wardrop equilibrium in this setting).
A directed graph is said vulnerable if there exists a latency function on edges
such that the resulting traffic network suffers from the so-called Braess-paradox:
the delay of agents in traveling from a given source node to the target node at
the Wardrop equilibrium can be reduced by removing edges. Interestingly, also
edge-weak and node-weak graphs can be made efficient by removing edges.
Here, we recall our graph theoretic characterisations edge-, node-weakness,
and vulnerability. These notions lead to three different classes of graphs in the
general case, whereas, in the acyclic case, node-weak graphs are a subset of edge-
weak graphs, that in turn coincide with vulnerable graphs. Our characterisations
lead to three polynomial time algorithms that check whether a directed graph
is edge-weak, node-weak, or vulnerable.
2 Inefficiencies 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 flow networks [1], edges are endowed with capacities
and admissible flows can not exceed edge capacities. In the graph of Fig. 1(b),
two flow 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 flow of one
:u 1
:u 1 :1 x
:u 1
" " " "
s >t s 1 >t ◦ =◦ s 0 >t
# 1 # 1 # 1 # x
(a) v (b) v (c) 1 (d) v
Fig. 1. The Wheatstone graph W (a) and three models built upon W: a flow network
(b), a depletable channel (c), and a traffic network (d).
unit along the path s → u → v → t would saturate the net (i.e., no more flow can
be sent from s to t). This is inefficient, since not all possible flow is delivered.
We call edge-weak those graphs that, as W in Fig. 1(a), admit non-maximum
saturating flows for some capacity-to-edge assignments, as in Fig. 1(b).
In depletable channels [3], a model for energy consumption in wireless net-
works, each node u is equipped with an integer η(u) ≥ 0 representing its
depletable charge. Node charges constrain admissible flows: 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 non-
maximum saturating flows for some charge-to-node assignment (Fig. 1(c)).
In traffic networks [2], edges are labelled with latency functions, that models
agent delay along an edge in terms of its congestion, that is the flow on that
edge. Autonomous selfish users choose the faster path and the traffic stabilises
to an equilibrium of a noncooperative game, (Wardrop equilibrium). The traffic
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 flow on them; the edge (u → v) causes no delay; two
edges (v → t and s → u) cause a delay linear in the flow on them. Selfish users
control a negligible part of traffic ε 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 flow 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 min-
imal 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
{u, v} 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 flows have always value min{η(v1 ) +
η(v2 ), η(v3 ) + η(v4 )}: no st-path touches any of its mvs’s twice.
Similarly, a minimal edge separator (mes for short) of an st–graph is a mini-
mal 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 flow network with the same flows as that of Fig. 1(b).
Indeed, the path s → v1 → v4 → t touches twice the mes {s → v1 , v2 → v3 , v4 → t}.
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 ) ; ψ(v 0 ) are node disjoint paths (apart for their extremes) whenever
u 6= u0 or v 6= v 0 , 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 iff there is an st-
embedding 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 ): {(sW → u, sc → v1 ), (sW → v, sc →
v2 → v4 ), (u → v, v1 → v4 ), (u → tW , v1 → v3 → tC ), (v → tW , v4 → tc )}. 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 {u} 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 {s → u} and {u → t} 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 {u} and
the mes {u → v}; 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 {s}, {u},
{v}, and {t} 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 {u → v, x → y}.
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.
Vulnerable Vulnerable =
Edge-Weak
A B W C D C
W
Node-Weak
Node-Weak Edge-Weak
8 v1 / v3
& A
/u /t /uf /t % /u /v /t
s F s v s :t s O
C
%
v2 /
v4
x
A v B
D x 8y
Fig. 2. The inclusion diagram for general directed graphs (top-left) and directed acyclic
graphs (top-right). W is the Wheatstone graph from Fig. 1(a).
4 Polynomial Detection of Net Inefficiency
Detecting Braess-paradox in a traffic network is an NP -complete problem [11].
We proved [4, 3] that computing the minimum saturating flow in depletable
channels is NP -hard (and the associated decisional problem is NP -complete).
This result can be easily adapted to flow networks. Stemming from our results
of Sect. 3, we succeeded in finding 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 |V |. In [4], we present a
polynomial algorithm that checks weakness by checking at worst O(|V |2 ) mvs.
Theorem 5 ([4]). Checking whether an st-graph G = (V, E) is node-weak can
be solved in time O(|V |2 · |E|).
The same algorithm to detect node-weakness can be adapted to edge-
weakness, 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 edge-
weak can be solved in time O(|E|3 ).
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 efficient
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 find an st-embedding of W. This process
always ends finding an st-embedding of W or in a DAG G0 that is vulnerable iff
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 vulner-
able can be solved in time O(|V | · |E|2 ).
The algorithm for checking vulnerability can be adapted to the homeomor-
phic 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(|V |3 · |E|2 ).
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 efficiency 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 be-
haviour. 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 efficiency in network design. Acta Informatica, 2018. Accepted.
5. P. Cenciarelli, D. Gorla, and I. Salvo. Inefficiencies 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 flows 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
selfish 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.