On the completeness of a generalized matching problem

ABSTRACT

A perfect matching in a graph H may be viewed as a collection of subgraphs of H, each of which is isomorphic to K2, whose vertex sets partition the vertex set of H. This is naturally generalized by replacing K2 by an arbitrary graph G. We show that if G contains a component with at least three vertices then this generalized matching problem is NP-complete. These generalized matchings have numerous applications including the minimization of second-order conflicts in examination scheduling.

REFERENCES

• 1: F. T. Boesch , J. F. Gimpel, Covering Points of a Digraph with Point-Disjoint Paths and Its Application to Code Optimization, Journal of the ACM (JACM), v.24 n.2, p.192-198, April 1977 [doi>10.1145/322003.322005]
• 2: Cockayne, E., Goodman, S., and Hedetniemi, S.,"A Linear Algorithm for the Domination Number of a Tree," Information Processing Letters 4,2(1975), 41-44.
• 3: Cole, A.J.,"The Preparation of Examination Time-Tables Using a Small Store Computer," The Computer J., 7 (1964), 117-121.
• 4: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 5: Edmonds, J.,"Paths, Trees, and Flowers," Canad. J. Math., 17(1965), 449-467).
• 6: Edmonds, J., and Johnson, E.L.,"Matching: a Well-Solved Class of Integer Programs," Proc. Calgary Inter. Conf. Combin. Structures and Their Applications, Gordon and Breach, N.Y., (1970), 89-92.
• 7: 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]
• 8: M. R. Garey , D. S. Johnson , L. Stockmeyer, Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803884]
• 9: Garinshteyn, L.L.,"The Partitioning of Graphs," Engineering Cybernetics, No. 1(1969), 76-82.
• 10: Harary, F., Graph Theory, Addison-Wesley Publishing Co., Reading, Mass., 1969.
• 11: Herbert, L.J.,"Some Applications of Graph Theory to Clustering," Psychometrika 39,3(1974), 283-309.
• 12: Hope, A.K.,"Component Placing Through Graph Partitioning in Computer-Aided Printed-Wiring-Board Design," Electronics Letters 8,4(1972), 87-88.
• 13: Johnson, D.S.,"Worst Case Behavior of Graph Coloring Algorithms," in F. Hoffman et al (eds.) Proc. Fifth Southeastern Conf. on Comb., Graph Th., and Comp., Utilitas Math., Winnipeg, 1974.
• 14: Johnson, D.S., private communication, August, 1977.
• 15: Karp, R.M.,"Reducability Among Combinational Problems," Complexity of Computer Computations, Miller, R.E., and Thatcher, J.W., (eds.), Plenum Press, N.Y. (1972), 85-103.
• 16: Karp, R.M.,"On the Complexity of Combinatorial Problems," Networks, 5(1975), 45-68.
• 17: Kernighan, B.W., and Lin, S.,"An Efficient Heuristic Procedure for Partitioning Graphs," The Bell System Technical Journal,Vol. 49 (1970), 291-307.
• 18: Matula, D.W., Marble, G., and Isaacson, J.D.,"Graph Coloring Algorithms," in R.C. Read (ed.) Graph Theory and Computing, Acad. Press, N.Y., 1972.
• 19: J. E. L. Peck , M. R. Williams, Algorithm 286: Examination scheduling, Communications of the ACM, v.9 n.6, p.433-434, June 1966 [doi>10.1145/365696.365713]
• 20: Welsh, D.J.A. & Powell, M.B.,"An Upper Bound for Chromatic Number of a Graph and its Applications to Time Tabling Problem," The Computer J. 10 (1967), 85-6.
• 21: Wood, D.C.,"A System for Computing University Examination Timetables," The Comp. J., 11 (1968), 41.
• 22: Wood, D.C.,"A Technique for Coloring a Graph Applicable to Large Scale Timetabling Problems," The Comp. J., 12(1969), 317-319.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

General Terms:
Theory