Use the flow model to detect non permissible edges in the separator graph constructed in Exercise. Does it identify all non-permissible edges?
Exercise
Consider the graph with directed edges (1, 2),(1, 4),(1, 5),(2, 3), (2, 7), (3, 4), (3, 7), (3, 8),(4, 1),(4, 5),(5, 6),(6, 2),(6, 5), (7, 3), (8, 1), (8, 4) and the separator S = {1, 2, 3, 4}. Use Theorem 3.41 to filter as many edges as possible. Does this filter remove any edges that are not removed by vertex-degree filtering? Does it remove any that are not removed by alldiff filtering? Does it remove all nonhamiltonian edges connecting vertices of S?
Theorem 3.41
If S is a separator of directed graph G, then G contains a hamiltonian cycle only if GS contains a permissible hamiltonian cycle. Furthermore, an edge of G connecting vertices in S is hamiltonian only if it is part of a permissible hamiltonian cycle of GS.