作者DJWS (...)
看板Prob_Solve
标题Re: [讨论] UVa12615
时间Thu Jan 15 22:54:46 2015
※ 引述《dreamoon (大笨蛋小月唷!)》之铭言：
1F：推 FRAXIS: 题目要求是不是要找一个maximal matching? 01/15 05:21
2F：→ 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。
本题是求後者。最小
权重边支配集。
然後前面介绍的那些极大极小关系，到了这边也成立。
如果我没搞错的话。
-----------
3F：推 FRAXIS: 题目要求是不是要找一个maximal matching?
这题跟极大没有关系。
再者，最小边支配集 != 最大边独立集(最大匹配)。
除非这题的图是某种特殊图类，刚好满足你说的那样。这部分我不清楚。
4F：→ dreamoon: 若把边当点，大概可以应转成一般图的最大独立集
最小边支配集 != 最大边独立集(最大匹配)。
-----------
结论就是不要再肖想独立集了，除非那是一种特殊的图类。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.250.88.58
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1421333690.A.4F6.html
※ 编辑: DJWS (111.250.88.58), 01/15/2015 22:57:59
5F：推 dreamoon: 不过这题显然就是特殊图 01/15 23:22
6F：推 dreamoon: 我喜欢FRAXIS所说的用tree decomposition去思考它 01/15 23:24
7F：→ dreamoon: 这样去思考感觉上比较有系统 01/15 23:24
9F：→ DJWS: 有线性时间算法 01/15 23:48
10F：→ DJWS: 不过我还没查到reference 01/15 23:48
11F：推 dreamoon: 线性是把tree-width当常数?若是这样应该就和我的方法 01/15 23:55
12F：→ dreamoon: 差不多 01/15 23:55
※ 编辑: DJWS (111.250.84.205), 01/16/2015 11:13:46