Data reduction and exact algorithms for clique cover

ABSTRACT

To cover the edges of a graph with a minimum number of cliques is an NP-hard problem with many applications. For this problem we develop efficient and effective polynomial-time data reduction rules that, combined with a search tree algorithm, allow for exact problem solutions in competitive time. This is confirmed by experiments with real-world and synthetic data. Moreover, we prove the fixed-parameter tractability of covering edges by cliques.

REFERENCES

• 1: Agarwal, P. K., Alon, N., Aronov, B., and Suri, S. 1994. Can visibility graphs be represented compactly? Discrete Comput. Geo. 12, 347--365.
• 2: Alber, J., Fellows, M. R., and Niedermeier, R. 2004. Polynomial-time data reduction for Dominating Set. J. ACM 51, 363--384.
• 3: Alber, J., Betzler, N., and Niedermeier, R. 2006. Experiments on data reduction for optimal domination in networks. Ann. Operations Res. 146, 1, 105--117.
• 4: Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., and Protasi, M. 1999. Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, New York.
• 5: Behrisch, M. and Taraz, A. 2006. Efficiently covering complex networks with cliques of similar vertices. Theoret. Comput. Sci. 355, 1, 37--47.
• 6: Bron, C. and Kerbosch, J. 1973. Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16, 9, 575--577.
• 7: Cai, L., Chen, J., Downey, R. G., and Fellows, M. R. 1997. Advice classes of parameterized tractability. Ann. Pure Appl. Logic 84, 119--138.
• 8: Chang, M.-S. and Müller, H. 2001. On the tree-degree of graphs. In Proceedings of the 27th WG. LNCS, vol. 2204. Springer, New York. 44--54.
• 9: Downey, R. G. and Fellows, M. R. 1999. Parameterized Complexity. Springer, New York.
• 10: Erdős, P., Goodman, A. W., and Pósa, L. 1966. The representation of a graph by set intersections. Canad. J. Math. 18, 106--112.
• 11: Flum, J. and Grohe, M. 2006. Parameterized Complexity Theory. Springer-Verlag, New York.
• 12: Frieze, A. M. and Reed, B. A. 1995. Covering the edges of a random graph by cliques. Combinatorica 15, 4, 489--497.
• 13: Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA.
• 14: Gramm, J., Guo, J., Hüffner, F., Niedermeier, R., Piepho, H.-P., and Schmid, R. 2007. Algorithms for compact letter displays: Comparison and evaluation. Comput. Stat. Data Analysis. 52, 2, 725--736.
• 15: Guillaume, J.-L. and Latapy, M. 2004. Bipartite structure of all complex networks. Inform. Processing Lett. 90, 5, 215--221.
• 16: Guo, J. and Niedermeier, R. 2007. Invitation to data reduction and problem kernelization. ACM SIGACT News 38, 1, 31--45.
• 17: Gyárfás, A. 1990. A simple lower bound on edge coverings by cliques. Discrete Math. 85, 1, 103--104.
• 18: Hoover, D. N. 1992. Complexity of graph covering problems for graphs of low degree. J. Combinatorial Math. Combinatorial Comput. 11, 187--208.
• 19: Hsu, W.-L. and Tsai, K.-H. 1991. Linear time algorithms on circular-arc graphs. Inform. Processing Lett. 40, 3, 123--129.
• 20: Kellerman, E. 1973. Determination of keyword conflict. IBM Tech. Disclosure Bull. 16, 2, 544--546.
• 21: Koch, I. 2001. Enumerating all connected maximal common subgraphs in two graphs. Theoret. Comput. Sci. 250, 1-2, 1--30.
• 22: Kou, L. T., Stockmeyer, L. J., and Wong, C.-K. 1978. Covering edges by cliques with regard to keyword conflicts and intersection graphs. Commun. ACM 21, 2, 135--139.
• 23: Leroy, X., Vouillon, J., Doligez, D., et al. 1996. The Objective Caml System. Available on the web. http://caml.inria.fr/ocaml/.
• 24: Lund, C. and Yannakakis, M. 1994. On the hardness of approximating minimization problems. J. ACM 41, 960--981.
• 25: Ma, S., Wallis, W. D., and Wu, J. 1989. Clique covering of chordal graphs. Utilitas Math. 36, 151--152.
• 26: McKee, T. A. and McMorris, F. R. 1999. Topics in Intersection Graph Theory. SIAM Monographs on Discrete Mathematics and Applications. SIAM.
• 27: Niedermeier, R. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford.
• 28: Okasaki, C. and Gill, A. 1998. Fast mergeable integer maps. In Proceedings of the ACM SIGPLAN Workshop on ML. 77--86.
• 29: Orlin, J. B. 1977. Contentment in graph theory: Covering graphs with cliques. Indagationes Math. (Proc.) 80, 5, 406--424.
• 30: Piepho, H.-P. 2004. An algorithm for a letter-based representation of all-pairwise comparisons. J. Comput. Graphical Stat. 13, 2, 456--466.
• 31: Prisner, E. 1995. Graphs with few cliques. In Proceedings of the 7th Conference on the Theory and Applications of Graphs. Wiley, New York. 945--956.
• 32: Rajagopalan, S., Vachharajani, M., and Malik, S. 2000. Handling irregular ILP within conventional VLIW schedulers using artificial resource constraints. In Proceedings of the CASES. ACM Press, New York. 157--164.

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Clique cover, data reduction, fixed-parameter tractability