Abstract:

Given a weighted graph $G=(V, E; w, c)$ and a spanning subgraph $G_{1}=(V, E_{1})$ of $G$, where a set $S=\{s_{1}, s_{2}, \cdots, s_{k}\}$ of $k$ sources in $V$, a weight function $w: E\rightarrow \mathbb{R}^{+}$, a cost function $c: E\setminus E_{1}\rightarrow \mathbb{Z}^{+}$, and a positive integer $B$, we consider two kinds of the constrained multi-sources eccentricity augmentation problems as follows. (1) The constrained multi-sources minimum eccentricity augmentation problem (the CMS-Min-EA problem, for short) is asked to find a subset $E_{2}\subseteq E\setminus E_{1}$ with a constraint $c(E_{2})\leq B$, the objective is to minimize the minimum of the eccentricities of vertices of $S$ in the graph $G_{1}\cup E_{2}$, and (2) The constrained multi-sources maximum eccentricity augmentation problem (the CMS-Max-EA problem, for short) is asked to find a subset $E_{2}\subseteq E\setminus E_{1}$ with a constraint $c(E_{2})\leq B$, the objective is to minimize the maximum of the eccentricities of vertices of $S$ in the graph $G_{1}\cup E_{2}$. For the two problems mentioned-above, we design two fixed parameter tractable (FPT) constant-approximation algorithms to solve them, respectively.

Key words: combinatorial optimization, eccentricity, augmentation problems, parameterized complexity, FPT approximation algorithms