Safe Edges: A Study of Triangulation in Fill-in and Tree-Width Problems

This paper considers two well-studied problems $\text{textsc}MinimumFill-In$ ($\text{textsc}MinFill-In$) and $\text{textsc}Treewidth$. Since both problems are $\mathsf{\text{NP}}$-hard, various reduction rules simplifying an input graph have been intensively studied to better understand the structural properties relevant to these problems. Bodlaender at el. introduced the concept of a safe edge that is included in a solution of the $\text{textsc}MinimumFill-In$ problem and showed some initial results. In this paper, we extend their result and prove a new condition for an edge set to be safe. This in turn helps us to construct a novel reduction tool for $\text{textsc}MinFill-In$ that we use to answer other questions related to the problem. In this paper, we also study another interesting research question: Whether there exists a triangulation that answers both problems $\text{textsc}MinFill-In$ and $\text{textsc}Treewidth$. To formalise our study, we introduce a new parameter reflecting a distance of triangulations optimising both problems. We present some initial results regarding this parameter and study graph classes where both problems can be solved with one triangulation.