Technical Report 2018-001

Redundancy eliminations for a polynomial solution of
the graph Hamiltonicity problem

Nikolay Mirenkov
July 4, 2018

Office for Planning and Management
The University of Aizu
Tsuruga, Ikki-machi, Aizu-Wakamatsu City
Fukushima 965-8580, Japan

Technical Report 2018-001
Title: Redundancy eliminations for a polynomial solution of the graph

Hamiltonicity problem

Author: Nikolay Mirenkov

Keywords and phrases: regional redundancy, redundancy with a remote impact,regional invariant, symbolic parameter system, Hamiltonicity polynomial solution,
P=NP.

A regional invariant method based on redundancy eliminations is presented for apolynomial solution of the graph Hamiltonicity problem. This method includes
searching logarithmic size regions, considering all possible partial solutions (ppsolutions) within corresponding regions and removing redundant pp-solutions. The
pp-solutions preserved are employed for extracting edge value invariants in theregions and composing a system of linear algebraic equations which is solved by astandard method applied for systems with symbolic parameters. Within the method,
regional redundancy and redundancy with remote impact eliminations are applied inorder to split the problem into a polynomial number of tractable subproblems.
Report Date:

Written Language:

3/9/2018

EnglishAny Other Identifying Information of this Report: to submit to a journal
Distribution Statement: First Issue: 10 copies
Supplementary Notes: abbreviations used in the report: pp-solution - possible partial
solutions; B-edge – boundary edge, B-case – boundary case, B-communicator –boundary communicator, n-invariant – node invariant, r-invariant – regional invariant, RRI redundancy related index, RUC - region under consideration, NR – neighboring region, RE –redundancy elimination, BR – basic region, TCs - tree chains

Active Knowledge Engineering Laboratory
The University of Aizu
Aizu-Wakamatsu
Fukushima 965-8580
Japan

2

Redundancy eliminations for a polynomial solution of thegraph Hamiltonicity problem
Nikolay Mirenkov
nikmirenkov@gmail.com
Abstract. A regional invariant method based on redundancy eliminations is presented for thepolynomial solution of the graph Hamiltonicity problem. This method includes searchinglogarithmic size regions, considering all possible partial solutions (pp-solutions) withincorresponding regions and removing redundant pp-solutions. The pp-solutions preserved are
employed for extracting edge value invariants in the regions and composing a system of
linear algebraic equations which is solved by a standard method applied for systems withsymbolic parameters. Within the method, regional redundancy and redundancy with remote
impact eliminations are applied in order to split the problem into a polynomial number oftractable subproblems.
Keywords and phrases: regional redundancy, redundancy with a remote impact, regional
invariant, symbolic parameter system, Hamiltonicity polynomial solution, P=NP.

1. Preliminary considerations
One of the main ideas behind the approach is the regional existence ofpossible partial solutions (pp-solutions) that can be removed without altering
Hamiltonicity. Another idea is the regional existence of invariants which are
represented by values of some edges in regions and do not include values ofedges from the “external world” (though for discovering such invariants,
values of edges from the external world can be employed). The invariants are
extracted within eliminating the redundant pp-solutions and within splitting the
pp-solution sets across all regions. The efficiency of this process is based on
reducing the problem to a polynomial number of the subproblems that are
related to different slices of pp-solutions and solved as the systems of linear
algebraic equations. To demonstrate this approach, we select the
Hamiltonicity problem on a planar graph G = G (V, E), where V is a set ofnodes and E is a set of edges. It is assumed that the graph is undirected withno weighted edges. It is also assumed that the number of nodes is N, thenumber of edges is M and the node degree is 3. The problem of searching a
Hamiltonian cycle in such a graph is still NP-complete [1]. Our goal is topresent a polynomial algorithm for finding a Hamiltonian cycle or to show thegraph is non-Hamiltonian.
For simplicity, we assume that the graph is 3-edge connected (otherwise, our initialproblem is reduced to problems of smaller sizes). In addition, nodes of 3-degree
faces are replaced by one node [2] and the problem is reduced to a graph with asmaller number of nodes. In any case, we expect that the graph is big enough.

Two symbolic parameters H and F are introduced to represent values ofedges: E1 = H means that edge E1 belongs to a Hamiltonian cycle and E2 = F
means that edge E2 does not belong to a Hamiltonian cycle (Failed to be a3

part of a cycle). For edges E1, E2 and E3 incident to a common node, we canwrite a node invariant (n-invariant) as the following equation:
E1 + E2 + E3 = 2H + F,

(1.1)

representing a necessary (for the graph Hamiltonicity) feature in this node.
This equation has to be valid in all nodes.
In a sense, H and F represents “yes” and “no” (1 and 0), but with different“units of measure.” For such parameters, symbolic expression
E4 + E5 + E6 + E7 + E8 = 5H
means that all Ei (i=4, …, 8) are equal to H, expression E1 = 2H – z1 is valid
only if z1 = H and expressions E1 = (H + F)/2 or E1 = 2H - F are just invalid. H
and F are convenient for reasoning about the symbolic expressions of edge
values.
Edges of a cut-set separating a subgraph (region) from other parts of thegraph are called boundary (B-) edges of a B-set. A set of B-edge values iscalled a B-set value. The B-edges are arranged in a set of pairs each ofwhich represents an in-out link related to a Hamiltonian cycle path going
through the region. Paths of different pairs are not intersected and jointly
cover all regional nodes.
This set of B-edge pairs (corresponding to their in-out links) is called a Bcommunicator. For a B-set value, there can be a number of different Bcommunicators. Together a B-set value and a corresponding B-communicator
are called a B-case. In other words, the number of B-cases with the same Bset value is equal to the number of different B-communicators.
Fig.1 depicts examples of B-edges, B-set values, in-out link sets and B-cases:-

B1, B2, B3, and B4 are B-edges in all examples;Fig. 1. Examples related to region boundary edges

4-(H,H,H,H) is a B-set value in examples g1 and g2; (H,H,F,F) is a B-set
value in examples g3 and g4;-{(B1, B4), (B2, B3)} is a B-communicator in example g1, {(B1, B2), (B3, B4)}
is a B-communicator in example g2. In other words, examples g1 and g2
present two different B-cases for the same B-set value.

-

Finally, {(B1, B2)} is a B-communicator (of one in-out link) in example g3; itis also a B-communicator in example g4. The coincidence of the Bcommunicators means that example g3 and g4 present one B-case andany of two different paths inside the region is allowed to be used.

A linear algebraic equation related to some region edges (forexample, Ei + Ej + Ek = 2H + F, Ei + Ej = H + F, Ei = H or Ei - Ej = 0) which isvalid for all possible B-cases is called a regional invariant.
Such invariants are extracted in logarithmic-size regions where the numbersof region B-edges and the number of interior faces are ≤ c×log2N (c is a predefined constant). In order to solve a Hamiltonicity problem, we need N/2
regional invariants (r-invariants), which have to be independent of ninvariants (1.1). In order to check independence, we can calculate the rank ofa corresponding matrix.
R-invariants together with the n-invariants allow
composing a system of M linear algebraic equations (M is the edge number),which is solved by a standard method (Gaussian elimination) applied forsymbolic parameter systems [3]. Absence of an appropriate solution meansthat the graph is non-Hamiltonian.
In the next sections, we consider ideas behind our approach: how to apply asystem of linear algebraic equations with symbolic parameters for discovering
pp-solutions, what redundant pp-solutions are and how to extract r-invariants.
Special attention is paid to regional redundancy and redundancy with aremote impact, as well as, covering the graph with a tree of region chains andcreating a set of the subproblems based on splitting the pp-solutions acrossall regions.

2. Valid pp-solutions and redundancy eliminations
Our eliminations are based on redundancies: they are regional pp-

solutions (or chains of pp-solutions in chains of regions) thatcan be removed without altering the graph Hamiltonicity.
5In order to apply the redundancy eliminations, first we have to find all valid(feasible) pp-solutions in the region under consideration.

A pp-solution is defined as a B-communicator set of
Hamiltonian non-intersected paths covering jointly all
regional nodes, satisfying n-invariants (1.1) in each nodeand excluding internal cycles of H-valued edges in the region.
This definition implicitly includes another necessary condition of Hamiltonicity
which should be applied for feasible pp-solutions:

For any region the symbolic expression of the sum of B-edges(related to any Hamiltonian solution) has to include an evennumber of H and this number should be ≥ 2.
For each B-set value, its own set of the feasible pp-solutions is discovered.
These pp-solutions are divided into clusters of equivalent B-communicators

possessing the same set of B-edge pairs. Redundancy elimination isapplied to these clusters; it preserves only one representative pp-solution
from each cluster of the feasible pp-solutions. In other words, the sum ofdifferent B-cases of each B-set value defines the number of pp-solutions left
in corresponding regions for extracting the r-invariants. The pp-solutions
eliminated in such a way are called redundant pp-solutions.
Here we consider examples to clarify some aspects of the feasible ppsolutions and redundancy eliminations.
Discovering feasible pp-solutions is based on composing a system of theequations and solving it. Assume that graph G of Fig. 2 is divided in two
regions by edges of a cut-set, which is behind the C-D-H-face path.
Then for the left region edges of G, we can write the following equations of the(1.1) type:
E1 + E2 + E3 = 2H + F
E3 + E7 + E22 = 2H + F
E2 + E4 + E5 = 2H + F
E6 + E7 + E12 = 2H + F(2.1)
E4 + E9 + E10= 2H + F
E8 + E9 + E13 = 2H + F
E5 + E6 + E8 = 2H + F
E1 + E10 +E14 = 2H + F,

6

Fig. 2. A cut-set line dividing graph G into two regions

where the right column of the equations is related to the B-set values (valuesof E22, E12, E13, and E14). Since we consider the system of the equations foreach possible B-set value (that is for assigned values of E22, E12, E13, andE14), then there are ten unknowns in eight equations. To decrease thenumber of B-cases to consider, we take into account that B-edge values,
making a contribution in such a B-set value, satisfy the above mentioned
condition of Hamiltonicity:
E22 + E12 + E13 + E14 = 2H + 2F or
E22 + E12 + E13 + E14 = 4H.
(2.2)
As an example, let E22 = E12 = F and E13 = E14 = H. Solving system (2.1) gives
us a solution for eight edges depending on H, F and two symbolic parameters
E2 and E5:
E1 = H+F- E2, E3 = H, E4 = 2H+F- E5- E2, E6 = H,
E7 = H, E8 = H+F- E5, E9 = E5, E10 = E2.
Possible values of E2 = H, E5 = F and E2 = F, E5 = H give us two pp-solutions:
E14 = E10 = E4 = E2 = E3 = E7 = E6 = E8 = E13 = H and
E14 = E1 = E3 = E7 = E6 = E5 = E4 = E9 = E13 = H(in both pp-solutions other edge values are equal to F), while values of E2 = H
and E5 = H give a pp-solution, which is eliminated because of a subtour of an
H-valued edge cycle {E2 = H, E3 = H, E7 = H, E6 = H, E5 = H}. It is important
to note that in the feasible pp-solutions, the pair of E13 = E14 = H has thesame B-communicator (entering the region at E14 and leaving it at E13, or viceversa).

one of these pp-solutions is a part of a
Hamiltonian cycle then the other pp-solution is also a part ofThis means that if

7

another Hamiltonian cycle which differs from the former one
only in our region.
For the second example with E22 = E13 = F and E12 = E14 = H, edges E2 andE5 can also play a role as symbolic parameters. For any possible variation ofthem, there is only one feasible pp-solution:
E14 = E10 = E9 = E8 = E5 = E2 = E3 = E7 = E12 = H
and for the third example with E22 = E12 = H and E13 = E14 = F, there are no
pp-solutions compatible with the necessary conditions of Hamiltonicity; one isbecause of an H-valued edge cycle and two others are because of invalid(infeasible) edge values in the form of 2H-F.
Finally, let us consider one more example with E 22 = E12 = E13 = E14 = H.
There are three pp-solutions (of two paths each):
E14 = E10 = E9 = E13 = H; E12 = E6 = E5 = E2 = E3 = E22 = H
E14 = E10 = E4 = E2 = E3 = E22 =H; E13 = E8 = E6 = E12 = H
E14 = E1 = E3 = E22 =H; E13 = E9 = E4 = E5 = E6 =E12 = H.
In the first pp-solution, the in-out pairs of B-communicator are (E14, E13) and(E12, E22), while in the second one, they are (E14, E22) and (E13, E12). Thismeans that if one of these pp-solutions is a part of a Hamiltonian cycle, then it
is not necessarily the same for the other pp-solution. On the other hand, inboth the second and third pp-solutions the in-out pairs of B-communicatorsare (E14, E22) and (E13, E12). This means that one of these pp-solutions

can be removed without eliminating the possibility of
discovering a possible Hamiltonian cycle.
Now let us consider another example related to the left region of Fig.3.

Fig. 3. A cut-set line based on the C-K-I-face path

8

The system of equations of the (1.1) type is the following:
E1 + E2 + E3 = 2H + F
E2 + E4 + E5 = 2H + F
E4 + E9 + E10 = 2H + F
E5 + E6 + E8 = 2H + F
E6 + E7 + E12 = 2H + F
E8 + E9 + E13 = 2H + F

E3 + E7 + E22 = 2H + F
E12 + E16 + E21 = 2H + F
E11 + E15 + E17 = 2H + F
E11 + E14 + E18 = 2H + F
E1 + E10 + E14 = 2H + F
E13 + E15 + E16 = 2H + F.

(2.3)

The B-set values are sets of values of E22, E21, E17, and E18. Taking thenames of these edges as symbolic parameters and a solving system (2.3)(with 12 equations and 16 unknowns), we find four independent edges (E9,
E10, E11 and E16) allowing all region edges to be presented as symbolic
expressions depending on these edges (as well as on E22, E21, E17, and E18).
In other words, by considering possible value variations of E22, E21, E17, andE18, as well as E9, E10, E11 and E16, we find all possible pp-solutions in theregion. Logarithmic sizes allow applying brute force for this consideration;
however, a more elegant approach can also be taken. For example, becauseof the condition for Hamiltonicity, the B-edge value has to satisfy one of theequalities: E22 + E21 + E17 + E18 = 4H or E22 + E21 + E17 + E18 = 2H + 2F (infact, the first equality means that E22 = H, E21 = H, E17 = H and E18 = H). In
addition, by consecutively adding equations of E9 – E11 = 0 or E9 + E11 = H+F
types, we can reason about the symbolic expressions of the edge values.
Under condition of E22 + E21 + E17 + E18 = 4H, let’s consider two assumptions,that E9=E11, E10=E16 (E9-E11=0, E10-E16=0) and E9=E11, E10 ≠E16 (E9-E11=0,
E10+E16=H+F). For the first assumption, the linear solver [3] provides symbolic
expressions for edge values, where we can see E1=3H+F-E4-2E10 and E2=2H-F+E4+3E10; the first can be valid only with E10=H and, after that, thesecond can be valid only for E4=F (see some rules for reasoning about edge
values in Appendix 1). Applying E10=H and E4=F gives us a pp-solution of twopaths (of H-valued edges):
E17, E11, E18;
E21, E16, E13, E9, E10, E1, E2, E5, E6, E7, E22.
For the second assumption, we receive among others E11= (E5+ E7)/2 and E1=-(2F-E5-3E7)/2. The first can be valid only if E5=E7 and the second if E5=E7=F.
Applying E5=F and E7=F gives us another pp-solution of two paths:
E17, E15, E13, E8, E6, E12, E21; E18, E14, E10, E4, E2, E3, E22.
Similarly, we can consider assumptions E9≠E11, E10=E16 and E9≠E11, E10≠E16
and obtain three pp-solutions:
E17, E15, E13, E9, E4, E5, E6, E12, E21; E18, E14, E1, E3, E22,
E17, E15, E16, E21;
E18, E14, E1, E2, E4, E9, E8, E6, E7, E22,
E17, E15, E13, E9, E10, E14, E18; E21, E12, E6, E5, E2, E3, E22.
Totally, three pp-solutions have B-communicator {(E17, E21), (E18, E22)} andtwo pp-solutions have B-communicator {(E17, E18), (E21, E22)}.
9

The redundancy elimination follows extracting pp-solutions acceptable inregions by considering all possible B-set values. First, each cluster of ppsolutions, based on the same B-set value and the same B-communicator, isreplaced by one pp-solution (a representative one). In our example, justconsidered, as well as in the first and fourth examples related to the left regionof Fig. 2, one-of-two and two-of-three pp-solutions can be removed. Then, a
set of B-cases is created. This set includes the cluster representatives thatare pp-solutions based on different B-set values and pp-solutions based on
the same B-set value, but with different B-communicators. In general, thenumber of different B-communicators for a B-set value is less or equal to 3p1/2 + 1/2, where p is the number of B-communicator pairs. For example, for a
B-set with four, six and eight H-valued B-edges, that is for p=2, 3 and 4, it is 2,
5 and 14, respectively (see Appendix 2).
The set of B-cases is employed for extracting the r-invariants. However, there arealternative ways for pp-solution eliminations; therefore, creating the set of B-cases canbe performed within the process of extracting the r-invariants or can be postponed until
some additional data from neighboring regions becomes available.

3. Examples of extracting regional invariants
R-invariants are extracted from pp-solutions preserved after the redundancy
eliminations. In fact, as mentioned above, the eliminations have alternatives inselecting representative pp-solutions; therefore, the final decision about such
pp-solutions should be performed within the framework of extracting the rinvariants. To demonstrate this, we will continue the consideration of theprevious example related to Fig. 3. This includes pp-solutions related to thesecond equality for B-edges: E22 + E21 + E17 + E18 = 2H + 2F. The number of
B-set values is 6:
Table 1: B-set values for the Fig. 3 example

1
2
3
4
5
6

B1=E22B2=E21

B3=E17

B4=E18

H
H
H
F
F
F

H
F
F
H
H
F

F
H
F
H
F
H

F
F
H
F
H
H

For each of these B-set values we consider solutions of the (2.3) system.
However, before such a consideration, we can enter symbolic parameters Bj(j=1,2,3,4) into this system and find values of region edges depending onthem, as well as on some independent edges (provided by the solver). In thiscase, they are E9, E10, E11, and E16. Value variations of this independent edgeset (ind-set), applied to each B-set value, allow us to discover all pp-solutionsin the region.
10

As we have already mentioned, logarithmic sizes allow applying brute force
for this discovery. However, some reducing operations can be done inadvance. For example, four cases with E9=E10=F and any values for E11 andE16 can be removed in advance from the consideration, because ofincompatibility with an n-invariant. A similar thing occurs with E9=E10=E11=H
and E16=F at B4=F; this is because of an internal H-valued cycle: E9, E10, E14,
E11, E15, E13. This means that if B4=F, for any values of B1, B2, and B3, weshould not try cases with E9=E10=E11=H and E16=F.
B-set value 1 is related to B1=B2=H, B3=B4=F. Then, E11 has to be equal onlyto H, and the variation of other independent edges includes five ind-sets:
1: {E9=E10=E16=H}, 2: {E9=H, E10=F, E16=H}, 3: {E9=F, E10=H, E16=H},
4: {E9=H, E10=F, E16=F}, 5: {E9=F, E10=H, E16=F}.
There are only three feasible pp-solutions for ind-sets 2, 4 and 5:
E21, E16, E15, E11, E14, E1, E2, E4, E9, E8, E6, E7, E22,
E21, E12, E6, E5, E4, E9, E13, E15, E11, E14, E1, E3, E22,
E21, E12, E6, E8, E13, E15, E11, E14, E10, E4, E2, E3, E22.
They have the same B-communicator {E21, E22}; therefore, the redundancy
elimination allows us to preserve only one of these pp-solutions.
B-set value 2 is related to B1=H, B2=F, B3=H, B4=F. Then, E11 and E16 haveto be equal only to H, and the variation of other independent edges includes
the following ind-sets: 1: {E9=E10=H}, 2: {E9=F, E10=H}, 3: {E9=H, E10=F}.
There is only one feasible pp-solution for ind-set 1:
E17, E11, E14, E10, E9, E13, E16, E12, E6, E5, E2, E3, E22.
B-set value 3 is related to B1=H, B2=F, B3=F, B4=H. Then, as above, E11 andE16 have to be equal only to H, and the variation of other independent edges
includes the following ind-sets: 1: {E9=E10=H}, 2: {E9=F, E10=H}, 3: {E9=H,
E10=F}. There are no feasible pp-solutions for these ind-sets and B-set value
3 is removed.
B-set value 4 is related to B1=F, B2=H, B3=H, B4=F. Then, as in B-set value 1,
E11 has to be equal only to H and the variation of other independent edges
includes five ind-sets:
1: {E9=E10=E16=H}, 2: {E9=H, E10=F, E16=H}, 3: {E9=F, E10=H, E16=H},
4: {E9=H, E10=F, E16=F}, 5: {E9=F, E10=H, E16=F}.
There are two feasible pp-solutions for ind-sets 2 and 3:
E17, E11, E14, E1, E3, E7, E6, E5, E4, E9, E13, E16, E21,
E17, E11, E14, E10, E4, E2, E3, E7, E6, E8, E13, E16, E21.
They have the same B-communicator {E17, E21}; therefore the redundancy
elimination allows us to preserve only one of these pp-solutions.

11B-set value 5 is related to B1=F, B2=H, B3=F, B4=H. Then, E11 has to be equal
only to H, and the variation of other independent edges includes five ind-sets:
1: {E9=E10=E16=H}, 2: {E9=H, E10=F, E16=H}, 3: {E9=F, E10=H, E16=H},
4: {E9=H, E10=F, E16=F}, 5: {E9=F, E10=H, E16=F}.
There is only one feasible pp-solution for ind-set 5:
E18, E11, E15, E13, E8, E5, E4, E10, E1, E3, E7, E12, E21.
B-set value 6 is related to B1=F, B2=F, B3=H, B4=H. Then, E16 has to be equal
only to H, and the variation of other independent edges includes six ind-sets:
1: {E9=E10=E11=H}, 2: {E9=H, E10=H, E11=F}, 3: {E9=H, E10=F, E11=H},
4: {E9=F, E10=H, E11=H}, 5: {E9=H, E10=F, E11=F}, 6: {E9=F, E10=H, E11=F}.
There is only one feasible pp-solution for ind-set 2:
E17, E15, E16, E12, E7, E3, E2, E5, E8, E9, E10, E14, E18.
In total, thirteen feasible pp-solutions have been discovered:
E17, E11, E18;
E21, E16, E13, E9, E10, E1, E2, E5, E6, E7, E22,
E17, E15, E13, E9, E10, E14, E18; E21, E12, E6, E5, E2, E3, E22,
E17, E15, E13, E8, E6, E12, E21;

E18, E14, E10, E4, E2, E3, E22,

E17, E15, E13, E9, E4, E5, E6, E12, E21; E18, E14, E1, E3, E22,
E17, E15, E16, E21; E18, E14, E1, E2, E4, E9, E8, E6, E7, E22,
E21, E16, E15, E11, E14, E1, E2, E4, E9, E8, E6, E7, E22,
E21, E12, E6, E5, E4, E9, E13, E15, E11, E14, E1, E3, E22,
E21, E12, E6, E8, E13, E15, E11, E14, E10, E4, E2, E3, E22,
E17, E11, E14, E10, E9, E13, E16, E12, E6, E5, E2, E3, E22,
E17, E11, E14, E1, E3, E7, E6, E5, E4, E9, E13, E16, E21,
E17, E11, E14, E10, E4, E2, E3, E7, E6, E8, E13, E16, E21,
E18, E11, E15, E13, E8, E5, E4, E10, E1, E3, E7, E12, E21,
E17, E15, E16, E12, E7, E3, E2, E5, E8, E9, E10, E14, E18.
Seven of these pp-solutions have to be preserved, and six can be eliminatedto simplify discovering an r-invariant. Extracting values of the independentedges from these pp-solutions gives us Table 2:12

Table 2: Values of independent edges

E9
E10
E11
E16

1
H

2
H

3
F

4
H

5
H

6
H

7
H

8
F

9
H

10
H

11
F

12
F

13
H

H

H

H

F

F

F

F

H

H

F

H

H

H

H

F

F

F

F

H

H

H

H

H

H

H

F

H

F

F

F

H

H

F

F

H

H

H

F

H

There are four clusters of columns of (1-2), (3-5), (6-8), (10-11), where in eachof them, we can preserve only one column, and there are three columns of 9,
12 and 13 which are not removable. Column 9 is coincident with column 1, socluster (1-2) can be represented by column 1; similarly, column 12 iscoincident with column 8 and cluster (6-8) can be represented by column 8.
For selecting representatives of clusters (3-5) and (10-11), we should decide
about an invariant pattern (Ej=H, Ej+Ek=H+F, Ej=Ek or Ej+Ek+Ep=2H+F, etc.)
to be searched. In our case, pattern E10=H leads to columns 3 and 11 as therepresentatives (see Table 3), while E9=E16 leads to columns 3 and 10 (or 5and 10) (see Table 4). In other words, we extracted two invariants (E10=H andE9=E16) and one of them can be used in further considerations.
Table 3: Representatives with columns 3 and 11

E9
E10
E11
E16

1

3

8

9

11

12

13

H

F

F

H

F

F

H

H

H

H

H

H

H

H

H

F

H

H

H

H

F

H

F

F

H

H

F

H

Table 4: Representatives with columns 3 and 10

E9
E10
E11
E16

1

3

8

9

10

12

13

H

F

F

H

H

F

H

H

H

H

H

F

H

H

H

F

H

H

H

H

F

H

F

F

H

H

F

H

To extract new invariants we should consider new regions. Fig. 4 depicts a
cut-set line based on the E-K-H-face path and a top-left region we are going
to consider. This region is overlapped with the previous one; therefore in thesystem of equations of (2.3), we add the E10=H invariant:

E10 = H

E1 + E2 + E3 = 2H + F
E2 + E4 + E5 = 2H + F
E4 + E9 + E10 = 2H + F
E5 + E6 + E8 = 2H + F
E6 + E7 + E12 = 2H + F
E8 + E9 + E13 = 2H + F
13E3 + E7 + E22 = 2H + F
E12 + E16 + E21 = 2H + F
E22 + E23 + E24 = 2H + F (3.1)
E21 + E23 + E20 = 2H + F
E13 + E16 + E15 = 2H + F
E1 + E10 + E14 = 2H + F

Fig. 4. A cut-set line based on the E-K-H-face path

The B-set values are sets of values of E24, E20, E15, and E14. Taking thenames of these edges as symbolic parameters and a solving system (3.1)(where 13 equations and 16 unknowns), we find three independent edges (E4,
E5 and E23). By considering possible value variations of these independentedges, as well as B-edges, we find all possible pp-solutions in this new region.
As for the previous region, the B-edge value has to satisfy one of theequalities: E24 + E20 + E15 + E14 = 4H or E24 + E20 + E15 + E14 = 2H + 2F. For
E24 + E20 + E15 + E14 = 4H, there are three feasible pp-solutions:
E14, E10, E9, E8, E5, E2, E3, E7, E12, E16, E15; E20, E23, E24 (for E4=F, E5=H, E23=H),
E14, E10, E4, E2, E3, E22, E24; E15, E13, E8, E6, E12, E21, E20 (for E4=H, E5=F, E23=F),
E14, E10, E9, E13, E15; E20, E21, E12, E6, E5, E2, E3, E22, E24 (for E4=F, E5=H, E23=F).

For E24 + E20 + E15 + E14 = 2H + 2F, B-set values are presented by Table 5.
Table 5: B-set values for the Fig.4 example

1
2
3
4
5
6

B1=E24B2=E20B3=E15

B4=E14

H
H
H
F
F
F

H
F
F
H
H
F

F
H
F
H
F
H

F
F
H
F
H
H

For these, there are five feasible pp-solutions:
1. E20, E21, E16, E13, E9, E10, E1, E2, E5, E6, E7, E22, E24 (for E4=F, E5=H, E23=F)
2. E15, E13, E8, E5, E4, E10, E1, E3, E7, E12, E21, E23, E24 (for E4=H, E5=H, E23=H)
3. E14, E10, E4, E2, E3, E7, E6, E8, E13, E16, E21, E23, E24 (for E4=H, E5=F, E23=H)
4. No solutions

5. E14, E10, E9, E13, E16, E12, E6, E5, E2, E3, E22, E23, E20 (for E4=F, E5=H, E23=H)
6. E14, E10, E4, E2, E3, E22, E23, E21, E12, E6, E8, E13, E15 (for E4=H, E5=F, E23=H).
14

Taking into account the redundancy elimination, we remove pp-solution
E14, E10, E9, E8, E5, E2, E3, E7, E12, E16, E15; E20, E23, E24
and after that discover three r-invariants: E13=H, E2=E6, and E4=E8. The edges
involved are not from the set of (E4, E5, E23); therefore the r-invariants arechecked for independence from the n-invariants and previously extracted rinvariants. As a result of this check, we discover that E4=E8 is dependent(derived from the n-invariants and E10=H, E13=H).
To continue extracting the invariants, we consider another region (see theright subgraph at Fig. 5).

Fig. 5. A cut-set line based on the B-F-H-face path

In the system of the (2.3) type equations, we add the E13=H invariant:

E13 = H

E22 + E23 + E24 = 2H + F
E6 + E7 + E12 = 2H + F
E20 + E21 + E23 = 2H + F
E12 + E16 + E21 = 2H + F
E18 + E19 + E24 = 2H + F
E13 + E15 + E16 = 2H + F

E17 + E19 + E20 = 2H + F
E11 + E15 + E17 = 2H + F
E7 + E22 + E3 = 2H + F (3.2)
E6 + E8 + E5 = 2H + F
E8 + E13 + E9 = 2H + F
E11 + E18 + E14 = 2H + F.

The B-set values are sets of values of E3, E5, E9, and E14. Taking names ofthese edges as symbolic parameters and solving system (3.2) (where 13
equations and 16 unknowns), we find three independent edges (E19, E23 andE24). By considering possible value variations of these independent edges, aswell as B-edges, we find all possible pp-solutions in this new region. As for theprevious region, the B-edge value has to satisfy one of the equalities:
E3 + E5 + E9 + E14 = 4H or E3 + E5 + E9 + E14 = 2H + 2F.
For E3 + E5 + E9 + E14 = 4H there are four valid pp-solutions:
E14, E11, E17, E19, E24, E23, E21, E16, E13, E9; E5, E6, E7, E3 (for E19=H, E23=H, E24=H),
E14, E18, E9, E17, E15, E13, E9; E5, E6, E12, E21, E23, E22, E3 (for E19=H, E23=H,E24=F),
15

E14, E11, E15, E13, E9; E5, E6, E12, E21, E20, E19, E24, E22, E3 (for E19=H, E23=F, E24=H),
E14, E18, E24, E22, E3; E5, E6, E12, E21, E20, E17, E15, E13, E9 (for E19=F, E23=F, E24=H).

For E3 + E5 + E9 + E14 = 2H + 2F there are five feasible pp-solutions:
At B-set value (E3=H, E5=F, E9=F, E14=H)
E14, E11, E17, E19, E24, E23, E21, E16, E13, E8, E6, E7, E3 (for E19=H, E23=H, E24=H),
E14, E18, E19, E17, E15, E13, E8, E6, E12, E21, E23, E22, E3 (for E19=H, E23=H, E24=F),
E14, E11, E15, E13, E8, E6, E12, E21, E20, E19, E24, E22, E3 (for E19=H, E23=F, E24=H)
At B-set value (E3=F, E5=H, E9=H, E14=F)E5, E6, E7, E22, E24, E18, E11, E17, E20, E21, E16, E13, E9 (for E19=F, E23=F, E24=H).
At B-set value (E3=F, E5=H, E9=F, E14=H)
E14, E18, E24, E22, E7, E12, E21, E20, E17, E15, E13, E8, E5 (for E19=F, E23=F, E24=H).
From these pp-solutions, we extract ind-set values (presented in Table 6). By
preserving column 3 from cluster 1-3 and column 7 from cluster 5-7, we
extract two invariants: E24=H and E23=F (in cases of reasoning on symbolic
expressions of the edge values, instead of invariants of the E23=F type, it ispossible to use a pair of the <E22=H, E21=H> type).
Table 6: Independent edge values

E19
E23
E24

1

2

3

4

5

6

7

8

9

H

H

H

F

H

H

H

F

F

H

H

F

F

H

H

F

F

F

H

F

H

H

H

F

H

H

H

To continue extracting the invariants, we consider a new region (see thebottom subgraph at Fig. 6).

Fig. 6. A cut-set line based on the A-B-C-E-face path

In the system of the (2.3) type equations, we add invariants extracted before
and applicable to this region. In addition, we analyze their influence on B-set
values. As a result, the B-set is reduced to two edges (E1 and E7; E2 is defined16

by them) and ind-set is reduced to edges E4 and E11. For various values of
the B-edges, there are five pp-solutions:
At B-set value (E7=H, E1=H)
E1, E10, E4, E2; E7, E6, E8, E13, E16, E21, E20, E17, E11, E18, E24 (for E4=H, E11=H),
E1, E10, E9, E13, E16, E21, E20, E17, E11, E18, E24; E7, E6, E5, E2 (for E4=F, E11=H).
At B-set value (E7=H, E1=F)
E7, E12, E21, E20, E17, E15, E13, E8, E5, E4, E10, E14, E18, E24 (for E4=H, E11=F).
At B-set value (E7=F, E1=F)
E2, E4, E10, E14, E11, E15, E13, E8, E6, E12, E21, E20, E19, E24 (for E4=H, E11=H),
E2, E5, E6, E12, E21, E20, E17, E15, E13, E9, E10, E14, E18, E24 (for E4=F, E11=F).
From these pp-solutions, E4+E5+E11=2H+F is extracted as the invariant.
In a similar way, we can consider additional regions and obtain additional
invariants. However, in our case we have already got six invariants; therefore,
we can consider the system of equations for the graph as a whole.
E1 + E2 + E3 = 2H + F
E2 + E4 + E5 = 2H + F
E4 + E9 + E10 = 2H + F
E5 + E6 + E8 = 2H + F
E6 + E7 + E12 = 2H + F
E8 + E9 + E13 = 2H + F
E17 + E19 + E20 = 2H + F
E18 + E19 + E24 = 2H + F
E10 = H
E24 = HE2 = E 6

E3 + E7 + E22 = 2H + F
E12 + E16 + E21 = 2H + F
E22 + E23 + E24 = 2H + F
E20 + E21 + E23 = 2H + F
E13 + E15 + E16 = 2H + F(3.3)
E1 + E10 + E14 = 2H + F
E11 + E15 + E17 = 2H + F
E11 + E14 + E18 = 2H + F
E13 = H
E22 = H, E20 = H (instead of E23 = F)
E4 + E5 + E11 = 2H + F.

The solver provides two independent edges E1 and E4 to get unique solutionsfor (3.3). There are no solutions for E1=E4, and there are two Hamiltonian
cycles for E1≠E4:{E1, E10, E9, E13, E16, E21, E20, E17, E11, E18, E24, E22, E7, E6, E5, E2} and{E10, E14, E11, E15, E13, E8, E6, E12, E21, E20, E19, E24, E22, E3, E2, E4},
respectively for (E1=H, E4=F) and (E1=F, E4=H).
4. Redundancy related index for searching appropriate regions
A fundamental point of our approach is regional redundancy and“independence” represented by corresponding invariants. For searching theappropriate regions and their shapes, we consider around each graph node a17

starting region including, first of all, three faces incident to this node. Then,these regions are sorted according to the growth of absolute values of a

(RR-index), that is defined as thenumber of interior faces in a region minus the number of theregion B-edges.
redundancy related index

The order mentioned is just used for some systematic search of the graph regions where
RR-index ≥ 1, and where the first attempt of discovering r-invariants is performed.

For obtaining a region with RR-index ≥ 1, we analyze the neighborhood of astarting region and attach to it one or a few faces to arrange a new region witha larger RR-index. A number of such arrangement steps can be performed forgetting a basic region with RR-index ≥ 1. To demonstrate this process, let’s
consider logarithmic size regions A and its neighbor D (Fig. 7), sharing some
B-edges with A, and assume compound region AD, including A and D, isconnected (otherwise another neighbor is selected). In addition, we assume
that region A has VA nodes and is surrounded by Ktlr + Kb B-edges (Ktlr is thenumber of B-edges on top-left-right sides and Kb is the number of B-edges on
the bottom side).

Fig. 7. Neighboring regions A and D

Applying the Euler formula we can obtain for interior faces of the region graph,the following expression:
FA = VA/2 – (Ktlr + Kb)/2 + 1.
It is a formula connecting the number of regional interior faces, the number ofregional nodes, and the number of regional B-edges. Then, for RR-index(RRI), we can obtain RRIA = FA – (Ktlr + Kb) = VA/2 – 3(Ktlr + Kb)/2 + 1.
Now, let region D have h internal rows representing nodes reachable by one
step from nodes of the upper neighboring row: the nodes of the first row arereachable from the bottom nodes of region A by the bottom side B-edges, thenodes of the second row are reachable from the nodes of the first row byedges going down (from the first row nodes), and so on. Denote the number18

of nodes in row j by Kj, the average number of nodes (among all rows) by K
and the number of B-edges on the bottom-left-right sides of region D by Kblr.
Then for the number of interior faces of compound region AD we can get:
FAD = (VA+h·K)/2 – (Ktlr + Kblr)/2 + 1
and for the RR-index of compound region AD:
RRIAD = FAD – (Ktlr + Kblr) = (VA+h·K)/2 – (Ktlr + Kblr)/2 + 1 – (Ktlr + Kblr) or
RRIAD = RRIA + h·K/2 + 3(Kb-Kblr)/2.

(4.1)

This formula shows how we can search regions with increasing values of RRindex. For a case with Kblr > Kb and h·K/2 + 3(Kb-Kblr)/2 ≤ 0, the shape ofregion D is modified by increasing h and/or “tuning” rows involved. For Fig.
7, tuning means removing the bottom-left node which is out of faces attached.
In region D of Fig. 8 (a), there are 4 black nodes (labeled b) in the first row, 4yellow and 4 white nodes in the second and third rows (labeled y and w,
respectively), and five black nodes (also labeled b) in the fourth row;a)b)Fig. 8. Neighboring regions A and two D-s, one of which is with “tuning” rows

RRIA = -1, Kblr > Kb but h·K/2 + 3(Kb-Kblr)/2 = 1 and RRIAD = 0.
However, “tuning” the shape of rows 2-4 decreases the value of Kblr; see Fig.
8 (b), where there are 3 yellow nodes in the second row, 3 white nodes in the19third rows, and two black nodes in the fourth row. As a result, RRIAD’ = 2. In
this example, such tuning operations are also applicable for two bottom rowsof region A (before considering region AD) for removing two right nodes ofthese rows and for getting RRIA = 1.
In general, tuning rows means decreasing a region cutting set by removing aface or by avoiding attachment of an incomplete face. In fact, the tuning
operations are automatically performed, if D regions include only complete
faces and their attachment increases the RR-index. A special point ofattention is that different D regions lead to different increases; for example,
attaching the right D at Fig. 8 (b) increases RRIA by 4, while attaching thebottom D increases RRIA by 3.

Formula (4.1) shows a “quadratic” growth of h·K/2 and a“linear” growth of 3(Kb-Kblr)/2. This means that basic regionswith RR-index ≥ 1 are achievable.
The number of faces, in a sense, represents a “regional square” and the number of Bedges represents a “regional perimeter”.

Every time, we need a basic region to start extracting r-invariants, thefollowing operations are performed.
For a starting region A, we consider, one-after-another, possible locations of
the region D attachment with h =1 and Kb = 2, 3,…,Ω (Ω is limited by anumber of B-edges of region A). This is for discovering compound region AD
with maximal RRIAD (which has to be > RRIA). Successful discovering leads
us to assign this region AD for being a new region A and to restart the search.
Unsuccessful discovering leads us to assign h = h+1 and after that to restart
the search. It is finished by getting a basic region with RRIAD = ©+1 (0≤©≤©,© is a constant). These steps are a growing RR-index search.
We can consider our search from another point of view. For each starting region A, we try to
attach a neighboring face (sharing some internal edges and B-edges with A and representing
region D), which increases RRI. Absence of such a face suggests that we should try attachinga set of two or more neighboring faces (the number of these faces is limited and predefined).
The failure of getting a result is used for selecting a set of faces preserving RRI. Then AD is
assigned as a new A, and the search is restarted.

The basic region discovered is employed for extracting the r-invariants (thisincludes finding pp-solutions and applying redundancy eliminations) or (in the case of theinvariant extracting failure) it is used for arranging neighboring regions (NRs) (seethe next section and Appendix 3) and for applying the NR redundancy eliminations
to unblock discovering invariants in the basic region. In a successful case, we
use this basic region for discovering other r-invariants. After exhausting all20

possibilities in this region, we reuse one of the NRs (as a basic one) or go to a
new starting region with the largest RR-index.
Discovering an r-invariant is followed by checking the number of the r-invariants available
and finishing the search, if this number is ≥ N/2 (it is also for checking the invariant
independence and duplication); otherwise employing (if any) a non-considered-yet
starting region. Results obtained in a region are saved and taken into account by further
operations in this and other regions.

5. Searching invariants in basic and neighboring regions
There are a lot of invariants in the graph regions. For example, let’s select any
graph node and consider all nodes reachable within two steps. Then, the sumof edges involved at the second step is always equal to 4H+2F. A similar
invariant exists for edges involved at the third step and related to nodes
reachable within three steps: the sum of these edges is equal to 8H+4F.
Another example is related to a region of one face with even degree k. Expression E1 - E2
+ E3 – E4 + … + Ek-1 – Ek (where edges neighboring in the expression are neighboring Bedges of the region) is always equal to 0. Unfortunately, they are derived from the ninvariants and cannot be used for the systems of equations mentioned above.

5.1.

Examples of independent r-invariants

A great variety of basic regions allows directly discovering the independent rinvariants. For example, in the region of Fig. 9 (a) with RRI=1, five rinvariants (E1=H, E7=H, E10=H, E13=H and E16=H) or alternatively (E2=H, E8=H,
E12=H, E14=H and E17=H) can be extracted. In the region of Fig.9 (b) with
RRI=2, r-invariants E1=E4 and E2=E5 are simultaneously available (however,they depend on each other); alternatively, E19=E21 or E14=E22 can also be
discovered. In the region of Fig. 9 (c) with RRI=1, E25=H is the invariant.
R-invariants also exist in regions presented by Fig.10 (a-d). E2=E5 (or E3=E6),
E1=E3 (or E9=E11), E12=H and E1=E8 (or E1=E6) can respectively be discovered
in Fig.10 (a) - (d). Even for cases with RRI = 0 and RRI = -1, r-invariants cana)b)Fig. 9. Examples of regions with r-invariants

21c)exist in regions with four B-edges.

d)

a)

b)

c)

Fig. 10. Additional examples of regions with r-invariants

It is important to note that an r-invariant extracted from a set of pp-

solutions in a region is valid on any subset of these pp-solutions. Thismeans that additional removal of pp-solutions from the set preserves
the r-invariant extracted.
However, there are basic regions without invariants we are interested in;
Fig.11 presents an example of such a region. Therefore (within the frameworkof the polynomial complexity), we consider some neighboring regions,overlapping the region under consideration (RUC), their pp-solutions andappropriate redundancy eliminations for decreasing the number of ppsolutions in RUC and, as a result, for discovering the r-invariants there.

Fig. 11. A region without invariants

5.2.

Arranging the neighboring regions

There can be a variety of approaches. Ours is based on selecting an invariant
pattern (a candidate to be an r-invariant) for a basic RUC and discovering pp22

solutions that block the recognition of this pattern as the r-invariant (Ej=H,
Ej+Ek=H+F and Ei+Ej+Ek=2H+F are examples of patterns to be considered).
For the blocking pp-solutions, we select (Ej,Ek) (and/or (Bi,Bp) and (Ei,Bp),
where Bi and Bp are B-edges) pairs of the RUC edges satisfying the equalityof Ej=Ek=F. Such pairs are used for orientation within arranging an NR. The
orientation means that a part of the pairs should be inside this NR.
Table 7 shows 15 clusters of pp-solutions related to the region presented by
Fig.11. Each cluster includes two pp-solutions and any of these two can beeliminated without altering the graph Hamiltonicity. The total number of theclusters is 29, however we selected 15; they possess all features we areinterested in to present. Though we cannot immediately discover an rinvariant, we can select an invariant pattern (for example, E 14=H) and analyze
conditions blocking the recognition of this pattern as the r-invariant. Within thecluster eliminations, pattern E14 = H can be recognized as an r-invariant in all
Table 7: A set of pp-solutions for the region presented by Fig. 11

E1
E2
E3
E4
E5
E6
E7
E8
E9
E10
E11
E12
E13
E14
E15
E16
E17
E18
E19
E20
E21
E22
E23
E24
E25
E26
E27
E28
E29
E30

F,F

H,H

H,H

F,F

H,H

H,H

H,H

H,H

H,H

H,F

H,F

H,H

H,F

H,H

H,H

H,H

F,H

H,F

H,H

H,H

H,H

H,F

F,F

H,H

F,H

F,H

H,F

F,H

H,H

H,H

H,H

H,F

F,H

H,F

H,F

H,H

F,H

H,H

H,F

H,H

H,H

F,H

H,F

F,H

F,F

H,F

H,H

H,H

F,H

F,H

H,F

H,F

F,H

F,H

H,F

F,F

H,H

F,H

H,F

H,H

F,H

F,H

F,F

H,H

H,H

F,H

F,H

H,F

H,H

F,H

H,H

H,H

H,H

F,H

F,H

H,H

H,F

H,H

H,H

H,H

H,H

H,H

H,H

F,F

H,H

H,H

F,F

H,H

H,F

H,F

H,H

F,H

F,F

H,H

F,F

F,F

F,F

F,F

H,H

F,H

F,H

H,H

F,H

F,H

F,H

H,H

H,F

F,H

H,H

F,F

F,F

F,H

H,H

F,F

H,H

H,H

F,H

H,H

F,F

F,F

F,F

H,H

H,H

F,H

F,H

F,F

H,H

H,H

F,H

H,F

H,F

H,H

H,H

H,F

H,H

F,H

F,H

H,F

H,H

H,H

F,H

H,H

H,F

H,H

F,H

H,H

H,F

H,H

H,H

H,H

H,H

H,F

H,H

H,F

H,F

H,H

H,H

H,H

H,F

H,H

H,H

F,F

H,F

H,H

H,F

H,F

H,H

H,H

F,F

F,F

H,F

H,F

F,H

H,H

H,F

F,F

H,H

F,F

H,H

H,H

H,H

F,H

F,F

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

F,H

F,H

F,F

H,F

H,H

F,F

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,F

H,F

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

F,F

H,F

H,F

F,F

H,F

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

F,F

H,H

F,H

F,H

H,H

F,H

H,H

H,H

F,F

F,H

H,F

F,F

H,H

H,H

H,F

H,H

H,H

H,F

H,F

H,F

H,F

H,H

H,H

H,H

H,F

F,H

H,H

H,H

H,H

F,H

H,H

H,H

F,H

F,H

F,H

F,H

H,H

F,F

H,H

F,H

H,F

H,F

H,F

H,H

H,F

F,F

H,F

H,H

H,H

H,F

H,F

F,H

H,H

H,H

H,F

F,H

F,H

F,H

H,H

F,H

H,H

F,H

H,H

F,F

F,H

F,H

H,F

H,H

H,F

H,H

H,H

H,F

H,F

H,F

H,F

F,H

H,F

H,F

H,H

H,H

H,F

F,H

F,F

F,H

H,H

F,F

F,H

F,H

F,H

F,H

H,F

F,H

F,H

H,H

H,H

F,H

H,F

H,H

H,F

F,H

H,H

H,H

H,H

H,F

H,F

F,H

H,H

H,F

F,F

H,H

H,H

F,H

F,H

F,H

H,F

H,H

H,H

H,H

F,H

F,H

H,F

F,F

F,H

H,H

F,F

H,H

H,F

H,F

H,H

H,H

H,H

H,H

F,F

F,F

F,F

F,F

F,F

F,F

F,F

F,F

F,F

H,H

H,H

F,F

F,F

F,F

F,F

F,F

F,F

F,F

H,H

H,H

H,H

H,H

H,H

H,H

F,F

F,F

H,H

H,H

H,H

H,H

F,F

F,F

H,H

F,F

F,F

H,H

H,H

H,H

H,H

F,F

H,H

F,F

H,H

H,H

H,H

H,H

F,F

H,H

H,H

H,H

F,F

H,H

H,H

H,H

H,H

F,F

H,H

F,F

H,H

H,H

H,H

H,H

H,H

H,H

H,H

H,H

F,F

F,F

H,H

H,H

H,H

H,H

H,H

F,F

F,F

F,F

H,H

H,H

H,H

H,H

H,H

H,H

H,H

F,F

H,H

H,H

23

clusters (including those we omitted for showing) except two of them (greylighted by a grey background of characters); all pp-solutions in these twoclusters have E14 = F.
In addition, in the left grey-lighted cluster all (in our case, just two) ppsolutions have E1=E9=E17=B26=B28=F and in the right grey-lighted cluster all
pp-solutions have E1=E12=E17=B26=B30=F. In order to recognize the pattern as
an r-invariant, in some way, pp-solutions with E14 = F should be eliminated in
the RUC. Such effect eliminations can be reached in an NR which overlaps
the RUC and includes the edges mentioned above as internal ones.
Redundancy eliminations in such an NR removing pp-solutions with, forexample, B26=B28=F and E1=E17=F, provides the necessary result; we callsuch eliminations 2F pair eliminations. In fact, the result could be provided byany pair from (E1, E9, E17, B26, B28) instead of B26=B28=F and any pair from (E1,
E12, E17, B26, B30) instead of B1=B17=F.
Considering Fig.11 as an example of the NR region and applying someredundancy elimination scheme, we can obtain that in each of the following
pairs, edges are never simultaneously equal to F:(E1,E4), (E1,E15), (E2,E17), (E2,E21), (E4,E21), (E5,E15), (E5,E23), (E15,E17), (E17,E23), (E21,E23).

In addition, by “rotating” the elimination scheme, we can get six different setsof such pair types; among them is(E1,E16), (E1,E20), (E3,E6), (E3,E20), (E4,E14), (E4,E22), (E6,E14), (E14,E16), (E16,E22), (E20,E22).

For arranging an NR (see Fig. 12 (a)-(d)), we select a part of its B-edges
inside RUC and extend the overlapping subregion into a basic region (as arule, with RRI ≥ 1) possessing pairs of edges that can unblock the invariant
recognition in the RUC. Fig.12 (a) depicts the Fig.11 region as a basic one
and an NR including E1, E3, E15 and E20 as its B-edges and B26 and B28 as its
internal edges. The redundancy eliminations, we are trying to find in this NR,
are related (the edges involved are blue) to E17=B26=F (for the right greylighted cluster) and one of the following cases: E9=E17=F, E9=B26=F, E9=B28=F,
E17=B26=F, E17=B28=F and B26=B28=F (for the left grey-lighted cluster).
Fig.12 (b) also depicts the Fig.11 region as a basic one and the NR including
E7, E11, E12, E15 and E21 as its B-edges and B26 and B28 as its internal edges.
The NR redundancy eliminations involved are related to any two pairs: one ofwhich is taken from E1=E17=B26=F and another from E1=E9=E17=B26=B28=F.
Fig.12 (c) is similar to Fig.12 (b). The difference is in the RUC pp-solution
elimination applied in advance for the right grey-lighted cluster (of Table 7). As
a result, the redundancy eliminations (REs), we are trying to find in the NR,
are related to any two pairs: one of which is taken from E1=E4=E9=E17=24E20=B26=F (the green elements of the pp-solution preserved in the right greylighted cluster) and another from E1=E9=E17=B26=B28=F (the green elementsof pp-solutions in the left grey-lighted cluster). In all cases related to Fig.12 (ac), the pair sets are overlapped; therefore, some single pairs are attempted forboth clusters.

a)

b)

c)

d)

Fig.12. Examples of arranging NRs

In the examples provided, edges involved in the invariant pattern have been
excluded from the NRs. However, the arrangement of NRs with such edges
located internally is also possible. Fig.12 (d) depicts such a case, where theREs we are trying to find are related to any two pairs: one of which is takenfrom E1=E9=E12=E17=B26=F and another from E1=E9=E17=B26=B28=F (such an
NR can be considered as another basic region).
The first step of arranging the NR, as a rule, includes considering a few
directions (of “top, bottom, left and right” types) from RUC for getting a joint
elimination impact of a few NRs; in Fig. 13 (a), these directions are presented
by NR(t), NR(b), NR(l) and NR(r). In addition, to enhance this impact,
alternative eliminations are checked for each direction to decrease thenumber of blocking pp-solutions in the RUC and in a corresponding NR. The
joint elimination failure leads (for the second step) to searching all directions
from an NR with minimum number of blocking pp-solutions. In Fig. 13 (b),
25

a)

b)

Fig.13. Directions of arranging NRs

NR(t) is presented as such an NR and NR1(t), NR1(l) and NR1(r) as its
directions for getting a joint elimination impact. The new joint elimination
failure leads, in its turn, to considering the directions from a new NR which is
selected among all “boundary” NRs (in Fig.13 (b), they are NR1(t), NR1(l),NR1(r), NR(b), NR(l) and NR(r)). In such a way (like a minimum spanningtree), NRs covering the graph and their tree-type chains are organized. Other
details of the NR arrangement within NR chains are presented in the next
subsection.
5.3.

2F pair eliminations in the neighboring regions

2F pair eliminations are based on Hamiltonicity-preserving REs applying in an

NR or in a remote NR (with impact through a chain of NRs) for removing ppsolutions blocking the invariant recognition in the basic region. Eliminating the
NR pp-solutions is related to the edge pair values of the Bj=Bk=F (and/or
Ei=Ep=F, Ei=Bp=F) type.
-

Successful REs in the NR unblock pp-solutions in the RUC and allow
discovering the RUC invariants. In order to reach this goal, we check REs
for each edge pair (above mentioned type) related to each blocking ppsolution in the RUC (pairs are from an overlapping area of the RUC and
NR). The success means that in the remaining NR pp-solutions, there are
not pair edges (in the area pointed to) simultaneously equal to F. Suchsuccess for one pair is enough for removing a related blocking pp-solution.
In fact, REs for each direction from RUC and their joint impact arechecked.

-Unsuccessful REs (or partially successful REs) lead to selecting an NR
with a minimum number of blocking pp-solutions and to extracting fromthis NR pp-solutions which block the success at the current step; these
pp-solutions are based on edge pairs from the NR area which is notoverlapped with the RUC. These pairs are applied for removing theblocking NR pp-solutions by REs in a new NR (the new NR direction is
selected on rules mentioned in the previous subsection). Successful REs
26

(including the joint REs) in this new NR leads to unblocking pp-solutions ina chain of the previous NRs and discovering the invariant in the RUC.
A blocking NR pp-solution is valid, if it is not involved in internal circles of a compound region
including the RUC and NRs (see Appendix 4).

The unblocking failure leads to a new-new NR and so on. In such a way, achain (a tree branch) of NRs is created and extended. In each NR of the chain,a set of blocking pp-solutions is discovered (removing these pp-solutions
unblocks blocking pp-solutions in the previous NRs and in the RUC). The
chain is extended until the unfavorable conditions are discovered in thenewest NR, then another chain is activated (the unfavorable conditions are thelarge number of blocking pp-solutions or absence of the graph space (including fully
covering the graph)).

-Fig.14 illustrates 2F pair elimination issues related to the NR chain growth(at each step we show one direction related to an NR with the minimum
number of blocking pp-solutions). At Fig.14 (a) a RUC is a point forstarting an NR chain. An invariant pattern (let it be E14 = H) is based on
the edge from RUC(b) (the bottom part of the RUC). Edge pairs that caneliminate the RUC pp-solutions with E14 = F are in RUC(t) (the top part of
the RUC), as well as in the b-part of the first NR (NR1(b)) overlapped withRUC(t); let them be E17=B26=F and E9=E17=F (E17=B26=F is related to one
part of the RUC pp-solutions with E14 = F, and E9=E17=F is related toanother part; the parts can be overlapped).

a)b)Fig. 14. Examples of the NR chains-

The failure to eliminate all pp-solutions in NR1 with simultaneous values of
E17=B26=F and E9=E17=F leads to discovering the NR1(t) edge pairs thatcan be applied for possible eliminations of pp-solutions in NR2; let thembe E27=B36=F, E27=B38=F and E33=E36=F. Then we attempt to eliminate all
pp-solutions in NR2 with simultaneous values of E27=B36=F, E27=B38=F
and E33=E36=F. The failure leads to discovering the NR2(t) edge pairs that27

can be applied for possible eliminations of pp-solutions in NR3. In this way,
we can go through the whole graph. In Fig.14 (b) the NR chain makes aloop by returning to the RUC (in fact, the return can be to any previous
NR).
-

The failure to discover the unblocking pp-solutions in NRk-1 requires
finding the 2F pairs in the left part of NRk-1 (NRk-1(l) which is overlappedwith NRk(r) (the right part of NRk)). Then, the absence of blocking ppsolutions is searched for in NRk.

The successful search means that among these pp-solutions there are no 2F
blocking pairs from NRk-1(l) and corresponding REs unblock pp-solutions in
NRk-1,…, NR2, NR1. Such a remote impact allows recognizing the invariant
pattern in the RUC.
The unsuccessful search leads to a deadlock finding the 2F pairs in the RUC
pp-solutions. This means that removing pp-solutions depends on removing
themselves. Then, we cancel the return to the RUC and take another direction(if the graph space is available) or activate another chain.
In such a way, we continue arranging the NR chains (based on directions ofan NR with minimum number of blocking pp-solutions) for covering a larger
and larger part of G and discovering the unblocking pp-solutions.
However, we can assume a special aspect of the search. It is related toincluding all NR pp-solutions in blocking pp-solutions. Such a situation can beassumable because of REs and some other operations (see the next
subsection) used for recognizing previous invariant patterns.

All NR pp-solutions in blocking pp-solutions mean that thecurrent invariant pattern cannot be recognized.
Then, we return to the RUC for selecting a complementing invariant pattern(for example, for E14 = H it can be E13 = H).

Complementing patterns cover all possible pp-solutions (as well as,
global solutions); failures to recognize all complementing patterns
mean the absence of Hamiltonicity.
In the next subsection, we continue the consideration of covering graph G by a treetype composition of the region chains for recognizing an invariant pattern in the root
region of this composition. For this goal, Hamiltonicity-preserving operations of theregional redundancy and the redundancy with a remote impact are employed. They
allow obtaining pp-solutions in all regions and recognizing the invariant pattern or
discovering a Hamiltonian cycle. For the smooth composition of the tree-type chains,28

a flexible region arrangement based on including additional graph space into a region
or on redesigning the regional neighborhood is naturally expected.

5.4.

Invariant pattern recognition in tree-type chains

As we have already mentioned, the minimum number of blocking pp-solutions
is applied as a criterion for arranging the tree-type chains of NRs covering
the graph. At each step of this arranging, all “boundary” NRs are analyzed forselecting an NR which is attached to a corresponding chain. The arranging
goal is in discovering the confirmation of 2F pair eliminations related toblocking pp-solutions of the RUC. A partial or full success unblocks
corresponding RUC pp-solutions remotely through the chain.
In such a way, we arrange and scan all regions covering graph G, and within
this process can get success presented by necessary unblocking recognitionsof 2F pair eliminations and applying them. On the other hand, after arranging
and scanning regions covering graph G, we can get failure presented byexistence of blocking pp-solutions in leaf regions of the tree chains. Thismeans that the invariant pattern cannot be recognized because of potential
existence of global solutions including the blocking pp-solutions in the RUC.
The only chance is to show that all these global solutions are invalid.
In order to reach this goal, we attempt to solve the Hamiltonicity problem ongraph G, but at employing in the regions only the blocking pp-solutions. First,
we require the involvement of all RUC’s pp-solutions infeasible for theinvariant pattern (because the presence of these pp-solutions blocks theinvariant pattern recognition). Then, in each NR, we also take into account all
blocking pp-solutions and exclude other pp-solutions.

Involving a pp-solution, which is not a blocking one in an NR,
means an assumption of a global solution skipping all
blocking pp-solutions in this NR; but this skipping leads to
unblocking the blocking pp-solutions in a chain of NRs andin the RUC.
After that, based only on blocking pp-solutions, in the RUC and each NR, anecessary number of r-invariants are extracted. Then, a system of theequations is composed and solved. Existence of a solution gives us a
Hamiltonian cycle; absence of a solution recognizes the invariant pattern in
the RUC. The number of the blocking pp-solutions in a region is less that the
number of all pp-solutions. This is favorable for extracting r-invariants from theblocking pp-solutions. Nevertheless, we can assume that there are not29enough r-invariants for composing the system of equations. Then, we selectan NR, as a new basic region (a new RUC), and an invariant pattern in it (infact, the old RUC and a new invariant pattern in it can be applied for
exhausting the RUC possibilities). After that, we repeat all operations
presented above for recognizing the invariant pattern in the new RUC (andinvariant patterns in NRs) and solving the Hamiltonicity problem related to the
new slice of blocking pp-solutions.
It is important to note, that there are two fundamental points in our approach.
The first is related to the polynomial complexity. We pay special attention to it
in the next subsection. The second is related to lossless solution operations,which are based on Hamiltonicity-preserving eliminations and on separationsof blocking pp-solutions from pp-solutions recognizing the invariant patterns.
The separation operations (as well as the elimination ones) can apply
alternative choices for arranging the blocking pp-solution slices across theregions. However, any choice is sufficient for recognizing the invariant pattern(in a case of non-Hamiltonicity of the graph where only the blocking ppsolutions in the regions are used) or for getting the problem solution (in a caseof Hamiltonicity of the graph just mentioned).
5.5.

Polynomial complexity of the approach

In order to demonstrate the polynomial complexity of the approach, we
present it in two parts. In the first part, we create a binary tree with apolynomial number of nodes representing Hamiltonicity subproblems.
Different nodes are represented by different slices of pp-solutions employed
across all regions of graph G. The “thickness” of the leaf node slices allows
discovering the necessary number of r-invariants. This discovering is
performed in the second part, which also includes composing the systems ofequations for the leaf nodes and solving the systems. In addition, a final
result, based on results in the nodes, is obtained. Splitting the problem into apolynomial number of subproblems depends on possible schemes related torecognizing the invariant patterns. Fig. 14 -16 depicts four basic schemes.
Scheme 1 (Fig. 15) assumes that blocking pp-solutions, extracted at each
step, and pp-solutions recognizing the invariant pattern, are split into two(more or less equal) parts in each NR. Then, within the first part, the splitting
step is based on selecting a new invariant pattern (in one of the regions) anddiscovering subsets of corresponding blocking and recognizing pp-solutions.
In such a case, after log2N steps the number of pp-solutions in each NR isdecreased by factor N. The number of leaf nodes in the scheme tree is of the2log2N = N level (if necessary, we can take even more steps; for example,
log2N + n steps with n < log2N; in any case, the number of pp-solutions in an
NR is much lesser than N2). As a result, within the second part, it is
discovered that the number of pp-solutions in each region of each leaf node is30

decreased to allow extracting the necessary invariants and solving thecorresponding system of equations. A positive solution, at least in one leaf
node, gives us a Hamiltonian cycle; negative solutions in all leaf nodes meansthat the graph is non-Hamiltonian.

Fig. 15. Two views of the subproblem nodes in scheme 1

Fig. 16. Two views of the subproblem nodes in scheme 2

Scheme 2 (Fig. 16) assumes that blocking and recognizing pp-solutions are
split into two (very unequal) parts in each NR. Then, within the first part, thenumber of pp-solutions in some NRs can be decreased very slowly and inothers very fast. This bias can be stable for some regions. Then, we canassume that the number of splitting steps is of the Π level (Π is the minimum
number of blocking or recognizing pp-solutions in NRs at the moment of theprocess beginning; it is much less than N2). However, the number of thescheme leaf nodes is not of the 2Π level, but the 2Π level. This is because ateach splitting step, the second part operations are employed for extracting
invariants in all regions of two nodes of the tree scheme and for solving thecorresponding systems of equations. As a result, from four nodes of eachlevel only two are used in splitting for the next level.
31

Fig. 17. Subproblem nodes in a combination of schemes 1 and 2

Scheme 3 (Fig. 17) is a combination of schemes 1 and 2. First, it is assumed
that blocking and recognizing pp-solutions are split into two (more or lessequal) parts for k steps (k < log2N). Then, in each scheme node of step k,scheme 2 is implemented. The number of these scheme nodes is evaluatedby 2k and the minimum number (Π’) of blocking and recognizing pp-solutionsin NRs by Π/2k (Π is the minimum number of blocking and recognizing ppsolutions at the moment of the scheme 1 beginning). In other words, within
the first part, the total number of the scheme leaf nodes created after Π’ stepsof scheme 2 is of the 2×2kΠ/2k = 2Π level and, within the second part, thenumber of nodes, where extracting the invariants and solving the systems ofequations are possible, is also of the 2Π level.
Scheme 4 is similar to scheme 2; it assumes that blocking and recognizing
pp-solutions are split into two (unequal) parts in each NR, but the part
inequality is not extremal; for example, in proportion 1 to 3 (or 1 to 4). Then,
within the first part (under conditions of the stable bias of a worse case for us),the fastest decrease of the pp-solutions in corresponding regions requires p
steps to reach factor N with 4p = N and p = (log2N)/2 and the slowest
decrease requires m steps to reach factor N with (4/3)m = N and m =(log2N)/log2(4/3). As a result, within the second part, the number of thescheme leaf nodes involved can be estimated by O(N1/2log2N); this is because
N1/2 is the number of the scheme nodes at level p, log2N(1/log2(4/3) – ½) isthe number of the levels after level p, 2N1/2 is the number of chains going
down after level p and (log2N(1/log2(4/3) – ½))/2 is an average number of leaf
nodes in chains mentioned above.
Any other combinations of these basic schemes and schemes with systematicor chaotic changes of biases in splitting the pp-solutions align (in some sense)
pp-solution slices and also lead to polynomial numbers of the leaf nodes.

32

6. About correctness of the approach
Our approach is based on the existence of redundancy in the graph regions,on Hamiltonicity-preserving eliminations of the redundancy and on discovering
regional invariants within the process of the eliminations and the pp-solution
splits across the regions. This allows efficient reducing of the Hamiltonicity
problem to a polynomial number of the subproblems, which are related todifferent slices of pp-solutions and solved as the systems of linear algebraic
equations. The following points are behind the approach.

Statement 1: Redundancy eliminations in regions preserve at least one
Hamiltonian cycle in the graph, if such cycles exist. Data dependence on
decisions in neighbouring regions excludes introducing incompatibility, which
is not derived from the graph features.

Statement 2: An r-invariant extracted from a set of pp-solutions in a region isvalid on any subset of these pp-solutions. Removing additional pp-solutions
from the set preserves the r-invariant extracted.

Statement 3: An r-invariant discovered in a region is valid for pp-solutions of
any region including edges of the r-invariant.

Statement 4: Removing blocking pp-solutions in any region induces
removing blocking pp-solutions in a chain of regions leading to a root region
from where recognizing an invariant pattern has been initiated. This allows
lossless consideration of the subproblems, based not on decomposing thegraph, but on splitting the sets of pp-solutions across the regions.

Statement 5: The non-Hamiltonicity is discovered by recognizing failures forthe complementing invariant patterns in a region or by inappropriate solutionsof the systems of equations.
All steps of the approach have polynomial complexity including memory weshould expend for saving pp-solutions in all possible sets of overlapping
regions; a rough layout of estimations gives us the following:-

The number of basic regions < N: we need N/2 r-invariants to compose asystem of M equations (for graph G M=3N/2); the r-invariants should befrom all regions of the graph; let the average number of nodes in such a
region be Δ, then N/Δ regions can cover graph G without overlapping;overlapping with four neighbouring regions (as we applied) can involve
two additional layers of the graph tiling to get 3N/Δ regions; in any case, 3
< Δ,

33

-

The number of neighbouring regions in tree chains (TCs) for one basic
regions < N: this is because of the previous item; the total number of theregions covering graph G is less than N,-

The number of pp-solutions in a region is O(N2): the number of different
B-set values is estimated by 2δ, where δ is the number of the region Bedges; we consider regions with ϭ0log2N (ϭ0 ≤ 1) B-edges, this meansthat 2δ is O(N); the number of different pp-solutions for each feasible Bset value is estimated by 2ω, where ω+1 is the number of region interior
faces; we consider regions with RR-index = ©+1 (0≤©≤©, © is aconstant); this means that ω = ©+log2N and 2ω = 2©N = O(N); in fact, anessential number of expected pp-solutions is involved in internal cycles of
H-valued edges or incompatible with n-invariants. In any case, the productof the number of different B-set values and the number of different ppsolutions for each feasible B-set value gives us O(N2).

-

The time to obtain these pp-solutions is O(N2(log2N)3); O((log2N)3) is thetime for solving the regional system of equations for obtaining a ppsolution,-

Total number of pp-solutions in a basic region and in all neighboring
regions related to TCs is O(N3), the total number of pp-solutions in all
basic regions and in all related NRs is O(N4) (in fact, arranging the region
reuse can allow the corresponding pp-solutions’ reuse, too; then N4 canbe replaced by N3),-

The number of operations for selecting the blocking edge pairs in all NRs
for all basic regions (under the condition that pp-solutions in the TCs’
regions obtained) is O(N6(log2N)2): in each region involved, the number ofedges is of log2N level and the number of 2F pairs is O((log2N)2) ; thenumber of comparisons in pp-solutions of one NR for all pairs is
O(N2(log2N)2) and for N NRs and N basic regions is O(N4(log2N)2). K
splitting steps for N/2 invariant patterns leads to O(K×N5(log2N)2) (K < N2).

7. Conclusion
A regional invariant method based on redundancy eliminations has beenpresented and the polynomial solution of the graph Hamiltonicity problem has
been demonstrated. The method includes searching basic and neighboring
regions, considering all possible partial solutions (pp-solutions) within suchregions, and removing redundant pp-solutions. Based on the concept ofboundary communicators, a feasible set of the pp-solutions is arranged foreach boundary case of the region. The redundancy elimination preserves only
one representative pp-solution from each of such sets. Introducing H and F
34

symbolic parameters allows applying systems of linear algebraic equations forthe incompatibility and redundancy eliminations, extracting regional invariantsfrom the representative pp-solutions, as well as for composing a system of thelinear equations and solving a Hamiltonicity problem as a whole. Within themethod, the invariant pattern recognition based on arranging the region
chains for 2F pair eliminations of a remote impact is also applied. 2F paireliminations employ a large-scale type of redundancy which is related not todecomposing the graph, but to splitting the sets of pp-solutions across theregions. This allows efficient reduction of the Hamiltonicity problem to apolynomial number of the subproblems, which are solved as the systems oflinear algebraic equations.
Existence of redundancy and how to eliminate it have been demonstrated. In
fact, this is an answer to questions about where the complexity disappears to
and why P=NP. Different NP-complete problems are related to different typesof redundancy. Therefore, solving such problems should commence withdiscovering corresponding types of redundancy and related equations withsymbolic parameters, as well as with understanding usefulness of possibly
failed retrieval operations.

References
1. M. R. Garey, D. S. Johnson, L. Stockmeyer, Some simplified NP-complete
problems, in STOC '74 Proceedings of the sixth annual ACM symposium on
Theory of computing, ACM, New York, 47-63.
2. N. C. Wormald, Triangles in labelled cubic graphs. In Combinatorial
Mathematics, Springer, 1978, pp. 337–345.
3. Linear solver (matrix method): http://wims.unice.fr/wims/wims.cgi

Acknowledgments
I’d like to express my appreciation to Dr. Lothar Schmitt and Dr. Pierre-Alain
Fayolle for their efforts and patience with reading my various updates. Also, I
want to thank Dr. John Brine and Dr. Alexander Vazhenin for their help andsupport with the material preparation and Dr. Evgeny Pyshkin, Dr. Maxim
Mozgovoy and Dr. Taro Suzuki for their interest and involvement.

35

Appendix 1

A subset of rules for reasoning about edge values
Ej = F - H + Ek → Ej = F, Ek = H
Ej = 2H - Ek

→ Ej = H, Ek = H

Ej = H - F + Ek → Ej = H, Ek = F
Ej = 2F - Ek

→ Ej = F, Ek = F

Ej = 3H - Ek - En → Ej=Ek=En= H

Ej = 2H - 3Ek + 2En → Ej = Ek = En = H

Ej = H–2F + Ek + En → En=Ek= F, Ej = H

Ej = 2H-F + En - Ek → Ej=Ek=H, En = F

Ej = 2Ek – En

→ Ek = E n

Ej = 2H + F - 2Ek→ Ej = F, Ek = H

Ej = (F + Ek)/2→ Ej = Ek = F

Ej = (2H + F - Ek)/2→ Ej = H, Ek = F

Ej = (Ek + En)/2→ Ek = En

Ej = (Ek + 3En –2F)/2 → Ej = Ek = En =F

Ej = (4H + F - 3Ek)/2 → invalid

Ej = (2Ek + 2En – F)/3 → Ej=Ek=En = F

Ej = (Ek+En + H)/3 → Ej=Ek=En=H

Ej = zH - E1-E2 -…- Ez-1 → Ej=E1=…=Ez-1=H(Ej = 2H+F - En - Ek) & (Ez = En + Ek

(Ej = En + Ek – H) & (En + Ek = H+F) →Ej = F- F)→

Ej=Ez=H, En + Ek = F + H→ En = E j(Ej = 2H + F - En - Ek) & (En = Ek) →En = Ek = H, Ej = F

Ej = 3H + F – Ek - 2En → En = H(Ej = 3H + F – Ek - 2En) & (Ez = Ek+3En

Ej = ∑𝑘𝑖=1 𝑐iHi - ∑𝑝𝑡=1 𝑑tHt → ∑𝑘𝑖=1 𝑐 i ∑𝑝𝑡=1 𝑑 t = 1 (ci, dt – integers; Hi, Ht –Ej = Ek - En + H + F(Ek + En = F + H) & (Ek + Ej = F + H)

- 2H - F) → En = H, Ek = Fedges or H or F)

36→ invalidAppendix 2
Maximal possible number of irremovable pp-solutions for k pairs of H-valued
B-edges
k=1: s1 = 1
k=2: s2 = 3s1 – 1 = 3 – 1
k=3: s3 = 3(3 – 1) – 1 = 32 – 3 - 1
k=4: s4 = 3(32 – 3 -1) – 1 = 33 - 32 – 3 - 1
k=5: s5 = 3(33 - 32 – 3 -1) – 1 = 34 - 33 - 32 – 3 - 1…
k=p: sp = 3(3p-2 – 3p-3 – …– 3 -1) – 1 = 3p-1 – 3p-2 –… – 32 – 3 – 1 = 3p-1/2 +1/2

Fig. A. Schemes of irremovable pp-solutions for 1 and 2 pairs of H-valued B-edges

Fig. B. Schemes of irremovable pp-solutions for 3 pairs of H-valued B-edges

The number of irremovable pp-solutions for a B-set value with 2k H-valued B-edges(1≤k≤p) and 2p+1 faces is limited by 3k-1/2+1/2 and the total number of (removable andirremovable) pp-solutions is limited by 22p (k and p are of a logarithmic level). Inequality
22p > 3k-1/2+1/2 is enhanced for regions with greater values of RR-index.

37

Appendix 3
2F pair eliminations in the NR chains
1. In each pp-solution intended for the elimination (that is a pp-solution blocking
an invariant recognition in a BR (basic region)), we find all pairs (Ej,Ek) ofedges (from overlapping area of NR-BR) with Ej=Ek=F values; the pairs of all
pp-solutions are united in one set (let their number be φ).
2. For each pair (Ep,Ez) of the set, we check all clusters of pp-solutions in the
NR for possible REs’ removal of the BR pp-solutions that block the invariant
recognition. Within a cluster, REs are fully performed only if there are notdecision alternatives. Otherwise, eliminations with alternative pp-solutions(where Ep=Ez=F is invalid) are postponed (for flexibility in further operations).
As a result, for each pair we find a number (which can be 0) of blocking ppsolutions with Ep=Ez=F. The pairs are sorted by ascending value of thenumber: P1, P2, P3, …, Pφ,
3. A subset of pairs, with the zero sum of the numbers and related to all blocking
pp-solutions in the RUC, leads to recognizing the invariant pattern in RUC,
under conditions of independency of REs induced by different pairs.
4. In cases with dependencies, for each pair Pj (1 ≤ j ≤ φ) from step 2,
sequences of the following type are created:
P1, P2, P3, …, Pφ
P2, P1, P3, …, Pφ…
Pj, P1, P2, …, Pj-1, Pj+1, …, Pφ…
Pφ, P1, P2, …, Pφ-1.
Then, REs on the NR are performed according to each sequence and thenumber of blocking pp-solutions remaining is extracted. After that, asequence with the minimum of the blocking pp-solutions is selected for further
operations in a new NR.
5. In the new NR, steps 1, 2, 3, and 4 are performed in areas that are arranged
by replacing the BR by the NR and the NR by a new NR. A remaining ppsolution is recognized as such, if it is not involved in local cycles (within thecompound region including BR and chain’s NRs).
6. This step is repeated for new regions until recognizing the invariant pattern orcovering the graph by the tree construction of the region chains.
2F pair eliminations in the NR chains are Hamiltonicity-preserving eliminations that
support arranging remote relations of blocking/unblocking types between ppsolutions. Blocking relations provide a set of pp-solutions in G-region with aconditional impact on a set of pp-solutions in D-region. The conditional impact meansthat removing (because of some reason) the set from G-region leads via an NR chain
to removing the corresponding set from D-region. Unblocking relations provide a setof the D-region pp-solutions that are a basis for discovering, via an NR chain, the Gregion pp-solutions, which unconditionally (because of redundancy eliminations)remove the D-region pp-solutions.

38

Appendix 4
Involvement of the blocking NR pp-solutions in internal H-valued circles

Here, we clarify checking possible involvement of the blocking NR ppsolutions in internal H-valued circles of a compound (c-) region including the
RUC and NRs. Such involvement eliminates blocking pp-solutions related andavoids additional operations for taking them into account. The checking is
performed at each step of the NR chain construction.
In the first step from the blocking RUC pp-solutions, we extract Bcommunicator pairs of B-edges that are internal to NR1(b) (see Fig. 14 (a)).
Then based on these pairs for each blocking NR1 pp-solution, we check its
involvement in the cycles within the c-region of NR1-RUC. In addition, Bcommunicator pairs (being internal in NR2(b)) of the c-region NR1-RUC ppsolutions are saved (if any).
In the second step, based on the B-communicator pairs saved, we check the
involvement of blocking NR2 pp-solutions in the circles within c-region NR2NR1-RUC and preserve its B-communicator pairs (being internal in NR3(b)).
Other steps are similar to the previous ones. In fact, instead of a pp-solutionof NRk, its part (a pp-solution of NRk(t)) is employed. The B-communicatorpairs saved at step k represent returning paths within c-region NRk-…-NR2NR1-RUC.
H-valued circles can be discovered not only in the linear chains, but also in
the NR chain loop (like at Fig. 14 (b)). For reaching this goal, in addition to thereturning paths, we save B-communicator paths, each of which has aninternal for NRj+1(b) B-edge of c-region NRj-NRj-1-…-NR1-RUC and aninternal for NRk(r) B-edge of the same c-region. With such data saved, we
can efficiently discover the internal cycles inside some c-regions.

39