※ 引述《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当常数?若是这样应该就和我的方法差不多