CS 4301 — Special Topics in Computer Science: Optimization, Homework 4

Iniyan Joseph and Suraj Mathashery

Download PDF

Increasing by a certain amount made the arc tight, which wouldn’t be possible if or , since increasing wouldn’t change . Additionally, if and , then increasing would decrease the value of , which couldn’t make the condition tight. Therefore, increasing will only make an edge go tight if and . Because , in every iteration of the loop, we add a vertex to . This is a shortest path. This is obviously true in the beginning, because the edge that goes tight the cheapest for a vertex . Because there is a to which the vertex newly added is connected, there is a path to the newly added vertex, where the path is a subset of , the statement holds true in every iteration of the loop. It is the cheapest path because if there was a cheaper edge connecting a vertex in to a vertex outside of , those edges would go tight first. Thus, the edge which goes tight is an edge of an shortest path which we are constructing. Once is added to the path, that means that is a tree, containing a minimum path, and the algorithm can terminate. (Indeed, it also contains the shortest path from to any other vertex ).

The quantity is equal to the sum of the weights of the arcs on the path , since all these arcs are tight. In our algorithm, we continuously add the vertex for which we have a “cheapest” path to that vertex in a BFS-style manner. This is Dijkstra’s Algorithm.

Let . Label an edge, , red if , and blue if . No edge can be both red and blue because otherwise, a lesser weight matching could be made with the edges and .

Because every vertex must be matched, must be matched to some vertex in . This creates two vertices in which cannot be matched using an edge connected to . These vertices must then match to two vertices in by the definition of a perfect matching. This creates another two edges in which we call and . This holds inductively until every vertex is matched with no loops in the projection. Because no edge is taken twice and contains no loops, it is an odd length path in .

The number of edges in must be odd (and thus the number of vertices even), since otherwise it would be possible to form a cheaper matching using a for at least one vertex not matched the matching.

contains a path from . Additionally, since each vertex copy can be matched to at most one edge, each vertex in the projection has a degree of at most 2. Let be a set of vertices that contain a cycle in . Each vertex’s quota of two edges is accounted for by the cycle, so is an independent set from the rest of the vertices. Additionally, since accounts for edges in the matching, each of which are of positive weight, we could replace the edges between C with the edges for each , for a lower cost matching, leading to a contradiction. Therefore, contains no cycles.

Because the projection is an path with no cycles, has no repeated edges, and has an odd number of edges, and because the non-loop edges are of minimum weight, is a path. It is the shortest path, because if there were a cheaper path, there would also be a corresponding cheaper matching that could be formed as follows: Label each edge in the path . For each edge with an odd label, (including the edges incident to and since the path is of odd length), the edge can be taken in the matching in . For every edge with an even label, the edge can be taken in the matching in . For all other vertices , a edge can be taken in the matching.

The new graph is of strongly polynomial size and takes strongly polynomial time to create. Computing a perfect matching is strongly polynomial, thus the algorithm takes strongly polynomial time to run.