Twin-Width Meets Feedback Edges and Vertex Integrity
<|reference_start|>Twin-Width Meets Feedback Edges and Vertex Integrity: The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number.   Here, we make several new steps in this research direction and obtain:   - An asymptotically tight bound between twin-width and the feedback edge number;   - A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency;   - An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph.<|reference_end|>
@article{balabán2024twin-width,
    title={Twin-Width Meets Feedback Edges and Vertex Integrity},
    author={Jakub Balab'an, Robert Ganian and Mathis Rocton},
    journal={arXiv preprint arXiv:2407.15514},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.15514},
    primaryClass={cs.DS}
}