※ 引述《FRAXIS (喔喔)》之铭言：
: ※ 引述《DJWS (...)》之铭言：
: : 推 FRAXIS: 题目要求是不是要找一个maximal matching?
: : 这题跟极大没有关系。
: : 再者，最小边支配集 != 最大边独立集(最大匹配)。
: : 除非这题的图是某种特殊图类，刚好满足你说的那样。这部分我不清楚。
: 其实 minimum edge dominating set 的大小是跟
: minimum independent edge dominating set 是一样的
: 然后 minimum independent edge dominating set 是一个
: minimum maximal matching
: http://cgi.di.uoa.gr/~vassilis/co/dominating-sets.pdf
: 当然，minimum maximal matching也不好找就是了，
: 而且当图是有weighted的时候，这关系就不存在了。
我前面有一句话有错：
极大独立集 = 极小支配集 这句话有错
这是单向不是双向。
1. 极大独立集，必是极小支配集。
2. 极小支配集，不一定是(极小)独立集。支配集的点可以相邻，不一定要独立。
然后你现在提到的是新概念：
独立支配集(independent dominating set)
支配集的点可以相邻，不一定要独立，但是我们只看那些独立的。
有了这个概念之后，先前的 1. 可以补充成：
3. 极大独立集，必是极小支配集（极小独立支配集）
以及根据定义可以知道：
4. 最小的极大独立集，必是最小独立支配集
不过这些内容，跟原问题没有直接关联。
原问题只是想求支配集。这跟独立集、独立支配集完全没有关联。更不要说匹配了。
但是由于这题是特殊图类 partial 2-tree
独立集、支配集很可能有某种关联，甚至相同。
不过我没有仔细去研究。
所以我要引用我前面那篇文的结论：
结论就是不要再肖想独立集了，除非那是一种特殊的图类。