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

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ã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 .

$\varphi$$n$$x_1,...x_n$$m$$C_1,...C_m$

• $M_k^+$$x_k$$\varphi$$M_k^-$$\bar{x}_k$$\varphi$
• $s$$x_i$$M_k^-$$\bar{x}_k$$M_k^+$$x_k$
• $C_j$$C_j$$M_k^+$$M_k^-$
• $t$

$s$$t$$\leq |V|$

$x_i$$M_k^-$$\bar{x}_i$$M_k^+$$x_i$$M_k$

$M_k$

$C_1 = x_1 \lor \bar{x}_2 \lor x_3$
$C_2 = x_2 \lor \bar{x}_3 \lor x_4$
$C_3 = \bar{x}_1 \lor x_3 \lor \bar{x}_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$