Набор дуги переходной обратной связи (TFAS): NP-полная?

13

Некоторое время назад я опубликовал справочный запрос для задач с графами, где мы хотим найти 2-секционное ребро, в котором оба набора удовлетворяют свойству, не связанному с их количеством элементов. Я пытался доказать, что следующая проблема NP-трудна:

Для турнира существует ли множество дуг обратной связи в которое определяет транзитивное отношение?граммзнак равно(В,Е)FЕграмм

У меня есть конструкция для попытки доказательства, но похоже, что это зашло в тупик, поэтому я подумал, что могу спросить здесь, чтобы увидеть, не упустил ли я что-то очевидное. Чтобы не ограничивать ваше творчество тем, что я использовал, я не буду размещать здесь свои попытки.

Эта проблема NP-сложная? Если да, то как это доказать?

Г. Бах
источник
1
отлично, спасибо! (Я удалил комментарий, потому что я написал G = (E, V) вместо стандартного G = (V, E) :-)
Марцио Де Биаси
6
Если я правильно понимаю, это равносильно тому, чтобы спросить, можно ли разделить ребра в турнире на два DAG, один из которых транзитивно закрыт.
dspyz
1
По поводу комментариев dspyz, существует не так много проблем с DAG, которые можно изучить из-за их сложности. даже не так много теорем о DAG, казалось бы. деревья немного более доступны. Ваша проблема (хотя и интересная, как отражено в голосах), похоже, смешивает множество необычных элементов и не вписывается ни в какую конкретную категорию.
ВЗН
5
@IgorShinkar дуги любого орграфа можно тривиально разбить на две группы DAG: произвольно упорядочить вершины; один DAG - это передние края, другой DAG - это задние края.
Сашо Николов
1
@SashoNikolov конечно!
Игорь Шинкарь

Ответы:

4

Чтобы добавить немного контекста, вот конструкция для графа, в котором не установлена ​​дуга транзитивной обратной связи. Для этой конструкции я буду использовать следующий график гаджетов:

График гаджетов, используемый для усиления последствий

Этот турнир имеет следующие свойства (которые я проверил с помощью программы, я не доказал это формально):

  • если (2,7) не входит в данный TFAS, то (1,3)
  • если (5,1) находится в данном TFAS, то и (3,6)
  • если (7,3) находится в данном TFAS, то (5,1) не

или немного неправильное использование логики предикатов:

  • ¬(2,7)(1,3)
  • (5,1)(3,6)
  • (7,3)¬(5,1)

Вы заметите, что для каждого следствия два ребра попарно не пересекаются, поэтому работает следующая конструкция:

конструкция для графа, который не имеет TFAS

A

Г. Бах
источник
Прости, я не следую. Есть ли какая-то причина, по которой вы не можете просто опубликовать список ребер, чтобы я мог запустить его через решатель ASP и попытаться проверить это? Согласно Clingo, ваш график гаджетов имеет 8 различных TFAS. Вот самый маленький из них: tfas (край (5,0)) tfas (край (6,0)) tfas (край (7,0)) tfas (край (6,2)) tfas (край (7,3)) tfas (edge ​​(1,2)) tfas (edge ​​(1,3)) tfas (edge ​​(7,5))
dspyz
Я только что заметил, что вы упомянули край (6,3) на графике гаджетов, но у предоставленного вами изображения есть край (3,6)
dspyz
Я понял это, см. Мой обновленный ответ: cstheory.stackexchange.com/a/20778/13643
dspyz
@dspyz Я думал, что конструкция была более понятной, чем просто список ребер, так как, если мои рассуждения не ошибочны, все, что потребуется, чтобы проверить, - действительно ли у турнира выше конструкции есть эти свойства импликации. Спасибо за указание на ошибку по краю (3,6)! Я также получил 8 TFAS за этот гаджет, один из которых вы перечислили.
Г. Бах
Мне жаль. Я построил график неправильно. Я исправил это, и clingo теперь сообщает об отсутствии TFAS.
dspyz
1

Я запустил короткую программу-клинго, которая не показала ни одного графика без TFAS, но была ошибка. Я исправил это, и теперь он проверяет, что нет графа без TFAS для n = 8 или меньше. Для n = 9 он находит это:

is_edge(edge(2,3)) is_edge(edge(1,4)) is_edge(edge(2,4)) is_edge(edge(3,5)) is_edge(edge(4,5)) is_edge(edge(1,6)) is_edge(edge(2,6)) is_edge(edge(3,6)) is_edge(edge(5,6)) is_edge(edge(1,7)) is_edge(edge(4,7)) is_edge(edge(5,7)) is_edge(edge(6,7)) is_edge(edge(1,8)) is_edge(edge(3,8)) is_edge(edge(4,8)) is_edge(edge(5,9)) is_edge(edge(6,9)) is_edge(edge(7,9)) is_edge(edge(2,1)) is_edge(edge(3,1)) is_edge(edge(4,3)) is_edge(edge(5,1)) is_edge(edge(5,2)) is_edge(edge(6,4)) is_edge(edge(7,2)) is_edge(edge(7,3)) is_edge(edge(8,2)) is_edge(edge(8,5)) is_edge(edge(8,6)) is_edge(edge(8,7)) is_edge(edge(9,1)) is_edge(edge(9,2)) is_edge(edge(9,3)) is_edge(edge(9,4)) is_edge(edge(9,8))

Вот (фиксированная) кодировка

% tfas.asp
#show is_edge/1.
vertex(1..n).

opp_edges(edge(A,B),edge(B,A)) :- vertex(A), vertex(B), A < B.
possible_edge(E1;E2) :- opp_edges(E1,E2).

{is_edge(E1); is_edge(E2)} = 1 :- opp_edges(E1, E2).
ntfas(E) :- possible_edge(E), not is_edge(E).
ntfas(edge(X, X)) :- vertex(X).

tfas(E) | fs(E) :- is_edge(E).
ntfas(E) :- fs(E).

broken :- ntfas(edge(A,C)), tfas(edge(A, B)), tfas(edge(B,C)).

reachable(X, Y) :- fs(edge(X, Y)), is_edge(edge(X, Y)).
reachable(X, Z) :- reachable(X, Y), fs(edge(Y, Z)), is_edge(edge(Y, Z)).
broken :- reachable(X, X).

tfas(E) :- broken, possible_edge(E).
fs(E) :- broken, possible_edge(E).
:- not broken.

Запустите его с 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 на графике

{tfas(E)} :- is_edge(E).
:- not tfas(edge(A,C)), tfas(edge(A, B)), tfas(edge(B,C)).

reachable(X, Y) :- not tfas(edge(X, Y)), is_edge(edge(X, Y)).
reachable(X, Z) :- reachable(X, Y), not tfas(edge(Y, Z)), is_edge(edge(Y, Z)).
:- reachable(X, X).

tfas_count(N) :- N = #count{tfas(E) : tfas(E)}.

#show tfas/1.
#show tfas_count/1.

Вот (обновленная) программа для генерации графа Г.Баха. В конце я добавил индикаторы, чтобы убедиться, что график является правильно сформированным графиком турнира:

gadget_vertex(0..7).

gadget_edge(0,1).
gadget_edge(0,2).
gadget_edge(0,3).
gadget_edge(0,4).
gadget_edge(1,2).
gadget_edge(1,3).
gadget_edge(1,6).
gadget_edge(1,7).
gadget_edge(2,3).
gadget_edge(2,4).
gadget_edge(2,5).
gadget_edge(2,7).
gadget_edge(3,4).
gadget_edge(3,5).
gadget_edge(3,6).
gadget_edge(4,1).
gadget_edge(4,5).
gadget_edge(4,6).
gadget_edge(4,7).
gadget_edge(5,0).
gadget_edge(5,1).
gadget_edge(5,6).
gadget_edge(6,0).
gadget_edge(6,2).
gadget_edge(6,7).
gadget_edge(7,0).
gadget_edge(7,3).
gadget_edge(7,5).

special_edge(a;b;c;d;e).

forces(a,b).
forces(b,c).
forcesn(c,a).
nforces(a,d).
forces(d,e).
forces(e,a).

relates(A,B) :- forces(A,B).
relates(A,B) :- nforces(A,B).
relates(A,B) :- forcesn(A,B).

is_se_pair(se_pair(A,B)) :- relates(A,B).
vertex_name(v(V,P)) :- gadget_vertex(V), is_se_pair(P).

matches(from(A), v(5, se_pair(A,B))) :- forces(A,B).
matches(to(A), v(1, se_pair(A,B))) :- forces(A,B).
matches(from(B), v(3, se_pair(A,B))) :- forces(A,B).
matches(to(B), v(6, se_pair(A,B))) :- forces(A,B).

matches(from(A), v(2, se_pair(A,B))) :- nforces(A,B).
matches(to(A), v(7, se_pair(A,B))) :- nforces(A,B).
matches(from(B), v(1, se_pair(A,B))) :- nforces(A,B).
matches(to(B), v(3, se_pair(A,B))) :- nforces(A,B).

matches(from(A), v(7, se_pair(A,B))) :- forcesn(A,B).
matches(to(A), v(3, se_pair(A,B))) :- forcesn(A,B).
matches(from(B), v(5, se_pair(A,B))) :- forcesn(A,B).
matches(to(B), v(1, se_pair(A,B))) :- forcesn(A,B).

same_vertex(V, V) :- vertex_name(V).
same_vertex(M, N; N, M) :- matches(X, M), matches(X, N).

already_found(v(Y,N2)) :- vertex_name(v(X,N1)), same_vertex(v(X,N1),v(Y,N2)), N1 < N2.
vertex(V) :- vertex_name(V), not already_found(V).

named_gadget_edge(edge(v(X,SE),v(Y,SE))) :- gadget_edge(X,Y), is_se_pair(SE).
from_gadget_edge_named(edge(A, B), edge(C,D)) :- named_gadget_edge(edge(C,D)), same_vertex(A,C), same_vertex(B,D), vertex(A), vertex(B).
from_gadget_edge(edge(A,B)) :- from_gadget_edge_named(edge(A,B),edge(C,D)).
is_edge(E) :- from_gadget_edge(E).
is_edge(edge(A,B)) :- vertex(A), vertex(B), A < B, not from_gadget_edge(edge(B,A)).

vertex_count(VN) :- VN = #count{vertex(V) : vertex(V)}.
edge_count(EN) :- EN = #count{is_edge(E) : is_edge(E)}.

#show vertex_count/1.
#show edge_count/1.

bidirectional :- is_edge(edge(A,B)), is_edge(edge(B,A)).
phantom_vertex :- is_edge(edge(A,B)), not vertex(A).
phantom_vertex :- is_edge(edge(A,B)), not vertex(B).
incomplete :- vertex(A), vertex(B), not is_edge(edge(A,B)), not is_edge(edge(B,A)), A != B.

#show bidirectional/0.
#show phantom_vertex/0.
#show incomplete/0.
dspyz
источник
Я уверен, что есть турнир на 18 вершин, который не имеет TFAS.
Г. Бах
Можете ли вы привести это в качестве примера? Просто прикрепите файл с краями в списке
dspyz
Как мне прикрепить файл? Это может занять несколько часов, сейчас у меня нет турнира. Я тоже просчитался, должно быть 34 вершины. Вероятно, легче проверить, если я дам строительные блоки турнира.
Г. Бах
Загрузите файл на любой хост и укажите ссылку на него (см. Meta.stackexchange.com/a/4643/185877 ) или, если он имеет регулярную структуру, просто опишите его (дайте строительные блоки)
dspyz
N
0

Гипотеза о SWAG [что-то лучше, чем ничего?]:

граммзнак равно(В,Е)FЕграммО(1)

Примечания: Добро пожаловать! кажется, ничего не дано до сих пор. еще лучше были бы некоторые наблюдения паттернов ориентации ребер, связанных с конкретными классами графов. или еще какая-то мотивация или увязка с какой-либо существующей литературой. предлагается в стиле « Доказательства и опровержения» (Lakatos) ... также, поскольку кажется, что такая необычная проблема, которая [еще?] не имеет отношения ко многим, предлагает изучить ее эмпирически ....

ВЗН
источник
1
Я запустил программу, чтобы проверить, верно ли это, и обнаружил, что есть турниры, в которых не установлена ​​дуга транзитивной обратной связи. Завтра выложу один, сегодня не пойду.
Г. Бах
@vzn Можете ли вы доказать гипотезу для случайного турнира?
Игорь Шинкарь
Контрпример только с 5 вершинами: a-> b, a-> c, b-> c, d-> a, b-> d, c-> d, e-> a, e-> b, c-> e , д-> э. Для любых четырех вершин индуцированный граф содержит цикл, поэтому транзитивная группа DAG может содержать не более 3 ребер среди 3 вершин графа. Есть только 5 возможностей (все остальные триплеты являются циклами): abc, eab, dea, bcd, cde. Легко проверить, что в каждом из пяти случаев есть цикл среди остальных 7 ребер
dspyz
1
Да, ум nvr, это не контрпример
dspyz
1
@dspyz Я провел проверку методом грубой силы на всех турнирах до 8 вершин. Все они имеют наборы дуг с транзитивной обратной связью, но есть некоторые, которые вы можете использовать, чтобы создать турнир, который этого не делает.
Г. Бах