Solving perfect graph modification problems and generating perfect graphs

Graph modification problems have been extensively explored for various graph classes, with the literature offering numerous NP-completeness proofs and polynomial time algorithms. However, exact algorithms for tackling NP-hard cases remain relatively scarce. In this study, we introduce exact solution methods based on integer programming for the minimum perfect editing, the minimum perfect completion, the minimum perfect deletion, and the perfect sandwich problems. The editing problem seeks the minimum number of edge additions and deletions required to transform a graph into a perfect graph, while the completion problem restricts modifications to only edge additions and the deletion problem restricts to only edge deletions. The perfect sandwich problem, formulated as a decision problem, asks whether a perfect graph can be obtained by adding edges from a specified subset of non-edges. Our approach leverages the Strong Perfect Graph Theorem, encoding odd holes and odd antiholes as linear constraints within an integer programming model. Due to the exponential number of constraints, we develop methods to handle larger graphs. We propose a cutting plane algorithm that dynamically identifies and adds violated constraints based on detected odd holes and odd antiholes. To improve the efficiency of the cutting plane algorithm, we analyze the expected number of odd holes and odd antiholes in random graphs. Additionally, we introduce a heuristic algorithm that transforms a graph into a perfect one, which provides better upper bounds for the editing and completion problems. We validate the effectiveness of our methods through computational experiments. Finally, we consider the proposed heuristic from graph generation perspective, and examine the structure of generated perfect graphs.