Pepe.Chess's blog

By Pepe.Chess, history, 9 years ago, In English

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

  • Vote: I like it
  • +5
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks all :) I appreciate it

  • »
    »
    9 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It is just a simple idea using Topological sort technique.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please verify it and give me feedback. if possible please provide me link as well.

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You have mentioned that the graph will be acyclic but this problem includes graph containing cycle even the second example in the sample contains two simple cycle. I think that we can modify my solution to find the answer.

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            actually i am not sure that your solution is right

            becuase each vertex can belong to more than one level

            anyway ... for this problem

            find strongly connected components of the graph ... so they form a DAG and then continue

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?