- KT, Ch. 13, Exercises 1 and 2.
- KT, Ch. 13, Exercise 3. This is not directly relevant for solving the problem but in case you don't know: An independent set, \( I \), in a graph \( G=(V,E) \) is a set such that there are no \( u,v \in V \) such \( (u,v) \in E \) and no sub-exponential algorithm is known for find the largest independent set in a graph. Having considered the last question in the exercise, what can you say about the problem as \( d \) gets larger?
- KT, Ch. 13, Exercise 4.
-
In this problem, we consider an undirected graph \( G=(V,E) \)
to model the problem where there are \( n=|V| \) small devices, each
of which uses wireless communication to communicate with \( d \) of
the other nearby devices. The vertices in \( V \) are the
devices, and there are edges between vertices representing pairs of
devices within communication range of each other. Thus, each vertex
has exactly \( d \) neighbors.
Some of the devices should be given an uplink transmitter so they can send data to the main station. We want to use as few uplink transmitters as possible while still getting all of the data from all of the devices. Thus, in our graph, we want a subset \( S\subseteq V \) such that for all \( v \in V \), either \( v \in S \) or \( v \) has a neighbor \( u \) such that \( u \in S \). Such a set \( S \) is called a dominating set. If the devices corresponding to vertices in \( S \) all get uplink transmitters, then all devices can either send data to the main station directly, or send data to a device that can send data directly.
Finding a minimum-sized dominating set is an NP-hard problem (this means that no sub-exponential algorithm is known), so one does not expect to find a polynomial-time deterministic algorithm to solve it.
In this problem, consider a randomized algorithm that chooses a set \( S \) of \( k = \frac{cn\ln(n)}{d+1} \) vertices from \( V \) uniformly at random. The constant \( c \) will be discussed later. You should show through the following that \( S \) is a dominating set with high probability.
In the following, assume that the vertices in \( S \) are chosen one at a time and choosing the same vertex more than once is allowed. A vertex \( v \) is said to dominate a vertex \( u \) if they are the same vertex or \( u \) is a neighbor of \( v \). A set \( S' \) dominates \( u \) if some vertex in \( S' \) dominates \( u \).
- What can you say about the minimum size a dominating set in \( G \) must have?
- Let \( D[v,t] \) be the event that the \( t \)th random vertex chosen dominates \( v \). Find the probability of \( D[v,t] \).
- Let \( D_v \) be the event that \( S \) dominates \( v \). What is the probability of the complement of this event, \( \overline{D_v} \)?
- Show that \( \left(\frac1e\right)^{c \ln(n)} \) is an upper bound on the probability of \( \overline{D_v} \) and that \( \left(\frac1e\right)^{c \ln(n)}=\frac{1}{n^c} \).
- Let \( A \) be the event that \( S \) is a dominating set. Use the Union Bound to give an upper bound on the probability of \( \overline{A} \).
- Discuss what value \( c \) should have.