edge modification problems

Assaf Natanzon

I will show that the perfect graph completion/deletion/editing problems are NP-hard, and that comparability graph edit/deletion/complition problems are np-complete. I will also show an approximation algorithm for the minimum vertex deletion problem and minimud edit/deletion problems for some families of graphs, and I will show an o(opt) approximation algorithm for the clustering problem (the problem that Erez thesis is about). if time will allow it I will show some combinatorical bounds on the size of the complition/deletion of perfect and chordal graphs , I will show that such a complition can be much larger then the number of edges in the original graph.