Fast FPT-approximation of branchwidth

DOI10.1145/3519935.3519996MaRDI QIDQ6083542zbMATH OpenOpenAlexFDO

Authors Fedor V. Fomin, Tuukka Korhonen

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.03492

zbMATH Keywords

branchwidthcliquewidthparameterized complexityrankwidth

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework. $$ An algorithm that for a given $n$-vertex graph $G$ and integer $k$ in time $2^{2^{O(k)}}{n}^2$ either constructs a rank decomposition of $G$ of width at most $2k$ or concludes that the rankwidth of $G$ is more than $k$. It also yields a $(2^{2k+1}-1)$-approximation algorithm for cliquewidth within the same time complexity, which in turn, improves to $f(k)n^2$ the running times of various algorithms on graphs of cliquewidth $k$. Breaking the "cubic barrier" for rankwidth and cliquewidth was an open problem in the area. $$ An algorithm that for a given $n$-vertex graph $G$ and integer $k$ in time $2^{O(k)}n$ either constructs a branch decomposition of $G$ of width at most $2k$ or concludes that the branchwidth of $G$ is more than $k$. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].

Recommendations

• Graph-Theoretic Concepts in Computer Science
• Computing branchwidth via efficient triangulations and blocks
• scientific article; zbMATH DE number 1990711
• Constructive linear time algorithms for branchwidth
• A SAT approach to branchwidth
• A SAT approach to branchwidth
• Pseudo-kernelization: A branch-then-Reduce approach for FPT problems
• Half-integrality, LP-branching and FPT algorithms
• Half-integrality, LP-branching, and FPT algorithms
• Algorithms – ESA 2005

Cited in

(7)

• Approximating clique-width and branch-width
• Treewidth versus clique number. II: Tree-independence number
• On budget-constrained coverage in multi-interface networks: branchwidth and treewidth perspectives
• Computing twin-width parameterized by the feedback edge number
• Computing twin-width parameterized by the feedback edge number and vertex integrity
• Parameterized complexity of weighted target set selection
• Comparing width parameters on graph classes

This page was built for publication: Fast FPT-approximation of branchwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083542)