Sobre la complejidad parametrizada de relajaciones no hereditarias de cliques

Investigamos la complejidad parametrizada de varios problemas que formalizan la identificación de clústeres en grafos. En otras palabras, preguntamos si un grafo contiene un subgrafo que sea lo suficientemente grande y conectado. Estudiamos aquí tres relajaciones de Clique: s-Club y s-Clique, en las que la relajación se centra en las distancias en el clúster y en el grafo original, respectivamente, y γ-Subgrafo Completo en la que la relajación se hace sobre el grado mínimo en el clúster. Como se sabe que estos tres problemas son NP-duros, aquí estudiamos sus complejidades parametrizadas. Demostramos que s-Club y s-Clique son NP-duros incluso restringidos a grafos con degeneración ≤3 siempre que s≥3, y a grafos con degeneración ≤2 siempre que s≥5, lo que es un resultado estrictamente más fuerte que su dureza W1 parametrizada por la degeneración. En cuanto a γ-Subgrafo Completo, demostramos que es W1-duro parametrizado tanto por la degeneración, lo que implica la dureza W1 parametrizada por el número de vértices en el γ-subgrafo completo, como por el número de elementos fuera del γ-subgrafo completo.