Author |
Topic: Maximal Weighted Induced Subgraph (Read 1567 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Maximal Weighted Induced Subgraph
« on: Jan 10th, 2003, 6:01am » |
 Quote  Modify
|
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
|
| « Last Edit: Jan 10th, 2003, 6:05am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Maximal Weighted Induced Subgraph
« Reply #1 on: Jan 10th, 2003, 6:07am » |
Quote Modify
|
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 
|
| « Last Edit: Jan 10th, 2003, 6:07am by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print