Minimalny rozmiar zawarcia DAG w nowy DAG

Mamy DAG. Mamy funkcję na węzłach (luźno mówiąc, numerujemy węzły). Chcielibyśmy utworzyć nowy ukierunkowany wykres z tymi zasadami:$F\colon V\to \mathbb N$

1. Tylko węzły o tym samym numerze można zawrzeć w tym samym nowym węźle. . (Jednak .)$F(x) \neq F(y) \Rightarrow x' \neq y'$$x' \neq y'\nRightarrow F(x) \neq F(y)$
2. Dodajemy wszystkie stare krawędzie między nowymi węzłami: .$(x,y) \in E \land x' \neq y' \iff (x',y')\in E'$
3. Ten nowy wykres jest nadal DAG.

Jaka jest minimalna? Co to jest algorytm tworzący nowy minimalny wykres?$|V'|$

Jednym podejściem do rozwiązania tego problemu byłoby zastosowanie programowania liniowego liczb całkowitych (ILP). Zajmijmy się wersją decyzyjną problemu: biorąc pod uwagę , czy istnieje sposób na zawarcie wierzchołków tego samego koloru, aby uzyskać DAG o wielkości ≤ k ?$k$$\le k$

Można to wyrazić jako instancję ILP przy użyciu standardowych technik. Kolor oryginalnego wykresu jest podany dla każdego wierzchołka. Sugeruję, aby oznaczyć każdy wierzchołek etykietą w ; wszystkie wierzchołki z tą samą etykietą i tym samym kolorem zostaną skurczone. Problemem decyzyjnym staje się zatem: czy istnieje oznakowanie, które powoduje, że skurczenie wszystkich wierzchołków tego samego koloru w ten sam sposób daje DAG?$\{1,2,\dots,k\}$

Aby wyrazić to jako całkowity program liniowy, wprowadź zmienną całkowitą dla każdego wierzchołka v , aby przedstawić etykietę na wierzchołku v . Dodaj nierówność 1 ≤ ℓ v ≤ k .$\ell_v$$v$$v$$1 \le \ell_v \le k$

Następnym krokiem jest wyrażenie wymogu, że zakontraktowany wykres musi być DAG. Należy zauważyć, że jeśli jest znakowanie postaci wymienionych powyżej, bez utraty ogólności istnieje taki oznakowania, gdzie etykiety indukowania topologiczne sortuje umownej wykresie (czyli jeżeli poprzedza W umownej wykresu, a V „S etykiety jest mniejszy, niż w „s etykiecie). Tak więc, dla każdej krawędzi v → wagowo w oryginalnym wykresie dodamy ograniczenie, że albo v i w mają taką samą etykietę i tego samego koloru, albo v „s etykieta jest mniejsza niż w ” s etykietą. W szczególności dla każdej krawędzi $v$$w$$v$$w$$v\to w$$v$$w$$v$$w$ w początkowym wykresu gdzie v , w mają ten sam kolor, dodać nierówność £ -l v ≤ £ -l wag . Dla każdej krawędzi v → w, gdzie v , w mają różne kolory, dodaj nierówność ℓ v < ℓ w .$v\to w$$v,w$$\ell_v \le \ell_w$$v \to w$$v,w$$\ell_v < \ell_w$

Sprawdź teraz, czy istnieje jakieś realne rozwiązanie tego programu liczb całkowitych. Możliwe będzie rozwiązanie, jeśli i tylko wtedy, gdy etykietowanie będzie miało pożądaną formę (tj. Skurczenie wszystkich wierzchołków tego samego koloru o tym samym kolorze daje DAG). Innymi słowy, możliwe będzie rozwiązanie tylko i wyłącznie wtedy, gdy istnieje sposób na zawężenie oryginalnego wykresu do DAG o wielkości . Możemy użyć dowolnego liczbowego solvera do programowania liniowego; jeśli solver ILP daje nam odpowiedź, mamy odpowiedź na pierwotny problem decyzyjny.$\le k$

Oczywiście nie można tego zagwarantować w czasie wielomianowym. Nie ma gwarancji. Jednak solwery ILP są całkiem niezłe. Spodziewałbym się, że dla rozsądnego wykresu masz spore szanse, że solver ILP może rozwiązać ten problem w rozsądnym czasie.

Możliwe jest również zakodowanie tego jako instancji SAT i użycie solvera SAT. Nie wiem, czy to byłoby bardziej skuteczne. Prawdopodobnie łatwiej jest myśleć o wersji ILP.

(Mam nadzieję, że to prawda. Nie sprawdziłem dokładnie każdego szczegółu, więc proszę dokładnie sprawdzić moje rozumowanie! Mam nadzieję, że gdzieś nie poszedłem źle).

Aktualizacja (10/21): Wygląda na to, że ILP tego formularza można rozwiązać w czasie liniowym, przetwarzając DAG w topologicznie posortowanej kolejności i śledząc dolną granicę etykiety dla każdego wierzchołka. To mnie podejrzewa o moje rozwiązanie: czy popełniłem gdzieś błąd?

UWAGA: AFAICT, DW znalazł dziurę w tej redukcji i jest ona błędna (patrz komentarze). Trzymanie go tutaj ze względów historycznych.

Wprowadzenie : najpierw zredukuję problem Monotone 3SAT do naszego problemu. Chociaż problem Monotone 3SAT jest trywialnie satysfakcjonujący, nasz problem może dodatkowo rozwiązać problem minimalnej prawdziwej Monotone 3SAT , który jest trudny dla NP; dlatego ten problem jest trudny dla NP.

Redukcja z Monotone 3SAT do naszego problemu

Mamy monotoniczną formułę logiczną wyrażoną jako ciąg zmiennych i ciąg klauzul. CNF ma postać taką, że:$\Phi = (\mathcal V,\mathcal C)$

i

Konwersja

Budujemy wykres, . Każdy wierzchołek w G ′ ma etykietę; wierzchołki z tą samą etykietą kwalifikują się do skurczu.$G'=V',E'$$G'$

Najpierw konstruujemy wykres w następujący sposób: dla każdego tworzymy dwa węzły, każdy oznaczony x i oraz skierowaną krawędź od jednego do drugiego (kliknij obrazy, aby wyświetlić w wysokiej rozdzielczości).$x_i \in \mathcal V$$x_i$

Te węzły mogą oczywiście zostać zakontraktowane, ponieważ mają tę samą etykietę. Rozważymy zmienne / węzły, które zostały zakontraktowane, jako wycenione jako fałszywe, a te, które nie są traktowane jako wycenione jako prawdziwe :

$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$

Oto kolejna wizualizacja, rozwijająca ograniczenie klauzuli:

Zatem każde ograniczenie klauzuli wymaga, aby co najmniej jedna ze zmiennych w nim zawartych pozostała niezakłócona; ponieważ niekontraktowane węzły są wyceniane jako prawda, wymaga to, aby jedna ze zmiennych była prawdziwa; dokładnie to, czego wymaga Monotone SAT dla swoich klauzul.

Redukcja od minimum True Monotone 3SAT

Monotone 3SAT jest banalnie satysfakcjonujący; możesz po prostu ustawić wszystkie zmienne na true.

Ponieważ jednak naszym problemem minimalizacji DAG jest znalezienie największego skurczu, przekłada się to na znalezienie satysfakcjonującego przypisania, które wytwarza najbardziej fałszywe zmienne w naszym CNF; co jest równoznaczne ze znalezieniem minimalnych prawdziwych zmiennych. Ten problem jest czasami nazywany minimalnym True Monotone 3SAT lub tutaj (jako problem optymalizacji lub problem decyzyjny) lub k-True Monotone 2SAT (jako słabszy problem decyzyjny); oba trudne problemy NP. Zatem nasz problem jest trudny NP.

Bibliografia:

• Minimalny True Monotone 3SAT
• Wykazać kompletność NP decydującej o satysfakcji monotonicznej formuły boolowskiej
• Monotone-2SAT i pokrywa wierzchołków

Źródła wykresów:

• źródło na gist
• zobacz na writelatex

Przy każdej zamianie (z wyjątkiem bezpośrednich zamian rodzic-dziecko) dodajesz nowe relacje przodek-potomek, które sprawiają, że ustalenie, który z nich jest tego wart w perspektywie długoterminowej, nie jest łatwe. Dlatego prosty chciwy algorytm zawiedzie w ogólnym przypadku. Jeśli jednak zastosujesz podejście z użyciem siły brutalnej, możesz określić najmniejszy wykres:

Python-ish (nie testowany):

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)

Nie jestem pewien, czy to naprawdę trudny problem, ale ręczna gra z niektórymi wykresami wydaje się bardzo kombinatoryczna. Jestem ciekawy, czy coś trudnego można zredukować do tego problemu, czy też istnieje algorytm o lepszym czasie działania.