@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
HR76.
},
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.)
},
}