Revisiting Connected Dominating Sets:
An Optimal Local Algorithm?
Samir Khuller (samir@cs.umd.edu), Sheng Yang (styang@cs.umd.edu)
University of Maryland, College Park
What is a Connected Dominating Set?
- A set of nodes $S$
- $S$ is a dominating set
- $S$ is connected
Problem Origin
Sudipto Guha and Samir Khuller.
Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387, 1998.
1000+ citations
[BOOK] Protocols and architectures for wireless sensor networks
On calculating connected dominating set for efficient routing in ad hoc wireless networks
Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networks
A clustering scheme for hierarchical control in multi-hop wireless networks
Connected sensor cover: self-organization of sensor networks networks for efficient query execution
Minimum-energy broadcasting in static ad hoc wireless networks
An extended localized algorithm for connected dominating set formation in ad hoc wireless networks
What is Ad hoc Wireless Network?
Ad hoc Wireless Network
Ad hoc Wireless Network
CDS Problem:
Given a graph $G$, find a CDS $S$, such that the size of $S$ is minimized
How can we solve CDS problem?
-
NP-hard
- By reduction to Set Cover
- Well, Set Cover?
Greedy!
Choose a node that maximizes the number of newly covered nodes.
However... does this really work?
The result is not connected.
We can...
- Connect them afterwards
- Maintain a connected set
Naive algorithm:
Counter Example
Solution
Choose a pair of nodes, i.e. a node and its neighbor, to maximize the number of newly covered nodes.
2-hop Local Algorithm *
$O(\log (\Delta))$
$2\ln (\Delta) + O(1)$
What about the other way?
First globally select dominating set using greedy,
then connect them.
$O(\log(\Delta)) + O(1)$
Well.. anything better?
Global Algorithm
We first color all nodes white, and color it black when we select it. All dominated nodes are colored gray.
Every white node, or every connected component of black node, is considered as a piece.
Phase 1: globally select a node that maximizes the reduction of the number of pieces.
Phase 2: connect the pieces.
$\ln(\Delta) + O(1)$
Global Algorithm *
Happy Ever After?
New Problems
- You know nothing about the graph.
- Storing the whole graph can be expensive.
- Graph can be dynamic and changes constantly.
- Algorithm needs to run periodically.
Local Information
C. Borgs, M. Brautbar, J. Chayes, S. Khanna, and B. Lucier
The power of local information in social networks. In Internet and Network Economics, pages 406–419. Springer, 2012
Local Information Algorithm
Do not know the whole graph.
Start from a random node to explore the graph.
Can only see nodes within some local neighborhood of the visited nodes.
When a new node is visited, you can see more nodes.
$k$-Hop Local Neighborhood
Visited nodes: $S$.
Visible nodes: $\bar{S} = \{u|\exists v\in S, \mathrm{s.\! t.}\ d(u,v) \leq k\}$.
The sub-graph induced by $\bar{S}$ is known.
The degree of nodes in $\bar{S}$ is visible.
Local Neighborhood Visualization
Looking Back
Guha and Khuller's algorithm requires 2-hop local information.
1-hop Local Algorithm*
Look among 1 hop neighborhood, and select a node $v$ that maximizes the number of newly covered nodes.
Then select one of the newly covered node uniformly at random.
Repeat the previous steps until all nodes are covered.
1-hop Local Algorithm Visualization
Still a $2\ln(\Delta) + O(1)$ approximation...
But
Requires less information.
Which implies...
- It is much faster, by an $O(\Delta)$ multiplicative factor.
- It is MUCH easier to program.
Recall the Approximation Ratio..
| Global * | $\ln(\Delta) + O(1)$ |
| Local 2 hop * | $\color{red}{2}\ln(\Delta) + O(1)$ |
| Local 1 hop ** | $\color{red}{2}\ln(\Delta) + O(1)$ |
Can We Get Rid Of This Factor Of 2?
YES!
Observation:
- It's too expensive to select two nodes at a time
- It's too expensive to always maintain connectivity.
Algorithm
Same framework.
Look among 2 hop neighborhood, and select 1 node $v$ that maximize a certain target function $f(v)$, until for all node $v$, $f(v)\leq 0$
NOTE: we do NOT maintain connectivity
Target Function
$w_v$ is the number of new nodes that $v$ can cover.
$c_v$ is the number of components $v$ adjacent to.
Correctness
Target function: $f(v) = 2w_v + c_v - 1$
- Dominating
- Every uncovered node $v$ will have $f(v)\geq 2\cdot 1 + 0 - 1 = 1$
- Connectivity
- Every node $v$ that can connect two components will have $f(v)\geq 0 + 2 - 1 = 1$
Analysis
Analysis Sketch:
Recall charging in Set Cover.
- We charge when selecting a set, and split the charge among nodes covered by it.
- Every node is charged only once.
- For a set $s$ in OPT, bound the charge of all nodes that are covered by $s$ in OPT
- Approximation ratio $\ln(n) + O(1)$
Analysis Sketch:
We charge when selecting a node, and split the charge magically among nodes.
Every node can be charged twice, the first time for being dominated, the second time for being connected.
For a node $v$ in OPT, bound the charge of all nodes that are covered by $v$ in OPT
Approximation ratio $\ln(2\Delta) + O(1)$.
Further Work:
- Can we further shrink the gap?
- Can we do better when we have only 1-hop information? Yes! $\ln(\Delta) + 2\sqrt{\ln(\Delta)} + O(1)$
- Can we apply this framework to other problems? e.g. partial CDS.
- Can we do even better when we have only 1-hop information?
Q & A
Powered by
- Reveal.js: the slide framework
- greuler.js: the graph
- animate.css: some animation
- magic.css: some other animation