Looking for a graph algorithm

[DrZiro]

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 polynomial-time 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?

[SeaCalMaster]

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 lowest-weight 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.

[++$_]

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.

This is what I thought at first, but it's a directed graph, and presumably he's only talking about directed cycles.

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 such-and-such a number of elements") is NP-complete (by reduction from the Hamiltonian cycle problem). But I don't think that's how it's supposed to work.

[SeaCalMaster]

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.

This is what I thought at first, but it's a directed graph, and presumably he's only talking about directed cycles.

... Right, but it doesn't make a difference. Would you like the proof?

Spoiler:

Create a list of (not necessarily distinct) vertices as follows: Choose an arbitrary vertex v_0. Then, for each k \geq 0, v_{k+1} is the vertex obtained by following the outgoing edge from v_k. Since each vertex contains an outgoing edge, this list can be arbitrarily long. Specifically, for a graph with n vertices, we can construct such a list of size n+1. By the pigeonhole principle, some vertex v must appear in the list at least twice; therefore, there exists a path from v to itself, and so the graph contains a cycle.

[++$_]

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 NP-complete (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, ..., i-1, i+1, ..., n}. Any edge allows you to cross out n-1 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(n-1) elements are crossed out in total. Thus a polynomial-time algorithm for this problem allows you to the Hamiltonian cycle problem in polynomial time.

[DrZiro]

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 n-1 elements, I think each edge would allow you to cross out n-2, right? So the hamiltonian cycle gives n(n-2) crossed out elements.

[++$_]

++$_, that proof looks promising. I'll have to think about it some more.
Although since each set has n-1 elements, I think each edge would allow you to cross out n-2, right? So the hamiltonian cycle gives n(n-2) crossed out elements.

Uh, yeah, that's right. Whoops.

[DrZiro]

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?

[++$_]

Oh, I see. I guess I misunderstood the problem. I thought you were required to select the edges from some pre-existing 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]

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 pseudo-graph G' so that minimizing this problem on G' is equivalent to solving a hard problem on G.

The pseudo-graph structure is a set of nodes, each one of which has a "set of things to cross out". For each node in our pseudo-graph, we can pick another node in the pseudo-graph and we "get to count" everything that we share.

An obvious thing to try is to set the nodes in the pseudo-graph 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 pseudo-graph, 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 only-if.

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 cross-out 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?

[++$_]

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(n-2) elements, where P is the size of the punishment sets. If G has no Hamiltonian cycle, then we can't.

[Yakk]

So, conclusion:
The problem DrZiro described is NP-hard (... and in NP unless I missed something), and NP-complete. 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?