wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Maximal Weighted Induced Subgraph
        
(Message started by: william wu on Jan 10^th, 2003, 6:01am)

Title: Maximal Weighted Induced Subgraph
Post by william wu on Jan 10^th, 2003, 6:01am

A friend of mine was organizing a get-together where he wanted every person to know at least 2 other people. We realized this was like a puzzle:

You are given a set of people and information about who is acquainted with whom. Devise an algorithm that determines the largest subset of people you can grab such that at the get-together, everyone will know at least k other people.

This puzzle can be formulated as a graph problem as follows: Given a graph G = (V,E), let an "induced subgraph" be defined as G' = (V',E'), where V' is a subset of V, and E' consists only of edges which have both endpoints in V'. Find the largest G' such that every vertex in V' has degree >= k.

We concluded that a greedy algorithm works for this puzzle, which makes the puzzle not that interesting. (You can think about how a greedy algorithm would work.) But what if the graph is weighted, and we want to find the largest and lightest (or heaviest) induced subgraph. (In the context of the get-together, this is like saying each person ranks how well acquainted they are with others, and you want to satisfy the >= k constraint AND minimize the sum of the ranks of all acquaintanceships at the get-together, thereby maximizing overall camaraderie in a sense.) Now the greedy algorithm would not work, because removing vertices in different orders can produce induced subgraphs with different weights. Any ideas? By the way, we don't know if this is a solved problem.

Apologies in advance for anything silly written above; it's very late here ...

Some Informal graph theory definitions for the unacquainted:
graph = a pair (V,E), where V is a set of vertices, and E is a set of edges that connect the vertices.
degree of a vertex = the number of other vertices that vertex is connected to

Title: Re: Maximal Weighted Induced Subgraph
Post by william wu on Jan 10^th, 2003, 6:07am

Yup, it doesn't make sense does it. Am I optimizing for weight or for graph size? I need a tradeoff function. Never mind I'm going to bed :P