@TechReport{HR73,
  author = 	 { L[aurent] Hyafil and R[onald] L. Rivest },
  title = 	 { Graph Partitioning and Constructing Optimal Decision Trees are Polynomial Complete Problems },
  institution =  { IRIA -- Laboratoire de Recherche en Informatique et Automatique },
  date =         { 1973-10 },                  
  OPTyear = 	 { 1973 },
  OPTmonth = 	 { October },
  number = 	 { Rapport de Recherche no. 33 },
  OPTaddress = 	 { Domaine de Voluceau, Rocquencourt 78150 - Le Chesnay, France },
  keywords =     { complexity, polynomial complete, graph partitioning, decision trees },                  
  htmlnote =     { The decision tree result from this paper was published in 
                   <a href="#HR76">HR76</a>.
                 },                  
  abstract =     {
        The problem of partitioning the nodes of a graph into subsets of bounded size
        so as to minimize the number of edges connecting nodes from distinct subsets is
        shown to be polynomial complete.  The problem of constructing a decision tree
        which minimizes the expected number of tests required to identify an object is also
        shown to be polynomial complete.  (Every polynomial complete problem (for example,
        traveling salesman, graph coloring) can be solved in polynomial time if one of them
        can.)                  
                 },
}