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

An extended localized algorithm for connected dominating set formation in ad hoc wireless networks

What is 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...

1. Connect them afterwards
2. Maintain a connected set

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 *

*:Sudipto Guha and Samir Khuller Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387, 1998.

$2\ln (\Delta) + O(1)$

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 *

*:Sudipto Guha and Samir Khuller Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387, 1998.

Happy Ever After?

New Problems

1. You know nothing about the graph.
2. Storing the whole graph can be expensive.
3. Graph can be dynamic and changes constantly.
4. 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.

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.

*: Borgs et al: The power of local information in social networks. In Internet and Network Economics, pages 406–419. Springer, 2012

1-hop Local Algorithm Visualization

Still a $2\ln(\Delta) + O(1)$ approximation...

But

Requires less information.

Which implies...

1. It is much faster, by an $O(\Delta)$ multiplicative factor.
2. 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)$
*:Sudipto Guha and Samir Khuller Approximation algorithms for connected dominating sets. Algorithmica, 20(4):374–387, 1998. **: Borgs et al: The power of local information in social networks. In Internet and Network Economics, pages 406–419. Springer, 2012

YES!

Observation:

1. It's too expensive to select two nodes at a time
2. 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

$f(v) = 2w_v + c_v - 1$
• $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$

1. Dominating
• Every uncovered node $v$ will have $f(v)\geq 2\cdot 1 + 0 - 1 = 1$
2. 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?