@article{oai:nagoya.repo.nii.ac.jp:00013171,
 author = {OTSUKI, Hideaki and HIRATA, Tomio},
 issue = {5},
 journal = {IEICE transactions on fundamentals of electronics, communications and computer sciences},
 month = {May},
 note = {For a property π on graphs, the edge-contraction problem with respect to π is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property π. This paper gives a lower bound for the approximation ratio for the problem for any property π that is hereditary on contractions and determined by biconnected components.},
 pages = {1425--1427},
 title = {Inapproximability of the Edge-Contraction Problem},
 volume = {E89-A},
 year = {2006}
}