Computing Twin-Width Parameterized by the Feedback Edge Number and Vertex Integrity

Abstract

The problem of whether and how one can compute the twin-width of a graph—along with an accompanying contraction sequence—lies at the forefront of the area of algorithmic model theory. While significant effort has been aimed at obtaining a fixed-parameter approximation for the problem when parameterized by twin-width, here we approach the question from a different perspective and consider whether one can obtain (near-)optimal contraction sequences under larger runtime parameters. As our main contributions, we obtain fixed-parameter approximation algorithms for twin-width when the runtime parameter is either the vertex integrity or the feedback edge number of the input graph. For the latter parameter, we also obtain a linear kernel for the problem of either computing a 2-contraction sequence or determining that none exists. For both parameters, we also obtain asymptotically tight upper bounds on twin-width.