推 FRAXIS: 題目要求是不是要找一個maximal matching? 01/15 05:21
→ dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集 01/15 19:53
原題我不會解，不過我可以解釋一下支配集和獨立集
獨立集(independent set)：選出一些點，互不相鄰。
最佳化問題是越多越好。
支配集(dominating set)：選出一些點，其餘點皆與之相鄰（所有點皆與之相鄰/重疊）。
最佳化問題是越少越好。
這兩個都是NP-complete，如果考慮權重就是NP-hard。
特殊的圖類才有多項式時間解，例如tree之類的。
-----------
極大獨立集(maximal independent set): 無法再選出一些點的獨立集。
最大獨立集(maximum independent set): 點數最多的獨立集（點數最多的極大獨立集）。
極大獨立集 = 極小支配集。EDIT: 這句話有誤，請見下一篇回文
這個很好想。拿掉一個點，阿就不支配了。補上一個點，阿就不獨立了。
但是
最大獨立集 != 最小支配集
極大極小都OK了，為什麼最大最小不OK?
簡單來說，最大獨立集肯定是極小支配集，但是不一定剛好是最小支配集。
再來
最大獨立集必是支配集
最小支配集不一定是獨立集
到這裡應該有人覺得很煩了，所以就不再多提了...
-----------
邊獨立集(edge independent set): 上述的點改成邊。 就是匹配(matching)啦。
邊支配集(edge dominating set): 上述的點改成邊。
前者是P，經典的算法例如 Edmonds' blossom algorithm。
後者是NP-hard。
本題是求後者。最小權重邊支配集。
然後前面介紹的那些極大極小關係，到了這邊也成立。如果我沒搞錯的話。
-----------
推 FRAXIS: 題目要求是不是要找一個maximal matching?
這題跟極大沒有關係。
再者，最小邊支配集 != 最大邊獨立集(最大匹配)。
除非這題的圖是某種特殊圖類，剛好滿足你說的那樣。這部分我不清楚。
→ dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集
最小邊支配集 != 最大邊獨立集(最大匹配)。
-----------
結論就是不要再肖想獨立集了，除非那是一種特殊的圖類。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.88.58
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1421333690.A.4F6.html
※ 編輯: DJWS (111.250.88.58), 01/15/2015 22:57:59
推 dreamoon: 不過這題顯然就是特殊圖 01/15 23:22
推 dreamoon: 我喜歡FRAXIS所說的用tree decomposition去思考它 01/15 23:24
→ dreamoon: 這樣去思考感覺上比較有系統 01/15 23:24
→ DJWS: 有線性時間算法 01/15 23:48
→ DJWS: 不過我還沒查到reference 01/15 23:48
推 dreamoon: 線性是把tree-width當常數?若是這樣應該就和我的方法 01/15 23:55
→ dreamoon: 差不多 01/15 23:55
※ 編輯: DJWS (111.250.84.205), 01/16/2015 11:13:46