Минимальный размер заключения DAG в новый DAG

15

У нас есть DAG. У нас есть функция на узлах (грубо говоря, мы нумеруем узлы). Мы хотели бы создать новый ориентированный граф с этими правилами:F:VN

  1. Только узлы с одинаковым номером могут быть заключены в один и тот же новый узел. . (Однако .)x y F ( x ) F ( y )F(x)F(y)xyxyF(x)F(y)
  2. Мы добавляем все старые ребра между новыми узлами: (Икс,Y)ЕИкс'Y'(Икс',Y')Е' .
  3. Этот новый график все еще DAG.

Что такое минимальное |В'|? Что такое алгоритм создания минимального нового графа?

СНХ
источник
1
Таким образом, проблема решения выглядит следующим образом: учитывая DAG вершинного цвета и целое число К , решите, существует ли DAG с не более чем К вершинами, образованными сжимающимися вершинами одного цвета.
Андрас Саламон
1
Если вы заключили контракт на два подключенных узла, получите ли вы запрещенный цикл?
Юваль Фильмус
1
Нет. Прочитайте еще раз 2. Мы добавляем ребро, только если два узла после сжатия все еще различны. Если два узла сжимаются в один, мы не добавляем ребро.
chx
1
@chx Вы спрашиваете «минимальный» или «минимальный»?
Реал Слав
1
Можете ли вы дать мотивацию / BKG?
13

Ответы:

5

Одним из подходов к решению этой проблемы было бы использование целочисленного линейного программирования (ILP). Давайте рассмотрим вариант решения проблемы: учитывая , есть ли способ сжимать вершины одного цвета, чтобы получить DAG размера ?kКК

Это можно выразить как экземпляр ILP с использованием стандартных методов. Нам дан цвет каждой вершины в исходном графе. Я предлагаю пометить каждую вершину меткой в ; все вершины с одинаковой меткой и одинаковым цветом будут сокращены. Итак, решается проблема: существует ли маркировка, такая, что сжатие всех вершин одного цвета с одинаковой меткой дает DAG?{1,2,...,К}

Чтобы выразить это как целочисленную линейную программу, целочисленную переменную для каждой вершины , чтобы представить метку на вершине . Добавьте неравенство . v v 1 л vKvvv1vК

Следующим шагом является выражение требования, чтобы контрактный граф был DAG. Обратите внимание, что если есть маркировка формы, перечисленной выше, без потери общности существует такая маркировка, где метки индуцируют топологическую сортировку на сжатом графе (т. Е. Если предшествует в свернутом графе, то метка ' меньше, чем метка ). Таким образом, для каждого ребра в исходном графе мы добавим ограничение, что либо и имеют одинаковую метку и одинаковый цвет, либо метка меньше метки . Конкретно для каждого ребраw v w v w v w v w v w v , w vw v w v , w v < wvвесvвесvвесvвесvвесvвесв начальном графе, где имеют одинаковый цвет, добавьте неравенство . Для каждого ребра где имеют разные цвета, добавьте неравенство .v,весvвесvвесv,весv<вес

Теперь посмотрим, есть ли возможное решение этой целочисленной линейной программы. Будет возможным решением, если и только если маркировка имеет желаемую форму (т. Е. Сокращение всех вершин одного цвета с одинаковой меткой дает DAG). Другими словами, будет выполнимое решение тогда и только тогда, когда есть способ свернуть исходный граф с DAG размера . Мы можем использовать любой решатель целочисленного линейного программирования; если решатель ILP дает нам ответ, у нас есть ответ на первоначальное решение проблемы.К

Конечно, это не гарантированно завершится за полиномиальное время. Там нет никаких гарантий. Тем не менее, ILP решатели получили довольно хорошо. Я ожидаю, что для графа разумного размера у вас есть хороший шанс, что решатель ILP сможет решить эту проблему за разумное время.

Также возможно закодировать это как экземпляр SAT и использовать решатель SAT. Я не знаю, будет ли это более эффективным. Версия ILP, вероятно, легче думать, хотя.

(Надеюсь, это правильно. Я не проверил каждую деталь тщательно, поэтому, пожалуйста, перепроверьте мои рассуждения! Надеюсь, я не ошибся.)


Обновление (10/21): Похоже, что ILP этой формы можно решить за линейное время, обрабатывая DAG в топологически отсортированном порядке и отслеживая нижнюю границу метки для каждой вершины. Это вызывает у меня подозрение по поводу моего решения: я где-то допустил ошибку?

DW
источник
Спасибо за подробный ответ! Я получаю ограничения, и они выглядят разумно. Однако, хотя я не очень хорошо разбираюсь в ILP, я думал, что целочисленное линейное программирование нуждается в функции, которую вы хотели бы максимизировать (или минимизировать), и я нигде этого не вижу. Я проверил только в Википедии, поэтому могу ошибаться.
chx
@chx, я использую ILP для проверки выполнимости ограничений. Это можно сделать, попросив решатель ILP максимизировать любую целевую функцию, которая вам нравится (например, maximize 0), а затем проигнорировав значение целевой функции и только посмотрев, выполнимо ли ILP или нет. Либо решатель ILP отвечает «Неосуществимо» (что означает, что не существует контракта DAG размера ), либо он отвечает «Осуществимо» и предоставляет наилучшее значение целевой функции, которую он может найти; в этом случае вы игнорируете значение целевой функции (и знаете, что существует DAG размера k ). КК
DW
Смотри, например, engineering.purdue.edu/~engelb/abe565/... ( «Я просто хочу знать , является ли или не является допустимым решением существует .»)
DW
Относительно вашего линейного временного решения; Я не усвоил вашу формулировку ILP, поэтому не могу судить об этом, но я почти уверен, что смогу доказать, что проблема NP-сложная, что сделало бы линейное решение по времени весьма удобным: P. Я скоро опубликую это.
Realz Slaw
@RealzSlaw, спасибо! В этом случае я сильно подозреваю, что мог где-то ошибиться (хотя пока не уверен, где именно).
DW
5

ПРИМЕЧАНИЕ: AFAICT, DW нашел дыру в этом сокращении, и это неправильно (см. Комментарии). Хранение здесь по историческим причинам.

Введение : сначала я сведу проблему Monotone 3SAT к нашей проблеме. Хотя проблема Monotone 3SAT тривиально выполнима, наша проблема может дополнительно решить проблему Minimum True Monotone 3SAT , которая является NP-трудной; таким образом, эта проблема является NP-трудной.

Сокращение от Monotone 3SAT до нашей проблемы

У нас есть монотонная логическая формула, выраженная в виде последовательности переменных и последовательности предложений. CNF имеет вид такой, что:Φзнак равно(В,С)

и

(сяС) сязнак равно(ИксJИксКИксL)||(ИксJ,ИксК,ИксLВ)

язнак равно1Nся|сяС,Nзнак равно|С|,

преобразование

Построим граф, . Каждая вершина в G ' имеет метку; вершины с одинаковыми метками имеют право на сжатие.грамм'знак равноВ',Е'грамм'

Сначала мы построим график следующим образом: для каждого мы создадим два узла, каждый из которых помечен x i , и направленный край от одного к другому (щелкните изображения для просмотра в высоком разрешении).ИксяВИкся

введите описание изображения здесь

Эти узлы, конечно, могут быть сокращены, потому что они имеют одинаковую метку. Мы будем рассматривать переменные / узлы, которые по контракту, будут оценены как ложные, а те, которые не сокращены, будут оценены как истинные :

введите описание изображения здесь

В'2|В|сяС, сязнак равно(ИксJИксКИксL)|ИксJ,ИксК,ИксLВся

введите описание изображения здесь

ся1ся

2|В|+|С|

ИксяИксJ ИксКсяся

Вот еще одна визуализация, разворачивающая ограничение предложения:

введите описание изображения здесь

Таким образом, каждое ограничение предложения требует, чтобы по крайней мере одна из переменных, которые в нем содержались, оставалась не сокращенной; поскольку несокращенные узлы оцениваются как истинные, для этого требуется, чтобы одна из переменных была истинной; именно то, что Monotone SAT требует для своих пунктов.

Сокращение от минимального истинного монотона 3SAT

Монотон 3SAT тривиально удовлетворителен; Вы можете просто установить все переменные в true.

Тем не менее, поскольку наша задача минимизации DAG состоит в том, чтобы найти наибольшее количество сокращений, это означает, что нужно найти удовлетворяющее назначение, которое дает большинство ложных переменных в нашем CNF; что аналогично нахождению минимальных истинных переменных. Эта проблема иногда называется Minimum True Monotone 3SAT или здесь (как проблема оптимизации или проблема решения), или k-True Monotone 2SAT (как проблема с более слабым решением); обе NP-сложные проблемы. Таким образом, наша проблема является NP-трудной.


Ссылки:

График источников:

Реал Слав
источник
1
Вау. тогда решение DW должно быть неправильным (или мы доказали NP = P, в чем я хотя бы немного сомневаюсь: P) - но где?
chx
(Икс1Икс2Икс6)(Икс1Икс4Икс5)(Икс3Икс4Икс6)Икс1знак равноИкс4знак равноИкс6знак равноЛожь Икс2знак равноИкс3знак равноИкс5знак равноПравдас1Икс1Икс4Икс6с1
@DW Также приятно снова с вами поговорить: D, и удачи, если мы оба правы, у нас может быть P = NP в вашем ответе! /
JK
(Икс1,Икс3)
@RealzSlaw, боюсь, я еще не следую ... Я не вижу причин, по которым моя формула должна быть преобразована. Я считаю , что это уже является экземпляром минимальной Истинного монотонной 3SAT. Но позвольте мне поднять это на уровень. В более широком смысле я вижу предлагаемое сокращение, но я не вижу никаких аргументов в пользу того, что сокращение является правильным - это отсутствует. Чтобы сокращение было правильным, оно должно отображать экземпляры YES на экземпляры YES, а NO - на экземпляры NO. Я подозреваю, что если вы попытаетесь выписать подтверждение правильности своего сокращения, вы столкнетесь с проблемой, если рассмотрите формулу, которую я дал.
DW
1

С каждой заменой (за исключением прямых замен родитель-потомок) вы добавляете новые отношения предок-потомок, которые делают нетривиальным определение того, какой из них действительно стоит в долгосрочной перспективе. Следовательно, простой жадный алгоритм в общем случае потерпит неудачу. Однако, если вы используете метод грубой силы, вы можете определить наименьший график:

Python-ish (не проверено):

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)

Я не уверен, что это действительно сложная проблема, но играя с некоторыми графиками вручную, это кажется очень комбинаторным. Мне любопытно, если что-то сложное можно свести к этой проблеме, или есть алгоритм с лучшим временем выполнения.

Реал Слав
источник
1
Мне тоже любопытно :)
chx