Partitioning a graph into small pieces with applications to path transversal

DOI10.1007/S10107-018-1255-7zbMATH Open1452.68137arXiv1607.05122OpenAlexW3014552119MaRDI QIDQ2316611

Author name not available (Why is that?)

Publication date: 6 August 2019

Published in: (Search for Journal in Brave)

Abstract: Given a graph $G=(V,E)$ and an integer $k$, we study $k$-Vertex Seperator (resp. $k$-Edge Separator), where the goal is to remove the minimum number of vertices (resp. edges) such that each connected component in the resulting graph has at most $k$ vertices. Our primary focus is on the case where $k$ is either a constant or a slowly growing function of $n$ (e.g. $O(logn)$ or $n^{o(1)}$). Our problems can be interpreted as a special case of three general classes of problems that have been studied separately (balanced graph partitioning, Hypergraph Vertex Cover (HVC), and fixed parameter tractability (FPT)). Our main result is an $O(logk)$-approximation algorithm for $k$-Vertex Seperator that runs in time $2^{O(k)}{n}^{O(1)}$, and an $O(logk)$-approximation algorithm for $k$-Edge Separator that runs in time $n^{O(1)}$. Our result on $k$-Edge Seperator improves the best previous graph partitioning algorithm for small $k$. Our result on $k$-Vertex Seperator improves the simple $(k+1)$-approximation from HVC. When $OPT>k$, the running time $2^{O(k)}{n}^{O(1)}$ is faster than the lower bound $k^{Omega(OPT)}{n}^{Omega(1)}$ for exact algorithms assuming the Exponential Time Hypothesis. While the running time of $2^{O(k)}{n}^{O(1)}$ for $k$-Vertex Separator seems unsatisfactory, we show that the superpolynomial dependence on $k$ may be needed to achieve a polylogarithmic approximation ratio, based on hardness of Densest $k$-Subgraph. We also study $k$-Path Transversal, where the goal is to remove the minimum number of vertices such that there is no simple path of length $k$. With additional ideas from FPT algorithms and graph theory, we present an $O(logk)$-approximation algorithm for $k$-Path Transversal that runs in time $2^{O(k^{3}logk)}{n}^{O(1)}$. Previously, the existence of even $(1-delta)k$-approximation algorithm for fixed $delta>0$ was open.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Partitioning a graph into small pieces with applications to path transversal

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