Approximation algorithm for the balanced 2-connected k-partition problem

详细信息    查看全文

• 作者：Di Wu^a ; Zhao Zhang^b ; ^{hxhzz@sina.com" class="auth_mail" title="E-mail the corresponding author} ; Weili Wu^c
• 关键词：Balanced m-connected k-partition ; Interval graph ; Pseudo-polynomial time algorithm ; FPTAS
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 January 2016
• 年：2016
• 卷：609
• 期：part_P3
• 页码：627-638
• 全文大小：435 K

文摘

For two positive integers m,k$m,k$ and a connected graph 742f6651182239e778faeea3197d758" title="Click to view the MathML source">G=(V,E)$G=(V,E)$ with a nonnegative vertex weight function w, the balanced m-connected k  -partition problem, denoted as 721b2b3cd1" title="Click to view the MathML source">BC_mP_k${\mathit{BC}}_m{P}_k$, is to find a partition of V into k   disjoint nonempty vertex subsets (V₁,V₂,…,V_k)$(V_1,V_2,\dots ,V_k)$ such that each G[V_i]$G[V_i]$ (the subgraph of G   induced by V_i$V_i$) is m  -connected, and 746c113899e36e9" title="Click to view the MathML source">min_1≤i≤k⁡{w(V_i)}${\min }_{1\le i\le k}\{w(V_i)\}$ is maximized. The optimal value of 721b2b3cd1" title="Click to view the MathML source">BC_mP_k${\mathit{BC}}_m{P}_k$ on graph G   is denoted as ${\beta }_m^{⁎}(G,k)$, that is, ${\beta }_m^{⁎}(G,k)=\max {\min }_{1\le i\le k}\{w(V_i)\}$, where the maximum is taken over all m-connected k-partition of G  . In this paper, we study the BC₂P_k${\mathit{BC}}_2{P}_k$ problem on interval graphs, and obtain the following results.

(1) For k=2$k=2$, a 4/3-approximation algorithm is given for BC₂P₂${\mathit{BC}}_2{P}_2$ on 4-connected interval graphs.

(2) In the case that there exists a vertex v   with weight at least 742664f1bce440fcdbd86da6c93d3" title="Click to view the MathML source">W/k$W/k$, where W   is the total weight of the graph, we prove that the BC₂P_k${\mathit{BC}}_2{P}_k$ problem on a 2k-connected interval graph G   can be reduced to the BC₂P_k−1${\mathit{BC}}_2{P}_{k-1}$ problem on the (2k−1)$(2k-1)$-connected interval graph G−v$G-v$. In the case that every vertex has weight at most 742664f1bce440fcdbd86da6c93d3" title="Click to view the MathML source">W/k$W/k$, we prove a lower bound ${\beta }_2^{⁎}(G,k)\ge W/(2k-1)$ for 2k-connected interval graph G.

(3) Assuming that weight w   is integral, a pseudo-polynomial time algorithm is obtained. Combining this pseudo-polynomial time algorithm with the above lower bound, a fully polynomial time approximation scheme (FPTAS) is obtained for the BC₂P_k${\mathit{BC}}_2{P}_k$ problem on 2k-connected interval graphs.