Efficient algorithms for the 2-gathering problem

ABSTRACT

Pebbles are placed on some vertices of a directed graph. Is it possible to move each pebble along at most one edge of the graph so that in the final configuration no pebble is left on its own? We give an O(mn)-time algorithm for solving this problem, which we call the 2-gathering problem, where n is the number of vertices and m is the number of edges of the graph. If such a 2-gathering is not possible, the algorithm finds a solution that minimizes the number of solitary pebbles. The 2-gathering problem forms a non-trivial generalization of the non-bipartite matching problem and it is solved by extending the augmenting paths technique used to solve matching problems.

REFERENCES

• 1: Elliot Anshelevich , Adriana Karagiozova, Terminal backup, 3D matching, and covering cubic graphs, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250849]
• 2: A. Armon. On min-max r-gatherings. In Proc. of the 5th WAOA, pages 128--141, 2007.
• 3: Gérard Cornuéjols, General factors of graphs, Journal of Combinatorial Theory Series B, v.45 n.2, p.185-198, Oct. 1988 [doi>10.1016/0095-8956(88)90068-8]
• 4: G. Cornuéjols, D. Hartvigsen, and W. Pulleyblank. Packing subraphs in a graph. Operations Research Letters, 1(1):139--143, 1982.
• 5: J. Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449--467, 1965.
• 6: Tomás Feder , Rajeev Motwani, Clique partitions, graph compression and speeding-up algorithms, Journal of Computer and System Sciences, v.51 n.2, p.261-272, Oct. 1995 [doi>10.1006/jcss.1995.1065]
• 7: Harold N. Gabow, An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.448-456, December 1983 [doi>10.1145/800061.808776]
• 8: H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences, 30(2):209--221, 1985.
• 9: Harold N. Gabow , Robert E. Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM (JACM), v.38 n.4, p.815-853, Oct. 1991 [doi>10.1145/115234.115366]
• 10: P. Hell and D. G. Kirkpatrick. Packings by cliques and by finite families of graphs. Discrete Mathematics, 49(1):45--59, 1984.
• 11: Adriana Karagiozova, Aspects of network design, Princeton University, Princeton, NJ, 2007
• 12: L. Lovász. Subgraphs with prescribed valencies. Journal of Combinatorial Theory, 8:391--416, 1970.
• 13: L. Lovász. The factorization of graphs. II. Acta Math. Acad. Sci. Hungar., 23:223--246, 1972.
• 14: Silvio Micali , Vijay V. Vazirani, An O(v|v| c |E|) algoithm for finding maximum matching in general graphs, Proceedings of the 21st Annual Symposium on Foundations of Computer Science, p.17-27, October 13-15, 1980
• 15: András Sebő, General antifactors of graphs, Journal of Combinatorial Theory Series B, v.58 n.2, p.174-184, July 1993 [doi>10.1006/jctb.1993.1035]
• 16: V. V. Vazirani. A theory of alternating paths and blossoms for proving correctness of the O(√V E) general graph maximum matching algorithm. Combinatorica, 14(1):71--109, 1994.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms