On the Incremental Approach to Minimal Chordal Edge Modification

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.