Algorítmica y complejidad computacional. DCBs: Algunos casos ¿ nuevos ? y ¿ difíciles ?.

He estado releyendo literatura más relacionada con nuestra investigación y he identificado algunos casos nuevos, que en algunos casos los autores señalan como difíciles, y cuyas propiedades estructurales quiero determinar, siempre y cuando esto no me exija reprogramar las implementaciones que ya tengo.

1. Tesis de Effler y/o Shields.

–Caso 1 (citado en páginas 72 y 73). Generadores (34)(56); (03) (1425), de A7 (2520 vértices) y del tipo  C2C4. Sí tiene ciclos según Shields, como grafo.

0124365, 3450216. IAS 7.  Circunferencia 6 (de 6 IASES). Este si lo tratamos como dígrafo (sin añadir el inverso de la no involución) es de tipo Rankin. De tal  modo no tiene ciclos. Entangled sólo por ser un generador una involución (sólo x C2). Por sus parámetros tiene pinta de ser complicado (twisted) como digrafo.

–Caso 2 (citado en páginas 72, 75, 76). Generadores (0123) (45) (6); (0) (1) (2) (34)  (56). Es un caso de A7, del tipo C2C4 y sí tiene ciclos hamiltonianos como grafo (pero fue complicado encontrarlos). 0124365, 1230546. IAS7. Circunferencia 4. Entangled sólo x C2. Posiblemente twisted (este podría serlo con mayor razón que el anterior). De tipo  Rankin y por lo tanto como digrafo sin ciclos. Este caso tiene propiedades interesantes. Es posible que intentemos determinar si es twisted o no.

Sobre estos dos casos, también citados por Shields, este autor comenta:

The Work of Effler and Ruskey
At about this time Effler and Ruskey [36] started cataloging results for isomorphism and Hamiltonicity
of Cayley graphs. They had confirmed that all but two of the cubic Cayley graphs on the
alternating group, A7, with generators from S7 were Hamiltonian. They had spent thousands of hours
of computer time on one of these using algorithms that had succeeded on similar graphs without finding
a Hamilton cycle and were about to embark on an exhaustive search on a supercomputer.

We were invited to try our algorithm on these graphs. The graph A7 has 2520 vertices and the
first set of generators was (0)(1)(2)(3, 4)(5, 6) and (0, 1, 2, 3)(4, 5)(6). We made further modifications to
the Vandegriend code to handle graphs generated by one involution and one non-involution. Using this
version of the Vandegriend algorithm we found a Hamilton cycle within a minute or so of computation
time.

Effler and Ruskey had also been unable to find a Hamilton cycle in the Cayley graph of A7
generated by (0)(1)(2)(3, 4)(5, 6) and (0, 3)(1, 4, 2, 5)(6). Again, the modified Vandegriend code found a
Hamilton cycle within a minute or so of computation time.

Nevertheless, the Vandegriend algorithm slowed down significantly on larger problems. For example,
we did not find a cycle using this algorithm on the graph with 2520 vertices generated by the
involution (03)(14)(25)(6) and the element (0)(1)(2)(3456) and its inverse which is result7.294 in the
table of Effler and Ruskey (Section 6.4).

Este último pasa a ser nuestro

–Caso 4. Generadores (o3) (14) (25) (6);  (0)(1)(2)(3456), de A7 y del tipo C2C4. 3450126, 0124563. IAS 7. Circunferencia 10. Idem anteriores. Entangled sólo por C2. De tipo Rankin como dígrafo no tiene ciclos. O twisted o sin problemas. Menos posibilidades de ser twisted que los dos anteriores. Pero todavía podría serlo.

–Caso 5 (citado en página 79). Generadores. (12) (34) (56) (78); (013) (245) (78). Del tipo C2C6. IAS12. Circunferencia 3 (6 IASES). Entangled sólo x C2. Muy probablemente twisted, por los parámetros. Pero no me queda claro el orden de este dígrafo y dependerá de esto (Ramyaa, que también ha bebido de la base de datos de Ruskey y Effler, nos habla de un caso de 2880 vértices cuyas propiedades de hamiltonicidad son desconocidas; ¿ será éste ?. ¡¡Voy a comprobarlo!!. No parecen ser de este orden. Tampoco de 2520. Pueden generar grupos mayores de orden: 4320 confirmado NO,  5040 NO, 10080 ¡¡ SI!! (salvo que el programa que diseñé  para esto funcione mal cosa que no creo pues lo he comprobado en múltiples casos; estoy haciendo una comprobación adicional: ¡¡ confirmado !!; por el camino he descubierto una mínima modificación del programa que permite encontrar el orden del grupo dados los dos generadores y que genera todas las permutaciones) y menos mal, 20160, 40320, 181440, 362880, este último S9. Voy a ir probando aunque alguno de estos tamaños me puede reventar el PC). Este caso quedó Unknown en el momento de redactar la tesis de Effler. Nos gustan los unknown. Se nos dan bien…Pero en este caso hay una novedad: ni es cycle-entangled ni es 1/2-entangled, como todos los otros unknown (de S6). Aun así es bastante restringido. Tenga el lector en cuenta que la para un orden de 10080, la circunferencia va a contener sólo 72 permutaciones diferentes.

La tesis de Effler es de 2000. En 2003 este caso seguía abierto:

Hamilton Cycles in Small Cubic Cayley Graphs

Frank Ruskey University of Victoria fruskey@cs.uvic.ca

We report on some exhaustive computer searches for Hamilton cycles in small cubic Cayley graphs and in small two-in two-out Cayley digraphs. One perplexing Cayley graph of 10080 vertices has resisted our attempts to show that it is Hamiltonian. (Scott Effler, Brendan McKay, Alex Hertel, Philip Hertel, and Ian Shields all contributed to the searches.

2. Tesis de Shields. Basado en la Tabla 6.1.Nuevos pero no necesariamente difíciles. Miraremos sus propiedades.

With this change we had more success with our heuristic, although we often required multiple attempts with a different random number seed on each attempt. Our successful results for some of the graphs used by Effler and Ruskey [36] generated by an involution and an element of Sn that is not an involution are shown in Table 6.1. The name shown is the internal name for the graph as used by Effler and Ruskey. In Section 6.5 we shall discuss characteristics of graphs where our heuristic was unsuccessful

Es decir en la tabla aparecen aquellos casos en los  que su heurística (no es un algoritmo) funcionó bien.

Table 6.1: Cubic Cayley graphs generated by one involution and one non-involution.
Running time and number of attempts before successfully finding a Hamilton cycle in Cubic Cayley
graphs generated by one involution and one non-involution.

|G|; Diameter; Shortest Odd Cycle; Shortest Even Cycle; Time (seconds); Attempts; Name.

–1,512 (0)(12)(34)(56)(78); (013)(2)(457)(6)(8); 20; 3; 18; 3; 9 result9.1853.

–2,160 (0)(1)(2)(34)(56)(78); (03)(1478)(25)(6); 18 none 4 1 1 result9.1166.

–2,160 (0)(1)(2)(34)(56)(78); (03)(1564)(27)(8); 18 none 4 1 1 result9.1337

–2,520 (0)(1)(2)(34)(56);  (0123)(45)(6); 19 21 4 1 1 result7.102

–2,520 (0)(1)(2)(34)(56); (03)(1425)(6) 19 27 4 2 5 result7.154

–2,880 (0)(1)(2)(34)(56)(78); (0134)(2576)(8) 24 none 4 1 1 result9.874

–5,040 (0)(12)(34)(5 6); (01)(2356)(4) 23 27 4 4 7 result7.1000

–5,040 (0)(12)(34)(56); (0123)(45)(6) 23 25 4 1 1 result7.1009

–5,040 (0)(12)(34)(56);  (0132)(45)(6); 20 27 4 1 1 result7.1020

–5,040 (0)(12)(34)(56); (0135)(2)(46); 19 27 4 1 2 result7.1034

5,040 (0)(12)(34)(56);  (013)(245)(6); 28 3 20 36 2211 result7.1037.  En este caso se necesitaron múltiples intentos para obtener el ciclo (en modo grafo pero podemos especular que esta dificultad esté relacionada con una dificultad  en modo dígrafo; veamos). Sus parámetros son S7, C2C3 (interesante por su relación con los casos de Milnor).

–5,040 (0)(12)(34)(56);  (0135)(24)(6); 19 27 4 3 3 result7.1044

–5,040 (0)(12)(34)(56); (013)(254)(6); 28 3 20 27 1472 result7.1048. Idem anterior.

–5,040 (0)(12)(34)(56); (0134)(25)(6); 23 25 4 2 3 result7.1058

–5,040 (0)(12)(34)(56); (0136)(25)(4); 19 25 4 1 1 result7.1069

–5,040 (0)(1)(2)(3456); (03)(14)(25)(6); 25 none 4 1 2 result7.294

–5,040 (0)(12)(34)(56);  (01)(2345)(6); 23 27 4 1 1 result7.996

–5,040 (0)(12)(34)(56);  (01)(2354)(6); 20 29 4 3 4 result7.998

–5,040 (0)(1)(2)(34)(56)(78); (03)(1425)(6)(7)(8); 20 29 4 2 2 result9.1129

–5,040 (0)(1)(2)(34)(56)(78); (03)(1425)(6)(78); 27 none 4 2 2 result9.1130

–5,040 (0)(1)(2)(3)(4)(56)(78);  (01)(25)(3647)(8); 21 27 4 2 2 result9.124

–5,040 (0)(12)(34)(56)(78); (01)(2345)(6)(7)(8);  23 27 4 1 1 result9.1501

–5,040 (0)(12)(34)(56)(78); (01)(2354)(6)(7)(8); 20 29 4 4 4 result9.1515

–5,040 (0)(12)(34)(56)(78); (01)(2356)(4)(7)(8); 23 27 4 5 7 result9.1533

–5,040 (0)(12)(34)(56)(78); (0123)(45)(6)(7)(8); 23 25 4 1 1 result9.1623

–5,040 (0)(12)(34)(56)(78); (0132)(45)(6)(7)(8); 20 27 4 1 1 result9.1733

–5,040 (0)(12)(34)(56)(78); (0135)(2)(4)(6)(78); 25 none 4 1 1 result9.1894

–10,080 (0)(12)(34)(56)(78); (01)(2356)(4)(78); 27 none 4 21 51 result9.1534

–10,080 (0)(12)(34)(56)(78); (0123)(45)(6)(78); 26 none 4 9 15 result9.1624

–10,080 (0)(12)(34)(56)(78); (0132)(45)(6)(78); 27 none 4 5 3 result9.1734

Comentarios de Shields.

If Cay(G : S) is cubic then either X is a set of three involutions or a set consisting of one involution and one element of G that is not an involution. The latter type can be studied as either a directed graph or an undirected graph but our research focuses on the undirected form

A nosotros nos interesan los segundos en forma de dígrafos. Notese que al añadir un generador más (el un inverso), la cosa se hace más sencilla, pues movimientos que antes no eran posibles ahora lo son.

After our success with other types of vertex transitive graphs we were very surprised when we were not able to find results. Our heuristic, even when allowed to try a large number of times with a different random number seed each time, was unable to find Hamilton paths or cycles in Cay(S7, X7) which has only 5,040 vertices. We decided to run a simple backtrack algorithm with no pruning or other enhancements as a comparison. This eventually ran for over a year on a 300MHz Intel processor without finding a Hamilton cycle.

En este último comentario se refiere a los cúbicos 3 generados. Luego utilizaron otro algoritmo genérico para cúbicos diseñado por Vandergriend.

Although we had some success with smaller graphs generated by three involutions, this code was still problematic when graphs contained a couple of thousand vertices. Nevertheless, we were able to answer some previously unsolved questions as we shall see in Section 6.2.3.

From the results in Table 6.1 it can be seen that this version of our algorithm was usually able to
find a Hamilton cycle in a relatively small number of attempts, when it could find one at all. For this
size of cubic Cayley graph, the graph was constructed and the cycle usually found in a matter of a few
seconds. Nevertheless, two of these graphs required over 1,000 attempts to find a Hamilton cycle.
This version of the algorithm was able to find a Hamilton cycle quickly in the graph with 2520
vertices generated by the involution (03)(14)(25)(6) and the element (0)(1)(2)(3456) and its inverse
which had defied our eorts with the Vandegriend algorithm (Sec 6.2.2). However, our algorithm was
still unsuccessful in finding a Hamilton cycle in many graphs, even with as many as 100,000 attempts as
was the case with the graph generated by the three involutions (0)(1)(24)(36)(5), (01)(2)(3)(4)(56) and
(02)(13)(4)(5)(6) which has diameter 16, a smallest odd cycle of 21, and a smallest even cycle of 6. This
is the graph, result7.10108, in the table of Eer and Ruskey (Section 6.2.3).
A common feature of most of the graphs where we were unsuccessful seems to be the diameter
of the graph which tends to be among the larger possible diameters for these graphs, often with a small
minimum even cycle.

Hay más tablas con más generadores pero son de la segunda clase de grafos cúbicos  y tienen tres generadores. De momento se salen un poco de nuestro campo de estudio.

3. Artículo de Curtin.

Cubic Cayley graphs with small diameter

Curtin no ha investigado el problema de RH sino el de grado /diametro. Pero el objeto es el mismo. Nos proporciona unas tablas con generadores.

Algunos comentarios del autor.

Delorme [Del85] defines b(∆,D) as the largest integer such that a bipartite graph on b(∆,D) vertices with maximum vertex degree ∆ and diameter D exists. The diameter 7 graph on 168 vertices and the diameter 12 graph on 2160 vertices in Table 3 are bipartite. Other large bipartite graphs found include a diameter 10 graph on 672 vertices of girth 8 and generator set {(12)(34)(56)(910), (13)(57)(68)(910), (14)(25)(38)(67)(910)} and a diameter 9 graph on 360 vertices with girth 10 and generator set {(12), (2678)(345)}. The resulting bounds b(3,9) ≥ 360 and b(3,10) ≥ 672 match those obtained in [BD88], and the bound b(3,7) ≥ 168 improves the bound given there. However the cubic symmetric graphs F364E and F720C of the Foster Census [Roy01] improve these bounds to b(3,9) ≥ 364 and b(3,10) ≥ 720. The Foster Census includes a complete listing of the cubic symmetric graphs of up to 768 vertices, so all of our smaller graphs have isomorphic copies on this list. None of the examples supersede the records for the smallest cubic graphs of given girth. The most notable example for girth was the bipartite graph with generator set {(12)(34)(56), (13254678)(91011)}, which has 1008 points, diameter 12 and girth 16. The smallest known graph of girth 16 has 990 points. See [Big98] for a survey of girth results. In Tables 2 and 3 below diameter is denoted by D, the order of the graph by n, and the girth by g. We indicate in the b column whether or not each graph is bipartite.

4. Tesis de Ramyaa. Tabla. 

Ramyaa utilizó la base de datos de Ruskey y Effler para testar sus algoritmos que son probabilísticos. También parten de la base del IAS y sus dos posibles activaciones.

Ella tenía muy claro el concepto de IAS e incluso en la tesis aparece un dibujo con tres de ellos, regulares. Otros investigadores utilizan este concepto implícitamente. Pero no aclara que puede haber IASes regulares e irregulares ni que los primeros están sobre todo vinculados con casos no conmutativos (hay conmutativos con el IAS regular y ya hemos dado las condiciones que tienen que cumplir).

Ni tampoco en base  a este concepto identifica las propiedades estructurales relevantes para el problema RH que hemos identificado nosotros. Las que son generadoras de obstrucciones.

Cuando conoces que hay IASes irregulares y las obstrucciones que generan determinadas propiedades estructurales, determinar que un caso tiene el IAS regular y ninguno de los dos generadores es una involución, ya es altamente informativo

Su algoritmo elige al azar el número de IASes que va a activar por cada generador.

Extracto.

Although a random 2 regular digraph does not contain a lot of Hamilton
cycles, Cayley graphs are very structured and most of them are Hamiltonian.

Creo que este comentario, que no está claro del todo pues no se sabe a que tipo de digrafos de Cayley se refiere, se puede matizar. Pero no lo vamos a hacer ahora.

It is
reasonable to expect that randomized algorithms using the structure of Cayley graphs will
have a good chance of finding Hamilton cycles. While this has proved to be true, i.e.
increasing the restrictions which exploit more and more of the structure of Cayley graphs
result in an increase in performance, most of the inherent structure was not captured by
these algorithms. They were unable to find Hamilton cycles in graphs with a very large
number of vertices, even though they were Hamiltonian.

The results are presented in Table 2. In the table, m denotes the number of τ
cycles along the Hamilton path, rnd denotes the number of trials the random algorithm
took, τ denotes the number of trials τ restrictions took and σ denotes the number of trials
σ restrictions took. For each vertex size reported, the website presented many nonisomorphic
graphs. Each algorithm was tested on all these graphs. However, as the
number of trials needed was extremely graph dependent, the values were not averaged.
Instead, the values for the first graph presented are reported. When Hamilton cycles could
not be found for some graphs while some others of the same vertex size were found to be
Hamiltonian, the table reports the failure as “xxx”, except for the vertex size of 2880.
There is a graph of vertex size 2880 for which hamiltonicity is unknown. Though our
algorithms do not find this, they were able to solve anther graph of the same size. So, this
is reported. For each vertex size, the table gives the values of a) the number of trials the
random algorithm needed to find a Hamilton path; b) the number of trials τ restrictions
needed to find a Hamilton path; c) the number of trials σ restrictions needed to find a
Hamilton path.

5. Tesis de Bijaya Rath. 

Su interés es sólo de cúbicos de segunda clase hasta S7. Hay múltiples triples de permutaciones.

Los casos cúbicos son los más estudiados por su relación con el problema y/o conjetura de Lovasz (esta conjetura tiene otros nombres). Todas las excepciones para los grafos vértices transitivos son cúbicas.

Como ya hemos comentado en otras entradas, un dígrafo de Cayley bigenerado que se puede convertir en cúbico de clase 1 es un objeto muy diferente a un Grafo de Cayley cúbico de clase 1. Añadir un generador cambia bastante. Si el dígrafo es hamiltoniano (ciclos o caminos) obviamente el correspondiente grafo también los será. Pero la reversa de esta proposición no se sigue: añadiendo un arco inverso, se puede convertir un dígrafo sin RHs en un grafo hamiltoniano. Si no fuese así la conjetura de lovasz ya se hubiese demostrado ser falsa.

Hay mucha literatura sobre los casos cúbicos que no vamos  a revisar. A continuación, algunos destacados, por su relación con nuestro tema.

Otros artículos en la misma línea:

–En este caso tratan de una clase de cúbicos de la clase 1, en modo grafo y por lo tanto no directamente comparables con  nuestros casos.

Hamiltonicity of cubic Cayley graphs

Received September 1, 2005 and in revised form September 11, 2006

Abstract. Following a problem posed by Lovasz in 1969, it is believed that every finite connected ´ vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from finite groups having a (2, s, 3)-presentation, that is, for groups G = ha, b | a 2 = 1, b s = 1, (ab)3 = 1, . . .i generated by an involution a and an element b of order s ≥ 3 such that their product ab has order 3. More precisely, it is shown that the Cayley graph X = Cay(G,{a, b, b−1 }) has a Hamilton cycle when |G| (and thus s) is congruent to 2 modulo 4, and has a long cycle missing only two adjacent vertices (and thus necessarily a Hamilton path) when |G| is congruent to 0 modulo 4.

Este paper ha tenido sus secuelas. la situación en 2016 es la siguiente:

Theorem (Glover, Maruˇsiˇc, Kutnar, Malniˇc, 2007–2012).

 Let K = Cay(H; r,r −1 , l) be a cubic Cayley graph, where H = hr, l | r s = l 2 = (rl) 3 = 1, . . .i is a finite quotient of the modular group PSL(2, Z). Then K has a Hamilton path.

Moreover, if |H| ≡ 2 (mod 4) or if |r| ≡ 0, ±1 (mod 4), then K has a Hamilton cycle.

Anuncios

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: