Quels problèmes de graphe sont

10

Suite aux questions équivalentes concernant NP-Completeness (voir la question de poids et la question dirigée ), je me demandais comment les problèmes paramétrés sont affectés par ces attributs.

  • Quels problèmes de graphes durs sont W [ 1 ] -Dur sur les graphes dirigés, mais les paramètres fixes traitables sur les graphes non orientés?NPW[1]
  • Quels problèmes de graphes durs sont W [ 1 ] -Dur sur les graphes pondérés, mais paramétrable fixe traitable sur les graphes non pondérés?NPW[1]

OK, nous avons donc des problèmes qui deviennent plus difficiles sur la version dirigée. Et les poids? Peuvent-ils rendre le problème paramétré plus difficile?

cc.complexity-theory graph-algorithms parameterized-complexity fixed-parameter-tractable RB
la source
Il y a des cas qui ne sont pas exactement identiques et inconnus. Par exemple, le calcul de la largeur d'arbre dans les graphiques non dirigés est fpt mais le calcul de la largeur d'arbre dirigé n'est pas connu s'il est fpt. mais dans le travail de johnson etal il y a une approximation fpt 3.
Saeed
2
Ou un autre cas, si nous jouons au jeu de largeur DAG dans des graphiques non orientés, nous obtenons une décomposition en arbre. Mais la largeur de l'arbre de calcul est FPT mais la largeur de calcul du fichier est complète sur PSPACE .
Saeed

Réponses:

9

GkkGk=2G

Chandra Chekuri
la source
3

Le calcul de la largeur d'arbre et de la décomposition d'arbre dans les graphiques non orientés est le paramètre FPT wrt width. De nombreuses mesures de largeur de graphe (ou leur jeu correspondant) sont équivalentes à la largeur d'arbre dans les graphiques non orientés. La classe de complexité exacte de beaucoup d'entre eux n'est pas connue, mais a récemment montré que la largeur du DAG est complète avec PSPACE .

Saeed
la source