Complejidad de reconocer a las clases [h,2,1], con h>2.

LILIANA ALCÓN; MARISA GUTIERREZ; MARÍA PÍA MAZZOLENI

Córdoba

Congreso; IV Congreso Latinoamericano de Matemáticos. 2012; 2012

Una (h,s,t)-representación de un grafo G consiste de una colección de subárboles de un árbol T, donde cada subárbol corresponde a un vértice de G tal que: (i) el grado máximo de T es a lo sumo h; (ii) todo subárbol tiene grado máximo a lo sumo s; (iii) existe una arista entre dos vértices en el grafo G si y sólo si los subárboles correspondientes tienen al menos t vértices en común en T. La clase de grafos que tiene una (h,s,t)-representación es notada [h,s,t]. Notar que $[infty,2,1]$ es la bien conocida clase de los grafos VPT.  Se sabe que el problema de reconocer a los grafos VPT es polinomial. En este trabajo nos centramos en las clases [h,2,1] las cuales son subclases de VPT. Mostramos que el problema de decidir si un grafo VPT está en [h,2,1], con h>2, es NP-completo, mientras que el problema de decidir si el grafo pertenece a [h,2,1]-[h-1,2,1], con h>3, es NP-difícil. Ambos problemas se mantienen difíciles aún cuando nos restringimos a la clase VPT intersección Split. Además, presentamos una subclase no trivial de VPT intersección Split en la cual ambos problemas son polinomiales.