Fast FPT-approximation of branchwidth

DOI10.1145/3519935.3519996arXiv2111.03492OpenAlexW3212717626MaRDI QIDQ6083542

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)

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].

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

zbMATH Keywords

parameterized complexitybranchwidthcliquewidthrankwidth

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Treewidth versus clique number. II: Tree-independence number ⋮ Approximating clique-width and branch-width

Recommendations

• Title not available (Why is that?) 👍 👎
• Computing branchwidth via efficient triangulations and blocks 👍 👎
• Pseudo-kernelization: A branch-then-Reduce approach for FPT problems 👍 👎
• Half-integrality, LP-branching, and FPT algorithms 👍 👎
• A SAT Approach to Branchwidth 👍 👎
• Constructive linear time algorithms for branchwidth 👍 👎
• A SAT Approach to Branchwidth 👍 👎
• Half-integrality, LP-branching and FPT Algorithms 👍 👎
• Algorithms – ESA 2005 👍 👎
• Graph-Theoretic Concepts in Computer Science 👍 👎

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)