Kolloquium Wintersemester 1998/99
Die Dozenten der Informatik
Prof. Martin Dyer, University of Leeds
speaks about
Counting Independent Sets in Graphs
| Datum: | Montag, November 2, 1998
| | Zeit: | 16:15 Uhr
| | Ort: | Hörsaal 1, Römerstraße 164
|
AbstractThe problem of counting and generating independent sets in graphs has received recent attention. Its relation to the hard-core gas model in statistical physics has been a particular stimulus. The counting problem is known to be #P-complete, even for graphs of maximum degree 3. On the other hand, it has been shown that, for graphs of maximum degree 4, fully polynomial randomized approximate counting is possible. This success has been achieved by using the Monte Carlo Markov chain method to generate random uniformly selected independent sets in the graph. We will examine a paticular Markov chain for this problem and outline its analysis by the method of "path coupling".
The degree 4 result suggests a natural question as to how far this success might extend. Unfortunately, the evidence now seems to be: not very far. We will outline two negative results. The first indicates that the Monte Carlo Markov chain method is likely to fail for graphs of degree not much greater than 4. The second gives a larger (but still relatively small) value of the maximum degree above which approximate counting by any means is impossible, unless P=NP under randomized reuctions.
(Vortrag auf Einladung von M. Karpinski)
Vor Beginn des Kolloquiums gibt es ab 15:45 Uhr in Raum N 315 (Neubau, III. Stock) die Gelegenheit, bei Kaffee und Tee mit dem Vortragenden zu diskutieren.
Last modified
October 16, 1998 14:35:18
|
.
Wintersemester 1998/99
Meyer
Kleine-Büning