# Equal end-partitioning of acyclic graph

This topic is 3983 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Alright, so I'm all thinked out, and all googled out, and still haven't gotten anywhere. Here's the deal. Consider an undirected, acyclic graph G = {V,E}. Of the vertices V, there is a set V' ⊂ V of "marked" vertices. (as a potential simplifying assumption, the problem can be reworked such that all elements of V' have degree 1.) The problem: to find an edge e ∈ E such that there are as equal as possible a number of marked vertices on each side of the edge; that is, if e were deleted from the graph, the two resultant components would have as close to the same number of marked vertices as possible. I just know there has to be a graph traversal/dynamic programming solution, but for the life of me I cannot think of one which is more efficient than the brute force approach of iterating through all edges and counting the marked vertices on either side.

##### Share on other sites
Wow, I cannot believe I did not see that before. Alright, simple traversal-based solution. Probably not useful or interesting to anybody other than myself, but let me know if you need it.

##### Share on other sites
Yeah, it seems to me like you could just pick a random vertex and recurse down to the leafs, counting "special" vertices as you go and storing that information at each vertex/edge. Then you'd have enough information to pick the best edge on the unroll.

##### Share on other sites
uh i have absolutely no idea what are you talking about but im wondering if it worthy googling it and understanding it?

##### Share on other sites
I wouldn't bother for this particular problem. If you're not familiar with the graph theory terms I've used, though, I'd say you should most certainly spend time getting to know them. They are crucial to being a useful programmer.

1. 1
2. 2
Rutin
17
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633735
• Total Posts
3013594
×