February « 2008 « The Algorithmic Lens

Computing Minimum Spanning Trees With Uncertainty

February 28, 2008

In this post we will partially discuss this paper by Erlebach et. al. The classical MST problem is studied for graphs with edge and vertex uncertainties. In general a problem with uncertainties can be specified as a triple $(C,A,\phi)$ where $C$ , the $\emph{configuration}$ for the problem consists of a set of data points ${c_1,c_2,\cdots,c_n}$ and $A={A_1,A_2,\cdots,A_n}$ is a set of $\emph{areas}$ where $c_i \in A_i$ . The function $\phi$ defines the solution for a particular configuration $C$ . The input of the problem is just the set of areas $A$ . An algorithm can $\emph{update}$ any of the $A_i$ and this determines the value of the data point $c_i$ . The objective is to minimize the number of such updates and still be able to compute $\phi(C)$ . An algorithm is $k$ update competitive if it can compute $\phi(C)$ with at most $k\cdot OPT+c$ updates where $OPT$ is the minimum number of updates required by any algorithm.

Example: Given a weighted graph $G=(V,E,w)$ the areas $A_e, e \in E$ can be open intervals such that the edge weight $w(e) \in A_e$ . The function $\phi(C)$ can then be a minimum spanning tree of $G$ .

The $\emph{Witness}$ algorithm in this paper gives a general strategy to solve problems with uncertainties. The algorithm is $k$ update competitive where $k$ is an upper bound on the size of a witness set $W$ . A witness set $W$ is a set of areas such that in order to verify the solution $\phi(C)$ at least one element of $W$ needs to be updated. The witness algorithm is a kind of template for problems with uncertainties as it does not specify how a witness set is to be computed.

Question : In general is it always possible to compute a witness set in polynomial time?

The problem discussed in this paper is an extension of the concept of MST to graphs with uncertain edge weights. A MST of such a graph is said to be a MST in all possible realizations of edge weights, that satisfy the basic condition of the edge weight belonging to its assigned area. The paper provides an algorithm that is $2$ update competitive when the areas are open intervals or singletons. Furthermore it is proved that, there is no $(2-\epsilon)$ update competitive algorithm in this case. When there are no restrictions on the areas at all, it is proved that there is no constant update algorithm for the MST problem. The paper also considers graphs with vertex position uncertainties [where vertices are points in an Euclidean space].

The algorithm looks a lot like Kruskals MST algorithm. The main crux it to find witness sets of size $2$ as edges are considered in their special sorted order. For details please refer to the paper.

Some comments and questions:

1) How about approximation algorithms for problems with uncertainties? The goal of an approximation algorithm would be to compute an approximate solution to problems with uncertainties with minimum updates.

2) In this model, there seems to be no restriction on the running time of the algorithm but the only importance seems to be given to the number of updates. Is there a model which combines the two meaningfully?

3) The notion of a MST that applies to all possible realizations of a graph with edge uncertainties seems too restrictive.

Leave a Comment » | CS Theory | Permalink
Posted by cstheory

Hello world!

February 23, 2008

I intend to blog mostly about CS theory papers that I read. As I am also very interested in theoretical Physics and Mathematics, some of my posts can also be from papers in those fields. Occasionally I may discuss more mundane stuff.

Let me also use this post to test latex. $a_n = b_n + c_n$ .