Gráfico de compatibilidad por pares

Gráfico (b) que son gráficos de compatibilidad por pares de los árboles (a) y (c).

Gráficos que no son gráficos de compatibilidad por pares

En teoría de grafos , un grafo${\displaystyle G}$es un grafo de compatibilidad por pares (PCG) si existe un árbol ponderado${\displaystyle T}$y dos números reales no negativos${\displaystyle d_{min}\leq d_{max}}$de tal manera que cada nodo${\displaystyle u'}$de${\displaystyle G}$tiene una correspondencia uno a uno con un nodo hoja${\displaystyle u}$de${\displaystyle T}$de tal manera que dos nodos${\displaystyle u'}$y${\displaystyle v'}$son adyacentes en${\displaystyle G}$si y solo si la distancia entre${\displaystyle u}$y${\displaystyle v}$están en el intervalo${\displaystyle [d_{min},d_{max}]}$. ^{[ 1 ]}

Las subclases de PCG incluyen grafos de como máximo siete vértices, ciclos , bosques , grafos completos , grafos de intervalos y grafos de escalera . ^{[ 1 ]} Sin embargo, existe un grafo con ocho vértices que se sabe que no es un PCG. ^{[ 2 ]}

Los gráficos de compatibilidad por pares fueron introducidos por primera vez por Paul Kearney, J. Ian Munro y Derek Phillips en el contexto de la reconstrucción filogenética . Al muestrear de un árbol filogenético , la tarea de encontrar nodos cuya distancia de camino se encuentra entre longitudes dadas${\displaystyle d_{min}\leq d_{max}}$es equivalente a encontrar una camarilla en el PCG asociado. ^{[ 3 ]}

La complejidad computacional de decidir si un grafo arbitrario es un PCG es NP-completa. ^{[ 4 ]} Además, el problema relacionado de encontrar para un grafo${\displaystyle G}$y una selección de relaciones que no son de borde${\displaystyle S}$un PCG que contiene${\displaystyle G}$como un subgrafo y sin ninguna de las aristas en${\displaystyle S}$Se sabe que es NP-difícil. ^{[ 2 ]}

La tarea de encontrar nodos en un árbol cuyas distancias de camino se encuentran entre${\displaystyle d_{min}}$y${\displaystyle d_{max}}$Se sabe que es resoluble en tiempo polinomial . Por lo tanto, si el árbol pudiera recuperarse de un PCG en tiempo polinomial, entonces el problema de la camarilla en PCGs también sería polinomial. Hasta 2020, no se conoce ninguna de estas complejidades. ^{[ 1 ]}