Em quais classes de gráficos o caminho mais curto (RCSP) com recursos restritos é difícil de usar?

8

Estou procurando vincular um problema em que estou trabalhando com um problema conhecido como NP-hard. Acho que posso modelar meu problema como um problema de caminho mais curto com recursos limitados. No entanto, a estrutura do meu gráfico não é completamente arbitrária. Assim, será útil saber quando o RCSP se torna difícil. É difícil para um DAG, para um DAG planar, para um DAG com grau limitado? Qualquer ajuda seria muito apreciada!

nômade
fonte
Importa qual é a restrição de recurso? por exemplo, está na forma de uma restrição de "número de links"?
Suresh Venkat
2
Não sei se o recurso real é relevante para o resultado da dureza. No entanto, a restrição de recurso é da seguinte forma. Há algum número (M) de conjuntos proibidos, aos quais cada vértice pode pertencer. As restrições devem codificar que o caminho mais curto satisfatório não passa por todos os vértices em nenhum desses conjuntos M (ou seja, se o conjunto proibido S contém k vértices, o caminho mais curto pode ser adjacente a até k-1 deles). Assim, cada link adjacente a um nó restrito mantém a contribuição desse nó para todos os seus conjuntos proibidos e buscamos um SP respeitando essas restrições.
N /
1
Folheando a literatura sobre o problema, notei algumas coisas: 1) possíveis nomes alternativos: caminho mais curto restrito (CSP), roteamento de qualidade de serviço (QoS) 2) o problema "padrão" usa um custo em cada borda, e uma constante ligado na soma dos custos sobre o caminho mais curto 3) o problema é NP-completas sobre gráficos acíclicos
Daniel Apon
Este não é o caminho mais curto restrito. O CSP possui uma solução de tempo pseudo-polinomial.
Saeed

Respostas:

6

Não sei se você ainda está interessado nesta (antiga) pergunta e se entendi bem as restrições de recursos que você deu no comentário; no entanto, parece que seu problema (que é um pouco diferente dos problemas comuns do RCSP) é NP-completo para gráficos planares (acíclicos não direcionados ou direcionados ou direcionados) de grau máximo 3 .

φnx1,...xnmC1,...Cm

  • Mk+xkφMkx¯kφ
  • sxiMkx¯kMk+xk
  • CjCjMk+Mk
  • t

st|V|

xiMkx¯iMk+xiMk

Mk

insira a descrição da imagem aqui

C1=x1x¯2x3
C2=x2x¯3x4
C3=x¯1x3x¯2

Você também pode facilmente tornar o gráfico direcionado, acíclico e bipartido. Deixe-me saber se você precisar de mais detalhes (ou se eu entendi completamente o problema :-).

k

Marzio De Biasi
fonte
k
1
@ Saeed: certo, eu vou editar a pergunta. Eu uso o yEd (aplicativo java) ... você não obtém desenhos profissionais se comparado aos produzidos pelo tikz (usando o TikZiT), mas é possível desenhar esboços muito rapidamente (levei ~ 5 minutos para o exposto).
Marzio De Biasi
Obrigado;) Muitas vezes, preciso de uma ferramenta para desenhar rapidamente, acho que isso é ótimo.
Saeed