5
$\begingroup$

Take grid graph as an example.

g = GridGraph[{6, 9}, VertexLabels -> Automatic]
pairs = {{6, 44}, {54, 33}, {35, 13}, {41, 8}, {14, 26}, {20, 32}};

enter image description here

For each vertex pair, try to find a simple path (no need to be shortest), so that all 6 paths meet both conditions:

1) each connects vertex 6 and 44, vertex 54 and 33, ..., respectively.

2) they are all independent, they do not have any vertex in common.

The paths in question need not to be the shortest nor covering all vertices.

One possible sln is:

enter image description here

It's better to get a general solution for any graph and any set of vertex pairs.

With a general solution, one can:

1) For a given graph and vertex pairs, solve the total number of slns (0 for no solution), the sln with minimum/maxmum vertices covering...

2) For a given graph, how many vertex pairs at least are needed to cover all vertices?

3) What if the end vertex in each pair is unknown but to find the paths covering all vertices?

I'm wondering if there are some typical concepts/discussions behind this kind of question in graph theory. It seems to split the graph into independent parts.

Any thought or keyword suggestion would be appreciated.

$\endgroup$
5
  • $\begingroup$ There are not 6 such independent paths starting from vertex 6 because this vertex has degree 2. You can find a path that starts with 6-12, one that starts with 6-5, but all the other paths must intersect with one of these two. None of the highlighted vertices have degree greater than 4, so it is not possible to have 6 independent paths starting from them. $\endgroup$ – Szabolcs Jun 8 '20 at 7:22
  • 1
    $\begingroup$ @Szabolcs thank you for your time. one possible sln is added to clarify the question $\endgroup$ – bigheadghost Jun 8 '20 at 8:04
  • $\begingroup$ I see, so you want one shortest path for each of those pairs, but in such a way as to cover all vertices. $\endgroup$ – Szabolcs Jun 8 '20 at 8:05
  • 1
    $\begingroup$ @Szabolcs Yes, one simple path for each of those pairs, but dont have to be the shortest. And covering all vertices (condition 3) can also be omitted. $\endgroup$ – bigheadghost Jun 8 '20 at 8:19
  • 1
    $\begingroup$ Are you looking for a general solution that will work for any graph, and any set of vertex pairs, and will be able to detect when a solution does not exist? $\endgroup$ – Szabolcs Jun 8 '20 at 10:09
3
$\begingroup$
pairs = {{6, 44}, {54, 33}, {35, 13}, {41, 8}, {14, 26}, {20, 32}};
vs = {"Triangle", "Square", "Star", "Rectangle", "Pentagon",  "Diamond"};
vshapes = Thread[Append[Flatten@pairs, Blank[]] -> Append[Riffle[vs, vs], Automatic]];

g = GridGraph[{6, 9}, VertexLabels -> Automatic, ImageSize -> Large, 
  VertexSize -> {Alternatives @@ Flatten[pairs] -> Large}, 
  VertexShapeFunction -> {v_ :> (v /. vshapes)}, 
  VertexStyle -> {Alternatives @@ Flatten[pairs] -> Yellow}]

enter image description here

For each pair {a,b} in pairs (1) we delete the nodes in g that belong to the complement of {a,b} in pairs, (2) find all shortest paths from a to b and (3) discard the paths that, if deleted from g, would make some pair in pairs disconnected. For a pair that does not have such a path in the first round, we repeat the process deleting the vertices that belong to the paths already found.

ClearAll[keep, indepPaths]
keep[g_, prs_][pth_] := Max[GraphDistance[
      VertexDelete[g, Union[Complement[Flatten[prs], {##}], pth]], ##] & @@@ 
    DeleteCases[prs, pth[[{1, -1}]]]] < Infinity

indepPaths[g_, prs_, u_: {}] := Module[{vd = VertexDelete[g,
       Complement[Union[u, Flatten[prs]], {##}]]}, 
    Select[keep[g, prs]]@ FindPath[vd, ##, {GraphDistance[vd, ##]}, All]] &;

For the example in OP, we find single paths for 4 of the pairs and no paths for two pairs in the first round:

as1 = Association[{##} -> indepPaths[g, pairs][##] & @@@ pairs]
 <|{6, 44} -> {{6, 12, 18, 24, 30, 36, 42, 48, 47, 46, 45, 44}}, 
{54, 33} -> {}, 
{35, 13} -> {}, 
{41, 8} -> {{41, 40, 34, 28, 22, 16, 10, 9, 8}}, 
{14, 26} -> {{14, 15, 21, 27, 26}}, 
{20, 32} -> {{20, 19, 25, 31, 32}}|>

In the second round the paths connecting the two pairs are found:

as2 = Association[{##} -> indepPaths[g, pairs, Flatten@Values@as1][##] & @@@ 
    Select[indepPaths[g, pairs][##] & @@ # == {} &][pairs]]
 <|{54, 33} -> {{54, 53, 52, 51, 50, 49, 43, 37, 38, 39, 33}},
 {35, 13} -> {{35, 29, 23, 17, 11, 5, 4, 3, 2, 1, 7, 13}}|>
as12 = Map[First]@Join[as1, as2]
 <|{6, 44} -> {6, 12, 18, 24, 30, 36, 42, 48, 47, 46, 45, 44}, 
 {54, 33} -> {54, 53, 52, 51, 50, 49, 43, 37, 38, 39, 33}, 
 {35, 13} -> {35, 29, 23, 17, 11, 5, 4, 3, 2, 1, 7, 13}, 
 {41, 8} -> {41, 40, 34, 28, 22, 16, 10, 9, 8}, 
 {14, 26} -> {14, 15, 21, 27,  26},
 {20, 32} -> {20, 19, 25, 31, 32}|>
HighlightGraph[g, Style[PathGraph[ as12@#], AbsoluteThickness[5]] & /@ pairs]

enter image description here

There may be multiple paths for a given pair in a given round. In that case, we need to consider all combinations of disjoint paths for the second round processing.

$\endgroup$
2
  • 1
    $\begingroup$ Ingenious pruning tech. 1) The indepPaths function uses shortest path, there would be more alternative paths in as1 with longer lengths. 2) When no paths pairs (i.e. {54, 33} and {35, 13} in question) appear, as2 searches down. How about searching up as of 1) ? 3) How to find exactly all the slns? $\endgroup$ – bigheadghost Jun 8 '20 at 15:20
  • $\begingroup$ @bigheadghost, great points. Perhaps we can change {GraphDistance[vd, ##]} to a range (that is, {0, k}+GraphDistance[vd, ##]), iterate over k until we get a non-empty path list for every pair, and select a pairwise-disjoint combination from Values@as1. $\endgroup$ – kglr Jun 8 '20 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.