Problèmes NP-hard dirigés sur les DAG

12

La largeur de l'arbre mesure la proximité d'un graphique avec un arbre. Plusieurs problèmes NP-difficiles sont traitables sur des graphiques avec une largeur d'arbre bornée. Si un problème reste NP-dur sur les arbres, la largeur de l'arbre ne peut pas nous sauver. C'était la motivation derrière une de mes questions précédentes demandant des problèmes NP-difficiles sur les arbres.

Il existe plusieurs versions dirigées de la largeur d'arbre mesurant la distance entre un graphique dirigé et un graphique acyclique dirigé (DAG). Quels sont les problèmes dirigés qui restent NP-difficiles sur les DAG? Un problème dirigé fait un usage essentiel des directions des bords. Par exemple, le chemin hamiltonien est un problème dirigé alors que la couverture des sommets ne l'est pas. L'une des réponses à ma question précédente a donné une recette générale pour générer des problèmes difficiles sur les arbres. Existe-t-il une telle recette pour les DAG?

np-hardness directed-acyclic-graph Shiva Kintali
la source

Réponses:

7

Cela ne vise qu'à répondre partiellement à la première question du poste:

Quels sont les problèmes dirigés qui restent NP-difficiles sur les DAG?

Dans [1], quelques problèmes naturels sur les graphes dirigés sont donnés qui restent NP-durs sur les DAG. La motivation de l'article est de trouver une "bonne" mesure de largeur d'arbre pour les digraphes. Ils soutiennent que l'inconvénient de nombreuses mesures pour les digraphes est qu'elles sont constantes pour les DAG, mais de nombreuses contreparties dirigées de problèmes naturels restent NP-dures sur les DAG. Pour plus d'informations sur ce sujet, voir également [2] et les références de ces articles.

[1] Robert Ganian, Petr Hlinený, Joachim Kneis, Alexander Langer, Jan Obdrzálek, Peter Rossmanith: On Digraph Width Measures in Parameterized Algorithmics. IWPEC 2009: 185-197. Version complète

[2] Robert Ganian, Petr Hlinený, Joachim Kneis, Daniel Meister, Jan Obdrzálek, Peter Rossmanith, Somnath Sikdar: Existe-t-il de bonnes mesures de largeur de graphe?. IPEC 2010, à paraître. arXiv

Serge Gaspers
la source
6

Plusieurs problèmes de routage sont connus pour être NP-difficiles et même difficiles à rapprocher des facteurs polynomiaux dans les DAG. Ceux-ci incluent des problèmes tels que les trajets maximum bord-disjoints et la réduction de l'encombrement. Voir les articles d'Andrews, Chuzhoy, Khanna, Zhang et autres pour plus de conseils.

Chandra Chekuri
la source
1

φ:=∃C1C2C3[∀x(C1x∨C2x∨C3x)∧⋀i=1,2,3∀x,y(¬Cix∨¬Ciy∨¬E(x,y))]GG′E(x,y)φE(x,y)∨E(y,x)G⊨φ⟺G′⊨φ′

Régularité
la source
Il semble que ce problème n'utilise pas les directions des bords. Je recherche des problèmes dirigés.
Shiva Kintali
@Shiva: Pourquoi cela ne répond-il pas à vos critères de problème dirigé?
András Salamon
@ András: La coloration du graphique se soucie de la présence d'un bord (u, v). Peu importe que le bord soit dirigé de u vers v ou de v vers u. D'un autre côté, Hamiltonian Path utilise les directions des bords. Il est possible de changer la direction de certaines arêtes et de convertir une instance YES en une instance NO.
Shiva Kintali
@Shiva: Vous voulez donc une propriété qui est exprimée par une formule qui n'est pas symétrique (invariante sous permutation de variables)?
András Salamon
@ András: Exactement.
Shiva Kintali
1

Le fameux problème OPEN [8] de la liste de Garey et Johnson est au-delà de P, mais ouvert à prouver qu'il est NP-C. Ce problème est sur DAG. Chaque tour, vous pouvez supprimer au plus trois sommets qui n'ont pas de bord entrant. Décidez si tous les sommets du DAG pourraient être supprimés en K tours? OUVERT à partir des années 1970.

Peng Zhang
la source