We introduce a novel framework of graph modifications specific to interval graphs. We study interdiction problems with respect to these graph modifications. Given a list of original intervals, each interval has a replacement interval such that either the replacement contains the original, or the original contains the replacement. The interdictor is allowed to replace up to $k$ original intervals with their replacements. Using this framework we also study the contrary of interdiction problems which we call assistance problems. We study these problems for the independence number, the clique number, shortest paths, and the scattering number. We obtain polynomial time algorithms for most of the studied problems. Via easy reductions, it follows that on interval graphs, the most vital nodes problem with respect to shortest path, independence number and Hamiltonicity can be solved in polynomial time.
翻译:我们引入了一个针对间距图的新的图形修改框架。 我们研究与这些图形修改有关的阻截问题。 根据原始间隔列表, 每个间距有一个替换间隔, 替换的间隔要么包含原始间隔, 要么包含原始间隔。 允许截击器用替换的间隔来替换最高为原间隔美元。 我们还利用这个框架研究与我们称之为援助问题的阻截问题相反的阻截问题。 我们研究这些问题, 包括独立编号、 分类编号、 最短路径和散射号。 我们为大多数研究过的问题获得了多元时间算法 。 很容易的缩短, 在间隔图上, 最关键的节点问题就是最短的路径、 独立号 和 密尔密尔顿度 问题可以在多元时间解决 。