P-Particiones convexas en una familia de grafos construidos mediante reemplazos

Abstract

Un conjunto de vértices de un grafo se dice convexo si contiene a los vértices de todos los caminos mínimos entre sus vértices. El problema de determinar si un grafo tiene una partición en p conjuntos convexos es NP-completo, pero hay diversas familias de grafos en las que se puede resolver en tiempo polinomial. El foco principal de este trabajo es estudiar el problema de la p-partición convexa en una familia de grafos definida recursivamente al reemplazar los vértices de un bosque por grafos de ésta. Esta familia resulta ser cerrada para subgrafos inducidos. Sin embargo, no queda totalmente determinada la familia de subgrafos prohibidos que determina a esta familia. Además, estos grafos resultan ser perfectos, por lo que varios problemas combinatoriales resultan tener soluciones polinomiales en esta familia. Además, se entrega un algoritmo polinomial para reconocer si un grafo pertenece a esta familia. Para atacar el problema de las particiones convexas en este contexto, combinaremos, mediante programación dinámica, particiones en subgrafos tales que sus particiones convexas son de tres tipos: todos los vértices, particiones en cliques y particiones en cliques más un conjunto localmente convexo. En el caso de las particiones en cliques, se entrega un algoritmo polinomial que lo resuelve.