An improved heuristic for computing short integral cycle bases

ABSTRACT

In this article, we consider the problem of constructing low-weight integral cycle bases in a directed graph G = (V, E) with nonnegative edge weights. It has been shown that low-weight integral cycle bases have applications in the periodic event scheduling problem and cyclic time tabling. However, no polynomial time algorithm is known for computing a minimum weight integral cycle basis in a given directed graph.

We give a necessary condition that has to be satisfied by any minimum weight integral cycle basis and guided by this necessary condition, we propose a new heuristic for constructing a low weight integral cycle basis. To the best of our knowledge, this is the first algorithm to construct integral cycle bases that are not necessarily fundamental. We implemented our heuristic and tested it on random graphs and compared the weight of the integral cycle basis computed by our algorithm with the weight of a minimum cycle basis and the weights of integral cycle bases (these are, in fact, fundamental cycle bases) computed by already existing and new heuristics for this problem. Empirical results suggest that our heuristic performs better than the existing heuristics for this problem and in fact, it computes a minimum weight integral cycle basis on these graphs. (In the above comparison, when the weight of the integral cycle basis computed and the weight of a minimum cycle basis turn out to be equal, it immediately implies that we have in fact found a minimum integral cycle basis.) The time needed for our heuristic is typically a little higher compared to the time taken by the other heuristics that compute fundamental cycle bases.

REFERENCES

• 1: Berger, F. 2002. Minimale kreisbasen in graphen. In Proceedings of the Lecture on the Annual Meeting of the DMV. Halle, Germany.
• 2: Franziska Berger , Peter Gritzmann , Sven de Vries, Minimum Cycle Bases for Network Graphs, Algorithmica, v.40 n.1, p.51-62, June 2004 [doi>10.1007/s00453-004-1098-x]
• 3: Cassell, A. C., Henderson, J. C., and Ramachandran, K. 1976. Cycle bases of minimal measure for the structural analysis of skeletal structures by the flexibility method. In Proceedings of the Royal Society of London Series A 350, 61--70.
• 4: de Pina, J. 1995. Applications of shortest path methods. Ph.D. thesis, University of Amsterdam, Netherlands.
• 5: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• 6: Gleiss, P. M. 2001. Short cycles: Minimum cycle bases of graphs from chemistry and biochemistry. Ph.D. thesis, Universitat Wien.
• 7: Alexander Golynski , Joseph D. Horton, A Polynomial Time Algorithm to Find the Minimum Cycle Basis of a Regular Matroid, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, p.200-209, July 03-05, 2002
• 8: Hariharan, R., Kavitha, T., and Mehlhorn, K. 2006. A faster deterministic algorithm for minimum cycle bases in directed graphs. In Proceedings of the 33rd ICALP, LNCS 4051. 250--261.
• 9: J. D. Horton, A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM Journal on Computing, v.16 n.2, p.358-366, April 1987 [doi>10.1137/0216026]
• 10: Telikepalli Kavitha , Kurt Mehlhorn, Algorithms to Compute Minimum Cycle Basis in Directed Graphs, Theory of Computing Systems, v.40 n.4, p.485-505, June 2007 [doi>10.1007/s00224-006-1319-6]
• 11: Kavitha, T., Mehlhorn, K., Michail, D., and Paluch, K. 2004. A faster algorithm for minimum cycle basis of graphs. In Proceedings of the ICALP, LNCS 3142. 846--857.
• 12: Liebchen, C. 2003. Finding short integral cycle bases for cyclic timetabling. In Proceedings of the ESA, LNCS 2832. 715--726.
• 13: Liebchen, C. and Peeters, L. 2002. On cyclic timetabling and cycles in graphs. Tech. rep., TU Berlin. Technical Report 761/2002.
• 14: Christian Liebchen , Romeo Rizzi, A greedy approach to compute a minimum cycle basis of a directed graph, Information Processing Letters, v.94 n.3, p.107-112, 16 May 2005 [doi>10.1016/j.ipl.2005.01.006]
• 15: Christian Liebchen , Romeo Rizzi, Classes of cycle bases, Discrete Applied Mathematics, v.155 n.3, p.337-355, February, 2007 [doi>10.1016/j.dam.2006.06.007]
• 16: Mehlhorn, K. and Michail, D. Minimum cycle bases: Faster and simpler. ACM Transactions on Algorithms.
• 17: Kurt Mehlhorn , Dimitrios Michail, Implementing minimum cycle basis algorithms, Journal of Experimental Algorithmics (JEA), 11, 2006 [doi>10.1145/1187436.1216582]
• 18: Nachtigall, K. 1994. A branch and cut approach for periodic network programming. Tech. rep., Hildesheimer Informatik-Berichte. Technical Report 29.
• 19: Rizzi, R. 2007. Minimum weakly fundamental cycle bases are hard to find. Algorithmica.
• 20: Swamy, M. and Thulasiraman, K. 1981. Graphs, Networks, and Algorithms. John Wiley & Sons, New York.
• 21: Geetika Tewari , Craig Gotsman , Steven J. Gortler, Meshing genus-1 point clouds using discrete one-forms, Computers and Graphics, v.30 n.6, p.917-926, December, 2006 [doi>10.1016/j.cag.2006.08.019]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Directed graph, combinatorial optimization, integral cycle basis, minimum cycle basis