minimum collection of vertice disjoint path that covers a given vertice set

Question

Problem

Given:

• A directed graph G
• A source vertex s in G and a target vertex t in G
• A set S of vertices of G

I want to find a collection of paths from s to t that covers S.

Then I want to partition the collection of paths into subcollections of vertex-disjoint paths.

Under these constraints, the objective is to minimise the number of subcollections.

Example

For instance, [C1 = {p1,p2,p3}, C2= {p4,p5}, C3= {p6,p7}] is a solution if:

• each p_i is a path from s to t
• p1,p2,p3 have no vertices in common except s and t;
• p4, p5 have no vertices in common except s and t;
• p6,p7 have no vertices in common except s and t;
• collectively, the 7 paths cover all vertices of S.

In that case, the number of subcollections is 3.

Question

What are some good algorithms or heuristics for this optimisation problem?

I already know min cost flow, and disjoint path algos, but they don't apply in my settings.

I tried min cost flow / node disjoint paths but one run only gives one collection at a time. I don't know how to adjust cost to cover the unexplored vertices.

Answer 1

Given:

A directed graph G

A source vertex s in G and a target vertex t in G

A set S of vertices of G

I want to find a collection of paths from s to t that covers S.

• Use Dijkstra's algorithm to find a path from s to every vertex in S and from every point in S to t.

• Connect the paths to and from each S vertex into one path from s to t via a point in S.

You now have a collection of paths that, together, cover S. Let's call it CS.

Then I want to partition the collection of paths into subcollections of vertex-disjoint paths.

Note that if s, the source vertex, has an out degree of sOD, there can be no more than sOD paths in each vertex disjoint collection.

• Construct vVDP, an empty vector of vertex disjoint path collections
• LOOP P over paths in CS
  • SET found FALSE
  • LOOP cs over collections in vVDP
    • IF P is vertex disjoint with every path in cs
      • add P to cs
      • SET found TRUE
      • BREAK out of LOOP cs
  • IF found == false ADD collection containing P to vVDP

Here is a C++ implementation of this algorithm

void cProblem::collect()
{
    // loop over paths
    for (auto &P : vpath)
    {
        // loop over collections
        bool found = false;
        for (auto &cs : vVDP)
        {
            //loop over paths in collection
            bool disjoint;
            for (auto &csPath : cs)
            {
                // check that P is vertex disjoint with path in collection

                disjoint = true;
                for (auto vc : csPath)
                {
                    for (auto &vp : P)
                    {
                        if (vp == vc) {
                            disjoint = false;
                            break;
                        }
                    }
                }
                if( ! disjoint )
                    break;
            }

            if (disjoint)
            {
                // P is vertex disjoint from every path in collection
                // add P to the collection

                cs.push_back(P);
                found = true;
                break;
            }
        }
        if (!found)
        {
            // P was NOT vertex disjoint with the paths in any collection
            // start a new collection with P

            std::vector<std::vector<int>> collection;
            collection.push_back(P);
            vVDP.push_back(collection);
        }
    }
}

The complete application is at https://github.com/JamesBremner/so75419067

Detailed documentation id the required input file format at https://github.com/JamesBremner/so75419067/wiki

If you post a real example in the correct format, I will run the algorithm on it for you.