※ 引述《dreamoon (大笨蛋小月唷!)》之銘言：
推 FRAXIS: 題目要求是不是要找一個maximal matching? 01/15 05:21
→ dreamoon: 若把邊當點，大概可以應轉成一般圖的最大獨立集 01/15 19:53
原題我不會解，不過我可以解釋一下支配集和獨立集
獨立集(independent set)：選出一些點，互不相鄰。
　　　　　　　　　　　　 最佳化問題是越多越好。
支配集(dominating set)：選出一些點，其餘點皆與之相鄰（所有點皆與之相鄰/重疊）。
　　　　　　　　　　　　最佳化問題是越少越好。
這兩個都是NP-complete，如果考慮權重就是NP-hard。
特殊的圖類才有多項式時間解，例如tree之類的。

題目要求是不是要找一個maximal matching?

若把邊當點，大概可以應轉成一般圖的最大獨立集不過這題顯然就是特殊圖我喜歡FRAXIS所說的用tree decomposition去思考它這樣去思考感覺上比較有系統

http://www.graphclasses.org/classes/gc_899.html有線性時間算法不過我還沒查到reference

線性是把tree-width當常數?若是這樣應該就和我的方法差不多