Independent Set - Proof Homepage

The FST&TCS'09 paper can be found here.

Errata

Unfortunately, the manual analysis of the non-computer aided part of the proof contains a branching vector that does not yield the claimed runtime bound.

Namely, in the proof of Lemma 19, in the case when S(v) contains exactly one node node and M(v) is empty, we claim that there are 2(d-d') edges to the outside. This only yields a runtime bound of 1.2134 if d=5 and d'=3 (and all neighbors of v are of degree five except for one neighbor of degree four).

We are very thankful to Bruno Escoffier and Vangelis Th. Paschos for finding this error.

Fortunately, this problem can be fixed, since we gain at least max{2(d-d'),5} edges in the above mentioned case: Since u is not a mirror, at least two nodes in N(v) \ N(u) contribute two edges, hence the term 2(d-d'). However, if only these two nodes contribute edges, they also form a separator of size two, which im implies that the graph is not reduced. Thus, we gain at least one additional edge.

Certificate

How to read these files

Files

Interactive graphlet generation

This Java applet allows to interactively generate a graphlet and simulate the branching algorithm.

Generator

Verifier

List of all Branching Vectors

A case is described by the list of its neighbors degree. For example, [ 3 3 5 5 5 ] represents a node of degree five with two neighbors of degree three and three neighbors of degree five. Note that these lists do not include cases analyzed using the automated proof. Instead, these lists present the precise bounds obtained in Lemma 16, Lemma 17, Lemma 18 and Lemma 19 (which form the traditional part of the proof).