论文标题
重新审视由双盖参数的不平衡参数
Imbalance Parameterized by Twin Cover Revisited
论文作者
论文摘要
我们研究了图形的双覆盖物参数的不平衡问题。我们表明，不平衡是通过双盖XP参数化的，当通过双盖和双盖外部最大集团的大小进行参数时，FPT是FPT。相比之下，我们从双胞胎覆盖物中介绍了图形的简洁表示的概念，并证明在简洁表示的情况下，即使是具有大小一号的双盖的图形，在简洁表示的情况下，不平衡是NP的概念。
We study the problem of Imbalance parameterized by the twin cover of a graph. We show that Imbalance is XP parameterized by twin cover, and FPT when parameterized by the twin cover and the size of the largest clique outside the twin cover. In contrast, we introduce a notion of succinct representations of graphs in terms of their twin cover and demonstrate that Imbalance is NP-hard in the setting of succinct representations, even for graphs that have a twin cover of size one.
