论文标题
关于诱导多部分图参数的参数化复杂性
On the Parameterised Complexity of Induced Multipartite Graph Parameters
论文作者
论文摘要
我们介绍了一个称为诱导多部分图参数的图形参数家族，并研究其计算复杂性。首先，我们考虑以下决策问题：一个实例是诱导的多方图参数$ p $和给定的图形$ g $，对于自然数量$ k \ geq2 $和$ \ ell $，我们必须确定在所有$ k $ g $的所有感应$ k $ g $的最大值$ p $中，最大值是$ g $的最大值。我们证明这个问题是W [1] -hard。接下来，我们考虑了此问题的变体，我们必须确定给定的图$ G $是否包含足够大的$ k $ - partite子图$ h $ h $，以便$ p（h）\ leq \ ell $。我们表明，对于某些参数，此问题是para-np-hard，而对于其他参数是固定参数可进行的。
We introduce a family of graph parameters, called induced multipartite graph parameters, and study their computational complexity. First, we consider the following decision problem: an instance is an induced multipartite graph parameter $p$ and a given graph $G$, and for natural numbers $k\geq2$ and $\ell$, we must decide whether the maximum value of $p$ over all induced $k$-partite subgraphs of $G$ is at most $\ell$. We prove that this problem is W[1]-hard. Next, we consider a variant of this problem, where we must decide whether the given graph $G$ contains a sufficiently large induced $k$-partite subgraph $H$ such that $p(H)\leq\ell$. We show that for certain parameters this problem is para-NP-hard, while for others it is fixed-parameter tractable.
