Given a graph G = (V, E) and an integer k ∈ N, we study k-Vertex Separator (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(log n) 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(log k)-approximation algorithm for k-Vertex Separator that runs in time 2 , and an O(log k)-approximation algorithm for k-Edge Separator that runs in time n O(1) . Our result on k-Edge Separator improves the best previous graph partitioning algorithm [KNS09] for small k. Our result on k-Vertex Separator improves the simple (k + 1)-approximation from HVC [BAMSN15]. When OPT > k, the running time 2 O(k) n O(1) is faster than the lower bound k Ω(OPT) n Ω(1) for exact algorithms assuming the Exponential Time Hypothesis [DDvH14]. 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(log k)-approximation algorithm for k-Path Transversal that runs in time 2 O(k 3 log k) n O(1) . Previously, the existence of even (1−δ)k-approximation algorithm for fixed δ > 0 was open [Cam15].
The problem has been studied in REF as k-path traversal problem which presents a log(k)-approximation algorithm for the unweighted version.
Partitioning a Graph into Small Pieces with Applications to Path Transversal
ArXiv
ArXiv
Mathematics Computer Science