Ukuran minimal mengontrak DAG menjadi DAG baru

Kami memiliki DAG. Kami memiliki fungsi pada node $F\colon V\to \mathbb N$ (secara longgar, kami beri nomor pada node). Kami ingin membuat grafik terarah baru dengan aturan ini:

1. Hanya node dengan nomor yang sama dapat dikontrak ke node baru yang sama. $F(x) \neq F(y) \Rightarrow x' \neq y'$ . (Namun, $x' \neq y'\nRightarrow F(x) \neq F(y)$ .)
2. Kami menambahkan semua tepi lama antara node baru: $(x,y) \in E \land x' \neq y' \iff (x',y')\in E'$ .
3. Grafik baru ini masih berupa DAG.

Apa yang minimal $|V'|$? Apa yang dimaksud dengan algoritma yang membuat grafik baru minimal?

Salah satu pendekatan untuk memecahkan masalah ini adalah dengan menggunakan integer linear programming (ILP). Mari kita menangani versi keputusan dari masalah: mengingat , apakah ada cara untuk mengontrak simpul dengan warna yang sama untuk mendapatkan DAG ukuran ≤ k ?$k$$\le k$

Ini dapat dinyatakan sebagai instance ILP menggunakan teknik standar. Kami diberi warna setiap simpul dalam grafik asli. Saya menyarankan agar kita memberi label pada setiap simpul dengan label pada ; semua simpul dengan label yang sama dan warna yang sama akan dikontrak. Jadi, masalah keputusan menjadi: apakah ada pelabelan, sehingga membuat kontrak semua simpul dengan label yang sama warnanya menghasilkan DAG?$\{1,2,\dots,k\}$

Untuk menyatakan ini sebagai program linear integer, perkenalkan variabel integer untuk setiap vertex v , untuk mewakili label pada vertex v . Tambahkan ketimpangan 1 ≤ ℓ v ≤ k .$\ell_v$$v$$v$$1 \le \ell_v \le k$

Langkah selanjutnya adalah menyatakan persyaratan bahwa grafik yang dikontrak haruslah DAG. Perhatikan bahwa jika ada pelabelan formulir yang tercantum di atas, tanpa kehilangan keumuman ada pelabelan di mana label menginduksi semacam topologi pada grafik yang dikontrak (yaitu, jika mendahului w dalam grafik yang dikontrak, maka label v 's lebih kecil dari label w ). Jadi, untuk setiap tepi v → w dalam grafik asli, kami akan menambahkan batasan bahwa v dan w memiliki label dan warna yang sama, atau label v lebih kecil dari label w . Khususnya, untuk setiap sisi $v$$w$$v$$w$$v\to w$$v$$w$$v$$w$ dalam grafik awal di mana v , w memiliki warna yang sama, tambahkan ketidaksetaraan ℓ v ≤ ℓ w . Untuk setiap tepi v → w di mana v , w memiliki warna yang berbeda, tambahkan ketidaksetaraan ℓ v < ℓ w .$v\to w$$v,w$$\ell_v \le \ell_w$$v \to w$$v,w$$\ell_v < \ell_w$

Sekarang lihat apakah ada solusi yang layak untuk program linear integer ini. Akan ada solusi yang layak jika dan hanya jika pelabelan adalah dari bentuk yang diinginkan (yaitu, mengontrak semua simpul sama-warna sama label yang sama menghasilkan DAG). Dengan kata lain, akan ada solusi yang layak jika dan hanya jika ada cara untuk mengontrak grafik asli ke DAG dengan ukuran . Kita dapat menggunakan pemecah program linear integer apa pun; jika pemecah ILP memberi kita jawaban, kita punya jawaban untuk masalah keputusan semula.$\le k$

Tentu saja, ini tidak dijamin selesai dalam waktu polinomial. Tidak ada jaminan. Namun, pemecah ILP sudah cukup bagus. Saya berharap bahwa, untuk grafik berukuran wajar, Anda memiliki peluang yang layak bahwa pemecah ILP mungkin dapat memecahkan masalah ini dalam jumlah waktu yang wajar.

Dimungkinkan juga untuk menyandikan ini sebagai instance SAT dan menggunakan pemecah SAT. Saya tidak tahu apakah itu akan lebih efektif. Versi ILP mungkin lebih mudah dipikirkan.

(Saya harap ini benar. Saya belum memeriksa setiap detail dengan hati-hati, jadi silakan periksa kembali alasan saya! Saya harap saya tidak pergi entah ke mana.)

Pembaruan (10/21): Sepertinya ILP dari formulir ini dapat diselesaikan dalam waktu linier, dengan memproses DAG dalam urutan yang diurutkan secara topologi dan melacak batas bawah pada label untuk setiap titik. Ini membuat saya curiga terhadap solusi saya: apakah saya membuat kesalahan di suatu tempat?

CATATAN: AFAICT, DW menemukan lubang dalam pengurangan ini dan itu salah (lihat komentar). Menyimpannya di sini karena alasan historis.

Intro : pertama saya akan mengurangi masalah Monotone 3SAT menjadi masalah kita. Meskipun masalah Monotone 3SAT sepele memuaskan, masalah kami selanjutnya dapat memecahkan masalah Minimum True Monotone 3SAT , yang NP-hard; dengan demikian masalah ini NP-hard.

Pengurangan dari Monotone 3SAT ke masalah kita

Kami memiliki rumus monoton boolean yang dinyatakan sebagai urutan variabel, dan urutan klausa. CNF berbentuk sedemikian rupa sehingga:$\Phi = (\mathcal V,\mathcal C)$

dan

Konversi

Kami membuat grafik, . Setiap simpul dalam G ′ memiliki label; simpul dengan label yang sama memenuhi syarat untuk kontraksi.$G'=V',E'$$G'$

Pertama-tama kita membuat grafik sebagai berikut: untuk setiap , kita membuat dua node, masing-masing berlabel x i , dan tepi terarah dari satu ke yang lain (klik gambar untuk tampilan resolusi tinggi).$x_i \in \mathcal V$$x_i$

Node ini tentu saja dapat dikontrak, karena mereka memiliki label yang sama. Kami akan mempertimbangkan variabel / node yang dikontrak untuk dinilai sebagai false, dan yang tidak dikontrak untuk dinilai sebagai benar :

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

Berikut ini visualisasi lain, membuka gulungan batasan klausa:

Jadi, setiap batasan klausa mensyaratkan bahwa setidaknya satu dari variabel yang dikandungnya tetap tidak berkontraksi; karena node yang tidak dikontrak dihargai sebagai benar, ini mengharuskan salah satu variabel menjadi benar; persis apa yang diminta SAT monoton untuk klausulnya.

Pengurangan dari Minimum True Monotone 3SAT

Monotone 3SAT sepele memuaskan; Anda cukup mengatur semua variabel menjadi true.

Namun, karena masalah minimisasi DAG kami adalah menemukan kontraksi terbanyak, ini berarti menemukan penugasan yang memuaskan yang menghasilkan variabel paling salah di CNF kami; yang sama dengan menemukan variabel benar minimum. Ini masalah kadang-kadang disebut Minimum Benar Monoton 3SAT atau di sini (sebagai masalah optimasi, atau masalah keputusan), atau k-Benar Monoton 2SAT (sebagai masalah keputusan lemah); kedua masalah NP-keras. Jadi masalah kita NP-hard.

Referensi:

• Minimum True Monoton 3SAT
• Buktikan NP-kelengkapan memutuskan kepuasan formula monoton boolean
• Monotone-2SAT dan Vertex Cover

Sumber grafik:

• sumber pada intisari
• lihat di writelatex

Dengan setiap penggantian (kecuali untuk penggantian orangtua-anak-anak langsung), Anda menambahkan hubungan leluhur-keturunan baru yang membuatnya tidak sepele untuk menentukan mana yang benar-benar layak untuk jangka panjang. Oleh karena itu, algoritma serakah sederhana akan gagal dalam kasus umum. Namun, jika Anda melakukan pendekatan brute-force, Anda dapat menentukan grafik terkecil:

Python-ish (tidak diuji):

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)

Saya tidak yakin apakah itu benar-benar masalah yang sulit, tetapi bermain dengan beberapa grafik secara manual, sepertinya sangat kombinatorial. Saya ingin tahu apakah sesuatu yang sulit dapat dikurangi untuk masalah ini, atau jika ada algoritma dengan waktu berjalan yang lebih baik.