论文标题
令人满意的分区问题
The Satisfactory Partition Problem
论文作者
论文摘要
令人满意的分区问题在于确定给定无向图的顶点的集合是否可以分为两个非空的部分，以便每个顶点在另一部分中至少具有至少邻居的数量。 Gerber和Kobler提出了这个问题[欧洲J. Oper。 res。 125（2000）283-291]，并由其他作者进一步研究，但其参数化的复杂性迄今仍保持开放。众所周知，令人满意的分区问题以及需要零件具有相同基数的变体是NP完整的。我们从参数化复杂性的角度来增强对问题的理解，表明（1）当通过输入图的邻域多样性参数化时，问题是fpt，（2）可以在$ o（n^{8 {\ tt cw}}} $中解决$ {\ tt cw} $ {\ tt cw} $是clique is clique-timite clique-timate n pentription n pamity n clique-parique-parique-parique-parique is pentripation-paramiate a pomamiate a;通过树宽。
The Satisfactory Partition problem consists in deciding if the set of vertices of a given undirected graph can be partitioned into two nonempty parts such that each vertex has at least as many neighbours in its part as in the other part. This problem was introduced by Gerber and Kobler [European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors, but its parameterized complexity remains open until now. It is known that the Satisfactory Partition problem, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. We enhance our understanding of the problem from the viewpoint of parameterized complexity by showing that (1) the problem is FPT when parameterized by the neighbourhood diversity of the input graph, (2) it can be solved in $O(n^{8 {\tt cw}})$ where ${\tt cw}$ is the clique-width,(3) a generalized version of the problem is W[1]-hard when parameterized by the treewidth.
