Enumeración eficiente de subgráficas máximas separadas y sub-cografías inducidas y clases relacionadas

En este artículo, nos interesan los algoritmos que toman como entrada un grafo G arbitrario y que enumeran como salida todos los "subgráficos" máximos (según inclusión) de G que cumplen una propiedad dada. A lo largo de este artículo, estudiamos varias propiedades diferentes, y la noción de subgrafo bajo consideración (inducido o no) variará de un resultado a otro. Más precisamente, presentamos algoritmos eficientes para listar todos los subgráficos máximos separados, sub-cografías y algunas subclases de cografías de un grafo de entrada dado. Todos los algoritmos aquí presentados funcionan con un retraso polinómico y, además, para grafos separados solo requieren espacio polinómico. Para desarrollar un algoritmo para subgráficas (de borde) máximas separadas, establecemos una biyección entre las subgráficas máximas separadas y los conjuntos independientes máximos de un grafo auxiliar. Para cografías y algunas subclases, los algoritmos se basan en un marco introducido recientemente por Conte & Uno llamado Búsqueda de Proximidad. Finalmente, consideramos el problema de extensión, que consiste en decidir si existe una subgráfica inducida máxima que satisface una propiedad que contiene un conjunto de vértices prescritos y que evita otro conjunto de vértices. Mostramos que este problema es NP-completo para toda propiedad hereditaria "interesante". Ampliamos el resultado de dureza a una versión específica del problema de extensión en relación con los bordes.