Naslov
The relation of Connected Set Cover and Group Steiner Tree

Autori
Jelić, Slobodan ; Matijević, Domagoj

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
ApplMath11: Conference on Applied Mathematics and Scientific Computing / - , 2011

Skup
7th Conference on Applied Mathematics and Scientific Computing

Mjesto i datum
Trogir, Hrvatska, 13.06.2011. - 17.06.2011

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
set cover; connected set cover; weighted connected set cover; group Steiner tree; node weighted Group Steiner tree; covering Steiner tree problem

Sažetak
Let $U$ be the universe of elements which have to be covered, $\mathcal{; ; S}; ; $ family of subsets of $U$ and $G=(\mathcal{; ; S}; ; , E)$ connected graph on vertex set $\mathcal{; ; S}; ; $. We say that subfamily $\mathcal{; ; R}; ; \subseteq\mathcal{; ; S}; ; $ is \emph{; ; connected set cover}; ; (CSC) if every $u\in U$ is covered by at least one set from $\mathcal{; ; R}; ; $ and subgraph $G[\mathcal{; ; R}; ; ]$ induced by $\mathcal{; ; R}; ; $ is connected. The problem is to find connected set cover with respect to $(U, \mathcal{; ; S}; ; , G)$ with minimum number of sets (vertices). On the other hand, suppose that we are given a graph $G$ with edge weight function $w:E(G)\rightarrow\R^+$ and family of subsets of vertices $\mathcal{; ; G}; ; = \ {; ; g_1, g_2, \ldots, g_k\}; ; , \quad g_i\subset V$ which will be called groups. The well known and well studied \emph{; ; Group Steiner Tree}; ; (GST) is to find a subtree $T$ that minimizes the weight function $\sum_{; ; e\in E(T)}; ; w(e)$ such that $V(T)\cap g_i\neq\emptyset$ for all $i\in\ {; ; 1, \ldots, k\}; ; $. We showed in our work that CSC is equivalent to the variant of GST when all edge weights equal to $1$. Hence, all algorithms for GST immediately apply for CSC problem as well. As a result, we obtain an approximation algorithm for CSC problem with approximation ratio $O(\log^2m\log\log m\log n)$ where $n$ is the size of universe $U$ and $m$ is the size of family $\mathcal{; ; S}; ; $. This is the first polylogarithmic approximation algorithm for CSC problem. Natural generalization of CSC problem is to associate the nonnegative weight function with sets in $\mathcal{; ; S}; ; $. Weighted CSC problem assumes finding of connected set cover that minimizes the total weight of subfamily $\mathcal{; ; R}; ; $. We showed that this problem can be solved by reduction to the fault-tolerant version of Group Steiner problems for which $O(\sqrt{; ; m}; ; \log m)$ approximation algorithm is known. We also consider generalization of CSC problem where each element $u$ from universe has requirement $r_u$ on number of sets covering element $u$ associated. We showed the reduction of this problem to the variant of GST problem with requirements associated to the groups for which $O(\log^2 m\log\log m\log(R\cdot n))$ approximation algorithm is known, where $R$ dentes the largest requirement.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA