A structural characterization of minimal completions for interval graphs

NINA PARDAL; MARIO VALENCIA-PABON

Buenos Aires

Workshop; INFINIS Workshop; 2017

DC-ICC (UBA)

Una clase de grafos Π es una familia de grafos conteniendo la propiedad Π, por ejemplo, Π puede ser la propiedad de ser cordal, o planar, o perfecto, etc. Dada una clase de grafos Π, una Π-completación de un grafo G = (V, E) es un grafo H = (V, E ∪ F) tal que H pertenezca a Π. En otras palabras, dado cualquier grafo G con un conjunto de vértices V y un conjunto de aristas E, se desea encontrar un conjunto de aristas F tales que al adicionarlas a G lo conviertan en un grafo de la clase Π. Una Π-completación H de G es minimal si H´= (V, E ∪ F) no pertenece a Π para todo F´ subconjunto propio de F. Una Π-completación H de G es mínima si para toda Π-completación H´= (V, E ∪ F´) de G, se tiene que el tamaño de F es inferior o igual al tamaño de F´. Claramente, una Π-completación mínima es minimal, pero la recíproca no es cierta. El problema de calcular una completación mínima de un grafo arbitrario auna clase especifica de grafos es un problema importante y bastante estudiado, el cual tiene aplicaciones en biología molecular, álgebra computacional, y más específicamente en áreas que involucran un modelamiento basado en grafos donde las aristas ausentes son debidas a la falta de datos, como por ejemplo en problemas de ´clustering´ de datos. Desafortunadamente, completaciones mínimas de grafos arbitrarios a clases de grafos específicas, como por ejemplo, cografos, grafos bipartitos, grafos cordales, etc., son NP-hard de calcular. Por este motivo, las investigaciones actuales sobre este problema se enfocan en encontrar completaciones minimales de grafos arbitrarios a clases especificas de grafos de la manera más eficiente posible desde el punto de vista computacional. Nuestro trabajo se concentra en hallar una caracterización estructural para completaciones minimales de grafos de intervalos a grafos de intervalos unitarios que permita construir un algoritmo de reconocimiento eficiente, y posteriormente basados en ella poder encontrar una caracterización de las completaciones mínimas con el mismo fin.