Mixed Postman Problem
1. Introduction
The mixed postman problem (MPP) is a generalization of the Chinese Postman Problem (CPP). In the MPP, the input
graph may contain both undirected edges and arcs (directed edges). The objective is to find a tour that traverses every
edge at least once and traversed directed edges only in the direction of the arc.
Even though both undirected and directed versions of the CPP are polynomial time solvable, Papadimitriou showed MPP
is NP-hard.
2. Definitions
Mixed graph: a graph may contain both undirected edges and arcs (directed edges).G(V,E,A,C): V-vertices E-edges A-arcs C-costs on E and A.
- Degree(v): the total number of edges and arcs incident to v.
- Indegree(v): the number of incoming arcs into v.
- Outdegree(v): the number of outgoing arcs from v.
3. Properties of Eulerian graphs
A graph is Eulerian if there is a tour that traverses each edge of the graph exactly once.
- An undirected connected graph is Eulerian if and only if the degree of each vertex is even.
- A directed connected graph is Eulerian if and only if for each vertex v, outdegree(v) = indegree(v).
If a mixed graph satisfies both the conditions, there exists a tour using each edges and arcs just once. And we can find the directed or undirected Eulerian tour in polynomial time. So here we are interested in is to find a set of additional edges and arcs of minimum total cost that can be added to mixed graph to make it Eulerian and identify the tour over the resulting graph.
Basically, the output is a Eulerian graph H that contains the input graph G as a subgraph. So each edge of H can be classified either as an original edge or as a duplicated edge. Also, each arc of H is either an original arc, a duplicated arc an oriented edge, or a duplicated and oriented edge.
Frederickson presented an approximation algorithm for MPP called Mixed algorithm. The algorithm comprises two
heuristics called Mixed1 and Mixed2. Both of them are 2-approximation algorithm for MPP.
4. Mixed1: 2 – approximation algorithm ( G.N.Frederickson 1979 )
Mixed1 (example see Fig1)
- Modify the graph to make the degree of each vertex even by duplicating edges and arcs with minimum cost.(call EVENDEGREE)
- Make the indegree of each vertex equal to the outdegree by orienting some edges and duplicated arcs and oriented edges with minimum cost.(call INOUTDEGREE)
- Because the second step may not necessarily maintain even degree of each vertex, adjust the graph to maintain the even degree and the indegree equals to outdegree by not increasing the cost.(call EVENPARITY)
Algorithm MIXED1
Input: Mixed graph G = (V, E, A) with cost function C;
Output: A postman tour
- Call EVENDEGREE
- Call INOUTDEGREE
- Call EVENPARITY
- Find an Eulerian tour over the new graph
- Algorithm EVENDEGREE
- Input: Mixed graph G = (V, E, A) with cost function C;
- Output: A mixed graph G’ = (V, E', A'), E ⊆ E' A ⊆ A' , and the degree of each vertex, ignoring arc direction, is even.
- 1. Identify the vertices of odd degree
- 2. Find all shortest paths between the odd vertices, ignoring arc direction
- 3. Perform a minimum-cost matching of the odd vertices using the shortest path distance
- 4. Duplicate the arcs and edges in the shortest paths used in the matching.
- 5. A'= A ∪ {duplicated arcs};E'=E ∪ {duplicated edges}
- The numer of the odd vertices is even, so we could do the minimum-cost matching among them. And duplicating the arcs and edges in the shortest paths used in the matching doesn't affect the degree of even degree, because the shortest pathes either not pass those vertices, or increase the degree of them by even number.
- Algorithm INOUTGREE
- Input: Mixed graph G(V, E,A) with cost function C;
- Output: M: every arc of G at least once and oriented edges; U ⊆ E:edges that have not been oriented and inserted into M; Every vertex has equal indegree and outdegree.
- 1. E' ← A ∪ E_{1} ∪ E_{2}
- E_{1}: for every edge (u,v) ∈ E, add arcs <u,v> and <v,u> to E_{1}
- E_{2}: same as E_{1}
- 2. b_{v} ← Indegree(v)-Outdegree(v) ∀ v
- 3. Formulating as a folw problem:
- min z = ∑_{s ∈ A} C_{s}X_{s} + ∑_{s ∈ E1} C_{s}X_{s}
- s.t.
- ∑{X_{s}| s ∈ E' and s is directed away from v} - ∑{X_{s}| s ∈ E' and s is directed towardsfrom v} = b_{v} ∀ v
- X_{s} ≤ 1 ∀ s ∈ E_{2}
- X_{s} ≥ 0 ∀ s ∈ E_{'}
- 4. Initialize M equal to A. ( M includes thoes originally directed arcs )
- For each arc s in A, insert X_{s} addicional copies of s into M; ( Duplicate some arcs )
- For each oriented edge s in E_{1}, insert X_{s} copies of s into M; ( Oriente and duplicate some edges )
- For each pair of corresponding oriented edges s_{1} = <v,w> and s_{2} = <w,v> in E_{2}, if X_{s1} = 1 then insert X_{s1} copies of s_{1} to M; if X_{s2} = 1 then insert X_{s2} copies of s_{1} to M ( Oriente some edges )
- 5. Initialize U to be empty. For each pair of corresponding oriented edges s_{1} = <v,w> and s_{2} = <w,v> in E_{2}, if X_{s1} + X_{s1} = 0 , then insert (v,w) to U. ( This indicates (v,w) remain undirected .)
- The arcs of E_{2} are used to represent the fact that the edges of E can be oriented for free by the flow problem. Therefor, E_{2} is not included in the objective function, but the capacity of its edges is limited to 1; The arcs of E_{1} represent the edges of E that are duplicated and oriented by the flow problem, hence the variables of E_{1} appear in the objective function .
- The optimal solution of flow problem are always integral, so optimal solution of this problem is integer too .
- Without loss of generality, we assume for each pair of corresponding oriented edges s_{1} = <v,w> and s_{2} = <w,v> in E_{2}, X_{s1} and X_{s2} are not equal to 1 at same time. Because if a solution uses both arcs corresponding to an edge, then deleting both of these arcs retains feasibility of the solution without increasing the cost.
- Algorithm EVENPARITY
- Input: Mixed graph G = (V, E, A) and multiset M and U;
- Output: Multiset M' and U' satisfying the same criteria as sets M and U from INOUTDEGREE, such that vertices in (V,U',M') are of even degree.
- 1. Identify the set of odd-degree vertices V' w.r.t (V, U, M). M' ← M\ and U' ← U).
:: 2. Let \( M'' ⊆ M be the set of additional arcs and oriented edges created by INOUTDEGREE.
- 3. Call ADJUSTCYCLES (ADJUSTCYCLES identifies cycles consisting of alternating paths in M'' and U, with each path anchored at each end by an odd vertex and without considering the directions of arcs and oriented edges. Then the arcs and oriented edges on the cycles will be either duplicated or deleted, and edges on the path will be oriented. This process change the parity of odd vertices while maintaing indegree equal to outdegree and without increasing the cost)
- While V' is not empty
- Selet v from V' and set v_{s} ← v
- While v is in V'
- Remove v from V'
- Repeat
- Remove <v,w> from M''
- If <v,w> is directed toward w then
- insert a duplicate copy of <v,w> to M'
- else
- delete a copy of <w,v> from M' and set v ← w
- Until v is in V'
- Remove v from V'
- Repeat
- Remove (v,w) from U'; Orient (v,w) from v to w and insert it into M'; Set v ← w
- Until v is in V' or v = v_{s}
- Each odd vertex v has an odd number of elements from M( M''_{v}), because #edges_{v} + #arcs_{v} + #M''_{v} is odd and #edges_{v} + #arcs_{v} is even because this is the result got from EVENDEGREE. Here #edges_{v} represents the number of edges incident on v and arcs_{v} represents the number of arcs incident on v, before INOUTDEGREE. Using the similar reasoning method, we know that every odd vertex has odd number of elements from M and odd number of elements from U; every even vertex has even number of elements from M'' and even number of elements from U
- EVENPARITY will change the parity of odd vertices only because it applies to an even number of the arcs and oriented edges incident on an even vertex, and to an odd number of the arcs and edges incident on an odd vertex
- M' and U' will not cost more than M and U. Suppose the cost of additional copies of edges and arcs in M' is greater than that in M. Then reverse the direction of each edge taken from U, insert two copies of each arc or oriented edge that was deleted, and delete two copies of each edge or arc that was inserted, which is a feasible solution of INOUTDEGREE and has less cost than M and U. This is impossible because M and U were created by a minimum-cost network flow algorithm
The approximation ration of Mixed1 is 2 and it is tight
- C*: optimal solution (minimum cost)
- C_{1}: the solution of Mixed1 on G
- C_{2}: the solution of Mixed1 on G_{2}, which results from duplicating every edge and arc of G
Let G_{2} be the graph results from duplicating every edge and arc of G. Every vertex of G_{2} has even degree, we only need run INOUTDEGREE and EVENPARITY for G_{2}, which gets the total cost C_{2}. C_{2} is optimal solution for G_{2} and doubling the optimal solution is a feasible solution of INOUTDEGREE, so C_{2} ≤ 2C*
Let G_{1} be the graph results from EVENDEGREE of G. Since EVENDEGREE employs a minimum-cost matching, no edge will be duplicated more than once. Thus G_{1} is a subgraph of G_{2} and the cost C_{1} got from applying Mixed1 on G_{1} is no more than C_{2}
Therefore, C_{1} ≤ C_{2} ≤ 2C*
- And the 2-approximation ratio is approachable, see the following example.The cost got from Mixed1 is
4+12ε (see b); and the optimal cost is 2+10ε (see c). When ε is small enough, the
ration is 2.
5. Mixed2: 2 – approximation algorithm ( G.N.Frederickson 1979 )
Mixed2 (example see Fig3)
- Make the indegree of each vertex equal to the outdegree by orienting some edges and duplicated arcs and oriented edges with minimum cost.(call INOUTDEGREE)
- The degree of each vertex is make even , while preserving the property that for each vertex the indegree equals the outdegree.(call LARGECYCLES)
Algorithm MIXED2
Input: Mixed graph G = (V, E, A) with cost function C;
Output: A postman tour
- Call INOUTDEGREE
- Call LARGECYCLES
- Algorithm LARGECYCLES
- Input: Output of INOUTDEGREE
- Output: A tour covering all edges and arcs of G
- 1. Identify the vertices with odd degree in the graph G'=(V,U) (U is the set of undirected edges got from INOUTDEGREE ).
- 2. Find all shortest paths between the odd vertices over the graph G''=(V,E) (V is the set of undirected edges in original graph).
- 3. Perform a minimum-cost matching of the odd vertices using the shortest path distances. Then insert the edges used in the matching into U.
- 4. Find a traversal of M and U.
- The number of odd vertices is always even because 2(#edges + #arcs)=∑_{i is odd vertices} #edges and arcs incident on i + ∑_{j iseven vertices} #edges and arcs incident on j . Since the latter part is a even number, to make the equation hold, the number of odd vertices has to be even, which make the matching always possible.
The approximation ration of Mixed2 is 2 and it is tight
- C*: optimal solution (minimum cost)
- C: the solution of Mixed1 on G
- C_{0}: the cost of all the edges and arcs in original graph
- C': the cost of the graph G' after INOUTDEGREE
- C'': the cost of additional edges added in LARGECYCLES
The graph resulting from assigning the direction to all the edges of optimal solution has the same cost as optimal cost C* and it is a feasible solution of INOUTDEGREE since it has equal indegree and outdegree for every vertex and it includes every edges( may be oriented) and arcs of original graph at least once. C' is the optimal solution of INOUTDEGREE, so C ≤ C*'.
In LARGECYCLES step , we perform the minimum-cost matching, which duplicate every edges at most once. Hence C'' ≤ C_{0}.
Therefore C=C'+C''≤ C*+C ≤ 2C*.
- And the 2-approximation ratio is approachable, see the following example.The cost got from Mixed2 is
2+3ε (see b); and the optimal cost is 4+2ε (see c). When ε is small enough, the
ration is 2.
5. 3/5 approximation algorithm ( G.N.Frederickson 1979 )
If we examine the worst-cases of MIXED1 and MIXED2, we discover the following facts: Algorithm MIXED2 produces an optimum tour for the worst-case of MIEXED1 in Fig2; Algorithm MIXED1 produces an optimum tour for worst-case of MIXED2 in Fig4. This suggests that we could combine two approach to get better performance.
Algorithm GENERALMIXED
Input: Mixed graph G = (V, E, A) with cost function C;
Output: A postman tour
- Call MIXED1
- Call MIXED2
- Select the tour of smaller cost
Now lets examine the approaximation ratio of GENERALMIXED.
- C*: cost of optimal tour
- C_{M}: cost of edges and arcs in set M produced by INOUTDEGREE on the original graph
LEMMA: The cost C of the tour generated by Algorithm MIXED2 is at most 2C*-C_{M}
Proof: When we apply MIXED2, the cost of edges not in M after INOUTDEGREE is at most C*-C_{M}. And since in the worst case each edge in U will be duplicate in LARGECYCLES. So the total cost of undirected edges after MIXED2 is at most 2(C*-C_{M}). And total cost is at most C_{M} + 2(C*-C_{M})=2C*-C_{M}.
LEMMA: The cost C of the tour generated by Algorithm MIXED1 is at most C*+2C_{M}
Proof:Let G_{1} be the graph results from applying EVENDEGREE to G and E' be the set of undirected edges in G_{1}. The total cost C_{E} of E' is no larger than the cost of all arcs and edges in G_{1}, which is no larger than C*.
Let M_{1} be the multiset of arcs and oriented edges such that for every element in M there are exactly two copies in M_{1}. Hence, M_{1} achieves equal indegree and outdegree at every vertex in G_{1}. Therefore, the cost of all arcs and edges in the graph resulting from INOUTDEGREE is bounded by C_{E}+2C_{M}, which is at most c*+2C_{M}.
- If the cost C_{M} is large relative to C*, then MIXED2 is an appropriate approach, otherwise MIXED1 is an appropriate approach.
THEOREM: Algorithm GENERALMIXED produces a tour such that C/C* ≤ 5/3
PROOF:
- if C_{M} > C*/3 then consider the Algorithm MIXED2:
- C/C* ≤ (2C*-C_{M})/C* ≤ (2C*-C*/3)/C* = 5/3
- if C_{M} ≤ C*/3 then consider the Algorithm MIXED1:
- C/C* ≤ (2C_{M}+C*)/C* ≤ (2C*/3 + C*)/C* = 5/3
- We cannot find a tigh example of approximation ratio 5/3. Acturally the tight ratio is 3/2 (see reference 2).
Reference:
[1] Greg N. Frederickson, Approximation Algorithms for Some Postman Problems , J.ACM, 26(1979), pp.538-554
[2] B. Raghavachari and J. Veerasamy, A 3/2-Approximation Algorithm For the Mixed Postman Problem , SIAM J. Discrete Math. Vol. 12, No. 4, pp. 425-433