Complejidad computacional de problemas definidos sobre Grafos de Cayley.

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.

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: