Minimalny rozmiar zawarcia DAG w nowy DAG

15

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:VN

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

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

chx
źródło
1
Problemem decyzyjnym wydaje się więc: biorąc pod uwagę DAG w kolorze wierzchołka i liczbę całkowitą , zdecyduj, czy istnieje DAG z co najwyżej wierzchołkami utworzonymi przez kurczenie się wierzchołków tego samego koloru. kkk
András Salamon,
1
Jeśli kontraktujesz dwa połączone węzły, czy otrzymujesz zakazaną pętlę własną?
Yuval Filmus,
1
Nie. Przeczytaj 2. ponownie: dodajemy krawędź tylko wtedy, gdy dwa węzły po skurczu są nadal różne. Jeśli dwa węzły zostaną skurczone w jeden, nie dodamy krawędzi.
chx
1
@chx Czy pytasz o „minimalny” czy „minimalny”?
Realz Slaw
1
czy możesz podać motywację / bkg?
vzn

Odpowiedzi:

5

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 ?kk

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,,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 vk .vvv1vk

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 vvwvwvwvwvw 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 .vwv,wvwvwv,wv<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.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?

DW
źródło
Dzięki za szczegółową odpowiedź! Dostaję ograniczenia i wyglądają rozsądnie. Jednakże, chociaż nie jestem dobrze zaznajomiony z ILP, myślałem, że programowanie całkowite wymaga funkcji, którą chciałeś zmaksymalizować (lub zminimalizować) i nigdzie tego nie widzę. Sprawdziłem tylko w Wikipedii, więc mogę się mylić.
chx
@chx, używam ILP do testowania wykonalności ograniczeń. Można tego dokonać, prosząc solver ILP o maksymalizację dowolnej funkcji celu, którą lubisz (np. Maksymalizację 0), a następnie zignorowanie wartości funkcji celu i tylko sprawdzenie, czy ILP jest wykonalna, czy nie. Albo solver ILP odpowiada „Nieosiągalny” (co oznacza, że ​​nie ma zakontraktowanego DAG o wielkości ) lub odpowiada „Wykonalny” i zapewnia najlepszą wartość funkcji celu, jaką może znaleźć; w takim przypadku ignorujesz wartość funkcji celu (i wiesz, że istnieje DAG o wielkości k ). kk
DW
Zobacz np. Engineering.purdue.edu/~engelb/abe565/… („Chcę tylko wiedzieć, czy istnieje wykonalne rozwiązanie .”)
DW
Jeśli chodzi o twoje liniowe rozwiązanie czasowe; Nie przetrawiłem twojego sformułowania ILP, więc nie mogę go ocenić, ale jestem prawie pewien, że mogę udowodnić, że problem jest trudny do NP, co uczyniłoby liniowe rozwiązanie czasowe całkiem przydatne: P. Wkrótce to opublikuję.
Realz Slaw
@RealzSlaw, dziękuję! W takim razie mocno podejrzewam, że mogłem gdzieś się pomylić (choć nie jestem jeszcze pewien, gdzie jeszcze).
DW
5

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:Φ=(V.,do)

i

(dojado) doja=(xjotxkxl)||(xjot,xk,xlV.)

ja=1ndoja|dojado,n=|do|.

Konwersja

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

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).xjaV.xja

wprowadź opis zdjęcia tutaj

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 :

wprowadź opis zdjęcia tutaj

V.2)|V.|dojado, doja=(xjotxkxl)|xjot,xk,xlV.doja

wprowadź opis zdjęcia tutaj

doja1doja

2)|V.|+|do|

xjaxjot xkdojadoja

Oto kolejna wizualizacja, rozwijająca ograniczenie klauzuli:

wprowadź opis zdjęcia tutaj

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:

Źródła wykresów:

Realz Slaw
źródło
1
łał. wtedy rozwiązanie DW musi być złe (lub udowodniliśmy NP = P, w co przynajmniej wątpię: P) - ale gdzie?
chx
(x1x2)x6)(x1x4x5)(x3)x4x6)x1=x4=x6=Fałszywy x2)=x3)=x5=Prawdziwedo1x1x4x6do1
@DW Miło też z tobą porozmawiać: D i powodzenia, jeśli mamy rację, możemy mieć P = NP w twojej odpowiedzi! / jk
Realz Slaw
(x1,x3))
@RealzSlaw, obawiam się, że jeszcze nie przestrzegam ... Nie widzę powodu, dla którego moja formuła musiałaby zostać przekształcona. Wierzę, że jest to już instancja minimum True Monotone 3SAT. Ale pozwól mi wznieść się na wyższy poziom. Mówiąc szerzej, widzę proponowaną redukcję, ale nie widzę żadnego argumentu, że redukcja jest poprawna - tego brakuje. Aby redukcja była poprawna, musi mapować instancje TAK na instancje TAK i NIE na instancje NIE. Podejrzewam, że jeśli spróbujesz napisać dowód poprawności swojej redukcji, napotkasz problem, gdy weźmiesz pod uwagę formułę, którą podałem.
DW
1

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.

Realz Slaw
źródło
1
Też jestem ciekawy :)
chx,