each vertex $v \in V(G)$ has at least one outgoing arc in any optimal solution. Hence, the cost paid by $v$ in any optimal solution is at least $\min_{vu \in A(G)} w(vu)$. Thus, $\ell(v) \ge \min_{vu \in A(G)} w(vu)$. Moreover, if a vertex $v$ has only one incoming arc $uv$, then the cost for the vertex $u$ is at least $w(uv)$, and thus $\ell(u) \ge w(uv)$. Clearly, finding more effective but still efficiently computable vertex lower bounds is challenging on its own.

\[obligatoryGraph\] The *obligatory subgraph* $G_\ell$ induced by a vertex lower bound $\ell$ for $G$ is a subgraph $(V(G), A_\ell)$, where $A_\ell = \{vu \mid w(vu) \le \ell(v) \}.$

It has been shown that sensors are optimally placed for fully covering an area when sensors are deployed in a triangular lattice pattern [@Zhang2005] or a strip based-pattern [@Bai2006; @IKB09]. In such cases, there are many arcs of minimum weight. Taking these arcs usually suffices to (almost) achieve strong connectivity. So even the obligatory subgraph induced by the trivial vertex lower bound described above yields a small number of SCCs.

Let $\ell$ be a vertex lower bound for a graph $G$. We denote the number of SCCs of the obligatory 