Algorítmica y complejidad computacional. Recopilación de enlaces abril 2015, 2.

Salvo tres puntos, esta edición está dedicada básicamente a recopilar algunos enlaces sobre la teoría de la complejidad computacional paramétrica (TCCP), una rama relativamente nueva del árbol TCS.

He llegado a ella a través de la PH (todavía no he aclarado mi gran duda al respecto; es sospechoso que no se pueda aclarar: igual es una pregunta sin sentido) y he encontrado que tiene algunos paralelismos (no se si finalmente resultarán ser sólo superficiales) con  los resultados de la patente.

Con respecto a los enlaces no relacionados con la TCCP destacamos una publicación reciente dónde se refutan dos demostraciones propuestas de P=NP con la presentación de sendos contraejemplos. Esto no es habitual… 

1. Los problemas tratables por un parámetro fijo  (Fixed Parameter Tractable).

He estado mirando por encima esta clase de complejidad. Normalmente la complejidad de estos problemas se mide de la siguiente manera f(k)*n^O(1), dónde f(k) suele ser una función exponencial del parámetro (por ejemplo c^O(k)) y O(1) una constante.

Básicamente hay tres tipos relevantes de problemas:

Strongly uniform fixed parameter tractability. Existe un algoritmo para todos los casos y la constante se puede determinar con exactitud.

Uniform fixed parameter tractability. Existe un algoritmo unforme pero la constante no se puede determinar con exactitud.

Non uniform fixed parameter tractability.   Ni existe un algoritmo uniforme para todos los niveles del parámetro ni se puede determinar la constante.

Una introducción en formato de presentación. Las clases de esta teoría son: FPT, Para-NP, XP y Jerarquía W.

La página web de uno de los padres de la criatura, Downey (el otro es Fellows), con acceso  a muchas de sus publicaciones.

Un tutorial (x Downey).

2. El problema RH en grafos generales y la clase FTP.

Título. Solving  hamiltonian cycle by an EPT algorithm for a non sparse parameter.

El problema RH en grafos con bounded treewidth pertenece a FPT e incluso a una clase más restringida EPT (dónde la constante de c^O(k) es igual a 2), es decir es soluble en tiempo  n^O(1)*2^O(k) utilizando el parámetro tree-width, que es computable en tiempo polinómico.   Un primer resultado EPT basado en este parámetro fue un algoritmo probabilístico de Cygan et al. Uno posterior fue de Fomin et al, determinista, basado en el mismo parámetro. Los grafos con bounded treewidth son sparse.

Un parámetro que incluiría los grafos densos (no sparse) sería el parámetro clique-width.  Sin embargo el problema RH para este parámetro es W-duro (W es una jerarquía).

Un parámetro intermedio entre estos dos para el que se ha encontrado un algoritmo ETP es split-matching width.  Se presenta en el artículo cuyo título hemos reseñado.

Nota. Conviene conocer en detalle al menos una de estas medidas, treewidth, tan útil para grafos. No obstante,

Extracto

The planar graphs do not have bounded treewidth, because the n × n grid graph is a planar graph with treewidth exactly n. Therefore, if F is a minor-closed graph family with bounded treewidth, it cannot include all planar graphs. Conversely, if some planar graph cannot occur as a minor for graphs in family F, then there is a constant k such that all graphs in F have treewidth at most k.

¿ Como se comportan los Grafos de Cayley con respecto al treewidth ? En el siguiente artículo, de manera muy indirecta nos informan sobre ello.

Título. On Balanced CSPs with High Treewidth

Abstract. Tractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose methods to increase their hardness by increasing the balance of both the constraint language and the constraint graph. The balance of a constraint is increased by maximizing the number of domain elements with the same number of occurrences. The balance of the graph is defined using the classical definition from graph theory. In this sense we present two graph models; a first graph model that increases the balance of a graph maximizing the number of vertices with the same degree, and a second one that additionally increases the girth of the graph, because a high girth implies a high treewidth, an important parameter for binary CSPs hardness. Our results show that our more balanced graph models and constraints result in harder instances when compared to typical random binary CSP instances, by several orders of magnitude. Also we detect, at least for sparse constraint graphs, a higher treewidth for our graph models. 

Extracto (un tanto técnico).

As we have said in the introduction, the treewidth of a graph is the most relevant structural parameter concerning the complexity of binary CSPs with arbitrary constraint languages (Grohe 2003).

Concerning the treewidth of random regular graphs, we can use the following lower bound, that is also valid for general graphs, based on the spectrum of the (combinatorial) Laplacian of the graph (Chandran & Subramanian 2003):

tw(G) ≥ [3V /4 (μ /Δ+2μ )] − 1. (los corchetes son de floor function).  

Where Δ is the maximum degree of G, the Laplacian of G is the matrix D − A, where D is the diagonal matrix in which Di,i is the degree of vi, A is the adjacency matrix of G and μ is the second smallest eigenvalue of the Laplacian.

For the case of a k−regular graph, where μ = k −λ2(G), this lower bound can be rewritten as:

tw(G) ≥ [3V / 4 ((k − λ2(G))/ (3k − 2λ2(G))] − 1. Corchetes Idem.

Where λ2(G) is the second largest eigenvalue of the adjacency matrix of G (k is the largest eigenvalue for a k−regular graph).

So, the higher the value of μ = k − λ2(G), also called the spectral gap, the closer the lower bound gets to V /4. This shows a connection between expander graphs and graphs with a high value for this treewidth lower bound, because this spectral gap also gives a lower bound on the edge expansion of a graph.

Roughly speaking, an expander graph is a graph that, for any, not too big, subset of vertices S, its set of neighbors outside S is big, compared with |S|. See for example (Sarnak 2004) for formal definitions.

For random k−regular graphs, with k fixed, it is known that asymptotically (as V → ∞) for epsilon > 0, Probability(λ2(G) ≤ 2 Raiz cuadrada [k − 1+ epsilon]) → 1 (Friedman 2004), where 2 Raiz cuadrada[k − 1] is, asymptotically, the lowest possible value for λ2(G). Regular graphs with λ2(G) ≤ 2 Raiz Cuadrada[k − 1] are called Ramanujan graphs.

For Ramanujan graphs, we have:

tw(G) ≥ [3V/4 (k − 2 Raiz cuadrada [k − 1] / 3k − 4 Raiz cuadrada[k − 1]] − 1. Corchetes idem.

So, for a fixed and sufficiently high k the lower bound will get very close to V /4. As we are considering regular (or biregular) graphs with the degrees growing with V , we cannot infer directly that asymptotically our graphs will have a spectral gap of order k − 2 √k − 1. Actually, as the degree grows with V , the expanding properties of the graphs can be better for higher degrees.

For example, some existing constructions of Ramanujan graphs based on certain Cayley graphs are obtained with a degree Ω(√ V ), whereas similar Cayley graphs with degree O(log V ) are also expander graphs but not as good as Ramanujan graphs (Alon & Roichman 1994). As far as we know the best result for non-constant degree random k−regular graphs is, if k > Raiz cuadrada [V log V] then asymptotically λ2(G) = o(k) (Krivelevich et al. 2001). So those regular graphs have a high spectral gap, and a high treewidth spectral lower bound 

De nuevo nos encontramos con los expanders.

Sigo sin tener muy clara de momentola medida de treewidth. La definición está clara, he visto un par de ejemplos con grafos pequeños y también están claros pero no entiendo la motivación, no tengo claro si dado un grafo una descomposición en árboles es única (entiendo que no)  y no se si podría reproducir el procedimiento.

En fin el concepto está relacionado directamente con un juego (helicóptero) e indirectamente con el juego policías y ladrones en grafos (cops and robbers). 3 papers sobre este último juego. Si lo he entendido bien, la mejor defensa para el ladrón es moverse en una secuencia de vértices del grado más alto posible (no tengo claro ahora mismo si es mejor que esta secuencia tenga forma de ciclo o de camino).

Título. Cops, robbers and graphs. 2007.

Es un survey relativamente reciente.

Título. THE COPS AND ROBBER GAME ON GRAPHS WITH FORBIDDEN (INDUCED) SUBGRAPHS. 

Abstract. The two-player, complete information game of Cops and Robber is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if, after a move, a cop and the robber are on the same vertex. The minimum number of cops needed to catch the robber on a graph is called the cop number of that graph. In this paper, we study the cop number in the classes of graphs defined by forbidding one or more graphs as either subgraphs or induced subgraphs. In the case of a single forbidden graph we completely characterize (for both relations) the graphs which force bounded cop number. En passant, we bound the cop number in terms of tree-width, and give a short proof for an upper bound on the cop number of sparse random graphs.

Sobre la complejidad computacional de este problema.

Título. On tractability of Cops and Robbers game. 2006.

Abstract. The Cops and Robbers game is played on undirected graphs where a group of cops tries to catch a robber. The game was defined independently by Winkler-Nowakowski and Quilliot in the 1980s and since that time has been studied intensively. Despite of that, its computation complexity is still an open question. In this paper we prove that computing the minimum number of cops that can catch a robber on a given graph is NP-hard. Also we show that the parameterized version of the problem is W[2]-hard. Our proof can be extended to the variant of the game where the robber can move s times faster than cops. We also provide a number of algorithmic and complexity results on classes of chordal graphs and on graphs of bounded cliquewidth. For example, we show that when the velocity of the robber is twice cop’s velocity, the problem is NP-hard on split graphs, while it is polynomial time solvable on split graphs when players posses the same speed. Finally, we establish that on graphs of bounded cliquewidth (this class of graphs contains, for example, graphs of bounded treewidth), the problem is solvable in polynomial time in the case the robber’s speed is at most twice the speed of cops.

Como era de esperar, la mayoría de los grafos no tienen un treewidth acotado, sino uno que aumenta con el número de vértices.

Titulo. Only few graphs have bounded degree.

El resultado se basa en grafos aleatorios. Uno de los autores ha estudiado mucho el problema treewidth. Desde su página web te puedes descargar muchos de sus artículos.

Fin de nota.

3. El problema RH en digrafos generales y la clase FTP.

¿ Que pasa cuando pasamos de grafos a digrafos ?.

De los mismos autores que el artículo anterior.

Título. On the algorithmic effectiveness of digraph decompositions and complexity measures.

Muestran las limitaciones de las generalizaciones / adaptaciones de la  medida treewidth (que es una medida válida para grafos) a digrafos (directed tree-width, DAG-width, Kelly-width). Hablan en concreto del problema RH.

Relacionado. Presentación de los mismos autores.

Título. On Digraph Width Measures in Parameterized Algorithmics

Abstract. In contrast to undirected width measures (such as treewidth or clique-width), which have provided many important algorithmic applications, analogous measures for digraphs such as DAG-width or Kelly-width do not seem so successful. Several recent papers, e.g. those of Kreutzer–Ordyniak, Dankelmann–Gutin–Kim, or Lampis– Kaouri–Mitsou, have given some evidence for this. We support this direction by showing that many quite different problems remain hard even on graph classes that are restricted very beyond simply having small DAG-width. To this end, we introduce new measures K-width and DAG-depth. On the positive side, we also note that taking Kant´e’s directed generalization of rank-width as a parameter makes many problems fixed parameter tractable.

Extracto.

3.1 Hamiltonian Path (HAM) and Disjoint Paths (k-Path)

The classical NP-hard Hamiltonian Path (HAM) problem [GJ79] is to find a directed path that visits each vertex of a digraph exactly once. A natural generalization of HAM is the Longest Path problem (Longest Path), where one is asked to find the longest simple path in a given digraph. It is easy to see that HAM can be solved on DAGs in polynomial time. When using the parameter DAG-width, HAM belongs to XP [JRST01], but was also proven to be W[2]-hard [LKM08]. We prove our new FPT results for the parameters K-width and DAG-depth on more general Longest Path. Using a simple enumeration of all distinct paths in the case of bounded K-width, or applying Proposition 2.9 and any FPT-algorithm for Longest Path in the standard parameterization (e.g. [CKL+09]) when DAG-depth is bounded, we get: Theorem 3.1. There is a fixed parameter tractable algorithm solving the Longest Path problem on a digraph G

a) in time O ( t · |V (G)| · |E(G)|) if G is of K-width at most t;

b) in time O (4^( 2 t+O(t 3 )) · |V (G)| · |E(G)| ) if G is of DAG-depth at most t

Relacionado. Are there any Good Digraph Width Measures?  Presentación de los mismos autores.

Relacionado. 2013. Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs

¿ Que relevancia tiene todo esto para los Digrafos de Cayley bigenerados, los que utilizamos como input en los resultados de la patente ?. De momento no lo se. Si lo que nos interesa son algoritmos eficientes en función del grado de las permutaciones input, estos métodos son impracticables (ya que sólo para obtener las medidas ya se requiere la construcción de todo el digrafo). De cualquier manera tengo que estudiar las medidas Kenny-width (que está más o menos clara) y DAG-depth (nada clara de momento).

4. Kernelization.

Es una técnica de resolución de problemas que se utiliza en problemas FTP. Me ha llamado la atención porque en su descripción general entiendo que se podría incluir como caso concreto la técnica que hemos aplicado para los casos cycle-entangled.

Recordemos que los digrafos de cayley bigenerados se pueden caracterizar por varios parámetros cuantitativos (orden de las 2 permutaciones, orden del IAS, orden de la circunferencia) y por características estructurales (entrelazado, entrelazado de ciclos).  Al ser digrafos muy sparse sería posible que los grafos densos contengan alguno de ellos. Me pregunto también si la descomposición de un digrafo en IAS no podría ser una de las medidas paramétricas a tener en cuenta para digrafos generales (densos).

5. Teoría de complejidad subexponencial y paramétrica. 

Título. An Isomorphism between Subexponential and Parameterized Complexity Theory. 2006.

Abstract.

We establish a close connection between (sub)exponential time complexity and parameterized complexity by proving that the so-called miniaturization mapping is a reduction preserving isomorphism between the two theories.

Extracto. 

Our main result is that subexponential and parameterized complexity theory are isomorphic. Let us explain what we mean by this: On the subexponential side, we consider the partial order induced by subexponential reduction families on the degrees, that is, equivalence classes under subexponential reduction families. On the parameterized side, we consider the partial order induced by fpt-reductions on the corresponding degrees. We define a mapping, the so-called miniaturization mapping, that associates a problem (Q, κ) with every problem (P, ν) and prove that this mapping is an isomorphism between the partial order of degrees inside EPT under subexponential reduction families and the partial order of degrees inside XP under fpt-reductions. This result holds for both many-one and Turing reductions. In particular, miniaturization maps the class SUBEPT (the lowest “subexponential degree”) to FPT (the lowest “parameterized degree”) and EPT to XP. 

If we look at degrees outside of EPT, then the miniaturization mapping is still an embedding, but we prove that it is no longer onto. That is, there are parameterized degrees outside XP that are not in the image of the miniaturization mapping. Technically, this is our most difficult result.

6.La jerarquía W. 

Para una explicación más clara ver aquí. Sinceramente, de momento no entiendo esta jerarquía.

7. Parametized complexity news. Una newsletter sobre esta temática. 

El número al que enlazamos incluye un artículo muy resumido sobre los temas sobre los que hemos hablado en los anteriores puntos.

Todas las newsletter similares se pueden descargar en el correspondiente sitio web: Parametrized complexity.

8. Information complexity (a survey).

Este punto ya no tiene nada que ver con la teoría de la complejidad computacional paramétrica.

9. Refutadas dos demostraciones P=NP.

Reseño este artículo dado que me parece conveniente que los académicos (en teoría guardianes del conocimiento verdadero) refuten por escrito cualquier intento de demostración, independientemente del medio de publicación, que resulte ser falsa. Mejor esto que dejar éstas publicaciones en el limbo de la duda (aunque en general nadie duda…).

Si recuerdo haber visto discusiones en foros, pero es la primera vez que veo una iniciativa de este tipo y la aplaudo (seguramente habrá más casos que yo desconozco; excluyo el bien conocido y fructífero caso Yannakakis).

Y en este caso lo destacable es que los que publican el artículo se dicen vinculados a un departamento de una universidad, de la Universidad de Rochester en concreto. Seguramente son estudiantes. Uno de los dos resultados que refutan aparece en la famosa P versus NP page que contiene una lista de presuntas soluciones a este problema en uno u otro sentido.

Para refutar las dos soluciones propuestas (una de Marzo de 2014 y la otra de Febrero del presente) presentan sendos contra-ejemplos (es la manera más directa para demostraciones algorítmicas de P=NP y a veces no es fácil; para demostraciones de P!=NP hay que encontrar el fallo en alguna demostración).

Nota. Me avergüenza confesar (pues le dediqué un cierto tiempo e incluso lo programé :-() que yo hace bastante tiempo también tuve una algoritmo supuestamente polínómico (aunque ineficiente por el elevado grado del polinomio) para un problema similar (RH en digrafos) y tras darle muchas vueltas encontré un contra-ejemplo. Me acuerdo perfectamente el lugar y momento de su descubrimiento. E incluso casi del contra-ejemplo, creo que tenía unos 21 vértices y dos componentes unidos por un vértice de articulación de grado bastante elevado. En teoría tenía que recorrer todos los vértices de un componente antes de pasar al  otro, y este era el primer caso, el de mínimo tamaño, en el que esta operación fallaba. A partir de este tamaño habría muchos otros más.

NonBiconnectedGraph

Esto es típico en este tipo de algoritmos cuando se aplica a grafos / digrafos generales: lo que se diseña y funciona para / con grafos pequeños puede fallar para grafos más grandes. Gracias a ello ya estoy vacunado…

10. Un problema de permutaciones.

Título. Optimal Shuffle Code with Permutation Instructions

Abstract. During compilation of a program, register allocation is the task of mapping program variables to machine registers. During register allocation, the compiler may introduce shuffle code, consisting of copy and swap operations, that transfers data between the registers. Three common sources of shuffle code are conflicting register mappings at joins in the control flow of the program, e.g, due to if-statements or loops; the calling convention for procedures, which often dictates that input arguments or results must be placed in certain registers; and machine instructions that only allow a subset of registers to occur as operands. Recently, Mohr et al. [8] proposed to speed up shuffle code with special hardware instructions that arbitrarily permute the contents of up to five registers and gave a heuristic for computing such shuffle codes. In this paper, we give an efficient algorithm for generating optimal shuffle code in the setting of Mohr et al. An interesting special case occurs when no register has to be transferred to more than one destination, i.e., it suffices to permute the contents of the registers. This case is equivalent to factoring a permutation into a minimal product of permutations, each of which permutes up to five elements.

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: