Improved algorithms for weakly chordal graphs

ABSTRACT

We use a new structural theorem on the presence of two-pairs in weakly chordal graphs to develop improved algorithms. For the recognition problem, we reduce the time complexity from O(mn²) to O(m²) and the space complexity from O(n³) to O(m + n), and also produce a hole or antihole if the input graph is not weakly chordal. For the optimization problems, the complexity of the clique and coloring problems is reduced from O(mn²) to O(n³) and the complexity of the independent set and clique cover problems is improved from O(n⁴) to O(mn). The space complexity of our optimization algorithms is O(m + n).

REFERENCES

• 1: Srinivasa R. Arikati , C. Pandu Rangan, An efficient algorithm for finding a two-pair, and its applications, Discrete Applied Mathematics, v.31 n.1, p.71-74, March 11, 1991 [doi>10.1016/0166-218X(91)90033-S ]
• 2: Anne Berry , Jean-Paul Bordat , Pinar Heggernes, Recognizing weakly triangulated graphs by edge separability, Nordic Journal of Computing, v.7 n.3, p.164-177, Fall 2000
• 3: Hayward, R. B. 1985. Weakly triangulated graphs. J. Combinatorial Theory Series B 39, 200--209.
• 4: Ryan B. Hayward, Meyniel weakly triangulated graphs—I: co-perfect orderability, Discrete Applied Mathematics, v.73 n.3, p.199-210, March 21, 1997 [doi>10.1016/S0166-218X(96)00008-X ]
• 5: Ryan B. Hayward, Meyniel weakly triangulated graphs II: a theorem of Dirac, Discrete Applied Mathematics, v.78 n.1-3, p.283-289, Oct. 21, 1997 [doi>10.1016/S0166-218X(97)00058-9 ]
• 6: Hayward, R. B., Hoàng, C. T., and Maffray, F. 1989. Optimizing weakly triangulated graphs. Graphs Combinatorics 5, 339--349; erratum in 6 1990, 33--35.
• 7: Ryan B. Hayward , Jeremy Spinrad , R. Sritharan, Weakly chordal graph algorithms via handles, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.42-49, January 09-11, 2000, San Francisco, California, United States
• 8: Dieter Kratsch , Jeremy Spinrad, Between O(nm) and O(n^α), Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 9: Stavros D. Nikolopoulos , Leonidas Palios, Hole and antihole detection in graphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 10: Vijay Raghavan , Jeremy Spinrad, Robust algorithms for restricted domains, Journal of Algorithms, v.48 n.1, p.160-172, August 2003 [doi>10.1016/S0196-6774(03)00048-8]
• 11: Rose, D. J., Tarjan, R. E., and Leuker, G. S. 1976. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comp. 5, 266--283.
• 12: Jeremy Spinrad , R. Sritharan, Algorithms for weakly triangulated graphs, Discrete Applied Mathematics, v.59 n.2, p.181-191, May 12, 1995 [doi>10.1016/0166-218X(93)E0161-Q ]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
Perfect graphs, coloring, graph algorithms, recognition, weakly chordal