TY - JOUR

T1 - Approximability and inapproximability of the minimum certificate dispersal problem

AU - Izumi, Tomoko

AU - Izumi, Taisuke

AU - Ono, Hirotaka

AU - Wada, Koichi

N1 - Funding Information:
This work is supported in part by KAKENHI numbers 21500013 and 21680001, Asahi-glass Foundation and Inamori Foundation.

PY - 2010/6/28

Y1 - 2010/6/28

N2 - Given an n-vertex directed graph G=(V,E) and a set R⊆V×V of requests, we consider assigning a set of edges to each vertex in G so that for every request (u,v) in R the union of the edge sets assigned to u and v contains a path from u to v. The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general R has Θ(log n) lower and upper bounds on approximation ratio under the assumption P≠NP. We then assume R forms a clique structure, called Subset-Full, which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes 2-approximable, though it has still no polynomial time approximation algorithm whose factor is better than 677/676 unless P=NP. Finally, we show that this approximation ratio can be improved to 3/2 for the undirected variant of MCD with Subset-Full.

AB - Given an n-vertex directed graph G=(V,E) and a set R⊆V×V of requests, we consider assigning a set of edges to each vertex in G so that for every request (u,v) in R the union of the edge sets assigned to u and v contains a path from u to v. The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinalities of the edge sets assigned to each vertex. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs and restricted request structures, such as bidirectional trees with requests of all pairs of vertices. In this paper, we give an advanced investigation about the difficulty of MCD by focusing on the relationship between its (in)approximability and request structures. We first show that MCD with general R has Θ(log n) lower and upper bounds on approximation ratio under the assumption P≠NP. We then assume R forms a clique structure, called Subset-Full, which is a natural setting in the context of the application. Interestingly, under this natural setting, MCD becomes 2-approximable, though it has still no polynomial time approximation algorithm whose factor is better than 677/676 unless P=NP. Finally, we show that this approximation ratio can be improved to 3/2 for the undirected variant of MCD with Subset-Full.

UR - http://www.scopus.com/inward/record.url?scp=77955425207&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955425207&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2010.03.029

DO - 10.1016/j.tcs.2010.03.029

M3 - Article

AN - SCOPUS:77955425207

SN - 0304-3975

VL - 411

SP - 2773

EP - 2783

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 31-33

ER -