ALCOMFT-TR-01-181

Fedor V. Fomin, Dieter Kratsch and Haiko Müller
Algorithms for graphs with small octopus
Paderborn. Work package 4. October 2001.

Abstract: A d-octopus of a graph G=(V,E) is a subgraph T=(W,F) of G such that W is a dominating set of G, and T is the union of d (not necessarily disjoint) shortest paths of G that have one endpoint in common.

First we study the complexity of finding and approximating a d-octopus of a graph. Then we show that for some NP-complete graph problems that are hard to approximate in general there are efficient approximation algorithms with worst case performance ratio c· d for some small constant c>0 (depending on the problem) assuming that the input graph G is given together with a d-octopus of G. For example, there is a linear-time algorithm to approximate the bandwidth of a graph within a factor of 8d. Furthermore the minimum number of subsets in a partition of the vertex set of a graph into clusters of diameter at most k can be approximated in linear time within a factor of 3d (for k=2) and 2d (for k>= 3).

Finally, we show that there are O(n^7d+2) time algorithms to compute a minimum cardinality dominating set respectively total dominating set for graphs having a d-octopus.

Postscript file: ALCOMFT-TR-01-181.ps.gz (152 kb).