Partitioning a graph into small pieces with applications to path transversal

• 成果类型: Article
• 署名作者: Lee, Euiwoong
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1255-7
• 发表日期: 2019
• 页码: 1-19
• 关键词: approximation algorithms; vertex cover; complexity

摘要

Given a graph G=(V,E) and an integer k is an element of 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 less than k vertices. 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. Our main results are the following improved approximation algorithms.O(logk)-approximation algorithm for k-Vertex Separator that runs in time 2O(k)n+nO(1). It improves the simple k-approximation, and runs faster than the lower bound k Omega(OPT)n Omega(1) for exact algorithms assuming the exponential time hypothesis (ETH)when OPT>k. We also prove that there is no n(1/loglogn)c-approximation algorithm that runs in time poly(n,k) assuming the ETH.O(logk)-approximation algorithm for k-Edge Separator that runs in time nO(1). It improves the best previous graph partitioning algorithm for small k=no(1).O(logk)-approximation algorithm for k-Path Transversal that runs in time nO(1)+2O(k3logk)n2logn. Previously, the existence of an (1-delta)k-approximation algorithm for fixed delta>0 (even using nf(k) time) was open.