The seminar is part of the Thematic Semester "Graphs and Beyond" (Part III), jointly organized by the International Centre for Research and Postgraduate Training in Mathematics (ICRTM) and CIMPA.

Time: 10:00 a.m., Friday, June 26, 2026

Venue: Room 507, A6 Building, 18 Hoang Quoc Viet

Abstract: Because edge modification problems are computationally difficult for most target graph classes, considerable attention has been devoted to inclusion-minimal edge modifications, which are usually polynomial-time computable and which can serve as an approximation of  minimum cardinality edge modifications, al-beit with no guarantee on the cardinality of the resulting modification set. Over the past fifteen years, the primary design approach used for inclusion-minimal edge modification algorithms is based on a specific incremental scheme. Unfortunately, nothing guarantees that the set E of edge modifications of a graph G that can be obtained in this specific way spans all the inclusion-minimal edge modifications of G. Here, we focus on edge modification problems into the class of chordal graphs and we show that for this the set E may not even contain anysolution of minimum size and may not even contain a solution close to the minimum; in fact, we show that it may not contain a solution better than within an Ω(n) factor of the minimum. These results show strong limitations on the current favored algorithmic approach to inclusion-minimal edge modification and suggest that further developments might be better using other approaches.