Terminal backup, 3D matching, and covering cubic graphs

ABSTRACT

We define a problem called Simplex Matching, and show that it is solvable in polynomial time. While Simplex Matching is interesting in its own right as a nontrivial extension of non-bipartite min-cost matching, its main value lies in many(seemingly very different) problems that can be solved using ouralgorithm. For example, suppose that we are given a graph with terminal nodes, non-terminal nodes, and edge costs. Then, the Terminal Backup problem, which consists of finding the cheapest forest connecting every terminal to at least one other terminal, is reducible to Simplex Matching. Simplex Matching is also useful for various tasks that involve forming groups of at least two members, such as project assignment and variants of facility location.

In an instance of Simplex Matching, we are given a hypergraphH with edge costs, and edge size at most 3. We show how to find the min-cost perfect matching of H efficiently, if the edge costs obey a simple and realistic inequality that we call the SimplexCondition. The algorithm we provide is relatively simple to understand and implement, but difficult to prove correct. In the process of this proof we show some powerful new results about covering cubic graphs with simple combinatorial objects.

REFERENCES

• 1: Z. Abrams, A. Meyerson, K. Munagala, S. Plotkin. On the Integrality Gap of Capacitated Facility Location. Techincal Report, CMU-CS-02-199, 2002.
• 2: K. Appel, W. Haken. Every planar map is four-colorable. Contemporary Mathematics, vol. 98, 1989.
• 3: Esther M. Arkin , Refael Hassin , Shlomi Rubinstein , Maxim Sviridenko, Approximations for Maximum Transportation with Permutable Supply Vector and Other Capacitated Star Packing Problems, Algorithmica, v.39 n.2, p.175-187, February 2004 [doi>10.1007/s00453-004-1087-0]
• 4: Markus Bläser , Bodo Manthey, Two Approximation Algorithms for 3-Cycle Covers, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.40-50, September 17-21, 2002
• 5: M. Bläser, L. Ram, M. Sviridenko. Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems. In Proceedings of the 9th WADS, vol. 3608 of Lecture Notes in Computer Science, pp. 350--359, 2005.
• 6: I. Cahit. Spiral Chains: The Proofs of Tait's and Tutte's Three-Edge-Coloring Conjectures. arXiv preprint, math CO/0507127 v.1, July 6, 2005.
• 7: G. Calinescu, A. Zelikovsky. The Polymatroid Steiner Problems. Journal of Combinatorial Optimization, vol. 9, no. 3, pp. 281--294, 2005.
• 8: J. Chen, S. Lu, S. Sze, F. Zhang. Improved algorithms for path, matching, and packing problems. In Proceedings of the 18th ACM-SIAM SODA, pp. 298--307, 2007.
• 9: G. Cornuéjols. Combinatorial Optimization: Packing and Covering. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74, SIAM 2001.
• 10: Gérard Cornuéjols , David Hartvigsen, An extension of matching theory, Journal of Combinatorial Theory Series B, v.40 n.3, p.285-296, June 1986 [doi>10.1016/0095-8956(86)90085-7]
• 11: G. Cornuéjols, D. Hartvigsen, W. Pulleyblank. Packing subgraphs in a graph. Operations Research Letters, vol. 1, 139--143, 1982.
• 12: W. Cunningham. Matching, matroids, and extensions. Mathematical Programming, Series B, vol. 91, pp. 515--542, 2002.
• 13: U. Derigs. A shortest augmenting path method for solving minimal perfect matching problems. Networks, vol. 11, pp. 379--390, 1981.
• 14: Guy Even , Guy Kortsarz , Wolfgang Slany, On network design problems: fixed cost flows and the covering steiner problem, ACM Transactions on Algorithms (TALG), v.1 n.1, p.74-101, July 2005 [doi>10.1145/1077464.1077470]
• 15: Michel X. Goemans , David P. Williamson, A General Approximation Technique for Constrained Forest Problems, SIAM Journal on Computing, v.24 n.2, p.296-317, April 1995 [doi>10.1137/S0097539793242618]
• 16: S. Guha , A. Meyerson , K. Munagala, Hierarchical placement and network design problems, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.603, November 12-14, 2000
• 17: A. Gupta, A. Srinivasan. On the Covering Steiner Problem. Theory of Computing, vol. 2, pp. 53--64, 2006.
• 18: D. Hartvigsen, P. Hell, J. Szabó. The k-piece packing problem. Journal of Graph Theory, vol. 52, pp. 267--293, 2006.
• 19: P. Hell. Graph Packings. Electronic Notes in Discrete Mathematics, vol. 5, pp. 170--173, 2000.
• 20: P. Hell, D. Kirkpatrick. Packings by cliques and by finite families of graphs. Discrete Mathematics, vol. 49, pp. 45--49, 1984.
• 21: Ury Jamshy , Michael Tarsi, Short cycle covers and the cycle double cover conjecture, Journal of Combinatorial Theory Series B, v.56 n.2, p.197-204, Nov. 1992 [doi>10.1016/0095-8956(92)90018-S]
• 22: Haim Kaplan , Moshe Lewenstein , Nira Shafrir , Maxim Sviridenko, Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs, Journal of the ACM (JACM), v.52 n.4, p.602-626, July 2005 [doi>10.1145/1082036.1082041]
• 23: D. R. Karget , M. Minkoff, Building Steiner trees with incomplete global knowledge, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.613, November 12-14, 2000
• 24: Alexander K. Kelmans, Optimal packing of induced stars in a graph, Discrete Mathematics, v.173 n.1-3, p.97-127, Aug. 20, 1997 [doi>10.1016/S0012-365X(96)00121-5]
• 25: Martin Loebl , Svatopluk Poljak, Efficient subgraph packing, Journal of Combinatorial Theory Series B, v.59 n.1, p.106-121, Sept. 1993 [doi>10.1006/jctb.1993.1058]
• 26: L. Lovasz, M. Plummer. Matching Theory. Elsevier Science Ltd, 1986.
• 27: G. Pap. Hypo-matchings in directed graphs. Graph Theory 2004, Birkhäuser Verlag, Basel, Switzerland, pp. 325--335, 2006.
• 28: G. Pap. A TDI description of restricted 2-matching polytopes. In Proceedings of the 10th IPCO, pp. 139--151, 2004.
• 29: P. D. Seymour, Graph minors. IX. Disjoint crossed paths, Journal of Combinatorial Theory Series B, v.49 n.1, p.40-77, Jun. 1990 [doi>10.1016/0095-8956(90)90063-6]
• 30: Neil Robertson , Daniel Sanders , Paul Seymour , Robin Thomas, The four-colour theorem, Journal of Combinatorial Theory Series B, v.70 n.1, p.2-44, May 1997 [doi>10.1006/jctb.1997.1750]
• 31: P.D. Seymour. Sums of circuits. Graph Theory and Related Topics. J.A. Bondy and U.R.S. Murty Eds, Academic Press, pp. 341--355, 1978.
• 32: P.G. Tait. Note on a theorem in geometry of position. Transactions of the Royal Society of Edinburgh, vol. 29, pp. 657--660, 1880.
• 33: D. Xu, E. Anshelevich, M. Chiang. Simplex Cover: Modeling, Algorithms, and Networking Applications. manuscript, http://www.princeton.edu/~dahaixu/pub/simplex/simplex.pdf.
• 34: C.Q. Zhang. Integer flows and cycle covers of graphs. Marcel Dekker, 1997.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Design, Theory

Keywords:
polynomial time, simplex matching, terminal backup