Computing Twin-Width Parameterized by the Feedback Edge Number

被引:0
|
作者
Balaban, Jakub [1 ]
Ganian, Robert [2 ]
Rocton, Mathis [2 ]
机构
[1] Masaryk Univ, Fac Informat, Brno, Czech Republic
[2] TU Wien, Algorithms & Complex Grp, Vienna, Austria
来源
41ST INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE, STACS 2024 | 2024年 / 289卷
基金
欧盟地平线“2020”;
关键词
twin-width; parameterized complexity; kernelization; feedback edge number; TREEWIDTH;
D O I
10.4230/LIPIcs.STACS.2024.7
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 l-contraction sequence (for an arbitrary specified l) or determines that the twin-width of the input graph is at least l. 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.
引用
收藏
页数:19
相关论文
empty
未找到相关数据