Existem resultados conhecidos sobre a complexidade de encontrar um separador (de qualquer tamanho) que satisfaça uma determinada propriedade?
Eu sei que é fácil encontrar um separador de clique (tempo polinomial) e também sei que muitos trabalhos consideram o problema de encontrar pequenos separadores ou separadores que deixam componentes de tamanho conectados no máximo uma fração do tamanho do gráfico original. Mas e se alguém precisar de um separador com outras propriedades, por exemplo, um separador cúbico, bipartido ou com 2 conexões? Também é fácil criar propriedades difíceis de decidir pelo NP; portanto, seria interessante distinguir entre os casos P e NPC.
Edit: Alguém (que não é usuário deste site) acabou de me dizer que o problema é polinomial se a propriedade é "tem um vértice universal" e NP-completo se a propriedade é "induz um conjunto independente" ou "induz um conjunto completo gráfico bipartido ".
fonte
Respostas:
Nosso artigo:
http://arxiv.org/abs/1110.4765
mostra que muitos desses problemas são tratáveis por parâmetros fixos, ou seja, podemos decidir no tempo f (k) * O (n + m) se existe um st separador de tamanho k. Isso é verdade, por exemplo, para o problema de encontrar um separador st conectado, ou um separador que seja um conjunto independente ou um separador que induza um gráfico bipartido. Um próximo artigo aborda o problema de encontrar um separador st com 2 conexões.
fonte
Também é difícil determinar se um gráfico tem um corte que induz um gráfico desconectado ou um gráfico com exatamente k componentes para todos os k> = 2 . Por outro lado, o corte conectado é fácil (ou seja, k = 1).
fonte