Hybrid Approach to Twin-width by Taming Red (HATTER): A heuristic solver for finding twin-width of an undirected graph

Twin-width was introduced by Bonnet et al. in 2020. The graph parameter twin-width intuitively measures the distance of a graph to a co-graph. In this paper, we propose “Hybrid Approach to twin-width by Taming Red (HATTER)”, a novel heuristic solver for computing the twin width of an undirected graph. The solver can be accessed through this link. We use preprocessing and divide-and-conquer techniques in HATTER. In the preprocessing phase, we first apply a reduction technique on the degree one vertices of the input graph based on some property. Later, we decompose the preprocessed graph into several components and compute the contraction sequence for each of these components independently. Finally, we identify vertices until the graph is reduced to a single vertex.