Pozytywne uporządkowanie topologiczne, weź 3

Załóżmy, że mamy macierz n na n. Czy można zmienić kolejność wierszy i kolumn, tak aby uzyskać matrycę górnego trójkąta?

To pytanie jest motywowane tym problemem: Pozytywne uporządkowanie topologiczne

Pierwotny problem decyzyjny jest co najmniej tak trudny jak ten, więc wynik kompletności NP również by go rozwiązał.

Edycja: Laszlo Vegh i Andras Frank zwrócili moją uwagę na równoważny problem zadany przez Guntera Rote'a: http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph

Edycja: Zmniejszenie pierwotnego problemu jest następujące. Załóżmy, że DAG ma tylko dwa poziomy, które odpowiadają wierszom i kolumnom macierzy. Ponadto mamy jeden pojedynczy węzeł o wadze +1. Wszyscy inni na niższym poziomie mają wagę -1, a na wyższym poziomie +1.

Problem okazał się być NP-zupełny. Możesz przeczytać więcej szczegółów tutaj i tutaj . Krótkie podsumowanie:

Redukcja wynika z problemu, który Dasgupta, Jiang, Kannan, Li i Sweedyk wykazali, że problem jest całkowity być wyjątkowo dopasowanym. Stéphane Vialette zauważył, że redukuje się to do dwustronnej unikalnej pasującej wersji tego problemu, jeśli dodamy nk izolowane węzły do ​​obu klas.

Uwaga: To jest częściowa odpowiedź oparta na domysłach i pogłoskach! Podczas gdy bardziej ogólny problem Davida Eppsteina jest NP-zupełny, być może ten jest w P.

$(A \cup B, E)$$|A|=|B|=n$

• nie może zawierać 2 idealnych dopasowań,
• $\le (1, 2, ..., n)$

Jak dotąd nie udało mi się znaleźć żadnego przykładu, w którym wykres spełnia te warunki, ale nie jest UPMX. W takim razie może są wystarczające. Można to udowodnić za pomocą następującego algorytmu:

1. jeśli wykres ma> 1 idealne dopasowanie, zwróć „nie UPMX”
2. jeśli wykres nie spełnia warunku stopnia, zwróć „nie UPMX”
3. jeśli wykres ma = 1 idealne dopasowanie, zwróć „UPMX”
4. w przeciwnym razie może pokażemy, że to UPMX. Być może następujący algorytm może to udowodnić:
   • $\le \tbinom{n+1}{2} - 2$
   • znajdź nową krawędź e, której dodanie nie tworzy idealnego dopasowania i nie narusza warunku stopnia; dodaj e do wykresu
5. $\tbinom{n+1}{2} - 1$

Możesz scharakteryzować, które nowe krawędzie stworzyłyby idealne dopasowanie, używając twierdzenia Halla, i nie jest trudno scharakteryzować, które nowe krawędzie naruszałyby stopień związany. Niestety, nawet jeśli prawdą jest, że zawsze istnieje odpowiedni typ krawędzi, nie byłem w stanie tego udowodnić.

Ten artykuł, Uzyskiwanie trójkątnej macierzy przez niezależne permutacje wierszy i kolumn Fertin, Rusu i Vialette, pokazuje, że problem jest NP-zupełny dla binarnych macierzy kwadratowych.

Problem jest NP-kompletny, ale gdzie jest algorytm do jego rozwiązania? Mam jeden algorytm, który działa na wielu przykładach, ale nie jestem w stanie wykazać, że cały czas będzie działał.