Relationship between Approximability and Request Structures in the Minimum Certificate Dispersal Problem

Computing and Combinatorics, 15th Annual International Conference, COCOON : Niagara Falls, NY, USA, July 13-15, 2009Given a graph $G=(V,E)$ and a set $R subseteq V\times V$ of requests, we consider to assign a set of edges to each node in $G$ such 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$. {em The Minimum Certificate Dispersal Problem} (MCD) is defined as one to find the assignment that minimizes the sum of the cardinality of the edge set assigned to each node. This problem has been shown to be NP-hard in general, though it is polynomially solvable for some restricted classes of graphs, such as bidirectional trees. 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 $Theta (log n)$ lower and upper bounds on approximation ratio under the assumption $P\eq NP$, where $n$ is the number of nodes in $G$. We then assume $R$ forms a clique structure, called {em Subset-Full}, which is a natural setting in the context of security systems. Interestingly, under this natural setting, MCD becomes to be $2$-approximable, though it has still no polynomial time approximation algorithm whose factor better than $391/390$ unless $P=NP$. Finally, we show that this approximation ratio can be improved to 3/2 for undirected variant of MCD with Subset-Full