Informace o publikaci

Computing Twin-Width Parameterized by the Feedback Edge Number



Rok publikování 2024
Druh Článek ve sborníku
Konference 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)
Klíčová slova twin-width, parameterized complexity, kernelization, feedback edge number
Popis 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 a larger parameterization, notably the feedback edge number k. As our main contributions, under this parameterization we obtain (1) a linear bikernel for the problem of either computing a 2-contraction sequence or determining that none exists and (2) an approximate fixed-parameter algorithm which computes an ??-contraction sequence (for an arbitrary specified ??) or determines that the twin-width of the input graph is at least ??. These algorithmic results rely on newly obtained insights into the structure of optimal contraction sequences, and as a byproduct of these we also slightly tighten the bound on the twin-width of graphs with small feedback edge number.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info