todo mundo sabe que existem muitos problemas de decisão que são difíceis de NP em gráficos gerais, mas estou interessado em problemas que são difíceis de NP quando o gráfico subjacente é um caminho. Então, você pode me ajudar a coletar esses problemas?
Eu já encontrei uma pergunta relacionada sobre problemas difíceis de NP em árvores .
graph-theory
np-hardness
Benjamin
fonte
fonte
Respostas:
Uma correspondência de arco-íris em um gráfico colorido de borda é uma correspondência cujas bordas têm cores distintas. O problema é: dado um gráfico colorido com arestas e um número inteiro , possui um arco-íris combinando com pelo menos arestas? Isso é conhecido como problema de correspondência do arco-íris e seu NP é completo mesmo para caminhos com bordas adequadamente. Os autores ainda observam que, antes desse resultado, nenhum problema de gráfico não ponderado é conhecido como NP -hard para caminhos simples, com o melhor de seu conhecimento.k G kG k G k
Veja Le, Van Bang e Florian Pfender. "Resultados de complexidade para combinações de arco-íris." Ciência da Computação Teórica (2013) ou a versão arXiv .
fonte
Aqui estão algumas observações simples.
Um gráfico de caminho sem cor basicamente codifica um número inteiro, para que você possa pegar qualquer problema difícil de NP que envolva números inteiros codificados por unário e reinterpretá-lo como um problema de gráfico de caminho. Se você permitir vários números inteiros codificados em unário (= uma união separada de gráficos de caminho), poderá usar alguns problemas fortemente completos de NP, como a 3-Partição.
Um gráfico de caminho colorido codifica uma palavra em um alfabeto fixo; portanto, novamente, você pode enfrentar um problema difícil de NP nas palavras. Um exemplo que eu conheço é o problema dos Fatores Disjuntos introduzido em Bodlaender, Thomassé e Yeo .
fonte
O motivo do gráfico MinCC é NP-hard quando o gráfico é um caminho (mesmo APX-hard). Dado um gráfico com cores nos vértices e um conjunto de cores, encontre um subgráfico que corresponda ao conjunto de cores e minimize o número de componentes conectados. Consulte Problemas de complexidade na correspondência de padrões gráficos coloridos em vértices, JDA 2011.
fonte
Isso é equivalente ao problema de Reconstrução da Permutação a Partir das Diferenças, que é o NPC (um dos meus resultados "não oficiais" :-).
fonte
Uma resposta trivial que se aproxima de parte do que aparece acima, mas, penso, distinto.
fonte
O Problema de Fluxo Incompleto (UFP) permanece com dificuldade de NP em um caminho. De fato, a UFP é NP-difícil, mesmo em uma única borda, pois é equivalente ao problema da mochila.
fonte
O Rainbow Dominating Set (RDS) permanece NP-hard nos caminhos. Dado um gráfico colorido de vértice, um RDS é um DS em que cada cor do gráfico aparece pelo menos uma vez.
Conjuntos dominantes tropicais em gráficos coloridos em vértices , JDA'18
fonte
Conjunto Dominante e Conjunto Dominante Independente são NP-hard nos caminhos se também houver na entrada um "gráfico de conflito", em que uma aresta neste gráfico é um par de vértices que não podem estar na solução.
Cornet, Alexis; Laforest, Christian , Problemas de dominação sem conflitos , Discrete Appl. Matemática. 244, 78-88 (2018). ZBL1387.05181 .
fonte