Algorithmes de couverture de sommet pour les graphiques dirigés?

Question

J'ai récemment travaillé sur un problème qui, je crois, peut être exprimé comme un problème de couverture de sommet sur un dirigée graphique.

Formellement, j'ai un graphique $ g = (v, e) $ où $ v $ est un ensemble de sommets et $ e $ est un ensemble de bords entre les sommets. Les bords sont dirigés afin que nous puissions avoir $ e_ {ij} = 1 $ mais $ e_ {ji} = 0 $ où $ i, j in v $. Ici, $ e_ {ji} = 0 $ signifierait qu'il n'y a pas d'avant de $ j $ à $ i $.

Mon problème est le suivant. Je voudrais trouver le le plus petit sous-ensemble de sommets $ s subseseq v $ tels qu'il y a un chemin De chaque sommet de S à chaque sommet à V. c'est-à-dire que pour chaque sommet $ j in v $, il y a un $ i in s $ tel que soit:

• $ e_ {i, j}> 0 $ (bord entre $ i $ et $ j $)
• $ e_ {i, {k_1}} e _ {{k_1, k_2}} $ ... $ e _ {{k_t, j}}> 0 $ (chemin de $ i $ à $ j $)

Je suppose que $ e_ {ii} = 1 $ pour s'assurer qu'un tel sous-ensemble existe, car je peux définir $ s = v $. Cependant, cela n'est optimal que lorsque l'ensemble des nœuds est entièrement déconnecté.

Je me demande si c'est un problème de couverture de sommet? Si oui, y a-t-il des algorithmes pour ce problème? Je suis légèrement confus parce que la plupart couverture de sommet Les algorithmes sont destinés aux problèmes où le graphique est non dirigée (par exemple, $ e_ {ij} = e_ {ji} $). Sinon, y a-t-il des algorithmes pour résoudre ce problème?