Heuristic vs. ILP: Destroying forbidden subgraphs. An application to GaTEx Graphs

Sammanfattning

This thesis explores methods for breaking forbidden induced subgraphs in graphs, focusing on developing a general framework applicable to any user-defined set of forbidden subgraphs. If such forbiddensubgraphs are present in a graph then this prevents it from belonging to a particular class of graphs.Eliminating these subgraphs transforms the graph into one that meets the desired structural criteria.Two main approaches have been formulated and evaluated: an Integer Linear Programming (ILP) solution and a heuristic method. The ILP method provides a benchmark for accuracy by offering anoptimal solution for eliminating forbidden subgraphs. In contrast, the heuristic method offers a poten-tially faster, approximate solution by iteratively removing edges based on their involvement in forbidden subgraphs. To demonstrate the applicability of these methods, we focus on Galled Tree Explainable(GaTEx) graphs, a class of graphs that can be fully explained by so-called labeled galled-trees. GaTEx graphs have been recently characterized by the absence of a specific set of 25 forbidden induced subgraphs. A systematic procedure was developed to generate random GaTEx graphs and introduce noise through additional edges, allowing for a thorough evaluation of the heuristic’s effectiveness. This study presents a comparative analysis of the ILP and heuristic approaches, identifying conditions underwhich each method is preferable. The results indicate that while the ILP method ensures optimality, itis computationally intensive, making the heuristic method more practical for larger graphs, albeit withsome loss in accuracy.