algorithmgraphdepth-first-searchdisjoint-setscyclic-graph

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


Problem

Given:

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:

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.


Solution

  • 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.

    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.

    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.