Covering edges by cliques with regard to keyword conflicts and intersection graphs

ABSTRACT

Kellerman has presented a method for determining keyword conflicts and described a heuristic algorithm which solves a certain combinatorial optimization problem in connection with this method. This optimization problem is here shown to be equivalent to the problem of covering the edges of a graph by complete subgraphs with the objective of minimizing the number of complete subgraphs. A relationship between this edge-clique-cover problem and the graph coloring problem is established which allows algorithms for either one of these problems to be constructed from algorithms for the other. As consequences of this relationship, the keyword conflict problem and the edge-clique-cover problem are shown to be NP-complete, and if P ≠ NP then they do not admit polynomial-time approximation algorithms which always produce solutions within a factor less than 2 from the optimum.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: M. R. Garey , D. S. Johnson, The Complexity of Near-Optimal Graph Coloring, Journal of the ACM (JACM), v.23 n.1, p.43-49, Jan. 1976 [doi>10.1145/321921.321926]
• 3: Harary, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 4: Harary, F. On the Intersection Number of a Graph. In Proof Techniques in Graph Theory, F. Harary, Ed., Academic Press, New York, 1969, pp. 71-72.
• 5: Johnson, D.S. Worst case behavior of graph coloring algorithms. Proc. Fifth Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathcmatica Pub., Winnipeg, Canada, 1974, pp. 513-528.
• 6: Johnson, D.S. Approximation algorithms for combinatorial problems. J. Comptr. Syst. Sci. 9(1974), 256-278.
• 7: Karp, R.M. On the computational complexity of combinatorial problems. Networks 5 (1975), 45-68.
• 8: Kellerman, E. Determination of keyword conflict. IBM Tech. Disclosure Bull. 16, 2 (July 1973), 544-546.
• 9: Welsh, D.J.A., and Powell, M.B. An upper bound to the chromatic number of a graph and its application to time tabling problems. Comptr. J. 10 (1967), 85-86.
• 10: Wood, D.C. A technique for coloring a graph applicable to large scale time-tabling problems. Comptr. J. 12 (1969), 317-319.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
NP-complete problems, computational complexity, edge clique cover, intersection graphs, keyword conflicts, node clique cover, polynomial-time heuristics