Taille minimale de la sous-traitance d'un DAG dans un nouveau DAG

Nous avons un DAG. Nous avons une fonction sur les nœuds (en gros, nous numérotons les nœuds). Nous aimerions créer un nouveau graphique dirigé avec ces règles:$F\colon V\to \mathbb N$

1. Seuls les nœuds avec le même numéro peuvent être contractés dans le même nouveau nœud. . (Cependant, .)$F(x) \neq F(y) \Rightarrow x' \neq y'$$x' \neq y'\nRightarrow F(x) \neq F(y)$
2. Nous ajoutons tous les anciens bords entre les nouveaux nœuds: .$(x,y) \in E \land x' \neq y' \iff (x',y')\in E'$
3. Ce nouveau graphique est toujours un DAG.

Quel est le minimal? Qu'est-ce qu'un algorithme créant un nouveau graphique minimal?$|V'|$

Une approche pour résoudre ce problème serait d'utiliser la programmation linéaire entière (ILP). Abordons la version décisionnelle du problème: étant donné , existe-t-il un moyen de contracter des sommets de même couleur pour obtenir un DAG de taille ?≤ $k$$\le k$

Cela peut être exprimé comme une instance ILP en utilisant des techniques standard. On nous donne la couleur de chaque sommet dans le graphique d'origine. Je suggère que nous étiquetons chaque sommet avec une étiquette dans ; tous les sommets avec la même étiquette et la même couleur seront contractés. Ainsi, le problème de décision devient: existe-t-il un étiquetage, tel que la contraction de tous les sommets de même couleur de même étiquette donne un DAG?$\{1,2,\dots,k\}$

Pour exprimer cela comme un programme linéaire entier, introduisez une variable entière pour chaque sommet , pour représenter l'étiquette sur le sommet . Ajoutez l'inégalité . v v 1 ≤ ℓ v ≤ $\ell_v$$v$$v$$1 \le \ell_v \le k$

L'étape suivante consiste à exprimer l'exigence selon laquelle le graphique contracté doit être un DAG. Notez que s'il existe un étiquetage du formulaire ci-dessus, sans perte de généralité, il existe un tel étiquetage où les étiquettes induisent un tri topologique sur le graphique contracté (c'est-à-dire, si précède dans le graphique contracté, alors l'étiquette de est plus petit que 'étiquette de ). Donc, pour chaque arête dans le graphe d'origine, nous ajouterons la contrainte selon laquelle soit et ont la même étiquette et la même couleur, soit l' étiquette de est plus petite que l'étiquette de . Plus précisément, pour chaque arêtew v w v → w v w v w v → w v , w ℓ v ≤ ℓ w v → w v , w ℓ v < ℓ $v$$w$$v$$w$$v\to w$$v$$w$$v$$w$$v\to w$dans le graphe initial où ont la même couleur, ajoutez l'inégalité . Pour chaque arête où ont des couleurs différentes, ajoutez l'inégalité .$v,w$$\ell_v \le \ell_w$$v \to w$$v,w$$\ell_v < \ell_w$

Voyons maintenant s'il existe une solution possible à ce programme linéaire entier. Il y aura une solution réalisable si et seulement si l'étiquetage est de la forme souhaitée (c'est-à-dire que la contraction de tous les sommets de même couleur de même étiquette donne un DAG). En d'autres termes, il y aura une solution réalisable si et seulement s'il existe un moyen de contracter le graphe d'origine à un DAG de taille . Nous pouvons utiliser n'importe quel solveur de programmation linéaire entier; si le solveur ILP nous donne une réponse, nous avons une réponse au problème de décision d'origine.$\le k$

Bien sûr, cela n'est pas garanti de se terminer en temps polynomial. Il n'y a aucune garantie. Cependant, les solveurs ILP sont devenus assez bons. Je m'attends à ce que, pour un graphique de taille raisonnable, vous ayez une chance décente qu'un solveur ILP puisse résoudre ce problème dans un délai raisonnable.

Il est également possible de coder cela en tant qu'instance SAT et d'utiliser un solveur SAT. Je ne sais pas si ce serait plus efficace. Cependant, la version ILP est probablement plus facile à penser.

(J'espère que cela est vrai. Je n'ai pas vérifié tous les détails attentivement, alors s'il vous plaît revérifiez mon raisonnement! J'espère que je n'ai pas mal tourné quelque part.)

Mise à jour (10/21): Il semble que les ILP de cette forme puissent être résolus en temps linéaire, en traitant le DAG dans un ordre trié par topologie et en gardant une trace de la limite inférieure sur l'étiquette pour chaque sommet. Cela me fait douter de ma solution: ai-je fait une erreur quelque part?

NOTE: AFAICT, DW a trouvé un trou dans cette réduction et c'est faux (voir commentaires). Le garder ici pour des raisons historiques.

Intro : je vais d'abord réduire le problème Monotone 3SAT à notre problème. Bien que le problème du Monotone 3SAT soit trivialement satisfaisable, notre problème peut en outre résoudre le problème Minimum True Monotone 3SAT , qui est NP-difficile; ce problème est donc NP-difficile.

Réduction de Monotone 3SAT à notre problème

Nous avons une formule booléenne monotone exprimée comme une séquence de variables et une séquence de clauses. Le CNF est de la forme telle que:$\Phi = (\mathcal V,\mathcal C)$

et

Conversion

Nous construisons un graphe, . Chaque sommet de G ' a une étiquette; les sommets avec la même étiquette sont éligibles pour la contraction.$G'=V',E'$$G'$

Nous construisons d'abord le graphique comme suit: pour chaque , nous faisons deux nœuds, chacun étiqueté x i , et un bord dirigé de l'un à l'autre (cliquez sur les images pour une vue haute résolution).$x_i \in \mathcal V$$x_i$

Ces nœuds peuvent bien sûr être contractés, car ils ont la même étiquette. Nous considérerons les variables / nœuds contractés comme étant évalués comme faux et ceux qui ne sont pas contractés comme évalués comme vrais :

$V'$$2\cdot \left|\mathcal V\right|$$c_i \in \mathcal C, ~ \left.c_i = (x_j \vee x_k \vee x_l) \right|_{x_j,x_k,x_l \in \mathcal V}$$c_i$

^{$c_i$$1$$c_i$}

$2\cdot \left|\mathcal V\right| + |\mathcal C|$

$x_i$$x_j$ $x_k$$c_i \rightarrow c_i$

Voici une autre visualisation, déroulant la contrainte de clause:

Ainsi, chaque contrainte de clause nécessite qu'au moins une des variables qu'elle contient reste non contractée; comme les nœuds non contractés sont évalués comme vrais, cela nécessite qu'une des variables soit vraie; exactement ce que Monotone SAT requiert pour ses clauses.

Réduction du minimum vrai monotone 3SAT

Monotone 3SAT est trivialement satisfaisable; vous pouvez simplement définir toutes les variables sur true.

Cependant, puisque notre problème de minimisation DAG consiste à trouver le plus de contractions, cela se traduit par la recherche de l'affectation satisfaisante qui produit le plus de fausses variables dans notre CNF; ce qui revient à trouver les vraies variables minimales. Ce problème est parfois appelé Minimum True Monotone 3SAT ou ici (comme problème d'optimisation ou problème de décision), ou k-True Monotone 2SAT (comme problème de décision plus faible); les deux problèmes NP-difficiles. Ainsi, notre problème est NP-difficile.

Les références:

• Minimum True Monotone 3SAT
• Prouver que NP est complet pour décider de la satisfiabilité de la formule booléenne monotone
• Couvercle Monotone-2SAT et Vertex

Sources du graphique:

• source sur l'essentiel
• vue sur writelatex

Avec chaque remplacement (sauf pour les remplacements directs parent-enfant), vous ajoutez de nouvelles relations ancêtre-descendant qui rendent non trivial la détermination de celle qui en vaut la peine à long terme. Par conséquent, un simple algorithme gourmand échouera dans le cas général. Cependant, si vous effectuez une approche par force brute, vous pouvez déterminer le plus petit graphique:

Python-ish (non testé):

def play((V,E),F,sequence=[]):
  """
  (V,E) -- a dag.
  V     -- a set of vertices.
  E     -- a set of directed-edge-tuples.
  F     -- a function that takes a vertex, returns an integer.
  sequence -- the sequence of moved taken so far; starts with/defaults to
              an empty list, will contain tuples of the form (x,y)
              where x is removed and replaced with y.

  Returns the best recursively found solution.
  """

  #find all the integer values in the graph, remember which
  # values correspond to what vertices. Of the form {integer => {vertices}}.
  n2v = {}
  for x in V:
    n = F(x)

    #for each integer, make sure you have a set to put the vertices in.
    if n not in n2v:
      n2v[n] = set()

    #for each integer, add the vertex to the equivalent set.
    n2v[n].add(v)

  #record the best sequence/solution. You start with the current sequence,
  # and see if you can obtain anything better.
  best_solution = list(sequence)

  #Now you will try to combine a single pair of vertices, obtain a new
  # graph and then recursively play the game again from that graph. 

  #for each integer and equivalent set of vertices,
  for n,vset in n2v.iteritems():

    #pick a pair of vertices
    for x in vset:
      for y in vset:

        #no point if they are the same.
        if x == y:
          continue

        #If there is a path from x => y or y => x, then you will be
        # introducing a cycle, breaking a rule. So in that case, disregard
        # this pair.
        #However, the exception is when one is a direct child of the other;
        # in that case you can safely combine the vertices.
        if pathtest((V,E),x,y) and (x,y) not in E and (x,y) not in E:
          continue

        #combine the vertices (function is defined below), discard x,
        # replace it with y, obtain the new graph, (V',E').
        Vp,Ep = combine_vertex((V,E),x,y))

        #record the sequence for this move.
        sequencep = list(sequence) + [(x,y)]

        #recurse and play the game from this new graph.
        solution = play(Vp,Ep,F,sequencep)

        #if the returned solution is better than the current best,
        if len(solution) > len(best_solution):
          #record the new best solution
          best_solution = solution
  #return the best recorded solution
  return best_solution


def combine_vertex((V0,E0),x,y):
  """
  (V0,E0)   -- an initial digraph.
  V0        -- a set of vertices.
  E0        -- a set of directed-edge-tuples.
  x         -- vertex to discard.
  y         -- vertex to replace it with.

  returns a new digraph replacing all relationships to and from x to relate
   to y instead, and removing x from the graph entirely.
  """

  #the final vertex set will have everything except x
  V = set(V0)
  V.discard(x)

  #now you construct the edge set.
  E = set()

  #for every edge,
  for (u0,v0) in E0:
    #recreate the edge in the new graph, but replace any occurence
    # of x.  
    u,v = u0,v0
    #if x is in the edge: replace it
    if u == x:
      u = y
    if v == x:
      v == y

    #sometimes u=v=y and can now be pointing to itself, don't add that
    # edge
    if u == v:
      continue

    #add the new/replaced edge into the edge-set.
    E.add( (u,v) )
  return (V,E)

Je ne sais pas si c'est vraiment un problème difficile, mais en jouant avec certains graphiques manuellement, cela semble très combinatoire. Je suis curieux de savoir si quelque chose de difficile peut être réduit à ce problème, ou s'il existe un algorithme avec un meilleur temps de fonctionnement.