Archive for the ‘ALGORITHMICS, NEW SUBRUTINES’ Category

HPC. Novedades investigacion.

agosto 20, 2017

Disclaimer. Escribimos la entrada desde el smartphone. Nos es complicado poner acentos. Pedimos disculpas al lector por ello.

Pocas entradas ultimamente eh ? Muchos motivos lo explican. Entre otros el smartphone, un autentico killer. Pero no solo esto.

Lamentablemente, pese a lo planificado tambien poca investigacion. Por los mismos motivos. Pero si he pensado mentalmente en algunos temas que queremos resumir muy brevemente en esta entrada y que desarrollaremos en otro momento. Lealos el lector como unas reflexiones no muy maduradas en voz alta que pueden ser incorrectas, sobre todo la parte que se refiere a los casos twisted.

–Primero, cuando un caso al aplicar el metodo de la escalera queda fuera del rango factible esta claro que no puede tener RHs. Pero que pasa cuando queda dentro ? Hemos dado por supuesto que entonces tiene RHs, y asi es, pero hay que demostrarlo.

–Segundo, una vez demostrado esto, es facil demostrar que cuando un caso es smooth, entonces necesariamente tiene RHs en todos los vertices finales posibles. Basta con demostrar que en estos casos aplicando el metodo de la escalera siempre caeremos en la region factible, y edto es facil ver que tiene que ser asi.

–Tercero, hay que demostrar que el caso medio (aquel que obtenemos al seleccionar al azar un par de permutaciones de Sn) es smooth. Ya hemos hablado en otras entradas sobre el valor de los parametros que tendra este caso medio: n^log n creo recordar (escribo de memoria basandome en un resultado de terceras partes). Este valor para todos los parametros: orden de los generadores, orden del ias, orden de la circunferencia.

Nota al margen.

Siempre volvemos a este tema. La ultima vez fue en marzo de 2016:https://ireneses.wordpress.com/2016/03/13/algoritmica-y-complejidad-computacional-algunos-resultados-sobre-permutaciones/. No fue la primera. El resultado es de Erdos-Turan. Luego ha sido revisitado. El concepto de orden medio de una permutacion existe tambien pero nos interesa menos.

Cuando decimos permutacion media queremos decir tipica y su orden tiende o esta acotado por n^raiz cuadrada de log n. Faltaba la raiz cuadrada en la formula que hemos dado de memoria.

Fin de nota..

–Cuarto, aunque hay avances sigo sin tener del todo claro algunos temas relacionados con los casos twisted. Al contrario, casi todo lo relacionado con los casos entangled esta claro.

Con respecto a los twisted, aunque no tengo claro si habra 3-twisted, 4-twisted etc…si parece claro que, si estos casos existiesen, los efectos de esta propiedad se tienen que diluir a medida que n crece. Cuando digo diluir quiero decir que se atenuan, o mas tecnicamente que el multiplicador disminuye. Lo veo claro, pero hay que demostrarlo. Primero que existen casos 3-twisted, 4-twisted etc…y segundo que los efectos se diluyen.

Tambien establecer un criterio claro que distinga estos casos n-twisted de los smooth. Ya hemos comentado sobre este tema en entradas anteriores.

En un caso smooth el entorno de la identidad, segun lo hemos definido, quedaria saturado. Esto nos lleva a una situacion paradojica: si esta saturado entonces es smooth; si no lo esta entonces sera 1-twisted o 2-twisted. Son posibles entonces, repetimos los casos 3-twisted, 4-twisted etc…Es lo que no conseguimos, desde hace tiempo, visualizar bien. Por ello quiero hacer comprobaciones adicionales al respecto y aterrizar este tema definitivamente.

Al hilo de todo lo comentado hasta ahora, es oportuno matizar un comentario anterior. No esta claro que el caso medio o mas bien tipicio sea, el que tiene los parametros indicados , sea smooth. Si es seguro que el caso medio tiene que ser o smooth o twisted (? 1-twisted, 2-twisted?) ?. Los casos entangled y cycle-entangled son muy restringidos. La pregunta clave es si este tipico o medio se satura asintoticamente o no se satura. Para contestarla hay que hacer calculos avanzados.

Una reflexion al respecto: si fijamos los parametros un caso smooth solo se puede dar de una manera, pero uno twisted se puede dar de varias. Tambien uno entangled. Simplificando mucho, si el valor de los parametros es X, en teoria puede haber 1 caso smooth, X casos entangled, y X^2 1 -twisted. Los casos cycle-entangled son necesariamente entangled y por lo tanto estos ultimos son cota superior. Todo esto es un calculo puramente teorico y estamos dando cotas superiores. Teniendo en cuenta que hablamos de objetos altamente estructurados, la realidad puede ser muy otra a lo permitido por la teoria que no tiene en cuenta esta estructura. Pero si la realidad no se aleja de la teoria,  de la cota superior, los casos twisted tienen que ser los mas abundantes y los smooth extremos.

Pero por otra parte el hecho de ser twisted (sobre todo si es 1-twisted o 2-twisted) limita el tamano  o el crecimiento del caso. Teniendo en cuenta el valor de los parametros del caso medio y que si lo relacionamos con n! el limite tiende a cero, no parece posible que el caso medio pueda ser twisted. En fin, ya se ve que este tema esta bastante confuso.

Quinto, la gran incognita sigue siendo como encajar los casos cycle-entangled en el metodo de la escalera.

Finalmente, tenemos pendiente encajar el tema del metodo de la escalera con el tema de la distribucion de la complejidad de casos por grados. Este ultimo es un tema sobre el que hicimos varias entradas hace anos.

P.s. Hemos seguido con interes los acontecimientos de este verano relacionados con el problema clasico de comlejidad computacional, que para algunos es el fundamental y para otros es uno mas…

 

 

Algoritmica y complejidad computacional. La complejidad de resolver el Cubo de Rubik de manera optima.

julio 9, 2017

Se ha publicado recientemente un articulo sobre el tema que indicamos en el titulo.

Nota. No se muy bien como cortar y pegar un enlace en el espacio habilitado para ello en wordpress, en el smartphone.

En general hay bastantes cosas que se pueden hacer en un portatil y no se como hacer en el smartphone, o no se como hacerlo de manera rapida.

Ya he aprendido. Pero el comentario general aplica…

Otro ejemplo es marcar un bloque completo de texto, para cortar y pegar o darle el formato adecuado. Siempre se marca solo una palabra.

Ya se como hacerlo en general pero no al editar un post en wordpress. Ya se como hacer esto tambien. No era evidente.

En fin, poco a poco…

. Fin de nota.

Solving the Rubik’s Cube Optimally is NP-complete.

Erik D. Demaine∗ Sarah Eisenstat∗ Mikhail Rudoy†

Abstract.

In this paper, we prove that optimally solving an n×n×n Rubik’s Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This improves the previous result that optimally solving an n×n×n Rubik’s Cube with missing stickers is NP-complete. We prove this result first for the simpler case of the Rubik’s Square—an n × n × 1 generalization oft he Rubik’s Cube—and then proceed with a similar but more complicated proof for the Rubik’s.

Nuestro interes en el articulo va mas alla de lo anecdotico (el hecho de que hable de un puzzle muy conocido), y lo estamos leyendo con atencion.

En particular nos interesan en el dos puntos:

–primero, en la cadena de reducciones aparecen los hipercubos, que como es bien conocido, son grafos de Cayley.

–segundo, la reduccion lo es del problema RH a un ? problema de camino mas corto ?. Signos de interrogacion pues esto ultimo no lo tengo claro.

Por otra parte me ha sorprendido conocer que la version cuadrada es mas “compleja” que la cubica. Pensaba que era lo contrario.

Comentar que el problema se queda en NP pues el diametro del tipo de grafos que representan el problema es polinomico.

P.s. En el blog hemos publicado mucho sobre la posible complejidad computacional del problema de nuestro interes. Ya tenemos intuitivamente claro el tema. Pero solo intuitivamente. Hablo de la version normal, no de la sucinta. De ahi nuestro interes en este articulo.

Actualizaciones.

(more…)

Algorítmica y complejidad computacional. Un caso de A5 (60 vértices) sin osbtrucciones pero con obstáculos.

mayo 23, 2017

1.Estoy poniendo a prueba el método de la escalera con este caso, que que me sirve para testar varios temas:

(more…)

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

mayo 21, 2017

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.

(more…)

Algorítmica y complejidad computacional. DBCs: Novedades.

mayo 20, 2017

Me está pasando una cosa extrañísima: no puedo entrar en mi blog desde ninguno de los ordenadores de mi vivienda, pero sí desde otros (desde un cibercafé).  Ni para editar ni para ver entradas. Los problemas son sólo para entrar en mi blog y en otras páginas de WordPress. Por ejemplo la páginaeffler de acceso al blog. Pero no tengo problemas para entrar en otros blogs de WordPress de terceras personas. Tampoco en otras páginas web. ¿¿??. Es decir la navegación es perfecta excepto para la página de acceso al blog de WordPress. No me explico que puede pasar. He borrado la caché, reseteado el router etc…es decir técnicas que otras veces han funcionado. Lo extraño es que pase con todos los ordenadores de la vivienda y no sólo con el que uso habitualmente.

Actualización mismo día noche: ¡ Solucionado !. Sin hacer yo nada. Otra rareza de internet que no me explico. Y no estoy pensando en ninguna “agresión” dirigida específicamente a mi vivienda. Seguramente ha sido un tema general de wordpress, pero sigo sin entender pq en el ciber si podía acceder… Paso a pulir la entrada. Fin de actualización.

En fin escribo desde un ciber. Por fin he tenido un poco de tiempo para releer entradas anteriores que listamos en una entrada anterior, y antes de que se me complique de nuevo la vida (seguramente dentro de una semana), tengo ya algunos temas completamente claros que son los que quiero publicar en esta entrada muy brevemente. De nuevo me está costando coger ritmo y no se si me va a dar tiempo en una semana a sumergirme lo suficiente en el tema como para obtener resultados tan notables como hace un par de meses más o menos. Como en esa ocasión no publicaremos todo.

Es posible que los comentarios que siguen contengan errores o inexactitudes que corregiremos cuanto tengamos acceso al blog desde el domicilio):

(more…)

Algorítmica y complejidad computacional. Muy breve historia (bibliográfica) de la teoría de grafos.

mayo 15, 2017

La primera versión, corta, de esta entrada se hizo el 15 de  mayo. Se ha actualizado para obtener una versión mas larga con actualizaciones el 16 y 17 de mayo.

(more…)

Algorítmica y complejidad computacional. La teoría y la práctica: isomorfismo de grafos.

mayo 11, 2017

 Tras  un breve paréntesis en el que nos hemos tenido que concentrar en otros temas, retomamos las entradas sobre estos contenidos.

Un artículo interesante sobre isomorfismo de grafos. La teoría es el reciente resultado de Babai. Y también un resultado publicado ayer que demuestra que un método de solución de este problema (obviamente no el de Babai sino al parecer uno de los más utilizados en la práctica) es exponencial peor caso.

An exponential lower bound for Individualization-Refinement algorithms for Graph Isomorphism

Daniel Neuen and Pascal Schweitzer RWTH Aachen University {neuen,schweitzer}@informatik.rwth-aachen.de

May 10, 2017

Abstract.  The individualization-refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, the currently fastest implementations of isomorphism solvers all follow this approach. While these solvers are fast in practice, from a theoretical point of view, no general lower bounds concerning the worst case complexity of these tools are known. In fact, it is an open question whether individualization-refinement algorithms can achieve upper bounds on the running time similar to the more theoretical techniques based on a group theoretic approach. In this work we give a negative answer to this question and construct a family of graphs on which algorithms based on the individualization-refinement paradigm require exponential time. Contrary to a previous construction of Miyazaki, that only applies to a specific implementation within the individualization-refinement framework, our construction is immune to changing the cell selector, or adding various heuristic invariants to the algorithm. Furthermore, our graphs also provide exponential lower bounds in the case when the k-dimensional Weisfeiler-Leman algorithm is used to replace the standard color refinement operator and the arguments even work when the entire automorphism group of the inputs is initially provided to the algorithm.

Extracto.  There are several highly efficient isomorphism software packages implementing the paradigm. Among them are nauty/traces [15], bliss [11], conauto [13] and saucy [6]. While they all follow the basic individualization-refinement paradigm, these algorithms differ drastically in design principles and algorithmic realization. In particular, they differ in the way the search tree is traversed, they use different low level subroutines, have diverse ways to perform tasks such as automorphism detection, and they use different cell selection strategies as well as vertex invariants and refinement operators.

With Babai’s [2] recent quasi-polynomial time algorithm for the graph isomorphism problem, the theoretical worst case complexity of algorithms for the graph isomorphism problem was drastically improved from a previous best e O( √ n log n) (see [3]) to O(n logc n ) for some constant c ∈ N. As an open question, Babai asks [2] for the worst case complexity of algorithms based on individualizationrefinement techniques. About this worst case complexity, very little had been known. In 1995 Miyazaki [16] constructed a family of graphs on which the then current implementation of nauty has exponential running time. For this purpose these graphs are designed to specifi- cally fool the cell selection process into exponential behavior. However, as Miyazaki also argues, with a different cell selection strategy the examples can be solved in polynomial time within the individualization-refinement paradigm. In this paper we provide general lower bounds for individualization-refinement algorithms with arbitrary combinations of cell selection, refinement operators, invariants and even given perfect automorphism pruning. More precisely, the graphs we provide yield an exponential size search tree (i.e., 2 Ω(n) nodes) for any combination of refinement operator, invariants, and the cell selector which are not stronger than the k-dimensional Weisfeiler-Leman algorithm for some fixed dimension k. The natural class of algorithms for which we thus obtain lower bounds encompasses all software packages mentioned above even with various combinations of switches that can be turned on and off in the execution of the algorithm to tune the algorithms towards specific input graphs. Our graphs are asymmetric, i.e., have no non-trivial automorphisms, and thus no strategy for automorphism detection can help the algorithm to circumvent the exponential lower bound.

En el segundo paper nos informan sobre el estado del arte de la práctica tras este resultado.

 Benchmark Graphs for Practical Graph Isomorphism Daniel Neuen and Pascal Schweitzer

May 11, 2017

Abstract The state-of-the-art solvers for the graph isomorphism problem can readily solve generic instances with tens of thousands of vertices. Indeed, experiments show that on inputs without particular combinatorial structure the algorithms scale almost linearly. In fact, it is non-trivial to create challenging instances for such solvers and the number of difficult benchmark graphs available is quite limited. We describe a construction to efficiently generate small instances for the graph isomorphism problem that are difficult or even infeasible for said solvers. Up to this point the only other available instances posing challenges for isomorphism solvers were certain incidence structures of combinatorial objects (such as projective planes, Hadamard matrices, Latin squares, etc.). Experiments show that starting from 1500 vertices our new instances are several orders of magnitude more difficult on comparable input sizes. More importantly, our method is generic and efficient in the sense that one can quickly create many isomorphism instances on a desired number of vertices. In contrast to this, said combinatorial objects are rare and difficult to generate and with the new construction it is possible to generate an abundance of instances of arbitrary size. Our construction hinges on the multipedes of Gurevich and Shelah and the Cai-FürerImmerman gadgets that realize a certain abelian automorphism group and have repeatedly played a role in the context of graph isomorphism. Exploring limits of such constructions, we also explain that there are group theoretic obstructions to generalizing the construction with non-abelian gadgets.

Extractos.

The practical algorithms underlying these solvers differ from the ones employed to obtain theoretical results. Indeed, there is a big disconnect between theory and practice [2]. One could 1 interpret Babai’s recent breakthrough, the quasipolynomial time algorithm [1], as a first step of convergence. The result implies that if graph isomorphism is NP-complete then all problems in NP have quasi-polynomial time algorithms, which may lead one to also theoretically believe that graph isomorphism is not NP-complete.

P.s. Otro paper que no tiene nada que ver con el anterior pero que nos  ha parecido interesante.

 A Survey of Shortest-Path Algorithms

Amgad Madkour1 , Walid G. Aref1 , Faizan Ur Rehman2 , Mohamed Abdur Rahman2 , Saleh Basalamah2 1 Purdue University, West Lafayette, USA 2 Umm Al-Qura University, Makkah, KSA

May 8, 2017

Abstract. A shortest-path algorithm finds a path containing the minimal cost between two vertices in a graph. A plethora of shortest-path algorithms is studied in the literature that span across multiple disciplines. This paper presents a survey of shortest-path algorithms based on a taxonomy that is introduced in the paper. One dimension of this taxonomy is the various flavors of the shortest-path problem. There is no one general algorithm that is capable of solving all variants of the shortest-path problem due to the space and time complexities associated with each algorithm. Other important dimensions of the taxonomy include whether the shortest-path algorithm operates over a static or a dynamic graph, whether the shortest-path algorithm produces exact or approximate answers, and whether the objective of the shortest-path algorithm is to achieve time-dependence or is to only be goal directed. This survey studies and classifies shortest-path algorithms according to the proposed taxonomy. The survey also presents the challenges and proposed solutions associated with each category in the taxonomy

Algorítmica y complejidad computacional. Problema RH en DCB: estado de la cuestión.

abril 7, 2017

En 2016 nos dedicamos a aterrizar el problema de Recorridos Hamiltonianos en Dígrafos de Cayley Bigenerados desde el punto de vista algorítmico, acabando con la sensación de haber realizado significativos avances.

En 2017 nos hemos centrado en la cuestión de la posible complejidad computacional de este mismo problema y pensamos que este otro tema ya está suficientemente claro para un documento que tenemos previsto preparar a la mayor brevedad posible.

El caso es que de 2016 de los avances en el aterrizaje de la parte algorítmica sólo queda en la memoria la buena sensación pues, debido a múltiples complicaciones vitales, se nos ha olvidado completamente el contenido de éstos.

Por eso precisamente, porque sabemos que estos temas por importantes que sean se olvidan si no se practican, los ponemos negro sobre blanco en el blog. Probablemente se me complique altamente la segunda quincena del mes así que quiero concentrarme en esto durante esta segunda semana que en principio debería de ser más tranquila. Aunque nunca se sabe.

Voy a releer todo lo que escribimos durante 2016 para hacer una “gran” síntesis que incluiremos en el documento ya comentado: algorítmica y complejidad computacional son dos caras de una misma moneda.

En lo que sigue, mientras espero una llamada importante, una compilación de las entradas, con fecha y título (no necesariamente exacto), sin enlace de momento ni resumen del contenido. Pero seguramente los añadiremos, pues nos va a ser más cómodo para su consulta.

Actualización 11 de abril. Hemos incluido también un listado de entradas de 2015, no todas directamente de investigación (éstas entre paréntesis). Y uno de 2014, el único de ese año sobre esta temática.

Finalmente se nos ha complicado también esta semana con un tema más prioritario que éste y que exigirá también elevada concentración. La “gran” síntesis seguramente tendrá que esperar a mayo, esperemos que de 2017. Fin de actualización. 

(more…)

Complejidad computacional de problemas definidos sobre Grafos de Cayley.

abril 1, 2017

Disclaimer. Entrada en construcción. Hemos borrado ya la parte de April´s Fools en caso de que alguien la haya leído…. 

¿ Que nos dice la complejidad computacional de un problema definido sobre un tipo de objetos sobre la  complejidad computacional de otros problemas definidos sobre la misma clase de objetos ?. Quizás poca cosa. Según y como.

No obstante en esta entrada compilamos artículos en los que se hable sobre complejidad computacional de problemas definidos sobre Grafos  de Cayley. Ya adelanto que no hay muchos, pero he encontrado algunos nuevos, recientes y no tan recientes.

Intentaremos especificar en cada caso si los resultados se refieren a grafos o dígrafos, el número de generadores y si se están considerando inputs normales o sucintos.  En los resultados ya conocidos seremos sucintos nosotros mismos y en los que son nuevos (para nosotros y por lo tanto no necesariamente recientes) nos extenderemos más, copiando el abstract y haciendo extractos.

1.Goldreich y Jerrum: MLGS (es decir shortest  path). P-SPACE-complete. Dígrafos, bigenerados y sucintos. Para mi un resultado clásico (y añejo, ya tiene décadas), que nos sorprendió conocer en su día. Hemos hablado mucho sobre ello y no los vamos a enlazar una vez más.

2. In 1998, Codenotti, Gerace, and Vigna [6] proved that computing clique number, and chromatic number, are NP-Hard when restricted to the class of circulant graphs (a circulant is a Cayley graph for a group Zm). 

Lo anterior es un extracto del artículo siguiente. Lo ponemos antes pq es anterior en el tiempo.

Los circulantes son un tipo de Grafos de Cayley para grupos cíclicos, que son abelianos. Hay un algoritmo polinómico para el problema de recorridos hamiltonianos en circulantes (Woeginger et all) pero creo recordar que es para los de grado 2-in-2-out.

Since circulants are Cayley graphs, they are vertex transitive. One might hope, or expect, that the assumption of vertex transitivity would confer some advantage when approaching computational problems on graphs. Codenotti et al.’s results show that this is not the case, and also raise the questioFn of whether there are classes of Cayley graphs on which these problems become easier

Relacionado. 

2. 2016. Hardness of Computing Clique Number and Chromatic Number For Cayley Graphs Chris Godsil and Brendan Rooney January 27, 2016

Abstract Computing the clique number and chromatic number of a general graph are well-known NP-Hard problems. Codenotti et al. (Bruno Codenotti, Ivan Gerace, and Sebastiano Vigna. Hardness results and spectral techniques for combinatorial problems on circulant graphs. Linear Algebra Appl., 285(1-3): 123–142, 1998) showed that computing clique number and chromatic number are still NP-Hard problems for the class of circulant graphs. We show that computing clique number is NP-Hard for the class of Cayley graphs for the groups G n , where G is any fixed finite group (e.g., cubelike graphs). We also show that computing chromatic number cannot be done in polynomial time (under the assumption P != NP) for the same class of graphs. Our presentation uses free Cayley graphs. The proof combines free Cayley graphs with quotient graphs and Goppa codes.

Extractos.

Our main results in this paper are analogues of Codenotti et al.’s hardness results for a different class of Cayley graphs. Our results apply to the class of Cayley graphs for the groups Gn, where G is any fixed finite group. When G = Z2, this is the class of cubelike graphs. We show that computing clique number for these graphs is an NP-Hard problem (Theorem 10.2). We also show that computing chromatic number for these graphs cannot be done in polynomial time under the assumption that P != NP (Theorem 11.3).

We prove that computing clique number is NP-Hard by reducing computing the clique number of a general graph X to computing the clique number of a Cayley graph on a group Gn. The key to this reduction is providing a construction of a Cayley graph Γ from X so that |Γ| is polynomially bounded in |X|, and so that ω(X) is easily computed from ω(Γ). We begin with a construction used by Babai and S´os [2] to embed graphs in Cayley graphs. This construction leads naturally to free Cayley graphs. We construct a free Cayley graph G(X) from X so that the cliques in X can be recovered from the cliques in G(X). To complete our construction we will quotient G(X) over a suitably chosen linear code. Specifically, we will give a Goppa code that satisfies the desired properties.

To prove that computing chromatic number cannot be done in polynomial time we use a similar strategy to Codenotti et al. In [6], the chromatic number result is proven by reducing computing clique number for general graphs to computing chromatic number for circulant graphs. This reduction does not work for the Cayley graphs we consider. However, we adapt this approach to show that if chromatic number can be computed in polynomial time for Cayley graphs for the groups Gn, then for any graph X, the clique number of X can be approximated to within a constant factor in polynomial time. This completes the proof by an inapproximability result of Hastad [8].

Constructing our reductions using free Cayley graphs situates them in a more general framework. Free Cayley graphs are relatively new and unstudied objects (they appear in a recent paper by Beaudou, Naserasr and Tardif [3]). Our complexity results rely on the clique structure of free Cayley graphs.

Relacionado: Homomorphisms of binary Cayley graphs Laurent Beaudoua , Reza Naserasrb , Claude Tardifc aCNRS, LIMOS, UMR6158, Univ. Clermont-Ferrand 2, Aubi`ere – France bCNRS, LRI, UMR8623, Univ. Paris-Sud 11, F-91405 Orsay Cedex – France cColl`ege Militaire Royal du Canada, Kingston, Ontario – Canada Abstract A binary Cayley graph is a Cayley graph based on a binary group. In 1982, Payan proved that any non-bipartite binary Cayley graph must contain a generalized Mycielski graph of an odd-cycle, implying that such a graph cannot have chromatic number 3. We strengthen this result first by proving that any non-bipartite binary Cayley graph must contain a projective cube as a subgraph. We further conjecture that any homomorphism of a non-bipartite binary Cayley graph to a projective cube must be surjective and we prove some special case of this conjecture. 

3.Fecha indeterminadaA well known tough open problem is the computational complexity of Cayley graph recognition

Lali Barri`ere, Pierre Fraigniaud, Cyril Gavoille, Bernard Mans, John Michael Robson: On Recognizing Cayley Graphs. ESA 2000: 76-87

Relacionado 1. Entrada en Complexity Theory Stack Exchange.

Evdokimov, Ponomarenko. Circulant graphs: Recognizing and isomorphism testing in polynomial time. St. Petersburg Math. J. 15 (2004) 813-835.

Relacionado 2.  Minimal Sense of Direction and Decision Problems for Cayley Graphs Paolo Boldi∗ Sebastiano Vigna∗

Abstract Sense of direction is a property of the labelling of (possibly anonymous) networks which allows to assign coherently local identifiers to other processors on the basis of the route followed by incoming messages. A graph has minimal sense of direction whenever it has sense of direction and the number of colours equals its maximum outdegree. We prove that an outregular digraph with minimal weak sense of direction is a Cayley colour graph (in the general sense, i.e., we do not require connectedness). Since Cayley colour graphs are known to possess minimal transitive sense of direction, we obtain a characterization of outregular graphs with minimal (weak,transitive) sense of direction. As a consequence, deciding whether a coloured graph is a Cayley colour graph reduces to deciding whether it has weak sense of direction, which can be done in AC 1.

Ver bibliografía de este último paper.

4. Power of Nondeterministic JAGs on Cayley graphs⋆ Martin Hofmann and Ramyaa Ramyaa Ludwig-Maximilians Universit¨at M¨unchen Oettingenstraße 67, 80538 Munich, Germany {mhofmann,ramyaa}@tcs.ifi.lmu.de

Abstract. The Immerman-Szelepcsenyi Theorem uses an algorithm for co-stconnectivity based on inductive counting to prove that NLOGSPACE is closed under complementation. We want to investigate whether counting is necessary for this theorem to hold. Concretely, we show that Nondeterministic Jumping Graph Autmata (ND-JAGs) (pebble automata on graphs), on several families of Cayley graphs, are equal in power to nondeterministic logspace Turing machines that are given such graphs as a linear encoding. In particular, it follows that ND-JAGs can solve co-st-connectivity on those graphs. This came as a surprise since Cook and Rackoff showed that deterministic JAGs cannot solve st-connectivity on many Cayley graphs due to their high self-similarity (every neighbourhood looks the same). Thus, our results show that on these graphs, nondeterminism provably adds computational power. The families of Cayley graphs we consider include Cayley graphs of abelian groups and of all finite simple groups irrespective of how they are presented and graphs corresponding to groups generated by various product constructions, including iterated ones. We remark that assessing the precise power of nondeterministic JAGs and in particular whether they can solve co-st-connectivity on arbitrary graphs is left as an open problem by Edmonds, Poon and Achlioptas. Our results suggest a positive answer to this question and in particular considerably limit the search space for a potential counterexample.

Extractos.

The question of implementing Immerman-Szelepcsenyi’s algorithm in ND-JAGs is considered in [4], but has been left as an open question. The results of this paper constitute an important step towards the solution of this question. Namely, we show that ND-JAGs can order and thus implement any NLOGSPACEalgorithm on a variety of graph families derived from Cayley graphs. This came as a surprise to us because Cayley graphs were used by Cook and Rackoff to show that deterministic JAGs cannot solve st-connectivity. Intuitively, this is due to the high degree of self-similarity of these graphs (every neighbourhood looks the same). It thus seemed natural to conjecture, as we did, that ND-JAGs cannot systematically explore such graphs either and tried to prove this. In the course of this attempt we found the conjecture to be false and discovered that in the case of pebble automata, nondeterminism indeed adds power. Our main results show that the Cayley graphs of the following groups can be ordered by ND-JAGs: all abelian groups and simple finite groups irrespective of the choice of generators, (iterated) wreath products G ≀ H once G can be ordered and a mild size condition on H holds. This implies that none of these groups can serve as a counterexample for a possible proof that ND-JAGs cannot solve co-st-connectivity on undirected graphs. One may criticize that we do not in this paper answer the question whether or not ND-JAGs can solve co-st-connectivity on undirected graphs. However, this is not at all an easy question and we believe that our constructions will help to eventually solve it because they allow one to discard many seemingly reasonable candidates for counterexamples such as the original counterexamples from Cook and Rackoff or the iterated wreath products thereof that were used by one of us and U. Sch¨opp [8] in an extension of Cook and Rackoff’s result. An anonymous reviewer of an earlier version wrote that trying to argue that NDJAGs can do co-st-conn without counting “seems silly”. One should “just take a graph that is between structured and unstructured and then it likely can’t be done.”. When we started this work this would have been our immediate reaction, but on the one hand, it is not easy to construct a graph “between structured and unstructured” in such a way that one can prove something about it. On the other hand, we found the additional power of nondeterminism in this context so surprising that we are no longer convinced that NDJAGs really cannot do co-st-connectivity and hope that our constructions will be helpful in the process of deciding this question.

5. The Computational Complexity Column by V. Arvind Institute of Mathematical Sciences, CIT Campus, Taramani Chennai 600113, India arvind@imsc.res.in http://www.imsc.res.in/~arvind

Expander graphs are of much importance in theoretical computer science, and the construction of expander graphs involves different areas of mathematics. It has attracted mathematicians and theoretical computer scientists alike and continues to be a flourishing area of research [14]. In this essay we discuss the Alon-Roichman theorem which states that for any finite group G, if S is a randomly picked multiset of O(log |G|) elements then the symmetric Cayley graph Cay(G, S) is a spectral expander with high probability.

We explain a proof of this theorem based on Erdős-Rényi sequences, which are interesting in their own right, and also outline a |G| O(1) time derandomized construction of the set S. We also discuss faster, (log |G|) O(1) time, derandomizations of the Alon-Roichman theorem for finite groups given by small generating sets as input and raise some open questions.

6. No exactamente de complejidad computacional pero interesante. Creo que ya lo conocía.

Turing machines, Cayley graphs, and inescapable groups

by da Cunha, Aubrey, Ph.D., UNIVERSITY OF MICHIGAN, 2012, 71 pages; 3530604

Abstract:

We present a generalization of standard Turing machines based on allowing unusual tapes. We present a set of reasonable constraints on tape geometry and conclude that the proper degree of generality is Cayley graphs. Surprisingly, this generalization does not lead to yet another equivalent formulation of the notion of computable function. Rather, it gives an alternative definition of the recursively enumerable Turing degrees that does not rely on oracles. We also get a comparable result for the polynomial time degrees and relate this to the difficulty of proving lower bounds in computational complexity. The definitions and constructions involved give rise to a number of questions about computable paths inside Cayley graphs of finitely generated groups, and several of these questions are answered.

Algorítmica y complejidad computacional. i.o. SUBEXP.

marzo 29, 2017

Disclaimer. El problema para publicar entradas en el blog se resolvió finalmente mucho más rápido de lo que esperaba y sin necesidad de ayuda externa. Los foros fueron suficientes.

Tras publicar en forma de comentarios, volvemos a la forma  de publicación habitual. En este nuevo periodo del blog nos vamos a centrar sobre todo en el mismo tipo de publicaciones que en la primera fase (dos primeros años) del blog. No obstante paramayor organización, vamos a seguir actualizando en los comentarios.  Fin de disclaimer.

Antes de volver a mancharnos las manos con el lápiz y la goma para rematar los flecos que quedan dentro de nuestra investigación (esto es necesario para la siguiente y última fase del proyecto y espero resolverlos pronto o no resolverlos y pasar a siguiente fase de cualquier manera), calentamos motores poniéndonos al día en complejidad computacional (por una parte me sigue costando leer sobre estos temas, por otra parte en esta última ronda estoy llegando más lejos en la comprensión de algunos temas; así es la madurez).

Conozco hoy por primera vez una clase, i.o. SUBEXP (infinitely often SUBEXP) aparentemente

(more…)