Re: [Tcllib-devel] ping gsoc graph work ...

[Lars H. <Lar...@re...>]

Michał Antoniewski skrev:
> - for each Gi^2 we seek for maximum independent set Mi. Just to clear:
> finding maximal is of course NP hard, we seek for maximum set.

You've got maximum and maximal the wrong way round here. Finding one 
maximal (w.r.t set inclusion) independent set is easy (add vertices 
until you've covered the graph). Finding one that achieves the maximum 
cardinality is hard.

But now that I think about it... is this really what you want? The next 
steps being

> - let the j be the min index, such that |Mj| <= k.
> 
> - return Mj.

it would seem more natural to seek a set which is somehow minimum here 
(as that would make it easier to meet this condition) than to pick the 
maximum. Indeed, given that

> The goal is to find such S, that |S| = k, and maxv { connect(v,S) } is as
> small as possible.

it seems more like you're after a minimal covering than a maximal 
independent set. Going to the square complicates the picture somewhat, 
but it still looks to me as though your algorithm won't work.

Consider the case that Gi is the path u--v--w. The square of this is 
the complete graph on these vertices, so a maximal independent set 
contains one vertex. If you pick u or w, then you won't cover all of 
Gi, which seems bad (it can be argued that connect(w,{u}) is infinite).

Also, there is the brute force approach of simply iterating over all 
k-subsets S of V, computing maxv { connect(v,S) } for all. For small 
fixed k this seems faster than what you're about to do, so it might be 
considered as an alternative algorithm for solving the problem as 
stated. (It could of course be that this range of parameters if fairly 
uninteresting.)

Lars Hellström