Generalized Spanning TreesProblem code: GST |
All submissions for this problem are available.
A spanning tree of an undirected, connected graph (V,E) with vertex set V and edge set E is a subset of edges F such that the graph (V,F) is connected and has no cycles. After a few moments thought, one realizes that an equivalent way to say this is to say:
- 1) |F| = |V| - 1
- 2) For any non-empty subset of nodes S, the number of edges with both endpoints in S is does not exceed |S|-1.
There is a fairly simple algorithm that can determine if a set of edges F is indeed a spanning tree of a graph. Simply check that |F| = |V| - 1 and that the graph (V,F) is connected using your favorite connectivity algorithm.
As in all topics in mathematics, the next step is to generalize what is known. So, consider the following generalization of spanning trees. Say a generalized spanning tree (GST) of a graph (V,E) is a function f from the set of edges E = {e1, e2, ..., eM} to the real interval [0,1] such that the following conditions hold:
- 1) f(e1) + f(e2) + ... + f(eM) = |V| - 1
- 2) For any non-empty subset of nodes S, the sum of the f(e) values for edges e with both endpoints in S does not exceed |S|-1.
One can see that this generalizes the notion of a spanning tree since spanning trees (in the classical sense) correspond to GSTs by setting f(e) = 1 if e is in the spanning tree and f(e) = 0 if e is not in the spanning tree.
Your task is to determine if a given function is a GST of a given graph.
Input:
The first line contains a single integer T (about 20) indicating the number of test cases to follow.
Each test case begins with two integers N and M where N is the number of nodes and M is the number of edges. The following M lines describe the edges, one per line. Each line contains three values u, v, f where 1 <= u, v <= n are the endpoints of the edge and f is a rational number between 0 and 1 (inclusive). This rational number is the value of the edge in the proposed GST.
The rational numbers are always presented as n/d (even if d=1) where both n and d are non-negative and have no common factors.
The input graphs have no parallel edges or loops and are, of course, undirected. Consecutive cases will be separated by a blank line (including a blank line preceding the first case).
Bounds: 1 <= N <= 50, 1 <= M <= 100, and no denominator of any fraction in the input exceeds 30.
Output:
If the function is a GST, you are to simply print a single line saying "GST".
If the first constraint (the sum of the values of all edges is N-1) is violated, then you should print a single line displaying just the number 1.
Otherwise, if constraint 1) holds but constraint 2) is violated for some non-empty set S, you should print three lines. The first line simply contains the integer 2. The second contains the size of a non-empty subset of the nodes whose corresponding constraint is violated. The third line lists the nodes (in any order) that are part of such a set with a violated constraint (the number of nodes is as reported in the second line).
If there are multiple non-empty sets whose constraints are violated, then any will do. Print a blank line after the output for each case.
Example:
Input:
3 3 3 1 2 2/3 2 3 2/3 3 1 2/3 3 3 1 2 1/1 2 3 1/1 3 1 1/1 4 6 1 2 1/5 1 3 1/5 1 4 1/5 2 3 4/5 2 4 4/5 3 4 4/5
Output:
GST 1 2 3 2 3 4
| Author: | friggstad |
| Date Added: | 10-04-2010 |
| Time Limit: | 7 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Can anyone explain this
Can anyone explain this testcase :-
What part of that output
What part of that output don't you understand?
I have named my class as main
I have named my class as main yet it shows compilation error that i should name my class as main..
What is the error?
Capitalization.
Capitalization.
If there are no loops, then
If there are no loops, then for n=1, we should not have edges. But m>=1, so is n=1 a possibility for this problem? Please clarify
You can assume N >= 2.
You can assume N >= 2.
at the verdict page it
at the verdict page it says: :( internal error occurred in the system
but it mailed me, AC. So should i assume that, i got an AC?
OK , so I learn your
OK , so I learn your technique.
how long they will send you
how long they will send you the status of submission?
it takes me about 5 minutes
it takes me about 5 minutes to receive a result of submission. "Edit profile" option if you want to do this.
Admins. Why have I vanished
Admins.
Why have I vanished from the all the ratings altogether. I have solved 3 !! :)
@Ravi: The issue is resolved
@Ravi: The issue is resolved now. Your name appears there :-)
Well, I've spent many hours
Well, I've spent many hours on varying approaches to this problem; the closest I've got is that it is possible to find the densest subgraph with min-cut, where density = weight of edges / number of nodes. Here that would only work if we could find the biggest (edges+1)/nodes or edges/(nodes-1), so that doesn't really help at all.
Any hints towards the correct approach?
It's all about finding the
It's all about finding the right google search term. In this case it's "arboricity" or "Nash-Williams".
@Stephen I solved it with
@Stephen
I solved it with maximum density subgraph, or actually using an algorithm that is able to check whether the density is greater than some given parameter. This can be done with one min-cut computation, see for instance http://www.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-171.pdf.
As you say this doesn't quite work since we need to check whether there exists a subgraph such that (weight of edges + 1)/number of nodes in the subgraph > 1, and we can only check that (weight of edges)/number of nodes > 1. However if we knew an edge that is part of a subgraph violating the constraint (weight of edges + 1)/number of nodes, then we could simply add one to its weight and we'd be able to verify the constraint. Since we don't know such an edge, we can just try all edges one-by-one, add one to its weight, and the check the constraint. I'll omit the remaining details of the proof for why this works.
I see. So I was just 'add
I see. So I was just 'add one' away from a solution the whole time. Sigh.
Lets assume we already know a
Lets assume we already know a vertex v which belongs to a subset of nodes which does not fulfill constraint 2). We start with a subset consisting of only vertex v. We can then see what happens each time when we connect another node u to the current subset. We add the weight of all edges with endpoint u and the other endpoint in the current set, and subtract 1 because the size of the subset increased by 1. Whenever we get a sum > 0 after such a step, we have found an inconsistent subset.
Now I used the following idea: each edge needs to give its weight to its adjacent vertices, where each vertex can have a total weight of at most 1 (and vertex v can have a total weight of 0). This can be modeled as a network flow problem: create a node for each edge, and connect the source to each edge node with capacity corresponding to the weight of the edge, then connect each edge node to the nodes which are its endpoint, and each original node is connected to the sink and has capacity 1 (or capacity 0 in the case of vertex v). The network flow algorithm tries to fill each edge from the source to an edge node up to its capacity. The first time when an edge cannot be filled to capacity, we can find the inconsistent subset by calculating which nodes belong to the minimum cut.
Since we originally do not know which vertex v belongs to an inconsistent set, we have to run the algorithm n times (each time selecting another node as vertex v).
@Mark Wow...that's a
@Mark
Wow...that's a completely different (and from the looks of it, much simpler) approach than mine. My approach was to partition the graph into spanning trees using ideas from https://www.cs.colorado.edu/department/publications/reports/docs/CU-CS-446-89.pdf. I wouldn't be suprised if there's some test case that my program times out on (since the total number of spanning trees is the LCM of the denominators).
I did an slightly different
I did an slightly different way. First we need to find the maximum weighted clique where the weight of the clique is the sum of the edges-weights - |V|. If we have the weight of a clique G', we can compute the weight of a clique G'U{v} and G'U{u}U{v} where u and v are vertices not in G'. I start with a G' which is randomly initialized(I try all sizes from 1 to |V|-1). For each size I try several random initializations. Then I do a gradient ascent type approach, where at each step, I pick a vertex or a pair of vertices which maximally increase the weight of the clique. If the weight of the maximal clique is more than -1, then we have a violated constraint 2. Otherwise, we continue doing the iteration described above until we have reached a certain level of confidence.
Although this seems probabilistic, it seemed to work(matches with Brute-force) on several random testcases of sizes<=22. However the exact computation of the probability of false-detection would be of interest for this randomized algorithm.
This problem can be reduced
This problem can be reduced to http://www.spoj.pl/problems/PROFIT/ with a slight modification. That problem itself is a special case of a more general problem found in CLR exercises on Network Flows (Space shuttle experiments I think), which can be solved by an algorithm similar to the one mentioned by Adrian Keugel.
Briefly, given the costs of choosing vertices and profits arising out of edges connecting two chosen vertices, consider the problem of maximizing the net profit from a subset of vertices ( = sum of profits of edges with endpoints in the subset minus costs of vertices in the subset). Solving GST then reduces to checking if a profit greater than -1 can be achieved. (Vertices cost 1 each and edge profit = edge weight)
You can solve this problem by the method Adrian Kuegel suggested. Constructing the Network flow graph and finding its max flow. The only problem remaining is we need to avoid the trivial min cut of the flow graph (this corresponds to choosing the empty set of vertices and thus a net profit of 0, but we need to find the best net profit arising out of a non-empty set of vertices).
To do that, you can force the presence of an edge by sufficiently incentivizing its profit by adding an amount, say W, where |V| << W << INF (INF is infinite flow capacity in your flow graph). Then running the maxflow gives you the max-profit with that edge included (after subtracting W). If it is > -1, we have found a violation of property 2. Report this maximizing subset as a witness for violation of 2nd constraint. The subset construction was not straightforward (not every min cut suffices), i used some heuristic, not sure if it is correct.
You can run once for each edge. Including an edge translates to increasing the capacity of one edge in the flow graph. Since the structure of the flow network changes very little in varying the edge to be included, you can "unflow" from the previous max flow computation to remove the excess capacity of the previous edge, increase capacity for the new edge and resume the max-flow, instead of starting from scratch each time.