NP-Hard Problems in Networks

Exercises

1 Disjoint Paths for Bounded Length

For two vertices x and y in G with (x, y) ∉ E(G), let ζ_{ℓ}(G; x, y) be the maximum number of internally disjoint (x, y)-paths in G whose length does not exceed ℓ, and let κ_{l}(G; x, y) be the minimum number of vertices in G the deletion of which destroys all (x, y)-paths of length at most l.

It is of interest to study the relation between these two parameters for any l with 2 ≤ d(G; x, y) ≤ ℓ ≤ n − 1, where n = |V (G)|. Menger’s theorem implies ζ_{n−1}(G; x, y) = κ_{n−1}(G; x, y). In general,

ζ_{ℓ}(G; x, y) ≤ κ_{ℓ}(G; x, y),  (1)

Lovász, Neumann-Lara and Plummer [2] proved that the equality holds if ℓ = 2, 3, 4 or d(G; x, y).

Itai, Perl and Shiloah [1] have showed that determining ζ_{ℓ}(G; x, y) is NP-complete for any graph G and ℓ ≥ 5. A heuristic algorithm for finding a maximum number of disjoint bounded length paths has been given by Ronen and Perl [3].

References

[1] Itai, A., Perl, Y., and Shiloah, Y., The complexity of finding maximum disjoint paths with length constraints. Networks, 12 (1982), 277-286.

[2] Lovász, L., Neumann-Lara, V., and Plummer, M. D., Mengerian theorems for paths of bounded length. Periodica Mathematica Hungarica, 9 (1978), 269-276

[3] Ronen, D., and Perl, Y., Heuristics for finding a maximum number of disjoint bounded paths. Networks, 14 (1984), 531-544

2 Forwarding Indices of Routings

A routing R in G is a set of n(n−1) fixed paths for all ordered pairs (x, y) of vertices of G. The path R(x, y) specified by R carries the data transmitted from the source x to the destination y. It is possible that the fixed paths specified by a given routing R pass too frequently through certain vertices or edges, which means that the routing R overloads the vertex or the edge. The load of any vertex or edge is limited by the capacity of the vertex or the edge, otherwise it would affect the efficiency of transmission, even resulting in malfunction of the network. In order to measure the load of a vertex or an edge, Chung, Coffman, Reiman and Simon [1] proposed the notion of the forwarding index.

Let G be a graph with a given routing R, x a vertex of G and e an edge of G. The load of x with respect to R, denoted by ξ(G, R, x) [resp. the load of e with respect to R, denoted by π(G, R, e)], is defined as the number of paths specified by R passing through x [resp. e].

The vertex-forwarding index and the edge-forwarding index of G with respect to R are, respectively, defined as

ξ(G, R) = max{ξ(G, R, x) : x ∈ V (G)}

and

π(G, R) = max{π(G, R, e) : e ∈ E(G)}.

The vertex-forwarding index and the edge-forwarding index of G are, respectively, defined as

ξ(G) = min{ξ(G, R) : R is a routing of G}

and

π(G) = min{π(G, R) : R is a routing of G}.

The original study of forwarding indices is motivated by the problem of maximizing network capacity, see [1]. Minimizing the forwarding indices of a routing will result in maximizing the network capacity. Thus, it becomes very significant to determine the vertex and edge-forwarding indices of a given graph.

Many researchers have been interested in the forwarding indices of a graph, see, for example, [1, 2, 3]. However, Saad [5] found that for an arbitrary graph determining its vertex-forwarding index is NP-complete even if the diameter of the graph is two. Heydemann, Meyer, Sotteau and Opatrný [4] first showed that Problem 2.1 is NPcomplete for graphs of diameter at least 4 when the routings considered are restricted to be minimal, consistent and symmetric; a P-problem for graphs of diameter 2 when the routings considered are restricted to be minimal. However, a similar problem has not yet been solved for graphs of diameter 2 or 3 when the routings considered are restricted to be minimal and/or, consistent and/or symmetric.

References

[1] Chung, F.R.K., Coffman, E.G., Reiman, M.I. and Simon, B., The forwarding index of communication networks, IEEE Trans Info Theory 33 (1987), 224-232.

[2] M.C. Heydemann, J.C. Meyer, and D. Sotteau, On the forwarding index problem for small graphs, Ars Combin 25 (1988), 253-266.

[3] Heydemann, M. C., Meyer, J. C., and Sotteau, D., On forwarding indices of networks. Discrete Applied Mathematics, 23 (1989), 103-123 [4] Heydemann, M.-C., Meyer, J.-C., Sotteau, D. and Opatrný, J. Forwarding indices

of consistent routings and their complexity. Networks, 24 (1994), no. 2, 75-82

[5] Saad, R., Complexity of the-forwarding index problem. SIAM J. Discrete Math., 6(3) (1993), 418-427.

3 Edge-Addition or Edge-Deletion Problems

In [1], Chung and Garey proposed the following problem: Give a graph G′ with diameter k′ and a positive integer k (k < k′), to obtain a graph G from G′ how many edges must be added to G′ such that the resulting G has diameter of at most k?

A version of this question can be stated as follows. For given positive integers t, k and a graph G′, can a graph G be obtained from G′ by adding t edges such that G has diameter of at most k?

In the literature, this question is called the “edge-addition problem”, and G is called an altered graph of G′. Although this problem has received quite a bit of attention in the literature, it is quite difficult in general, since it has been proved by Schoone, Bodlaender and van Leeuwen [2] to be NP-complete.

The dual of the “edge-addition problem” is the “edge-deletion problem”:

Give a graph G′ with diameter k′ and a given positive integer k (k′ ≤ k), how many edges can be removed from G′ such that the resulting graph G has a diameter of at most k?

Like the edge addition problem, the answer to this question seems to be also difficult in general, since it has been also proved by Schoone, Bodlaender and van Leeuwen [2] to be NP-complete.

References

[1] Chung, F. R. K., Garey, M. R., Diameter bounds for altered graphs. Journal of Graph Theory, 8 (4) (1984), 511-534

[2] Schoone, A. A., Bodlaeder, H. L., and van Leeuwen, J., Diameter increase caused by edge deletion. Journal of Graph Theory, 11 (3) (1987), 409-427

4 Rabin Numbers of Networks

In [1], Hsu and Lyuu proposed Rabin number of networks. Let G be a w (≥ 1)- connected graph, the w-Rabin number, denoted by r_{w}(G), is defined as the minimum number r such that for w+1 distinct vertices x, y_{1}, ⋯, y_{w} there exist w internally disjoint (x, y_{i})-paths in G of length at most r for each i = 1, 2, ⋯, w. In other worlds, r_{w}(G) is the minimum integer r for which there exists an (x, Y)-fan F_{w}(x, Y) such that every path in F_{w}(x, Y) is of length at most r for any vertex x in G and any set Y consisting of w vertices in G − x.

Hsu and Lyuu [1] have proved that the problem of determining r_{w}(G) ≤ l is NPcomplete for a given w-connected graph G and an integer l. Thus, the problem we are concerned with is determining the exact value of r_{w}(G) for a given w-connected graph G. We will below introduce the exact values of the Rabin numbers for some well-known networks. All proofs will be here omitted because of the limitations of space.

References

[1] Hsu, D. F., and Lyuu, Y. D., A graph-theoretical study of transmission delay and fault tolerance. International Journal of Mini and Microcomputers, 16 (1)1994, 35-42

5 Wide Diameter

In [1], Hsu proposed the concept of the wide-diameter of G. Suppose that G is a w-connected graph, w ≥ 1. The w-diameter of G, d_{w}(G), is defined as the maximum number ℓ for which there are w internally disjoint (x, y)-paths of length at most ℓ for any pair of distinct vertices x and y of in G.

It is desirous that an ideal interconnection network G should be one with connectivity κ(G) as large as possible and diameter d(G) as small as possible. The wide-diameter d_{w}(G) combines connectivity κ(G) and diameter d(G), where 1 ≤ w ≤ κ(G). Hence d_{w}(G) is a more suitable parameter than κ(G) and d(G) to measure fault-tolerance and efficiency of parallel processing computer networks. Thus, determining the precise value of d_{w}(G) is of significant for a given graph G and an integer w. However, Hsu [1] proved that this problem is NP-complete.

References

[1] Hsu, D. F., On container width and length in graphs, groups, and networks. IE-ICE Transaction on Fundamentals of Electronics, Communications and Computer Science, E77-A (1994), 668-680