All work should be done on your own. If you discuss this assignment in any way with anyone else, or find help for getting the answer from any source, you must state so clearly at the top of your submission. There should be no working together except to understand the question.

    1. Show that the following greedy algorithm fails to find the minimum cut if you are given a network which arises from the bipartite cardinality matching problem:

      • Place s in S and t in T.
      • Repeatedly consider adding all vertices to both S and T, and count the number of edges this would make go across the cut. (I.e. if v is placed in S, see how many edges v has to vertices already placed in T, and then repeat if placed in T.)
      • Choose to minimize the number of new edges which go across the cut from S to T.
      • If there's a tie, select the tied vertex that has the most edges which would go from S to T if placed in the other set.

      This algorithm is somewhat unintuitive. Consider the following bipartite matching problem considered as a max flow problem:

      The basic bipartite cardinality matching problem is potential matches. A can only match with 1, B can match with 1 or 3, etc. A solution which will find the maximum number of matches can be found by representing the matching as a maximum flow problem with the following characteristics:

      • "Producers" are represented as sources
      • "Consumers" are represented terminals
      • All edges are have a weight of one (c(u, v) = 1)
      • To simplify, all sources are bound to a single super-source and all terminals to a super-terminal

      A cut of the graph is simply a partition of the set of all vertices, V, into two sets, S and T, ∋

      • s ∈ S
      • t ∈ T
      • S ⋃ T = V
      • S ⋂ T = ∅

      For any cut of the graph, there is an associated cost which is the sum of the edges which have one end in S and the other in T. Out of the 2|V| - 2 possible cuts there is a minimum cost. This minimum cost is also the maximum flow through a graph. This makes sense because flow has to get from s in S to t in T and can only do so via edges that bridge S and T.

      Consider a mincut for the original bipartite example:

      For an edge to count toward the cut cost it must start in S and end in T. The dashed edges are the only edges that meet this criteria. There are three of them and the max flow can, through an examination of the graph, be seen to be three.

      Drawing the graph and the cut is at times misleading. For example, the edge (B, 3) crosses the drawn cut line, but note that it passes back out before arriving at 3. Likewise the edge (C, 4) crosses the line into T, but it originates there as well.

      Recall that edges from T to S do not count toward the cost, so (C, 3) does not contribute.

      To examine the algorithm and it's potential issues, consider the following graph:

      The optimum cut of this graph is of cost 1 and is simply:

      The first iteration the state is as follows:

      • S = {s}
      • T = {t}
      • v |{(u, v}| ∋ u ∈ S |{(v, u}| ∋ u ∈ T
        A10
        101
        201

      Adding A to S will minimize the number of edges from the current S to the current T. (Since there are 0 edges to the current T from A.

      The minimum cut needs to be made between s and A and the algorithm now cannot find an optimum cut. It will ultimately end with a cut of cost 2:

    2. Show that the following local improvement algorithm fails to find the minimum cut if you are given a network which arises from the bipartite cardinality matching problem:

      • Start with an arbitrary cut.
      • If there is a vertex v which can be switched from one set to the other and reduce the number of edges which cross the cut from S to T, switch v to the other set.
      • Stop when no further improvements can be made.

      As is often the case with local improvement that relies on an arbitrary starting point, a poor solution can result from a poorly chosen starting point. Consider the following graph and cut:

      There are four vertices that could be considered for flipping:

      1. A:
      2. B:
      3. 1:
      4. 2:

      Each of these produces a cost of three which is more than the optimum solution of two.

  2. Show that there can be Ωn phases of the max flow algorithm when Dinic's algorithm is run on a network which comes from a bipartite matching problem. (Hint: Make the graph disconnected, and make each component require a different length augmenting path.)

    See attached sheet.

  3. Suppose you have a graph such that for each vertex v, the neighborhood of v does not contain 3 independent vertices. Show that you can find a matching in such a graph in linear time. (Hint: Build a breadth-first search tree, and do your search from the bottom of the search tree to the root.)

    Independent vertices in a graph are vertices which do not share an edge. Though the question does not say that the graph is a representation of a bipartite matching, we are asked to find a matching, so it is assumed this is the case.

    In a flow diagram to find a bipartite matching there are always three levels of edges. These can be identified as:

    • "Source" from the source to each of the set of producers — (s, v) ∋ v ∈ P
    • "Terminal" from each of the set of consumers to the terminal — (v, t) ∋ v ∈ C
    • "Preference" between the producers and the consumers depending on the characteristics of the matching — (u, v) ∋ u ∈ P, v ∈ C

    The problem is the producers in a bipartite matching are, by definition, independent, since they are only connected to consumers. In order for the source to not have three independent vertices, the producers would have to be connected to each other (or there could only be two of them). Therefore it is assumed that this is a general graph with edges all of weight 1 and a "matching" is a set of paths from s to t. Moreover, since a single path from s to t can be found for an arbitrary graph via search in O(m + n) time, it is assumed a "matching" refers to the maximal size set of paths from s to t.

    The solution to such a problem is essentially given by the hint. Building a breadth-first search tree from the root with marking of nodes so they are not revisited would take O(m + n) time. Such a marked tree would not work in the general case because a node might be marked as used which is part of a path without which the maximal set of paths cannot be found. Because of the high degree of connectivity in this graph, this cannot happen.

    In order for a node to be eliminated which is a part of necessary path the edges entering this node must be connected to nodes for which there is no alternate path. This would require three vertices to be independent which is contrary to the problem statement.

    The paths in the non-repeated node breadth-first search tree that include an edge connected to the terminal are a maximal set of paths from s to t. This set of paths can be found in a tree with a maximum depth of d in time O(d × |{(v, t)}|)

  4. Suppose that a marriage broker is very worried about affairs among couples he arranged marriages for. The goal in the suspicious broker problem is to match as many married couples as possible with the additional constraint that if m1 is married to f1, and m2 is married to f2 there can be no edge between m1 and f2, or m2 and f1.

    Show that this problem is NP-complete for the matching of k couples. (Hint: Use independent sets.)

    Consider Cook's theorem for proving NP-completeness. It devises a system for representing the tape and states of an arbitrary Turing machine as the components of a boolean satisfiability problem. This means that if the boolean satisfiability problem can be solved in polynomial time then the solution of an arbitrary Turing machine may be solved in polynomial time as well.

    The above problem may be represented as a boolean satisfiability problem in a straightforward way using the following predicates:

    • r(m, f) → m is married to f ((m, f) is a part of the matching solution)
    • a(m, f) → m is attracted to f (there exists an edge (m, f))

    The boolean statements are expansion of the possible values of:

    ∀ i, j m(mi, fj) ⇒ ¬∃ k ≠ j ∋ a(mi, fk)

    This may be converted to a boolean statement using the equality: A ⇒ B ⇔ ¬B ∨ A.