可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）667-676www.elsevier.com/locate/entcs广义最大覆盖问题的约束逼近Breno Piva1Dep artamentodeComputaCzechao UniversidadeFederal deSergipeSzechaoCrist'ovCzechaoSE，Br asil摘要本文给出了从广义最大覆盖问题到具有连通图的背包问题的保逼近约化。减少用于产生多项式时间近似方案的特殊类的情况下，这些问题。使用这些近似方案，伪多项式算法的存在性被证明，在更特殊的情况下，这些算法被证明具有多项式时间复杂度。此外，分析了这些算法关键词：最大覆盖，广义最大覆盖，连通图背包，近似算法，伪多项式算法1介绍简化的最大覆盖问题（BMC）[6]是经典的最大覆盖问题的推广，其中给出了附加的背包约束形式上，bmc的实例由集合S ={s1，s2，.，s m}定义在元素X ={x1，x2，...，xn}，成本函数δ：S→Z，预算L和权重函数ω：X→Z。 一个解决方案是一个集合SJ≤S，总成本不大于L，并最大化cov的总重量。的元素。为了清楚起见，我们在下面给出了BMC的整数规划（IP）公式。1电子邮件：brenopiva@dcomp.ufs.br2.作者感谢匿名推荐人提供的宝贵建议。https://doi.org/10.1016/j.entcs.2019.08.0581571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。668B. Piva/理论计算机科学电子笔记346（2019）667ΣΣΣ⊆⊆s∈x∈sS× → ×→s∈Ss∈Sx∈s（BMC）z= maxω（x）px（1）x∈X服从δ（s）qs≤L（2）s∈Spx≤s∈S：x ∈sqs<$x∈X（3）px，qs∈ {0，1};x∈X，s∈S（4）在BMC的IP模型中，变量px是二进制的，并指示元素是否x∈X是否被覆盖，变量qs，也是二进制的，指示集合s∈S是否在解中。 不等式（2）是一个背包不等式，它定义了解决方案的成本不大于预算。同时，限制（3）将两种变量联系起来，定义了一个元素只能在包含它的集合在解中时才这个问题在几个领域有重要的应用，包括：从停电中恢复[5]，网络监视器的位置[10]，自动文本摘要[11]，软件测试用例优先级[12]，参与式传感数据收集的招募[9]和新闻推荐系统[7]。广义最大覆盖问题（GMC）[3]通过根据用于覆盖它的集合对项目赋予不同的权重和成本来推广bmc。形式上，该问题可以定义为：给定集合S ={s1，s2，. s m}定义在元素X ={x1，x2，.， xn}、成本函数δ：S → Z、第二成本函数δ：X SZ、预算L和权重函数ω：X S Z，找到三元组（SJ，XJ，f），其中SJS，XJX和f是从XJ到SJ的分配函数，其中Sj中集合的成本之和加上覆盖元素的成本之和不大于L，并且最大化元素的加权和覆盖下面给出了GMC的IP模型（GMC）z=maxω（x，s）pxs（5）服从δ（x，s）pxs≤L（6）pxs≤qs<$s∈S，<$x∈s，（7）s∈S：x∈spxs≤1，<$x∈X（8）pxs，qs∈ {0， 1};x∈X，s∈S（9）模型（GMC）中的二元变量pxs定义了一个元素x∈X是否被一个集合s∈S覆盖。变量qs也是二进制的，表示一个集合s∈S是否在解中。不等式（6）强制要求覆盖要素的成本之和加上所选集合的成本必须适合预算。限制条件（7）指出，一个元素x∈X只能被一个集合s∈S覆盖，如果s在解中。最后，不等式（8）定义了S中至多有一个集合可以覆盖X中的一个元素。除了是BMC的一般化之外（因为BMC的任何实例都可以被视为GMC的实例，其中任何元素的成本都是零，B. Piva/理论计算机科学电子笔记346（2019）667669元素的权重总是相同的，而不管覆盖它的集合如何），并且因此具有BMC所具有的所有应用，GMC具有在图和社交网络中发现重叠社区[4]、规划观光旅游[2]、基于链路的传感器选择[1]等方面的应用。由[6]证明的逼近阈值和从最大覆盖问题的明显减少证明了BMC是强NP-困难的，并且除非P=NP，否则不允许多项式时间逼近方案（PTAS）。 由于GMC是BMC的推广，所以这些不可逼近性结果也推广到它。对于上述两个问题，不太可能存在PTAS或伪多项式算法（除非P=NP）。然而，这种算法可能存在于问题的特殊情况在目前的工作中，我们将展示这样实例组确实存在，并给出必要和充分的条件来识别这些实例的子集在接下来的部分中，我们将介绍从BMC和GMC到具有连续图的背包问题（KCG）的多项式时间近似保持约简，并证明它们产生这些问题的限制的近似算法（第2节）。在第3节中，展示了满足算法条件的BMC和GMC第4节描述了从特殊的例最后，在第5节中，我们提出了一些结论和未来的研究方向。2约简和近似有几个带边约束的背包问题，其中之一是KCG问题。这个问题的一个例子是一个图G=（V，E），其中它的顶点对应于背包物品，它的边对应于物品之间的冲突，预算B，成本函数δ：V→Z和权重函数ω：V→Z。 目标是选择一组具有最大权重并遵守预算和合同约束的项目。另一种看待这个问题的方式是作为一个背包约束的最大权重独立集问题由于KCG可以看作是最大权独立集问题的推广，因此它是强NP-困难的，不允许PTAS。然而，在[8]中证明了，KCG有一个FPTAS的情况下，其中的冲突图是弱弦或有界树宽。在本节中，我们将描述一个约化R，给定BMC的一个实例I1=（S，X，L，δ1，ω1），产生R（I1）=I2=（G=（V，E），B，δ2，ω2），即KCG的一个实例。我们的希望是，使用这种减少有可能获得一个近似算法的BMC。设Gbe的顶点集V=V1<$V2<$V3，其中V1={us|s∈S}，that集合S中的每个集合都有一个顶点，表示该集合在解中的存在。 V2={ws|s∈S}，即对于S中的每一个集合，都存在一个等价的顶点，表示该集合在解中的不存在性. 最后，V3={vx s|s∈S，x∈s}，即，对于X的每个元素x，对于每个s∈S的集合都有一个顶点，其中x∈s，670B. Piva/理论计算机科学电子笔记346（2019）667Σ1ΣΣX4（3，0）S4（3，2）(14（9）S1S2X1S1（3，0）(14，0）S2X2S1S2（5，0）（5，0）（2，0）（2，0）S4S2（2，0）（2，0）S4S3S3（5，0）(14，0）S4(11，0）S3(11（4）(14（6）S4S3X3S2S3（6，0）（6，0）这些顶点表示x被该集合覆盖。边的集合被定义为E = E1<$E2<$E3，其中E1={（u s，w s）|us∈ V1，ws∈V2且s∈S}，即表示解中同一组S的存在和不存在的顶点不能同时是解的一部分。E2={（w s，v xs）|ws∈V2，vxs∈V3，x∈X和s∈S}意味着如果集合S中的一个集合在解中不存在，它不能用来覆盖X中的任何元素。最后，E3 = x ∈ X {（v xr，v xs）vxr，vxs ∈ V3和r，s ∈ S}意味着S中至多有一个元素x ∈ X的集合将被计为覆盖X。|E3的定义也意味着，对于每个x∈X，在G中存在一个团，其顶点在V3中表示集合s∈S，其中x∈s。如果us∈V1，则成本函数由δ2（us）=δ1（s）给出，如果v1 ∈V1，则δ2（v）= 0。预算B等于L。最后，权函数由ω2（vxs）=ω1（x）给出，如果vxs∈V3，并且ω2（us）= 1 +x∈sω1（x），如果us∈V1<$V2。图给出了一个KCG的实例，该实例是从约简实例中获得的：其中S={s1={x1}，s2={x1，x2，x3}，s3={x1，x2，x3}，s4={x1，x2，x4}}，X={x1，x2，x3，x4}，L= 11，δ1={（s1，2），（s2，9），（s3，6），（s4，4）}和ω1={（x1，2），（x2，5），（x3，6），（x4，3）}。Fig. 1. kcg的实例，从应用于k的约化R获得。括号中的一对数字分别表示顶点的权重和成本。 带有上划线标签的顶点是集合V2中的顶点（表示该集合在解中不存在），它们的邻居hb或度为1的顶点是集合V1中的顶点（表示该集合在解中存在）。 其余的顶点组成集合V3. 虚线的椭圆表示代表覆盖X的每个元素的顶点的团。命题2.1 b m c 的实例I1具有值为OPT（I1）的最优解当且仅当I2= R（I1），kcg的实例，具有值为OPT（I2）= Γ+ OPT（I1）的最优解，其中Γ = |S|+s∈S x∈s ω1（x）.B. Piva/理论计算机科学电子笔记346（2019）667671ΣΣΣΣΣΣ证据设I1的最优解为λ 1 λ S，λ 1λX为该最优解覆盖的元素集，则OPT（I1）= x∈λ1ω1（x）. 考虑kcg的以下解：将子集V1的对应于Kcg 1的元素的所有顶点和子集V2的对应于Kcg 1的元素的所有顶点都带入该解。S1。这些顶点的权重之和等于|S| + s∈S x∈sω1（x）= Γ.现在，对于每个元素x∈x1，在解中包括来自V3的顶点，该顶点对应于覆盖x的x1的元素。因为V3中所有对应于集合的顶点复盖x有权ω1（x），则解的总权为Γ +x∈ω1（x）.此外，我们必须注意到，所选择的顶点之间没有冲突，因为只有一个顶点对应于覆盖每个x的集合被选择（不违反集合E3），只有V2中的顶点对应于不在集合E1中的集合被包括在解中（不违反集合E2），最后，从集合V1和V2中选择的顶点集合没有交集（不违反集合E1）。现在为了证明相反的情况，设I2=R（I1）的最优解为I2∈V，值为OPT（I2）。首先，我们必须注意到，I2的任何最优解必须包含每对顶点的一个元素，其中一个在V1中，另一个在V2中。V2，表示在解中存在或不存在来自S的集合.其中一个必须在解中的原因是它们不能都在解中（集合E1），并且它们中的每一个的权重都大于所有相邻元素的权重之和（除了它的一对权重相同）。这些顶点在任何最优解中的存在与Γ一起贡献于解的值的剩余部分解V3J的顶点集。因此，如果OPT（I2）= Γ + OPT（I1），这意味着vxs∈V3′ ω2（v）= OPT（I1）。注意，从E3开始，两个顶点代表S中的集合，覆盖X的相同元素的元素不能同时存在于解中。因此，我们认为，V3J中的每个顶点覆盖X的一个相异元素。因此，还存在一种解决方案，I1覆盖相同的集合，因此具有值OPT（I1）。Q从GMC到KCG的约简可以简单地通过改变约简中的权重和成本函数来获得。在GMC中，对于S中的每个元素都有一个代价函数δ1：S→Z，但是对于一个元素x∈X被S中的一个元素覆盖，也有一个代价函数δ1：X×S→Z。同样，权函数ω1：X×S→Z表示S中的元素覆盖了x∈X的元素的权。定义δ2（us）=δ1（s），如果us∈V1;定义δ2（vxs）=δ1（x，s），如果vxs∈V3。 否则δ2（v）= 0。 权函数定义为ω2（us）= 1+x∈sω1（x，s），如果us∈V1<$V2;ω2（vxs）=ω1（x，s），如果vxs∈V3。接下来，我们证明了上述的约简R保持近似，从而得到了BMC命题2.2如果kcg存在一个（1 − ε）-近似多项式时间算法，那么bmc存在一个多项式时间算法，对于任何给定的实例I1，它产生一个值为z1≥（1 −ε）OPT（I1）− ε Γ的解。证据 首先，很容易注意到约简R是多项式时间672B. Piva/理论计算机科学电子笔记346（2019）667εMM还原然后，从命题2.1我们知道，具有最优解值OPT（I1）的BMC的实例I1具有对应的具有最优解值OPT（I2）= Γ +OPT（I1）的KCG的实例I2=R（I1此外，I2的任何解2都可以分裂成2中位于V3中的顶点和2中位于{V1<$V2}中的顶点。{V1<$V2}中的顶点贡献的值至多为Γ，而V3中的顶点对应于I1的值为z1的解。因此，I2的任何解都有一个值z2≤z1+ Γ。因此，如果对I2有一个（1−ε）-近似，我们有（1−ε）OPT（ I2）≤z2≤OPT（ I2），因此（1−ε）（Γ +OPT（ I1））≤z2≤z1+Γ≤ Γ+OPT（I1），然后，（1−ε）OPT（I1）−εΓ≤z1≤OPT（I1）。Q命题2.3设I1是bmc的一个实例，I2= R（I1）是利用上述约化从I1得到的kcg的一个实例。如果I2中的图是弱弦的或具有有界树宽，则存在一族I1的近似算法，其近似保证为（1-ε）OPT（I1）-ε Γ，并且运行时间为多项式，|I1|和1. 此外，I1的这类近似算法定义为PTAS。证据I1的一族近似算法的存在直接来自于当连续图是弱弦或有界度时kcg的全多项式时间近似方案（fptas）的存在[8]和命题2.2。由于Γ≤（M− 1）OPT（I1），其中M= 2 |S|最大值（|S|）max（ω1（x）），我们可以定义εJ= ε。 因此，存在满足（1-εJ）OPT（I1）-εJr ≤ z1≤ OPT（I1）. 通过将εJ替换为ε，我们得到（1−ε）OPT（I1）≤z1≤OPT（I1）.Q对于GMC，使用相同的思想和上述约简可以实现与命题2.2和命题2.3中的结果类似的结果3BMC和GMC的表征从命题2.3我们知道，当对应的KCG实例是弱弦或有界树宽时，存在BMC然而，了解具有这些类的相应KCG实例的BMC在本节中，我们定义了一个BMC实例应该是什么样子的，因为它有一个对应的KCG实例和弱弦连接图。命题3.1归约R生成的图不能包含反洞。证据设I2=（G，B，δ，ω）是从R得到的KCG的一个实例.首先，注意集合V1中的所有顶点都是度为1的，因此不可能在反洞中。现在，让我们尝试使用V2和V3中的顶点构造一个反洞。我们考虑的第一种情况是仅由V3中的顶点组成的反洞。请注意，V3中的顶点被分组为团，对应于S中覆盖X的相同元素的集合，并且来自两个不同团的顶点是不相邻的。不失一般性，设v1，v2和v3是由下式组成的反路径：B. Piva/理论计算机科学电子笔记346（2019）667673V3中的顶点和反洞的一部分。我们知道，v1和v3必须在同一个团中，v2必须在不同的团中。设v4是反洞中的第四个顶点，在反圈中位于v3因为它在v3之后，所以它必须来自不同的团，但是因为它不是v1的后继者，也不是v 1的前趋者，所以v4和v1必须相邻，因此必须在同一个团中，但是v1和v3在同一个团中。矛盾现在假设反洞的顶点来自V2.若取任意反洞的任意三个顶点，则至少有一条边连接它们，并且V2在G因此，任何反洞最多可以有两个顶点从V2，如果有两个顶点，他们必须是连续的。因为奇洞必须至少有5个顶点，所以如果G中存在反洞，它必须有来自V2和V3的顶点。还请注意，V3中的任何顶点都只有一条边将其连接到V2中的顶点。在不失一般性的情况下，假设v1，v2和v3组成一个反路径，该反路径是反洞的一部分，其中v1∈V2，v2，v3∈V3，因此，v2和v3必须来自不同的集团，并且我们必须有v1=wsk，v3=vxisk，v2=vxjsl，对于xi，xj∈X，sk，sl∈S，xixj和sksl。现在，我看了电视，反洞中的第四个顶点，在反圈中的v3之后。 我们有v4/∈V2，因为如 果 有 两 个顶 点 来 自 V2 ， 它 们 必 须 是 连 续 的 ， 因 此 v4∈ V3 。 另 外 ， 我 们musthavev4=vxjsk且t hus，（v2，v4）∈E3且（v1，v4）∈E2。最后，设v5是反洞中的一个顶点，在反圈中跟随v4。假设 v5∈ V2 ，则如果 v5=wsp，则我们可以得出v2=vxjsp和v3=vxisp，但由于v3=vxisk和v2=vxjsl和skl=sl，这是不可能的。如果满足，则v5∈V3，因此v2，v3和v5必须在同一个团中，这也是不可能的。矛盾Q考虑BMC的实例I1=（S，X，L，δ，ω）和实例I2=R（I1）关于KCGsi，sj∈S，其中|sisj| ≥2（ 10）si，sj∈S，|sisj| ≤1且d≤SJ≤S，|SJ|>2如果您的数据不完整，sJ0 ， sJ1 ， . ，sj （|S′|−1 ） ofitselementsandsJlsJ（ l+1 ） mod|S′|/=（ 11）l ∈ {0，.，（一）|SJ| {\fnSimHei\bord1\shad1\pos（200，288）}命题3.2从R（I1）得到的KCG的实例I2的连通图当且仅当满足条件（10）或（12）时，包含一个洞。是的。 （3）补充命题I1满足条件（10）。然后，在集合S中有两个集合si和sj，|sisj|≥2，设y满足xk，xl∈si∈j. 因此，在I2的图G中，顶点序列vxksi，vxksj，wsj，vxlsj，vxlsi，wsi，vxksi，其中vxksi，vxksj，vxlsj，vxlsi∈V3，wsj，wsi∈V2诱导出一个洞.另一方面，假设I1满足条件（12）。 用xij表示sj排序中某对召唤集si，sj在si∈SJ中的唯一元素NT。 然后，得到了如下顶点序列， 其中ws′0，ws′1，. ，ws′（|S′| −1）∈V2且vx01s′0，vx01s′1，vx12s′1，vx12s2′，.，vx（S′10 ）0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000S ′1），v x（S ′|1）0 s ′ 0 ∈ V 3诱导G中674B. Piva/理论计算机科学电子笔记346（2019）667的空穴：v x（S ′| − 1）0 s ′ 0，w s ′ 0，v x 0 1 s ′ 0，v x 0 1 s ′ 1，w s ′ 1，.||||||，w s ′（S ′1），v x（S ′10）0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000S ′|1），v x（S ′|-1）0 s ′ 0。||||||（1）让我们首先考虑关于图G在I2中的一些事实： (1)所有顶点B. Piva/理论计算机科学电子笔记346（2019）667675因此，V1中顶点不可能在洞中。(2)V3可以划分成团;对于每个x∈X都有一个团划分，并且同一个团中的顶点对应于集合s∈S，使得x∈s。 (3)没有边（vxisk，vxjsl）∈E其中vxisk，vxjsl∈V3且xixj，即，没有边缘连接不同团划分的顶点（4）V2在G中诱导出一个独立集，如果V2中一个顶点有两个V3中的顶点作为邻居，则它们一定在V3的不同团划分中，即如果（ws，vxis）∈E和（ws，vxjs）∈E，其中wees∈V2，vxis，vxjs∈V3，thehenxixj . （5）V3中的任意一个顶点恰好有一个Neighb或V2中的Neighb。(6)由于洞H中任何顶点u恰好有两个邻居v，w，v和w是不相邻，H最多可以有两个顶点来自V3的同一团划分。(7)由于与事实（6）以及事实（5）和（6）中相同的原因，包含来自V3的团划分的顶点的任何洞H必须恰好包含来自该划分的两个顶点，并且它们是连续的。(8)由（4）可知，如果洞H包含一个顶点u∈V2，则它的两个邻点v，w∈V3必为真。(9)由事实（3）和（7）可知，如果洞H包含一对顶点u，v∈V3，则这对顶点的前后必有V2中的顶点.(10)由事实（7）、（8）和（9）我们知道G中的任何洞必有来自V2和V3的顶点。此外，V3中的顶点只能成对取，并且每对顶点的前面和后面必须是V2中的顶点，而V2中的顶点又必须有V3中的两个顶点作为其邻居。因此，G中的任何洞都是由V3中的两个顶点（来自相同的团划分）和V2中的一个顶点组成的序列，因此顶点的数量是3的倍数设图G在I2中有一个洞H. 我们将考虑两种情况：|≤ 6且|H|> 6.|> 6. 如果|H|≤ 6，则|H|= 6由于顶点数必须是f3的倍数，因此必须存在一个顶点序列vxksi，vxksj，wsj，vxlsj，vxlsi，wsi，vxksi，whevxksi，vxksj，vxlsj，vxlsi∈V3和wsj，wsi∈V2，因此条件（10）满意。如果|H|> 6、自H必须是3的倍数，|H| ≥ 3k且k> 2，且由于G中的任何洞都由V3中的两个顶点和V2中的一个顶点组成，因此H必须由顶点序列vx组成（S ′ |10）0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000| S ′ 1），v x（S ′ − 1）0 s ′ 0，w s ′ 0，v x 0 1 s ′ 0，v x 0 1s ′ 1，||||||ws′1，.，ws′（S′1），vx（S′10）0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000S ′−1）||||||其 中k=|SJ|>2，ws′0，ws1′，. ，ws′（|S′| −1）∈V2和 vx01s′0 ， vx01s′1 ， vx12s′1 ， vx12s′2 ， .， vx （ S′10 ）0.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000S ′1），v x（S ′|−1）0 s ′ 0||||| ∈V3. 因此，我们认为，条件（12）满足。Q676B. Piva/理论计算机科学电子笔记346（2019）667由命题3.1和3.2我们可以推出BMC的实例I1有一个对应的KCG的实例R（I1）具有弱弦压缩图当且仅当I1既不满足条件（10）也不满足条件（12）。请注意，GMC提供的一般化对从KCG约简得到的图的结构没有影响。因此，BMC关于实例特征的所有结果也适用于GMC。B. Piva/理论计算机科学电子笔记346（2019）667677Σε定义一个界B >Γ≥OPT（I1），我们可以定义ε=12B2B4精确算法从第2节中的约简获得的PTAS可以用于产生BMC的限制的伪多项式时间算法，即BMC的实例与对应的KCG实例，其具有弱弦或具有有界树宽的图。这 一事实由命题4.1描述。命题4.1命题2.3中的算法可以用来为bmc的限制产生一个伪多项式时间算法。证据设I2 = R（I1）是kcg的一个实例，它是将约化R应用于bmc的一个实例I1而得到的.设OPT（I1）为I1的最优解的值，OPT（I2）为I2的最优解的值。根据R的定义，我们知道，|S|+的v∈V1ω2（v）≥OPT（I1）.由此2B 在算法中，提议2.3. 由于算法的解具有值z1≥（1-ε）OPT（I1）-εr，则有z1≥OPT（I1）−εOPT（I1）−εr> OPT（I1）−εB−εB=OPT（I1）−1。因此z1必须等于OPT（I1）。由于该算法的复杂性时间是多项式，|I1|和1，其中ε =1它是I1的一元编码大小的多项式，因此是伪多项式。Q一个特别有趣的限制是元素的权重是由一个与实例无关的常数k限定。如果此限制适用，则该算法实际上是多项式，|I1|如命题4.2所示。这种情况有应用，例如，在时间感知测试用例优先级问题[12]中，权重是单一的。命题4.2如果bmc的实例中元素的权重由某个与该实例无关的常数k限定，则命题2.3的算法可用于为bmc的该约束产生多项式时间算法。证据 如果元素的权重由常数k限定，则Γ≤K|S||X|+的|S|在命题4.1的伪多项式算法中，我们可以定义B = k|S||X|+的|S|+1，则ε = 1是二进制大小的多项式编码I1。Q通过对命题4.1和命题4.2进行适当的修改，可以为gmc实现相同的结果。5结论和今后的工作本文给出了从BMC和GMC到KCG的多项式时间约简。 这些减少允许我们使用现有的FPTAS的限制KCG即实例与弱弦图或有界树宽的图，得到多项式时间近似计划，伪多项式精确和多项式精确算法的限制BMC和GMC。我们阻止-678B. Piva/理论计算机科学电子笔记346（2019）667挖掘BMC和GMC的实例的特征，产生弱弦图的KCG作为未来的工作，我们离开的BMC和GMC它们有一个对应的KCG实例，这个实例有一个有界树宽的连通图。引用[1] 查鲁角，澳-地Aggarwal，Amotz Bar-Noy，and Simon Shamoun.链接信息网络中的传感器选择。计算机网络，126：100[2] Igo Ramalho Brilhante，Jose Antonio Macedo，Franco Maria Nardini，Ra Ravaele Perego，and ChiaraRenso.用tripbuilder规划观光旅游。信息处理管理，51（2）：1– 15,[3] 埃文·科恩和利兰·卡茨尔。广义最大覆盖问题。Information Processing Letters，108（1）：15[4] 埃丝特·加尔布伦，阿里斯蒂德斯·吉奥尼斯，尼古拉·塔蒂。标记图中的重叠社区检测。数据挖掘和知识发现，28（5）：1586[5] Sudipto Guha， Anna Moss， Joseph （ Se） Naor，and Baruch Schieber.从 停 电中 有 效 恢 复（ 扩 展 摘要 ） 。 在 Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing ，STOCACM。[6] Samir Khuller，Anna Moss和Joseph Naor。 预算最大覆盖问题。Information Processing Letters，70（1）：39[7] Lei Li，Dingding Wang，Tao Li，Daniel Knox，and Balaji Padmanabhan.场景：一个可扩展的两阶段个性化新闻推荐系统。第34届国际ACM SIGIR信息检索研究与开发会议论文集，SIGIR'11，第125-134页，美国纽约州纽约市，2011年。ACM。[8] Ulrich Pferschy和Joachim Schauer。具有约束图和强迫图的背包问题的逼近。Journal of CombinatorialOptimization，33（4）：1300[9] Sasank Reddy，Deborah Estrin，and Mani Srivastava.参与式感测资料收集之招募架构。InPatrikFlor'een，AntonioK ru？ ger，andMirjanaSpas ojevic，editors，PervasiveComputing，pages 138 -155 ，Berlin ， Heidelberg， 2010. 施普林格柏林海德堡。[10] Kingwon Suh，Yang Guo，Jim Kurose，and Don Towsley.定位网络监视器：复杂性，复杂性和覆盖范围。计算机通信，29（10）：1564- 1577，2006年。IP网络的监控和测量。[11] Hiroya Takamura和Manabu Okumura。基于最大覆盖问题的文本摘要模型及其变体。在计算语言学协会欧洲分会第12次会议的会议记录中，EACL'09，第781-789页，Stroudsburg，PA，USA，2009。计算语言学协会。[12] 张璐，侯珊珊，郭超，谢涛，红梅。 使用整数线性规划的时间感知测试用例优先级。第十八届软件测试与分析，ISSTAACM。
