Abstract of Paper |

*Hardness Results and Efficient Approximations for Radiocoloring in Planar Graphs*

by D.A. Fotakis, S.E. Nikoletseas, V.G. Papadopoulou and P.G. Spirakis

**Abstract:**

The communication in wireless systems, such as radio networks or ad-hoc mobile networks, is accomplished through exploitation of a rather limited range of the frequency spectrum. One of the mechanisms utilized in this direction is to reuse frequencies where this does not result to unacceptable levels of signal interference. In graph theoretic terms, such issues are usually modeled by the interference graph $G(V, E)$, where the vertex set $V$ corresponds to the set of transmitters, and variations of coloring of the vertices of $G$ have been proposed in order to represent distance interference constraints. In this paper we study the {\em radiocoloring problem for planar graphs $G$}. A proper radiocoloring of the planar graph $G$ with $\lambda$ colors is a function $\Phi: V \rightarrow \rm{I}\!\!\!\rm{N} $ such that $|\Phi_{u}-\Phi_{v}| \geq 2$, when $u, v$ are neighbors in $G$ and $|\Phi_{u}-\Phi_{v}|\geq 1$ when the minimum distance of $u, v$ in $G$ is 2. Also, only $\lambda$ integers are used. The least possible $\lambda$ is called the radiochromatic number of $G$, denoted as $X_{r}(G)$. Notice that $X_{r}(G)$ is also the vertex chromatic number of the {\em square graph} of $G$, $G^2$, which has the same vertex set $V$ as $G$ and an edge set $E': \{ u, v \} \in E' $ iff their {\em minimum} distance is at most $2$ in $G$. Let $\Delta$ be the maximum degree of the vertices of $G$. In this paper we are interested in the problem of {\em minimizing $\lambda$ (the radiocoloring problem, RAP}): \begin{enumerate} \item We show that {\em RAP is NP-complete for planar graphs}. \item We provide an $O(n\Delta)$ time algorithm ($|V|=n$) which obtains a radiocoloring of a planar graph $G$ that {\em approximates $X_{r}$ within a ratio which tends to 2} as the maximum vertex degree $\Delta$ of $G$ increases. \item We provide a {\em fully polynomial randomized approximation scheme} (fpras) for the {\em number of radiocolorings of a planar graph} $G$ with $\lambda$ colors, in the case $\lambda \geq 4 \Delta+50$. \end{enumerate}