Estou interessado em gráficos em vértices que podem ser produzidos através do processo a seguir.
- Comece com um gráfico arbitrário em vértices. Rotule todos os vértices em como não utilizados .
- Produzir um novo gráfico pela adição de um novo vértice , o qual está ligado a um ou mais não utilizados vértices em , e não está ligado a nenhum usados vértices em . Rotule como não utilizado .
- Rotule um dos vértices em ao qual está conectado conforme usado .
- Defina como e repita do passo 2 até conter vértices.
Chame esses gráficos de "gráficos de complexidade " (desculpas pela terminologia vaga). Por exemplo, se é um gráfico de complexidade 1, é um caminho.
Eu gostaria de saber se esse processo já foi estudado antes. Em particular, para arbitrário , é NP-completo determinar se um gráfico tem complexidade ?
Este problema aparece um pouco semelhante à questão de saber se é um parcial -trees , ou seja, tem treewidth . Sabe-se que determinar se tem largura de árvore é NP-completo. No entanto, alguns gráficos (estrelas, por exemplo) podem ter uma largura de árvore muito menor que a medida de complexidade discutida aqui.
4 de outubro de 2012: pergunta postada no MathOverflow depois que não houve resposta conclusiva após uma semana (embora obrigado pelas informações sobre fluxos causais).
fonte