11446 - Where is the 'back' button?

[pradhanp]

If I understand the problem correctly, it is asking us to find the minimum number of edges to add, so that, in the resulting graph, every vertex belongs to a cycle. I am getting WA for the following algorithm. Could someone please provide a counter?

Let G be the given graph.
1) G' = transitive closure of G.
2) In G', delete all vertices which belong to cycles. G' is now a DAG.
3) Let c1 = number of vertices in G' with zero in-degree, c2=number of vertices in G' with zero out-degree. Since we need every vertex of G' to belong to a cycle, no vertex can have zero in-degree or out-degree. Hence, the answer is atleast max(c1, c2). However, we can add max(c1, c2) suitably chosen edges going from zero out-degree vertices to zero in-degree ones so that the resulting graph is strongly connected. Therefore, the minimum number of edges needed is exactly max(c1, c2).

[kelvin yang]

The algorithm you described is not exactly right for this problem.

In this problem the requirement is:
"every node can click one or more links and then return to itself"
so there are actually two requirements:
1) by clicking one or more links
2) return to the node itself

And the intention of your algorithm is to make every node reachable from every node, which is not what the problem asks for.

Consider cycles, and also consider isolated nodes.

Good luck!

[pradhanp]

The intention of my algorithm is not to make the graph strongly connected. I will try to clarify what I meant.

1) We might as well consider the graph G'(after making it a DAG, as described in my previous post). Is this correct?
2) Assuming that it is correct, we need to add atleast max(c1, c2) edges, since no vertex may have zero in-degree or zero out-degree. Hence, the answer is >= max(c1, c2). However, adding max(c1, c2) edges will be sufficient to even make the DAG strongly connected. If the DAG is strongly connected, then every vertex belongs to a cycle. This shows that answer is <= max(c1, c2). Therefore, the answer is equal to max(c1, c2).

Could you please point out what I am missing here?

[kelvin yang]

Mind that while you contract your graph into an DAG, you contracted the cycles into single vertices.
and if the contracted vertices happen to be the leaf/root of your DAG, you might requre less edges added than max(c1, c2).
(since the nodes in the cycle are actually already linked to itselfs)

[pradhanp]

I am deleting all the vertices which belong to a cycle. I am doing this on the transitive closure so that the connectivity of the other vertices is not affected.

[kelvin yang]

No......
I do understand your algorithm.

Sorry if I was too implicit.
What I meant is that for those nodes in the cycles, they don't necessary need additional links even if they are roots/leaves.
I already tried to emphasize that point and I think you should try reading the constraints more carefully.

[pradhanp]

That would be true if I was considering the DAG formed by the strongly connected components. That is not the DAG in picture. In this DAG, the only vertices that remain are those which did not belong to any cycle in the original graph. There is an edge from u to v, where u and v are two vertices in this DAG iff there was a path from u to v in the original graph. Again, the vertex set of this DAG is a subset of the vertex set of the original graph, and contains only those vertices(from the original graph) which did not belong to any cycle.

[pradhanp]

I am sorry. I misread your post.

What I meant is that for those nodes in the cycles, they don't necessary need additional links even if they are roots/leaves.

I don't understand that. If a vertex belongs to a cycle, then, its in-degree>=1 and out-degree>=1. Hence, if a vertex has zero in-degree(root), then, it needs atleast one incoming edge added to it. This tells us that the number of edges we add should be >= number of vertices with zero in-degree. A similar argument for leaves.

Mind that while you contract your graph into an DAG, you contracted the cycles into single vertices.
and if the contracted vertices happen to be the leaf/root of your DAG, you might requre less edges added than max(c1, c2).
(since the nodes in the cycle are actually already linked to itselfs)

Just to clarify, there are no contractions of vertices. Only deletions.

[sclo]

I think the idea of contraction is still correct. But you need to keep track of vertices of 2 types, those that already formed a loop, and those that don't. There is an obvious upper bound and lower bound of number of additional edges needed, but I can construct examples that actually requires the upper bound number of edges, so you need to have some algorithm to compute the minimum number you need to add.

[pradhanp]

Would the answer for the case P=1, L=0 be 0 or 1?

[sclo]

My guess would be 0, but I could be wrong. What I'm getting at is that isolated vertices can be treated separately anyway. Just try both and see which one works.

A more general question, for P=2 and L=2, and if we have edge (0,0) and (0,1). Is the solution 0, since you can never leave vertex 1, and vertex 0 already satisfies condition?

[pradhanp]

I finally managed to get my solution accepted. However, the accepted solution gives an output of 1 on the following input:

1
7 8
0 1
1 0
2 3
3 2
1 4
3 5
4 6
5 6

The correct answer should be 2, shouldn't it?

@Yang, could you please tell me the output of your code on this case.

[kelvin yang]

Yes, it should be 2.
and the output of my program is 2 for the testcase above.

I think maybe you forget to search on the root? dunno..

oh, and the answer to the question..

A more general question, for P=2 and L=2, and if we have edge (0,0) and (0,1). Is the solution 0, since you can never leave vertex 1, and vertex 0 already satisfies condition?

I think the requirement of the problem is to make sure "every node can get back to itself traversing one or more link"
so the output for the statement above should be 1.. (as far as I am concerned)

At least that's how I implement this problem and the code got AC anyway.

though at first I got very confused with the story as well
I suppose the author is trying to convey that we should make it possible for all workers to leave their homepage and then back, so that they wouldn't get too bored. :p

[sclo]

So what's the idea for the correct algorithm?

[kelvin yang]

I'll talk about my method here. Hope it would be of help.

-- spoiler --
/* those who wish to solve the problem themselves might not want to read ahead */

First we can limit our choice of link to only some nodes - Only those that are leaves/roots had to be considered.
This should be fairly easy to prove.
I'm talking about the SCC contracted graph here, and yes, even those leaves/roots that are originally a SCC had to be considered, too.

At this stage the problem is much like a set covering problem.
We choose some leaves and make sure every node could reach at least one of them.
(and choose some roots to make sure every node could be reached from them)
We should considered both roots and leaves as the covering set seperately, then yet again choose the larger one.

This is NP-complete(or am I wrong?) so I do a 2^n brute-force attempt. (where n is MAX(the number of leaves, the number of roots))

-- end of spoiler --