Блог пользователя Pepe.Chess

Автор Pepe.Chess, история, 9 лет назад, По-английски

Hello

I need Help please in this graph problem

I think you all know the minimum path cover problem in a DAG

You are given a DAG and you have to compose it into K paths so that every vertex must belong to exactly one path

So you have to find a solution where K is minimum

This can be solved by maximum matching.

But what if the vertex can belong to more than one path in the composition ???

For further understanding ... let's imagine this DAG

1->2

2->3

4->2

2->5

The standard covering will give us 3 as a result (1->2->3 , 4 , 5)

But in this version the answer would be 2 (1->2->3 , 4->2->5)

Does anyone have any idea?

Thanks in advance

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Seems like if we consider a transitive closure of given graph (let's call it G), with its fixed non-disjoint path-covering, we can obtain a disjoint path-covering of a transitive closure of a given graph (denote it ).

Indeed, let's fix some not vertex-disjoint path covering of G. We can build almost "the same" path covering of the : add next path until the first intersection by vertex appears. Obviously, we can prevent this intersection by going through one of the "transitive-closure edges" (if needed, maybe there are some cases when we can simply stop at the vertex before the intersection). This procedure covers by exactly the same number of paths, but this time vertex-disjointly.

In similar manner we can prove a reverse statement.

In sum, if I'm not mistaken, you can just find a vertex-disjoint path-covering of transitive closure.

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    I'm not sure if I'm following you entirely, but if you're saying that the size of the minimal vertex-disjoint path-covering of a DAG is the same as the minimal vertex-disjoint path-covering of its transitive closure, then I'm afraid you're wrong. Consider V = {0, 1, 2, 3, 4} and E = {(0, 2), (1, 2), (2, 3), (2, 4)}. To cover G = (V, E) you need at least three paths, but you can cover its transitive closure with 2 paths.

    That said, the general method to solve this problem still works, but you just need to forget about the transitive closure (just do the normal bipartite matching procedure on the graph itself, not its transitive closure).

    EDIT: to expand on that for the OP: note that when we cover the DAG with vertex-disjoint paths, each vertex has at most one incoming edge, and at most one outgoing edge. The number of paths is thus equal to the number of vertices with no incoming edges (or equivalently, the number of vertices with no outgoing edges). How can we model this as a bipartite matching problem?

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      I see a way to cover G by two paths: (0,2,3), (1,2,4). Remember that we're not talking about vertex-disjoint case, paths can intersect.

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        Read again:

        You are given a DAG and you have to compose it into K paths so that every vertex must belong to exactly one path

        Vertex 2 belongs to two paths, thus the cover is invalid.

        EDIT: Oh, nevermind, I can't read. Yea I guess you're right then, my bad.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

This might help

So you just have to add edges from every vertex v to every vertex which is reachable from v, and then use the algorithm you described first.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks all :) I appreciate it

  • »
    »
    9 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    I do have a simple algo put all the vertices in a set A (vertices are ordered by indegree) and do the following until set becomes empty.

    const int maxn = 1e5 + 20;
    vector<int> graph[maxn];
    int indegree[maxn];
    
    int ans = 0;
    int solve() {
      set<pair<int,int> > A;
      for(int i=1; i<=V; i++) {
        A.insert({indegree[i], i});
      }
      while(!A.empty()){
         vector<int> B;
         while(!A.empty() && A.begin()->first == 0){
            B.push_back(A.begin()->second);
            A.erase(A.Begin());
         }
         ans = max(ans, B.size());
         for(int I=0; I < B.size(); I++){
           for(int J=0; J < graph[B[I]].size(); J++){
             A.erase({indegree[graph[B[I]][J]],graph[B[I]][J]}) ;
             in degree[graph[B[I]][J]]--;
             A.insert({indegree[graph[B[I]][J]],graph[B[I]][J]});      
           }
         }
     }
     return ans;
    }
    

    This is very simple solution i am just checking what is the maximum number of nodes at a given level. and this is the answer.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm trying to solve the same problem on LOJ and finding the transitive closure seems to be really the way to go ... but with V=1000 and E = 10000 ... finding transitive closure in O(V^3) using floyd or O(VE+V^2) using DFS seems to not be able to pass

is there a faster to find the transitive closure or is there a different approach that should be used ?

Pepe.Chess if you solved it ... how did you do it eventually ?