We have a set of n nodes. From each node, we can place one outgoing edge. The goal is to place them in an optimal way.
Associated with each node is a set S of k elements. If there is an edge from x to y, we can "cross out" all elements in S(x) which are also in S(y). That applies even if those elements are also crossed out.
The goal is to minimise the number of elements which are not crossed out. However, if there is a cycle, those elements which are present in all the nodes in the cycle (and therefore crossed out in all of them) must still be counted once.
How should the edges be chosen? Is there a polynomialtime solution?
My first thought was that the optimal solution should not contain any cycles. Then each pair of nodes would have a potential weight of how many things they have in common, and we could use Kruskal's algorithm. But it turns out sometimes the optimal solution does have cycles, so that doesn't work. My latest idea is an algorithm which basically branches whenever it finds a potential cycle; I'm pretty sure it finds an optimal solution, but it's not guaranteed to be polynomial, and in fact seems to be quite slow in the typical case.
Any ideas?
Looking for a graph algorithm
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 8
 Joined: Fri Feb 10, 2012 6:07 am UTC
Re: Looking for a graph algorithm
When you say "From each node, we can place one outgoing edge," do you mean that each node must have an outgoing edge? If so, then any solution you create will necessarily have a cycle. Even if it's not mandatory, I can't see how adding an outgoing edge to a vertex that doesn't have one would ever increase the number of elements not crossed out, since the new edge would create at most one cycle.
If you don't have the "elements which are present in all the nodes in the cycle (and therefore crossed out in all of them) must still be counted once" condition, then this puzzle is rather easy once you weight each edge by the number of elements that are unique in the adjoining vertices (exercise for the reader). With that condition, however, my best idea is a greedy algorithm, i.e. pick the lowestweight edge u>v, update the graph to remove all other edges leading out from u and change edge weights to account for creating cycles, and iterate. I don't know if that's optimal, though.
If you don't have the "elements which are present in all the nodes in the cycle (and therefore crossed out in all of them) must still be counted once" condition, then this puzzle is rather easy once you weight each edge by the number of elements that are unique in the adjoining vertices (exercise for the reader). With that condition, however, my best idea is a greedy algorithm, i.e. pick the lowestweight edge u>v, update the graph to remove all other edges leading out from u and change edge weights to account for creating cycles, and iterate. I don't know if that's optimal, though.
Re: Looking for a graph algorithm
This is what I thought at first, but it's a directed graph, and presumably he's only talking about directed cycles.SeaCalMaster wrote:When you say "From each node, we can place one outgoing edge," do you mean that each node must have an outgoing edge? If so, then any solution you create will necessarily have a cycle. Even if it's not mandatory, I can't see how adding an outgoing edge to a vertex that doesn't have one would ever increase the number of elements not crossed out, since the new edge would create at most one cycle.
If the special "cycle behavior" happens for an undirected cycle in the selected subgraph, I believe I can prove that the corresponding decision problem (i.e. "Is there a solution that crosses out suchandsuch a number of elements") is NPcomplete (by reduction from the Hamiltonian cycle problem). But I don't think that's how it's supposed to work.

 Posts: 8
 Joined: Fri Feb 10, 2012 6:07 am UTC
Re: Looking for a graph algorithm
++$_ wrote:This is what I thought at first, but it's a directed graph, and presumably he's only talking about directed cycles.SeaCalMaster wrote:When you say "From each node, we can place one outgoing edge," do you mean that each node must have an outgoing edge? If so, then any solution you create will necessarily have a cycle. Even if it's not mandatory, I can't see how adding an outgoing edge to a vertex that doesn't have one would ever increase the number of elements not crossed out, since the new edge would create at most one cycle.
... Right, but it doesn't make a difference. Would you like the proof?
Spoiler:
Re: Looking for a graph algorithm
Oh, right, you are limited to one outgoing edge per vertex. So you're right, there is always a cycle if you include the full number of edges.
In that case, I'm pretty sure the problem is NPcomplete (whether or not including the full number of edges is mandatory).
Proof: Let G be a digraph on {1, ..., n} and let S(i) be {1, ..., i1, i+1, ..., n}. Any edge allows you to cross out n1 elements. For any cycle you have to put back some elements, except for a Hamiltonian cycle. Also, if we have n edges in total, then there must be a cycle somewhere, as you just showed above. Therefore, a Hamiltonian cycle exists in G if and only if there is a way to select the edges so that n(n1) elements are crossed out in total. Thus a polynomialtime algorithm for this problem allows you to the Hamiltonian cycle problem in polynomial time.
In that case, I'm pretty sure the problem is NPcomplete (whether or not including the full number of edges is mandatory).
Proof: Let G be a digraph on {1, ..., n} and let S(i) be {1, ..., i1, i+1, ..., n}. Any edge allows you to cross out n1 elements. For any cycle you have to put back some elements, except for a Hamiltonian cycle. Also, if we have n edges in total, then there must be a cycle somewhere, as you just showed above. Therefore, a Hamiltonian cycle exists in G if and only if there is a way to select the edges so that n(n1) elements are crossed out in total. Thus a polynomialtime algorithm for this problem allows you to the Hamiltonian cycle problem in polynomial time.
Re: Looking for a graph algorithm
It is technically not necessary to have an edge from each node, but adding an edge can never make anything worse, so there must be an optimal solution with an edge from every node. And that solution must therefore have a cycle, as you say.
I don't see how there can be any cycles which are not directed. Surely that would require one of the nodes to have two outgoing edges?
SeaCalMaster, I don't think your greedy algorithm is optimal. It might be tricked into adding an edge which will later turn out to lead to a cycle.
++$_, that proof looks promising. I'll have to think about it some more.
Although since each set has n1 elements, I think each edge would allow you to cross out n2, right? So the hamiltonian cycle gives n(n2) crossed out elements.
I don't see how there can be any cycles which are not directed. Surely that would require one of the nodes to have two outgoing edges?
SeaCalMaster, I don't think your greedy algorithm is optimal. It might be tricked into adding an edge which will later turn out to lead to a cycle.
++$_, that proof looks promising. I'll have to think about it some more.
Although since each set has n1 elements, I think each edge would allow you to cross out n2, right? So the hamiltonian cycle gives n(n2) crossed out elements.
Re: Looking for a graph algorithm
Uh, yeah, that's right. Whoops.DrZiro wrote:++$_, that proof looks promising. I'll have to think about it some more.
Although since each set has n1 elements, I think each edge would allow you to cross out n2, right? So the hamiltonian cycle gives n(n2) crossed out elements.
Re: Looking for a graph algorithm
When I looked at it before, it looked good, but now when I look at it again, I can't make any sense of it.
You can place edges anywhere you like, so with your setup, you could always make a hamiltonian cycle anywhere you like, couldn't you?
You can place edges anywhere you like, so with your setup, you could always make a hamiltonian cycle anywhere you like, couldn't you?
Re: Looking for a graph algorithm
Oh, I see. I guess I misunderstood the problem. I thought you were required to select the edges from some preexisting digraph, but I guess that's a more general problem than you wanted to solve. You're just asking about the case where G is complete.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Looking for a graph algorithm
Rambling attack on it. While it ends with a solution, it doesn't start with one:
Let G be a general graph. Our goal is to build a pseudograph G' so that minimizing this problem on G' is equivalent to solving a hard problem on G.
The pseudograph structure is a set of nodes, each one of which has a "set of things to cross out". For each node in our pseudograph, we can pick another node in the pseudograph and we "get to count" everything that we share.
An obvious thing to try is to set the nodes in the pseudograph to be exactly the nodes in G, and the things to cross out to be the nodes against to the node in G, plus ourselves. Then note that a Hamiltonian path in our original graph will, when turned into edges in our pseudograph, cross out everything.
This doesn't quite work, because two nodes adjacent to us end up being able to mutually cross us out, so we lack the important onlyif.
A way to start to solve this is to add in punishment for trying to do this. For each edge E in the original graph, build a punishment set that is large (as in, G^2) and contains unique elements. Augment each of the corresponding nodes in G' with that punishment set in the crossout list. This punishment should prevent any path in G' that isn't a path in G from being minimal. And as each such connection crosses out exactly the same number of nodes, it won't otherwise interfere with the optimal solution.
Hmm, that might be enough  that punishment technique lets you restrict the allowed edges to any set you want (increasing the punishment size to G^4 to make sure that it dominates). We then apply ++$_'s solution, and QED. Sound good?
Let G be a general graph. Our goal is to build a pseudograph G' so that minimizing this problem on G' is equivalent to solving a hard problem on G.
The pseudograph structure is a set of nodes, each one of which has a "set of things to cross out". For each node in our pseudograph, we can pick another node in the pseudograph and we "get to count" everything that we share.
An obvious thing to try is to set the nodes in the pseudograph to be exactly the nodes in G, and the things to cross out to be the nodes against to the node in G, plus ourselves. Then note that a Hamiltonian path in our original graph will, when turned into edges in our pseudograph, cross out everything.
This doesn't quite work, because two nodes adjacent to us end up being able to mutually cross us out, so we lack the important onlyif.
A way to start to solve this is to add in punishment for trying to do this. For each edge E in the original graph, build a punishment set that is large (as in, G^2) and contains unique elements. Augment each of the corresponding nodes in G' with that punishment set in the crossout list. This punishment should prevent any path in G' that isn't a path in G from being minimal. And as each such connection crosses out exactly the same number of nodes, it won't otherwise interfere with the optimal solution.
Hmm, that might be enough  that punishment technique lets you restrict the allowed edges to any set you want (increasing the punishment size to G^4 to make sure that it dominates). We then apply ++$_'s solution, and QED. Sound good?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Looking for a graph algorithm
That looks good to me. If G has a Hamiltonian cycle, and G has more than 2 vertices, then we get to find a solution to DrZiro's problem on G' that crosses out Pn + n(n2) elements, where P is the size of the punishment sets. If G has no Hamiltonian cycle, then we can't.
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Looking for a graph algorithm
So, conclusion:
The problem DrZiro described is NPhard (... and in NP unless I missed something), and NPcomplete. There is no reasonable possibility that you'd find an efficient algorithm for the general case.
To find an efficient algorithm you'll have to focus on ways in which your actual problem is more restricted than the general case, and/or aim to accept "approximations" of ideal instead of actually ideal solutions.
Is being very close to ideal good enough? Is there any bound on the number of "cross out" elements associated? Is there any pattern in how the "cross out" elements are distributed?
The problem DrZiro described is NPhard (... and in NP unless I missed something), and NPcomplete. There is no reasonable possibility that you'd find an efficient algorithm for the general case.
To find an efficient algorithm you'll have to focus on ways in which your actual problem is more restricted than the general case, and/or aim to accept "approximations" of ideal instead of actually ideal solutions.
Is being very close to ideal good enough? Is there any bound on the number of "cross out" elements associated? Is there any pattern in how the "cross out" elements are distributed?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Who is online
Users browsing this forum: No registered users and 4 guests