Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
复制标题
带小派系的真区间图的路径宽度、带宽和补全问题
DOI：
10.1137/s0097539793258143
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
R. Shamir
中科院分区：
文献类型：
--
作者：
Haim Kaplan;R. Shamir
我们研究两个相关的问题，分子生物学的动机。
给定一个图G$和一个常数k$，是否存在G$的一个单位区间图G '$且团大小不超过k$？
给定图$G$和$G$的适当$k$-着色$c$，是否存在$G$的超图$G '$被$c$适当着色并且是单位区间图？
我们表明，这些问题是多项式固定$k$。另一方面，我们证明了第一个问题是等价于决定，如果$G$的带宽是最多$k-1$。因此，它是NP-难的，并且对于所有的$t$都是$W[t]$-难的。我们还证明了第二个问题是$W[1]$-困难的。这意味着对于固定的$k$，这两个问题都不太可能有一个O（n^\alpha）$算法，其中$\alpha$是一个与$k$无关的常数。
在我们的研究中的一个中心工具是一个新的图论参数密切相关的路径宽度。一个意想不到的有用结果是这个参数与图的带宽相等。
We study two related problems motivated by molecular biology.
Given a graph $G$ and a constant $k$, does there exist a supergraph $G'$ of $G$ that is a unit interval graph and has clique size at most $k$?
Given a graph $G$ and a proper $k$-coloring $c$ of $G$, does there exist a supergraph $G'$ of $G$ that is properly colored by $c$ and is a unit interval graph?
We show that those problems are polynomial for fixed $k$. On the other hand, we prove that the first problem is equivalent to deciding if the bandwidth of $G$ is at most $k-1$. Hence, it is NP-hard and $W[t]$-hard for all $t$. We also show that the second problem is $W[1]$-hard. This implies that for fixed $k$, both of the problems are unlikely to have an $O(n^\alpha)$ algorithm, where $\alpha$ is a constant independent of $k$.
A central tool in our study is a new graph-theoretic parameter closely related to pathwidth. An unexpected useful consequence is the equivalence of this parameter to the bandwidth of the graph.