Making a graph unit interval by a minimum number of vertex deletions is NP-hard. The problem is motivated by applications in seriation and measuring indifference between data items. We present a fixed-parameter algorithm based on the iterative compression technique that finds in O((14k+14)^(k+1)kn^6) time a set of k vertices whose deletion from an n-vertex graph makes it unit interval. Additionally, we show that making a graph chordal by at most k vertex deletions is NP-complete even on claw,net,tent-free graphs.
[ bib | DOI | slides | .pdf ] Back
This file was generated by bibtex2html 1.98.