LP-branching algorithms based on biased graphs

DOI10.1137/1.9781611974782.102zbMATH Open1422.90065arXiv1610.06060OpenAlexW2951611859MaRDI QIDQ4575845FDOQ4575845

Magnus Wahlström

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We give a combinatorial condition for the existence of efficient, LP-based FPT algorithms for a broad class of graph-theoretical optimisation problems. Our condition is based on the notion of biased graphs known from matroid theory. Specifically, we show that given a biased graph $Psi=(G,mathcalB)$, where $mathcalB$ is a class of balanced cycles in $G$, the problem of finding a set $X$ of at most $k$ vertices in $G$ which intersects every unbalanced cycle in $G$ admits an FPT algorithm using an LP-branching approach, similar to those previously seen for VCSP problems (Wahlstr"om, SODA 2014). This framework captures many of the problems previously solved via the VCSP approach to LP-branching, as well as new generalisations, such as Group Feedback Vertex Set for infinite groups (e.g., for graphs whose edges are labelled by matrices). A major advantage compared to previous work is that it is immediate to check the applicability of the result for a given problem, whereas testing applicability of the VCSP approach for a specific VCSP requires determining the existence of an embedding language with certain algebraically defined properties, which is not known to be decidable in general. Additionally, we study the approximation question, and show that every problem of this category admits an $O(logextOPT)$-approximation.

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

Mathematics Subject Classification ID

Linear programming (90C05) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cited In (2)

• An Updated Experimental Evaluation of Graph Bipartization Methods
• Title not available (Why is that?)

This page was built for publication: LP-branching algorithms based on biased graphs

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