Pemesanan topologi positif, ambil 3

Misalkan kita memiliki matriks n oleh n. Apakah mungkin untuk menyusun ulang baris dan kolomnya sehingga kita mendapatkan matriks segitiga-atas?

Pertanyaan ini dimotivasi oleh masalah ini: Urutan topologis positif

Masalah keputusan awal setidaknya sekeras yang ini, jadi hasil NP-kelengkapan akan menyelesaikannya juga.

Sunting: Laszlo Vegh dan Andras Frank meminta perhatian saya pada masalah serupa yang diajukan oleh Gunter Rote: http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph

Sunting: Pengurangan masalah asli adalah sebagai berikut. Misalkan DAG hanya memiliki dua level, ini akan sesuai dengan baris dan kolom dari matriks. Selain itu, kami memiliki satu simpul tunggal dengan bobot +1. Semua orang di level bawah memiliki bobot -1 dan pada level atas +1.

Masalahnya ternyata NP-lengkap. Anda dapat membaca lebih detail di sini dan di sini . Ringkasan singkat:

Pengurangan dari masalah ditunjukkan sebagai NP-lengkap oleh Dasgupta, Jiang, Kannan, Li, dan Sweedyk: diberi grafik bipartit G dan integer k, putuskan apakah G memiliki subgraf yang diinduksi pada simpul 2k yang dapat diperluas ke bisa dicocokkan secara unik. Telah diamati oleh Stéphane Vialette bahwa ini mengurangi versi pencocokan unik bipartit dari masalah ini jika kita menambahkan nk node terisolasi ke kedua kelas.

Perhatian: Ini adalah jawaban parsial berdasarkan dugaan dan desas-desus! Sedangkan masalah David Eppstein yang lebih umum adalah NP-complete, mungkin yang ini ada di P.

Katakanlah grafik bipartit dengan adalah "UPMX" jika dapat diperpanjang ke grafik dengan pencocokan sempurna yang unik. Berikut adalah beberapa kondisi yang diperlukan untuk UPMX:| A | = | B | = $(A \cup B, E)$$|A|=|B|=n$

• itu tidak boleh mengandung 2 pasangan yang sempurna,
• urutan derajat A, ketika diurutkan dalam urutan yang meningkat, harus sesuai komponen , dan juga untuk B. Saya akan menyebutnya "kondisi derajat."$\le (1, 2, ..., n)$

Sejauh ini, saya belum dapat menemukan contoh di mana grafik memenuhi kondisi ini, tetapi gagal menjadi UPMX. Kalau begitu, mungkin mereka sudah cukup. Orang mungkin membuktikan ini dengan algoritma berikut:

1. jika grafik memiliki> 1 kecocokan sempurna, kembalikan "bukan UPMX"
2. jika grafik gagal pada kondisi derajat, kembalikan "bukan UPMX"
3. jika grafik memiliki = 1 pencocokan sempurna, kembalikan "UPMX"
4. kalau tidak, mungkin kita bisa menunjukkan itu adalah UPMX. Mungkin algoritma berikut dapat membuktikannya:
   • sedangkan grafik memiliki tepi,$\le \tbinom{n+1}{2} - 2$
   • temukan beberapa keunggulan baru e yang tambahannya tidak menciptakan kecocokan yang sempurna dan tidak melanggar kondisi derajat; tambahkan e ke grafik
5. sekarang grafik memiliki tepi dan tidak ada yang cocok sempurna, dan memenuhi kondisi derajat. Saya pikir itu tidak terlalu sulit untuk menunjukkan itu adalah UPMX, maka grafik aslinya juga demikian.$\tbinom{n+1}{2} - 1$

Anda dapat menandai tepi baru mana yang akan menciptakan pencocokan sempurna dengan menggunakan teorema Hall, dan tidak sulit untuk mengkarakterisasi tepi baru mana yang akan melanggar batas derajat. Sayangnya, meskipun benar bahwa edge dari tipe yang tepat selalu ada, saya belum dapat membuktikannya.

Makalah ini, Memperoleh matriks segitiga dengan permutasi kolom-baris independen Fertin, Rusu, dan Vialette, menunjukkan bahwa masalahnya adalah NP-lengkap untuk matriks persegi biner.

Masalahnya adalah NP-complete tetapi di mana algoritma untuk menyelesaikannya? Saya memiliki satu algoritme yang berfungsi pada banyak contoh, tetapi saya tidak dapat mendemonstrasikannya akan bekerja setiap saat.