Issue in `HomomorphismDigraphsFinder` for restricted image

[MeikeWeiss]

I used the method SubdigraphsMonomorphisms for my algorithms and for this example:

G:=Digraph([ [ 5, 7, 8 ], [ 5, 6, 7 ], [ 4, 6, 8 ], [ 3, 6, 7, 8 ], [ 1, 2, 6, 7, 8 ], [ 2, 3, 4, 5, 7, 8 ], [ 1, 2, 4, 5, 6, 8 ], [ 1, 3, 4, 5, 6, 7 ] ]);
H:=Digraph([[2,3,4],[1,3,4],[1,2,4],[1,2,3,5,6,7],[4,6,7],[4,5,7],[4,5,6]]);

For this example SubdigraphsMonomorphisms(H,G) returns an empty list but MonomorphismsDigraphs(H,G) not. In my opinion this is a contradiction.

I debugged the code and I think the problem is in HomomorphismDigraphsFinder, because:

  HomomorphismDigraphsFinder(H,                   # domain
                                G,                   # range
                                fail,                # hook
                                [],                  # user_param
                                1,                   # max_results
                                HN,                  # hint (i.e. rank)
                                true,                # injective
                                [ 1, 3, 4, 5, 6, 7, 8 ], # image
                                [],                  # partial_map
                                fail,                # colors1
                                fail,                # colors2
                                DigraphWelshPowellOrder(H));

returns an empty list but

HomomorphismDigraphsFinder(H,                   # domain
                                G,                   # range
                                fail,                # hook
                                [],                  # user_param
                                1,                   # max_results
                                HN,                  # hint (i.e. rank)
                                true,                # injective
                                [2,3,4,5,6,7,8],     # image
                                [],                  # partial_map
                                fail,                # colors1
                                fail,                # colors2
                                DigraphWelshPowellOrder(H));

returns a transformation and the both given images lie in the same orbit under the automorphism group of G.

[james-d-mitchell]

Thanks for the report @MeikeWeiss, I agree this is a bug, and I can reproduce it, I'll see if I can fix it now.

[james-d-mitchell]

So interestingly it seems that without specifying the last argument, everything works ok.

HomomorphismDigraphsFinder(H,                   # domain
G,                   # range
fail,                # hook
[],                  # user_param
1,                   # max_results
fail,                  # hint (i.e. rank)
true,                # injective
[ 1, 3, 4, 5, 6, 7, 8 ], # image
[],                  # partial_map
fail,                # colors1
fail);

returns [ Transformation( [ 1, 5, 7, 8, 3, 4, 6, 8 ] ) ]

[james-d-mitchell]

Just for the record this is related to #111. The issue is related to some incorrect assumptions in the C code, if we try:

gap> H := DigraphFromGraph6String("F~CWw");;
gap> p := PermList(DigraphWelshPowellOrder(H)) ^ -1;
gap> H := OnDigraphs(H, p); # reorder H to remove the ordering from the equation
gap> G := DigraphFromGraph6String("G@p}|{");
gap> HomomorphismDigraphsFinder(H,      
> G,                      # range
> fail,                   # hook
> [],                     # user_param
> 1,                      # max_results
> fail,                   # hint (i.e. rank)
> true,                   # injective
> [1, 3, 4, 5, 6, 7, 8],  # <----- IMAGE
> [],                     # partial_map
> fail,                   # colors1
> fail);
[ ]

When there is a monomorphism from H to G with the specified image, for example:

 Transformation( [ 8, 1, 5, 7, 3, 4, 6, 8 ] )

is one such example. Just to note that if we do

gap> First(MonomorphismsDigraphs(H, G), x -> ImageSetOfTransformation(x) = [1, 3, 4, 5, 6, 7, 8]);
Transformation( [ 8, 1, 5, 7, 3, 4, 6, 6 ] )

so the homomorphism finding code works as expected in this case.

The issue is that 7 and 8 belong to the same orbit of the automorphism group of G and as such 7 is used
as the image of 1 (since it's an orbit rep), but 8 is not, and there is no monomorphism f from H to G with rank 7, $(1)f \neq 8$, and image [1, 3, 4, 5, 6, 7, 8], so nothing is returned.

If we do:

gap> H := DigraphFromGraph6String("F~CWw");;
gap> p := PermList(DigraphWelshPowellOrder(H)) ^ -1;
gap> H := OnDigraphs(H, p); # reorder H to remove the ordering from the equation
gap> G := DigraphFromGraph6String("G@p}|{");
gap> HomomorphismDigraphsFinder(H,      
> G,                     
> fail,                  
> [],                     
> 1,                      
> fail,                  
> true,                 
> [1, 3, 4, 5, 6, 7, 8],
> [8],                     # <---- EXPLICITLY SPECIFY THE FIRST VALUE
> fail,                   
> fail);
[ Transformation( [ 8, 1, 5, 7, 3, 4, 6, 8 ] ) ]

or

gap> H := DigraphFromGraph6String("F~CWw");;
gap> p := PermList(DigraphWelshPowellOrder(H)) ^ -1;
gap> H := OnDigraphs(H, p); # reorder H to remove the ordering from the equation
gap> G := DigraphFromGraph6String("G@p}|{");
gap> HomomorphismDigraphsFinder(H,      
> G,                      
> fail,                   
> [],                     
> 1,                      
> fail,                   
> true,                  
> [1, 3, 4, 5, 6, 7, 8],  
> [],                     
> fail,                   
> fail, 
> [1 .. 7], 
> Group(())); # <---- EXPLICITLY DISABLE USING THE AUT. GROUP
[ Transformation( [ 8, 1, 5, 7, 3, 4, 6, 8 ] ) ]

everything works as expected.

I'm not immediately sure how to resolve this properly. The proper fix would be if (as in the example above), we define the first value of the monomorphism to be 7, then we account for the fact that 7 and 8 belong to the same orbit (somehow, but not sure exactly how).

[james-d-mitchell]

After some thought and some discussion with @reiniscirpons, we decided that this isn't really a bug after all but rather a feature. However, given the amount of time it took the author of the code (me!) to figure this out we decided to do the following:

1. Document more clearly that HomomorphismDigraphsFinder with a specified image argument (that isn't the entire target digraph) might return unexpected results, and how to avoid this (pass the trivial automorphism group as last argument);
2. Print an info warning if HomomorphismDigraphsFinder is invoked with arguments that might lead to unexpected results (such as those in this issue).

We arrived at this position because HomomorphismDigraphsFinder can't effectively use the symmetries (automorphism group) of the target digraph when image is specified. It might be possible to update the function to somehow modify the specified image depending on which orbit representatives are chosen, but this would be rather difficult (conceptually, and even more so technically). Also it seems likely that doing this would also have more or less the same complexity as just not using symmetries (passing the trivial group as the final aut_grp argument).

The question then becomes "why not just force the trivial group as last argument when image is specified?". The reason we opted not to do this is: there are examples where HomomorphismDigraphsFinder can use the symmetries of the target digraph, and where the results are not unexpected (i.e. the sought homomorphisms are found). Using the trivial group in these examples rather than the automorphism group, leads to significantly worse performance (i.e. examples that currently take <500ms taking 10s of seconds or more). So we opted for the softest change which permits the old behaviour, but warns about the possibility of unexpected results.

We resolved your specific issue with MonomorphismsSubdigraphs @MeikeWeiss, by just passing the trivial group of automorphisms, so that all the homomorphisms are actually found. Does all of this sound ok to you @MeikeWeiss ?

[MeikeWeiss]

Sounds good to me. Thank you very much!