DM582 - Advanced Algorithms

Home ☰

Exercises

As always, we expect you to be prepared for the exercises. However, if you didn't find time to work thoroughly through them, then at least make sure you have read all the texts. The exercises in [KT] are quite verbose and it's a waste of time to read the texts at the exercises, where it's better to focus on the core algorithmic and probabilistic issues.

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 \).
1. What can you say about the minimum size a dominating set in \( G \) must have?
2. Let \( D[v,t] \) be the event that the \( t \)th random vertex chosen dominates \( v \). Find the probability of \( D[v,t] \).
3. Let \( D_v \) be the event that \( S \) dominates \( v \). What is the probability of the complement of this event, \( \overline{D_v} \)?
4. 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} \).
5. 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} \).
6. Discuss what value \( c \) should have.

Data protection at SDU ▪ Databeskyttelse på SDU