Jakiś czas temu wysłałem prośbę o referencję dotyczącą problemów z grafem, w której chcemy znaleźć 2-partycję krawędzi, w której oba zestawy spełniają właściwość niezwiązaną z ich licznością. Próbowałem udowodnić, że następujący problem jest NP-trudny:
Biorąc pod uwagę turniej , czy istnieje zestaw sprzężeń zwrotnych F ⊆ E w G, który definiuje relację przechodnią?
Mam konstrukcję na próbę dowodu, ale wygląda na to, że wpadnie to w ślepy zaułek, więc pomyślałem, że mogę tutaj zapytać, czy coś mi brakuje. Aby nie ograniczać swojej kreatywności do kierunków myślenia podobnych do tych, z których korzystałem, nie zamieszczę tutaj mojej próby.
Czy ten problem jest trudny NP? Jeśli tak, jak to udowodnić?
np-hardness
reductions
G. Bach
źródło
źródło
Odpowiedzi:
Aby dodać mały kontekst, oto konstrukcja wykresu, który nie ma ustawionego łuku przechodniego sprzężenia zwrotnego. Do tej konstrukcji użyję następującego wykresu gadżetów:
Ten turniej ma następujące właściwości (które sprawdziłem za pomocą programu, nie udowodniłem tego formalnie):
lub nieco nadużywając notacji logiki predykatu:
Zauważysz, że dla każdej implikacji dwie krawędzie są rozłączone parami, więc następujące prace budowlane:
źródło
Uruchomiłem krótki program clingo, który nie zgłosił żadnego wykresu bez TFAS, ale wystąpił błąd. Naprawiłem to i teraz sprawdza, czy nie ma wykresu bez TFAS dla n = 8 lub mniej. Dla n = 9 znajduje to:
Oto (stałe) kodowanie
Uruchom go za
clingo -c n=7 tfas.asp
pomocą (Korzystanie z clingo 4.2.1)(n = 7 oznacza wykresy dokładnie 7 wierzchołków)
Powinien zwrócić zadowalający wtedy i tylko wtedy, gdy istnieje wykres bez TFAS na 7 wierzchołkach.
Ok, zorientowałem się, co opisuje wykres @ G.Bach, i zakodowałem go w clingo (patrz opis clingo poniżej. Zaczyna się od opisu wykresu gadżetów i przechodzi do opisu, jak połączyć kopie razem, aby uzyskać pełny Opis 34-wierzchołkowego turnieju G.Bach opisuje. Załączam również opis uziemionego grafu).
Następnie zacząłem uruchamiać clingo na tym wykresie i twierdziłem, że znalazłem TFAS z 241 krawędziami. Ale popełniłem błąd w kodowaniu wykresu. Naprawiłem błąd, a clingo zgłasza teraz niezadowolenie (tzn. Nie ma TFAS).
Oto program znajdowania TFAS na wykresie
Oto (zaktualizowany) program do generowania wykresu G.Bacha. Na końcu dodałem wskaźniki, aby sprawdzić, czy wykres jest dobrze uformowanym wykresem turniejowym:
źródło
Przypuszczenie SWAG [coś lepszego niż nic?]:
uwagi: Witamy w kontrprzykładach! jak dotąd wydaje się, że nie podano żadnego. jeszcze lepsze byłyby niektóre obserwacje wzorów orientacji krawędzi związanych z poszczególnymi klasami grafów. lub trochę więcej motywacji lub powiązanie jej z istniejącą literaturą. oferowane w stylu dowodów i odrzuceń (Lakatos) ... również, ponieważ wydaje się tak niecodzienny problem, który [jeszcze?] nie odnosi się do wielu, sugeruje zbadanie go empirycznie ...
źródło