Scribd Logo
Upload

Welcome to Scribd!

  • 156 views

    Solutions To Assignment 4

    Uploaded by

    radin1
    The document discusses solutions to exercises on data structures and algorithms. Exercise 1 asks about finding the minimum effort required to isolate a spammer in a communication network using spam filters on network edges. The solution formulates this as a minimum cut problem on a capacity graph and provides an algorithm that runs in O(n^2*m) time. Exercise 2 provides counterexamples showing that certain properties are not always true for the "most vital arc" of a network, which is defined as the arc whose removal causes the largest decrease in maximum flow value. It also shows that property (c) is always true.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Solutions To Assignment 4

    Uploaded by

    radin1
    156 views4 pages
    The document discusses solutions to exercises on data structures and algorithms. Exercise 1 asks about finding the minimum effort required to isolate a spammer in a communication network using spam filters on network edges. The solution formulates this as a minimum cut problem on a capacity graph and provides an algorithm that runs in O(n^2*m) time. Exercise 2 provides counterexamples showing that certain properties are not always true for the "most vital arc" of a network, which is defined as the arc whose removal causes the largest decrease in maximum flow value. It also shows that property (c) is always true.

    Original Description:

    Operation research

    Original Title

    sol4

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses solutions to exercises on data structures and algorithms. Exercise 1 asks about finding the minimum effort required to isolate a spammer in a communication network using spam filters on network edges. The solution formulates this as a minimum cut problem on a capacity graph and provides an algorithm that runs in O(n^2*m) time. Exercise 2 provides counterexamples showing that certain properties are not always true for the "most vital arc" of a network, which is defined as the arc whose removal causes the largest decrease in maximum flow value. It also shows that property (c) is always true.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    156 views4 pages

    Solutions To Assignment 4

    Uploaded by

    radin1
    The document discusses solutions to exercises on data structures and algorithms. Exercise 1 asks about finding the minimum effort required to isolate a spammer in a communication network using spam filters on network edges. The solution formulates this as a minimum cut problem on a capacity graph and provides an algorithm that runs in O(n^2*m) time. Exercise 2 provides counterexamples showing that certain properties are not always true for the "most vital arc" of a network, which is defined as the arc whose removal causes the largest decrease in maximum flow value. It also shows that property (c) is always true.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    Data Structures and Algorithms

    FR 6.2 Informatik
    Sanders, Telikepalli

    WS 03/04

    http://www.mpi- sb.mpg.de/~sanders/courses/algdat03/index.html

    Solutions to assignment 4
    Exercise 1
    A spammer is located at one node q in a undirected communication network G and peaceful
    email users are located at nodes denoted by the set S. Let c uv denote the eort required to
    install a spam lter for the network edge (u, v). The problem is to determine the minimal eort
    required to isolate the spammer from the email users using the spam lters. Find an ecient
    polynomial time algorithm to solve this problem.
    Solution: The communication network can be seen as a capacity-graph. The network participants are the nodes, the connections are the edges and the spam blocking eorts are the edge
    capacities. We interpret the spam mails as a ow through the network, the start node of which
    is q. We create an articial target node t, which we connect to all nodes of S. We calculate the
    sum K of all capacities cuv . We set the capacities of the edges between S and t to K + 1. The
    goal is to nd a minimal q-t-cut: If we block all edges leaving this cut, we get a total isolation
    of q with a minimal eort. In order to nd this cut, we rst calculate a maximum ow (e.g. by

    the Highest-Level-Preow-Push-Algorithm in time O n2 m ). Then we create the residual


    network (in time O(m)) and look at all nodes reachable from q (e.g. by breadth-rst-search in
    time O(n + m)). By the Min-Cut-Max-Flow-Theorem, we know that the set of nodes reachable
    from q constitutes a minimal cut. The cut does not contain any node of S: Suppose the cut
    contains a node v S. Since we set cap((v, t)) = K + 1, there will always be the edge (v, t) in
    the residual network, because no possible ow can use up this capacity. Hence, if v is reachable
    from q, then so is t. Hence, t would belong to the cut, which is a contradiction. Now, we
    block all edges leaving the cut (O(m)) and the spammer is isolated. The total time needed is

    O n2 m .
    Exercise 2
    We dene a most vital arc of a network as an arc whose deletion causes the largest decrease
    in the maximum s-t-ow value. Let f be an arbitrary maximum s-t-ow. Either prove the
    following claims or show through counterexamples that they are false:
    (a) A most vital arc is an arc e with the maximum value of c(e).
    (b) A most vital arc is an arc e with the maximum value of f (e).
    (c) A most vital arc is an arc e with the maximum value of f (e) among arcs belonging to some
    minimum cut.
    (d) An arc that does not belong to some minimum cut cannot be a most vital arc.
    (e) A network might contain several most vital arcs.

    Solution:

    c
    1/1

    1/1
    s

    1/1

    2/1

    1/1
    1/1

    2/2

    2/2
    t

    d
    2/1

    2/1

    a
    This is a counterexample for (a), (b) and (d) and an example for (e). The specied ow f is
    a maximum ow with the value three. The deletion of any edge decreases the ow value by
    one. Hence, each edge is a most vital arc ( (e) is true). The edge e = (s, b) has neither the
    maximum value of c(e) nor the maximum value of f (e); still, it is a most vital arc ( (a) and
    (b) are false). The edge (s, a) does not belong to any minimum cut; still, it is a most vital arc
    ( (d) is false).
    (c) is true. The maximum ow value is equal to the value of the ow through any minimum cut.
    When we remove an edge e from a minimum cut, the value of the ow through the minimum
    cut and thus the maximum ow value decrease by f (e). Hence, a most vital arc e must have
    the maximum value of f (e) among arcs belonging to some minimum cut because, if there was
    another edge e with f (e ) > f (e) in the same minimum cut, the deletion of e would cause a
    larger decrease than the deletion of e so that e could not be a most vital arc.
    Exercise 3
    Dining Problem. Several families go out to dinner together. To increase their social interaction,
    they would like to sit at tables so that no two members of the same family are at the same table.
    Show how to formulate nding a seating arrangement that meets this objective as a maximum
    ow problem. Assume that the dinner contingent has p families and that the ith family has a(i)
    members. Also assume that q tables are available and that the jth table has a seating capacity
    of b(j).
    Solution
    The capacitated graph G(V, E) is dened as:
    V

    = {s, t} {ui | 1 i p} {vj | 1 j q}

    E = {(s, ui ) | 1 i p} {(ui , vi ) | 1 i p, 1 j q} {(vj , t) | 1 j q}

    cap(s, ui ) = a(i)
    cap(ui , vj ) = 1

    cap(vj , t) = b(j)
    An integral solution to the maxow problem gives an assignment of families to tables. A
    ow from ui to vj is either zero or one, with one meaning that a member of family i sits in
    table j. The maximum ow maximizes the number of people that can be seated under the
    stated constraints.
    Exercise 4
    In this exercise we analyze the running time of dierent variations of the preow-push algorithm
    with the highest-level selection rule. Assume that ties are broken as follows:
    Of active nodes on the highest level the one with the smallest number is selected rst.
    Of eligible edges the one leading to the largest numbered node is selected rst.
    (Would a dierent ordering of the eligible edges change your answer in any of the cases?)
    Consider the following capacitated graphs:

    v1

    v2

    1
    1

    v3
    1

    G1

    vn2

    v1

    v2

    2
    1

    v3
    1

    G2

    vn2

    vn3

    vn4
    1

    vn2 n 3

    1
    This is n 3 not n 2 on purpose.

    G3

    n3

    n3

    v1

    n3

    s
    Give the asymptotic running time (total number of pushes and relabelings) of the following
    three heuristics for all three graphs. Justify your answer. (Hint: The running time is (n) or
    (n2 ) in all cases.)
    (a) Local relabeling. When relabeling a node v, the new level is computed as
    d(v) = 1 + min{d(w) | (v, w) Gf }.
    Solution
    (n) for G1 , (n2 ) for G2 and G3 .
    (b) Global relabeling. In the beginning and after every m (= 2n 4 in this case) operations,
    the distance labels are recomputed as follows:

    if there is a path from v to t in G f


    (v, t)
    d(v) =
    n + (v, s) if there is a path from v to s but not to t in G f

    2n 1
    otherwise
    Here (v, w) is the smallest number of edges on a path from v to w.
    Solution
    (n2 ) for G1 , (n) for G2 and G3 .
    (c) Gap heuristic. When a level
    lifted to level n.

    becomes empty, all nodes on the levels

    + 1 to n 1 are

    Solution
    (n) for G1 and G2 , (n2 ) for G3 .
    An explanation for G3 :
    We start running the algorithm. In the rst step we push one unit of ow through all the
    outgoing from s edges. Now the excess of the nodes v 1 , v2 ,.., vn2 is exactly 1. According
    to the rules we start choosing the active nodes on the highest level with the smallest index
    number. The node v1 will be chosen rst. The distance label of all the nodes except s
    is zero, so we do not have any eligible edges outgoing from v 1 . Hence, we recalculate the
    distance label of v1 increasing it by one. After this procedure we didnt get any gaps but
    we got an eligible edge (v1 , t). We push one unit of ow through this edge. The next node

    with positive excess is v2 . The current distance of v2 is zero. To get an eligible edge we
    have to increase the distance label twice. And again we dont get any gaps. We send a
    unit of ow from v2 to t. We continue this procedure n 3 times (because of the capacity
    of the edges). In the end we reach the node v n2 with excess one. We repeat the distance
    relabelling operation n 2 times and send this unit of ow to v n3 . The only outgoing
    edges from vn3 are (vn3 , vn2 ) with distance n2 and (vn3 , s) with distance n. Current
    distance label of vn3 is n 3. We increase it once and get a gap. Hence the labels of the
    nodes vn2 and vn3 become n. We increase the label of the node v n2 once again and
    after this procedure we have two eligible edges (v n2 , vn3 ) and (vn2 , s). According to
    our rule that in every step we choose the eligible edge with the largest numbered index,
    we push the ow from vn2 to vn3 and after increasing the distance label of v n3 by one
    we have the possibility to send this last unit of ow back to the source. The procedure
    described above takes (n2 ) time.

    You might also like