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

[Andreas K. <and...@ac...>]

Lars Hellström wrote:
> 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.

Yes. I just googled for
	weighted metric k-center
and found the PDF

http://www.corelab.ntua.gr/courses/approx-alg/material/k-center.pdf

which seems to be the basis of Michal description, it is very similar.

And it also describes it as finding maximal, not maximum, the latter being NP-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 pdf explains a bit more, maybe that helps.

>> 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.)

Andreas.