Некоторое время назад я опубликовал справочный запрос для задач с графами, где мы хотим найти 2-секционное ребро, в котором оба набора удовлетворяют свойству, не связанному с их количеством элементов. Я пытался доказать, что следующая проблема NP-трудна:
Для турнира существует ли множество дуг обратной связи в которое определяет транзитивное отношение?
У меня есть конструкция для попытки доказательства, но похоже, что это зашло в тупик, поэтому я подумал, что могу спросить здесь, чтобы увидеть, не упустил ли я что-то очевидное. Чтобы не ограничивать ваше творчество тем, что я использовал, я не буду размещать здесь свои попытки.
Эта проблема NP-сложная? Если да, то как это доказать?
np-hardness
reductions
Г. Бах
источник
источник
Ответы:
Чтобы добавить немного контекста, вот конструкция для графа, в котором не установлена дуга транзитивной обратной связи. Для этой конструкции я буду использовать следующий график гаджетов:
Этот турнир имеет следующие свойства (которые я проверил с помощью программы, я не доказал это формально):
или немного неправильное использование логики предикатов:
Вы заметите, что для каждого следствия два ребра попарно не пересекаются, поэтому работает следующая конструкция:
источник
Я запустил короткую программу-клинго, которая не показала ни одного графика без TFAS, но была ошибка. Я исправил это, и теперь он проверяет, что нет графа без TFAS для n = 8 или меньше. Для n = 9 он находит это:
Вот (фиксированная) кодировка
Запустите его с
clingo -c n=7 tfas.asp
помощью (используя clingo 4.2.1)(n = 7 обозначает графики ровно 7 вершин)
Он должен возвращать выполнимо тогда и только тогда, когда существует граф без TFAS на 7 вершинах.
Хорошо, я выяснил, что граф @G.Bach описывал, и закодировал его в clingo (см. Описание clingo ниже. Оно начинается с описания графа гаджета и далее описывает, как объединять его копии, чтобы получить полную Граф с 34 вершинными турнирами описывает Г.Бах. Я также приложил описание обоснованного графа).
Затем я приступил к запуску клинго на этом графике, и он утверждал, что нашел TFAS с 241 ребром. Но я ошибся в кодировке графа. Я исправил ошибку, и теперь clingo сообщает о неудовлетворительности (т.е. TFAS отсутствует).
Вот программа для нахождения TFAS на графике
Вот (обновленная) программа для генерации графа Г.Баха. В конце я добавил индикаторы, чтобы убедиться, что график является правильно сформированным графиком турнира:
источник
Гипотеза о SWAG [что-то лучше, чем ничего?]:
Примечания: Добро пожаловать! кажется, ничего не дано до сих пор. еще лучше были бы некоторые наблюдения паттернов ориентации ребер, связанных с конкретными классами графов. или еще какая-то мотивация или увязка с какой-либо существующей литературой. предлагается в стиле « Доказательства и опровержения» (Lakatos) ... также, поскольку кажется, что такая необычная проблема, которая [еще?] не имеет отношения ко многим, предлагает изучить ее эмпирически ....
источник