У нас есть DAG. У нас есть функция на узлах (грубо говоря, мы нумеруем узлы). Мы хотели бы создать новый ориентированный граф с этими правилами:
- Только узлы с одинаковым номером могут быть заключены в один и тот же новый узел. . (Однако .)x ′ ≠ y ′ ⇏ F ( x ) ≠ F ( y )
- Мы добавляем все старые ребра между новыми узлами: .
- Этот новый график все еще DAG.
Что такое минимальное ? Что такое алгоритм создания минимального нового графа?
Ответы:
Одним из подходов к решению этой проблемы было бы использование целочисленного линейного программирования (ILP). Давайте рассмотрим вариант решения проблемы: учитывая , есть ли способ сжимать вершины одного цвета, чтобы получить DAG размера ?≤ kК ≤ k
Это можно выразить как экземпляр ILP с использованием стандартных методов. Нам дан цвет каждой вершины в исходном графе. Я предлагаю пометить каждую вершину меткой в ; все вершины с одинаковой меткой и одинаковым цветом будут сокращены. Итак, решается проблема: существует ли маркировка, такая, что сжатие всех вершин одного цвета с одинаковой меткой дает DAG?{ 1 , 2 , … , к }
Чтобы выразить это как целочисленную линейную программу, целочисленную переменную для каждой вершины , чтобы представить метку на вершине . Добавьте неравенство . v v 1 ≤ л v ≤ Kℓv v v 1 ≤ ℓv≤ k
Следующим шагом является выражение требования, чтобы контрактный граф был DAG. Обратите внимание, что если есть маркировка формы, перечисленной выше, без потери общности существует такая маркировка, где метки индуцируют топологическую сортировку на сжатом графе (т. Е. Если предшествует в свернутом графе, то метка ' меньше, чем метка ). Таким образом, для каждого ребра в исходном графе мы добавим ограничение, что либо и имеют одинаковую метку и одинаковый цвет, либо метка меньше метки . Конкретно для каждого ребраw v w v → w v w v w v → w v , w ℓ v ≤ ℓ w v → w v , w ℓ v < ℓ wv вес v вес V → W v вес v вес V → W в начальном графе, где имеют одинаковый цвет, добавьте неравенство . Для каждого ребра где имеют разные цвета, добавьте неравенство .V , W ℓv≤ ℓвес V → W V , W ℓv< ℓвес
Теперь посмотрим, есть ли возможное решение этой целочисленной линейной программы. Будет возможным решением, если и только если маркировка имеет желаемую форму (т. Е. Сокращение всех вершин одного цвета с одинаковой меткой дает DAG). Другими словами, будет выполнимое решение тогда и только тогда, когда есть способ свернуть исходный граф с DAG размера . Мы можем использовать любой решатель целочисленного линейного программирования; если решатель ILP дает нам ответ, у нас есть ответ на первоначальное решение проблемы.≤ k
Конечно, это не гарантированно завершится за полиномиальное время. Там нет никаких гарантий. Тем не менее, ILP решатели получили довольно хорошо. Я ожидаю, что для графа разумного размера у вас есть хороший шанс, что решатель ILP сможет решить эту проблему за разумное время.
Также возможно закодировать это как экземпляр SAT и использовать решатель SAT. Я не знаю, будет ли это более эффективным. Версия ILP, вероятно, легче думать, хотя.
(Надеюсь, это правильно. Я не проверил каждую деталь тщательно, поэтому, пожалуйста, перепроверьте мои рассуждения! Надеюсь, я не ошибся.)
Обновление (10/21): Похоже, что ILP этой формы можно решить за линейное время, обрабатывая DAG в топологически отсортированном порядке и отслеживая нижнюю границу метки для каждой вершины. Это вызывает у меня подозрение по поводу моего решения: я где-то допустил ошибку?
источник
ПРИМЕЧАНИЕ: AFAICT, DW нашел дыру в этом сокращении, и это неправильно (см. Комментарии). Хранение здесь по историческим причинам.
Введение : сначала я сведу проблему Monotone 3SAT к нашей проблеме. Хотя проблема Monotone 3SAT тривиально выполнима, наша проблема может дополнительно решить проблему Minimum True Monotone 3SAT , которая является NP-трудной; таким образом, эта проблема является NP-трудной.
Сокращение от Monotone 3SAT до нашей проблемы
У нас есть монотонная логическая формула, выраженная в виде последовательности переменных и последовательности предложений. CNF имеет вид такой, что:Φ = ( V, C)
и
преобразование
Построим граф, . Каждая вершина в G ' имеет метку; вершины с одинаковыми метками имеют право на сжатие.грамм'= V', E' грамм'
Сначала мы построим график следующим образом: для каждого мы создадим два узла, каждый из которых помечен x i , и направленный край от одного к другому (щелкните изображения для просмотра в высоком разрешении).Икся∈ V Икся
Эти узлы, конечно, могут быть сокращены, потому что они имеют одинаковую метку. Мы будем рассматривать переменные / узлы, которые по контракту, будут оценены как ложные, а те, которые не сокращены, будут оценены как истинные :
Вот еще одна визуализация, разворачивающая ограничение предложения:
Таким образом, каждое ограничение предложения требует, чтобы по крайней мере одна из переменных, которые в нем содержались, оставалась не сокращенной; поскольку несокращенные узлы оцениваются как истинные, для этого требуется, чтобы одна из переменных была истинной; именно то, что Monotone SAT требует для своих пунктов.
Сокращение от минимального истинного монотона 3SAT
Монотон 3SAT тривиально удовлетворителен; Вы можете просто установить все переменные в true.
Тем не менее, поскольку наша задача минимизации DAG состоит в том, чтобы найти наибольшее количество сокращений, это означает, что нужно найти удовлетворяющее назначение, которое дает большинство ложных переменных в нашем CNF; что аналогично нахождению минимальных истинных переменных. Эта проблема иногда называется Minimum True Monotone 3SAT или здесь (как проблема оптимизации или проблема решения), или k-True Monotone 2SAT (как проблема с более слабым решением); обе NP-сложные проблемы. Таким образом, наша проблема является NP-трудной.
Ссылки:
График источников:
источник
С каждой заменой (за исключением прямых замен родитель-потомок) вы добавляете новые отношения предок-потомок, которые делают нетривиальным определение того, какой из них действительно стоит в долгосрочной перспективе. Следовательно, простой жадный алгоритм в общем случае потерпит неудачу. Однако, если вы используете метод грубой силы, вы можете определить наименьший график:
Python-ish (не проверено):
Я не уверен, что это действительно сложная проблема, но играя с некоторыми графиками вручную, это кажется очень комбинаторным. Мне любопытно, если что-то сложное можно свести к этой проблеме, или есть алгоритм с лучшим временем выполнения.
источник