广义依赖生成树问题的NP完全性

可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）711-723www.elsevier.com/locate/entcs广义相依约束生成树问题Luiz Alberto do Carmo Viana1，3CampusdeCrateu'sUniversidadeFe deraldoCear'aCrateu's，BrazilManoelCamppouchelo1，2，4DepartamentodeEstat'ısticcaeMatem'aticaAplicadaUniversidadeFederaldoCear'a巴西福塔莱萨摘要我们介绍了广义依赖约束生成树问题（G-DCST），其中只有当从其依赖集中选择的边的数量在一定的区间内时，才可以选择边。输入图G的边之间的依赖关系由输入有向图D描述，其顶点是G的边。D的一个顶点的内邻点形成它的依赖集。我们表明，G-DCST统一和推广了一些已知的生成树问题，适用于边缘或顶点度的上下界的约束。我们证明了G-DCST的可行性版本是NP完全的，即使在G和D的结构以及定义最小或最大依赖数的函数的严格限制下也是如此。我们还表明，这个问题保持在G和D的严格假设下的lnn不可逼近阈值。另一方面，我们发现一个多项式的情况下，通过拟阵的交集参数。关键词：依赖约束生成树问题; NP-困难性;不可逼近性1引言设G=（V，E）是一个图，D=（E，A）是一个顶点为G的边的有向图.我们称e1∈E是e2的D-依赖，如果（e1，e2）∈A.对于每个e∈E，我们定义它的D-依赖集为depD（e）={EJ∈E：（EJ，e）∈A}。同样，设l，u：E→N是从G的边集到自然数的函数（我们认为，1由CNPq-巴西（Proc.443747/2014-8）和FUNCAP（PNE-0112-00061.01.00/16）2部分得到CNPq-巴西的支持（Proc.305264/2016-8）3电子邮件地址：luizalberto@crateus.ufc.br4电子邮件：mcampelo@lia.ufc.brhttps://doi.org/10.1016/j.entcs.2019.08.0621571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。712洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711Σ∈T0∈ N）。我们称G（l，u）-的一个子图H∈G满足D，如果对每个e∈E（H），l（e）≤|副署长（戊）及副署长（戊）|≤u（e）。设TG表示G的所有生成树的集合。本文定义了广义依赖约束生成树问题（G-DCST（G，D，l，u）），即判定是否存在T∈TG使得T（l，u）-满足D的问题。设W：E→R+是G的边集上的权函数. 对每个子图H∈G，定义w（H）=e∈E（H）w e.我们可以定义广义相关约束最小生成树问题，我们将其作为G-DCMST（G，D，l，u，w），作为在（l，u）-满足D的TG中寻找一个w（T_∞）最小的T_∞的下一节将介绍有关G-DCST和G-DCMST的结果。第2节建立了本问题和文献中发现的生成树问题的广义版本之间的关系。第3节展示了G-DCMST（G，D，l，u，w）的复杂性结果，其参数可以是G和D，也可以主要是l和u。最后，第4节结束了本文的评论和未来的工作方向2相关生成树问题本节揭示了G-DCST和其他生成树问题之间的关系。我们表明，它统一和推广了一些已知的问题。特别是，我们建立了G-DCST与约束生成树问题之间的关系，后者可以看作是G-DCST的对应问题，其中有向图D被无向图所代替.2.1先前的依赖约束问题在以前的工作[15]中，我们已经介绍并解决了类似于G-DCST的问题。我们定义了最小依赖约束生成树问题，简称为L-DCST（G，D），它包括判定是否存在T ∈ TG，使得对于每个e∈E（T），其中d∈ pD（e）/=0，E的至少一个D-分解也在T中（即：如果depD（e）/=Δ，则depD（e）Δ E（T）/=ΔE。同时，我们还引入了A-DCST（G，D）问题，简称A-DCST（G，D）。它包括决定是否存在T∈TG，使得对于每个e∈E（T），e的所有D-依赖也在T中（即dep D（e）<$E（T）= dep D（e））。定理2.1L-DCST（G，D）和A-DCST（G，D）是特别例G-DCST（G，D，l，u）.证据L-DCST的实例（G，D）等价于G-DCST的实例（G，D，l，u），其中l（e）=min {|de pD（e）|，1}（如果de pD（e）=0，e可以自由地在溶液中加入ke部分）和u（e）= |D（e）部|，对所有e∈E（G）. 类似地，实例（G，D）A-DCST的实例等价于G-DCST 的实例（G，D，l，u），其中l（e）= u（e）=|，对所有e ∈ E（G）.|, for all e ∈ E (G).Q由于G-DCST推广了这两个问题，它继承了它们的应用。例如，依赖关系可以对具有协议转换的洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711713J限制[14]。此外，在第3节中，我们从定理2.1和[15]中提出的计算复杂性研究中获得了G-DCST的硬度结果。L-DCST（G，D）和A-DCST（G，D）的优化形式分别记为L-DCMST（G，D，w）和A-DCMST（G，D，w），其中w：E（G）→R+是G的边集上的权函数.这些问题包括：根据w，在它们的决策对应物的解中具有最小权重的解。作为定理2.1的结果，它们是G-DCMST（G，D，l，u，w）的特殊情况。在[15]中，我们评估了L-DCMST（G，D，w）和A-DCMST（G，D，w）的分支定界算法的计算性能，该算法基于节点选择和分支策略。2.2连续约束最小生成树问题设G=（V，E）是一个无向图.设Gc=（E，Ec）是一个图，其顶点是G的边.我们称e1，e2∈E是（Gc）-相容的如果{e1，e2}∈Ec.如果E（H）中没有e1，e2是（Gc）-连通的，则称H∈G为（Gc）-连通自由子图给定w：E→R+，连续约束最小生成树问题（CCMST（G，Gc，w））是指找到一个（Gc）-连续自由的T∈TG，其中w（T∈ G）最小.这个问题在[4]中提出。证明了它是强NP-困难的，即使Gc是长度为2的路的不交并[4]， 有一个多项式的情况下，当Gc是不相交的并团[16]。此外，即使G是仙人掌，问题也是NP难的[16]。在[16]和[12]中分别示出了使用启发式算法和分支切割算法的实验。G-DCMST也推广了这个问题。定理2.2 CCMST（G，Gc，w）是G-DCMST（G，D，l，u，w）的一个特例.证据 给定一个CCMST的实例（G，Gc，w），我们以如下方式构建一个G-DCMST的实例（GJ，D，l，u，w）：首先，我们使GJ= G和D =（E（GJ），A），其中A ={（e1，e2），（e2，e1）：{e1，e2}∈ E（Gc）};对于每个e ∈ E（GJ），l（e）= u（e）= 0。D 的结构如图1所示。证明了T是CCMST（G，Gc，w）的解的充要条件是T是G-DCMST（GJ，D，l，u，w）的解.设T是CCMST（G，Gc，w）的解.这意味着T是G的一棵生成树，并且没有e1，e2∈E（T）是（Gc）-连通的.考虑D，这意味着，对于eache1，e2∈E（T），e1∈/depD（e2）和e2∈/depD（e1）。然后，对于eache∈E（T），我们有depD（e）<$E（T）=<$，导致l（e）≤|副署 长（e）助理署长（T）| ≤u（e）。 由此，我们看到T（l，u）-满足D，因此T是G-DCMST（G，D，l，u，w）的解。反之，取T作为G-DCMST（GJ，D，l，u，w）的解。这意味着T是GJ的生成树，并且T（l，u）满足D。通过定义，对于每个e∈E（T），我们有一个depD（e）<$E（T）=<$。 考虑D的构造，对于e1，e2∈E（T），e1和e2都不是（Gc）-连通的，则T是（Gc）-连通自由的.由此，T是CCMST（G，Gc，w）的解。这表明CCMST（G，Gc，w）和G-DCMST（GJ，D，l，u，w）具有相同的解集.由于这两个实例都是按w加权的，因此它们具有相同的最优714洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711JJe1e2e1e2值Q(a) Gc.（b）D.图1.一、CCMST减少的图示2.3度约束的生成树问题设G=（V，E）是一个图.记dG（v），v∈V，G中顶点v的度，即G中与v相邻的顶点的个数。另外，如果dG（v）= 1，则称v∈V为G中的对于VJ<$V，设G[VJ]是由VJ诱导的G的子图.我们提出了G-DCMST和生成树问题之间的关系，其特征在于其生成树解的度约束。这样的约束表示在树中的顶点度的下界或上界2.3.1最大度约束最小生成树设G=（V，E）是一个图.给定k：V→N和w：E→R+，我们提出了经典的最大度约束最小生成树问题，简称为MaxDeg-MST（G，k，w）.它包括在T∈ TG中，使得dT（v）≤k（v），对于每个v∈V，找到一个具有最小值w（T）的T这个NP难问题最早是在[11]中提出的。从那时起，它被广泛研究。对于该问题已经提出了几种启发式、近似和精确方法（例如参见[8，13，3]和其中的参考文献定理2.3 MaxDeg-MST（G，k，w）是G-DCMST（G，D，l，u，w）的一个特例。证据设（G，k，w）是MaxDeg-MST的一个实例。 我们如下构建G-DCMST的实例（GJ，D，l，u，wJ）：GJ =（V<$VJ，E<$EJ），其中VJ={vJ： v是一组人工顶点， V中的每个顶点一个，并且EJ={ev={v，vJ}：v∈V}是一组人工割边，每个割边连接一个原始顶点v∈V和它对应的人工顶点vJ∈VJ;D=（E<$EJ，A），其中A={（{u，v}，eu），（{u，v}，ev）：{u，v}∈E};l（e）=u（e）=0，对于每个e∈E，而l（ev）=0且u（ev）=k（v），对于eachv∈V;atast，WEJJ=we，对于eache∈E，且weJ=0，对于ache∈EJ. 这种结构如图2所示。 在part ic u l ar中，注意，对于所有v∈ V，dep D（e v）是G中与v关联的边的集合。我们证明了T是MaxDeg-MST（G，k，w）的解当且仅当G-DCMST（GJ，D，l，u，wJ）存在解TJ，其中T=TJ[V].首先，设T =（V，ET）是MaxDeg-MST（G，k，w）的解。 我们将T展开为TJ=（V <$VJ，ET′）<$GJ，其中ET′=ET <$EJ.我们需要证明TJ是G-DCMST（G，D，l，u，w）的解。 因为T是G的一棵生成树，所以很明显TJ是G j的一棵生成树。 Ea ch边e∈ET有depD（e）=u，s o l（e）=u（e）=0意味着l（e）≤|dep D（e）E（T J）|≤ u（e）。现 在 ，设e ∈ ET ′\ET=EJ。 则对于某个v∈V，e = ev，且根据T的可行性，dT（v）≤k（v）.这意味洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711715≤JJ∗∗123412344311uJeuVJevuv{u，v}euevdepD（ev）的至多k（v）条边在ET′中。 由此，可以得出l（ev）≤|≤ U（E V）。|≤ u (e v). 因此，TJ（l，u）-满足D，并且我们有TJ是G-DCMST（G，D，l，u，w）的解反之，取TJ=（V<$VJ，E T′）作为G-DCMST（GJ，D，l，u，wJ）的解。我们证明了T=TJ[V]是MaxDeg-MST（G，k，w）的解。设v∈V.设ev是G j中的一条截边，则ev∈ET′.通过D和函数u的构造，这意味着在E T ′中至多有k（v）条边{u，v}∈E. 因为T是子树由V诱导的TJ，得出d T（v）k（v）。 此外，由于TJ是Gj的一棵生成树，所以T也是G的一棵生成树. 因此T是MaxDeg-MST（G，k，w）的解。为了完成证明，请注意，由于EJ中的边具有零权重，因此MaxDeg-MST（G，k，w）和G-DCMST（GJ，D，l，u，wJ）的相应解具有相同的权重。这得出MaxDeg-MST（G，k，w）和G-DCMST（GJ，D，l，u，wJ）具有相同的最优值的结论。Q(a) G′。(b) D.图二. MaxDeg-MST减小的图示。2.3.2广义度约束最小生成树设G=（V，E）是一个图.给定κ∈N和w：E→R+，最小度约束最小生成树问题，这里简称为MD-MST（G，κ，w），包括在T∈ TG中寻找，使得T的每个非叶v有dT（v）≥κ，一个具有最小w（T）的T这个问题在[2]中被引入，其中它被证明是NP困难的。 文献[1，2，10]提出了非线性规划及其求解方法。让我们引入这个问题的一个广义版本，记为GD-MST（G，kJ，k，w），其中我们用函数k，kJ：V→N代替标量κ，并要求T的每个非叶v满足kJ（v）≤dT（v）≤k（v）。我们将揭示GD-MST 和G-DCMST 之间的关系。在处理前，我们用 NG（v）={u∈V（G）：{u，v}∈E（G）}表示G中与v相邻的顶点集.定理2.4 GD-MST（G，k，J，k，w）是G-DCMST（G，D，l，u，w）的一种特殊情况。证据给定GD-MST的实例（G=（V，E），kJ，k，w），我们以以下方式构建G-DCMST的实例（GJ，D，l，u，wJ）： 首先，GJ=（V<$VJ，E<$EJ），其中VJ={v1，v2，v3：v∈V}且EJ={ev={v，v1}，ev={v，v2}，ev={v1，v3}，ev={v2，v3}：v∈V};设D=（E<$EJ，A），其中A=A1<$A2，A1={（{u，v}，ev），（{u，v}，ev）：v∈V，u∈NG（v）}和A2={（ev，ev），（ev，ev）：v∈V};对于每个e∈E，l（e）=u（e）=0;对于每个v∈V，l（ev）=KJ（v），u（ev）=k716洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711（v），洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711717我11∪12我≤≤我342134我我我2221111212l（ev）=u（ev）=1，2 ≤i≤4;最后，wej=we，i fe∈E，且WEJJ=0，否则.这种结构如图3所示。 注意，dep D（e v）= dep D（e v）是1 2与v关联的边的集合，对于每个v∈V。证明了T是GD-MST（G，kJ，k，w）的解的充要条件是G-DCMST（GJ，D，l，u，wJ）存在解Tj，其中T=TJ[V].首先，设T=（V，ET）是GD-MST（G，k，J，k，w）的解。我们将T展开为TJ=（V<$VJ，ET′）<$GJ，其中ET′等于ET连同以下边：对于每个v ∈ V，ev和ev;对于每个v ∈ V，ev或ev，取决于v是否为一片叶在T中或不在T中。显然，T=TJ[V]。它仍然表明，TJ是一个G-DCMST（GJ，D，l，u，wJ）解 由于T是G的一棵生成树，并且对于每个v∈V，正好有三个ev，i∈[4]在ET′中，所以TJ是G j的一棵生成树。现在，我们证明了D-依赖性是满足的。每个边e∈ET都有dep D（e）=0且l（e）= u（e）=0，所以l（e）≤|dep D（e）E（TJ）|u（e）的值，则是平凡的。E T′\E T中的剩余边可以分组如下：(i) e v和e v，对于每个v∈V：1=l（e v）≤|dep D（e v）E（T J）|≤u（e v）=1，3 ≤i ≤4，是直接的，因为ev是ev的唯一依赖，反之亦然。3 4反之亦然;V V(ii) e2，对于T中的每个叶v：由于dep D（e2）的恰好一个边在ET′中，我们有1=l（e v）≤|dep D（e v）E（T J）|n（e）=1;(iii) ev，对于T中的每个非叶v：从T的可行性，kJ（v）≤dT（v）≤k（v），即，dep D（e v）的至少kJ（v）且至多k（v）条边在E T<$E T′中，这意味着kJ（v）= l（e v）≤ |dep D（e v）E（TJ）|≤ u（e v）= k（v）.因此，TJ （l，u）-满足D，和我们 有 的 TJ是 一 解决方案G-DCMST（GJ，D，l，u，wJ）.反之，设TJ=（VVJ，E T′）是G-DCMST（GJ，D，l，u，wJ）的解。我们证明了T=TJ[V]是GD-MST（G，KJ，k，w）的解. 由于依赖性约束，ev和ev在TJ中，对于每个3 4v∈ V。由此，由于ev和ev是GJ中的一个切割，因此ev和ev中的恰好一个是在TJ中，对于每个v∈V。取v∈V。若ev在TJ中，则在ET ′中有从KJ（v）到k（v）条边{u，v}∈ E. 如果ev在TJ中，则在Tj中有恰一条边{u，v}∈EE T′。因此，kJ（v）d T（v）k（v）或d T（v）=1。由于TJ是GJ的生成树，T是G的生成树，因此T是GD-MST（G，kJ，k，w）的解为了完成证明，观察GD-MST（G，kJ，k，w）和G-DCMST（GJ，D，l，u，wJ）的相应解具有相同的权重，因为EJ边的权重为零这得出结论，GD-MST（G，kJ，k，w）和G-DCMST（GJ，D，l，u，wJ）具有相同的最优值Q当叶子先验固定时，得到MD-MST（G=（V，E），k，w）的一个有趣的变化.确切地说，给定C<$V和d：C→Z+，它包括在T∈ TG中找到一个T<$，使得对于每个u∈C，dT（u）≥d（u），并且对于每个v∈V\C，dT（v）=1，其中w（T<$）最小。这个问题被简称为FMD-MST（G，C，d，w），并在[5]中被引入。类似地，让我们引入一个广义版本，表示为FGD-MST（G，C，dJ，d，718洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711w），其中我们添加一个下界函数dJ：V→N洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）71171921veu3u3eu4ev3v3ev4u1u2v1v2eu1euevevu21v2(a) G′。(b) D.图3.第三章。MD-MST减少的图示并要求任意可行树T中的每个顶点v∈C都满足DJ（u）≤dT（u）（除了FMD-MST的约束）。我们可以证明FGD-MST（G，C，DJ，d，w）也是G-DCMST（G，D，l，u，w）的特殊情况，在定理2.4的证明中所作的构造中有一点修改。给定如定理2.4所述构建的GJ，我们从GJ中移除边来构建GJJ：对于每个v∈C，我们移除边ev;对于每个v∈V\C，我们移除边e。也需要对D进行明显的调整。类似于定理2.4的证明的论证足以得出以下定理。定理2.5 FGD-MST（G，C，d，J，d，w）是G-DCMST（G，D，l，u，w）的一种特殊情况。3复杂性3.1G和D分析在本小节中，我们分析了G-DCST（G，D，l，u）和G-DCMST（G，D，l，u）作为输入图G和D的函数的复杂性。我们证明了G-DCST的NP-完全性结果。此外，我们建立了一个不可逼近的阈值G-DCMST。以下结果在[15]中得到了证明。请注意，对于G和D上的非常有限的条件，硬度也成立。定理3.1L-DCST（G，D）和A-DCST（G，D）是NP-完全的，即使G是直径为2的弦图，D是高为2的树形图的并或高为3的树形图。定理3.2L-DCST（G，D）和A-DCST（G，D）是NP-完全的，即使G是一个弦图，Δ（G）≤ 3，D是一个高2的树形图的并或一个高3的树形图。作为定理2.1，3.1和3.2的直接结果，我们可以建立NP-eu1{u，v}ev1eu2ev2eu3eu4ev3ev4720洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711G-DCST的完整性如下。最后一个观察是由于定理2.1的证明。推论3.3 G-DCST（G，D，l，u）是NP-完全的，即使G和D在定理3.1或3.2的假设下。 这个结果甚至在l = u时也成立。值得注意的是，由于G-DCST是NP-完全的，G-DCMST是不可逼近的。这同样适用于L-DCMST和A-DCMST。实际上，在[15]中，我们证明了L-DCMST和A-DCMST对于非常有限的逼近保持ln（n）不可逼近阈值这个结果在下面的定理中给出。定理3.4 L-DCMST（G，D，w）和A-DCMST（G，D，w）是APX-难的，不能近似于（1 − Ω（1））ln（|V（G）|）除非P=NP。此外，它们是W[2]-硬参数化的解决方案树的成本即使G是二部的，依赖关系也只发生在G的相邻边之间，且D的每个弱分支的直径为1。基于定理2.1，很容易看出L-DCMST（G，D，w）和A-DCMST（G，D，w）是G-DCMST（G，D，l，u，w）的特殊情况由此，我们有以下推论。推论3.5定理3.4对G-DCMST（G，D，l，u，w）成立，其中G和D在相同的假设下。这个结果甚至在l = u时也成立。3.2l和u的分析在这一小节中，通过主要关注函数l和u来检查G-DCMST（G，D，l，u，w）。通过这种方法，我们试图获得更深入的了解G-DCMST的硬度和现场的情况下，这个问题可以在合理的时间内处理。特别地，G-DCMST的多项式情况通过拟阵交集来识别。3.2.1l= 0当我们取G-DCMST的实例（G，D，l，u，w），其中l（e）=0，对于每个e∈E（G），我们允许包含边e∈E（G）以及至多u（e）个它的D-依赖。 很自然地认为，对于这种情况，G-DCMST似乎是CCMST的一个由此，可以想象在l=0下CCMST和G-DCMST之间的可能关系。在继续之前，我们注意到G-DCMST（G，D，l，u，w），其中l= 0，u（e）≥|对任意e ∈ E（G），对任意的e ∈ E（G），都是一个易解的问题.|, for each e∈ E (G), is an easily solvable problem.由于G的每一棵生成树平凡地（l，u）-满足D，所以它可以找到一棵具有最小权的根据W.而且看|D（e）部|≤ |E（G）|，我们看到考虑u（e）≤|E（G）|，对每个e∈ E（G）.下面的定理建立了G-DCMST（G，D，l，u，w）在l=0下的硬度是CCMST硬度的直接结果。换句话说，洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711721eeee∪∪∪\JJ可以看出，即使我们“削弱”CCMST的约束条件，CCMST仍保持其NP-困难性。定理3.6 G-DCMST（G，D，l，u，w）是NP-难的，即使l = 0且u是正常函数.证据设k>0为整数。给定CCMST的实例（G=（V，E），Gc=（E，Ec），w），我们描述了在下式中对G-DCMST（GJ，D，l，u，wJ）的成本保持约简GJ=（V<$VJ，E<$EJ），其中VJ={p}<${pi：e∈E，i∈[κ]}，EJ={{p，q}}<${ai={p，pi}：e∈E，i∈[κ]}，对于某个q∈V;D=（E<$EJ，A），其中A=A1<$A2，A1={（e1，e2），（e2，e1）：{e1，e2}∈Ec}且A2={（ai，e）：e∈E，i∈[κ]};l（e）=0，对于eache∈E<$EJ;u（e）=κ，对于ache∈E<$EJ;weJ=we，对于eache∈E，和wej， =0，对于ache∈EJ. 既然我们可以限制自己，类型的实例|E| ≥ κ证明NP-困难，约简是多项式的。看到图4是一个例子。 注意GJ[VJ<${q}]是一棵树。现在，我们证明了T是CCMST（G，Gc，w）的解当且仅当存在G-DCMST（GJ，D，l，u，WJ）的解Tj，其中T=TJ[V]。首先，取T=（V，ET）作为CCMST（G，Gc，w）的解。我们将T展开为TJ=（VVJ，E T′），定义E T′=E T EJ。显然，T=TJ[V]。我们需要证明TJ是G-DCMST（GJ，D，l，u，wJ）的解由于T是G的一棵生成树，并且EJ中的每条边都是GJ中的一条割边，我们可以看到TJ是GJ的一棵生成树。由T的可行性可知，对于e1，e2∈ET，我们有e1∈/ depD（e2）和e2∈/depD（e1）. 对于每个e ∈ ET，|dep D（e）E T′ |= κ，因为很明显，|dep D（e）|= κ。由此得出，对于每个e∈ET，l（e）≤|dep D（e）E（TJ）|≤u（e）。注意，对于eache∈EJ，depD（e）=ε，soitisimmmediatetthatt，对于yk≥0，l（e）≤ |dep D（e）E（TJ）|≤ u（e）。因此，T J（l，u）-满足D，所以T J是G-DCMST（G，D，l，u，w）的解。反之，设TJ=（VVj，ET'）是G-DCMST（GJ，D，l，u，WJ）的解. 证明了T= TJ[V]是CCMST（G，Gc，w）的解. 由于E j中的每条边都是G j中的一条割边，我们看到EJ<$E T′。然后，通过D的构造，可以得出：|dep D（e）E T′|≥ |dep D（e）|= κ，对于每个e ∈ E。 设e ∈ E T′\EJ. 通过T j的可行性，我们有|dep D（e）E T′ |≤ u（e）= κ，因此|dep D（e）E T′ |= u（e）.从这些观察，我们得出结论，|dep D（e）（E T′\EJ）|=0。换句话说，如果e1，e2∈ET′\EJ，则我们有e1∈/depD（e2）和e2∈/depD（e1）.Now，取T=T [VJ]=（V，ET′EJ）。因此T是（Gc）-相容自由的.最后，由于TJ是Gj的一棵生成树，所以T也是G的一棵生成树.这说明T是CCMST（G，Gc，w）的解.为了完成证明，请注意EJ边的权重为零。这意味着CCMST（G，Gc，w）和G-DCMST（GJ，D，l，u，WJ）的相应解具有相同的权，从而CCMST（G，Gc，w）和G-DCMST（GJ，D，l，u，WJ）具有相同的最优值。Q文[16]证明了CCMST（G，Gc，w）在多项式时间内可解，其中Gc是不相交团的并.由于它与CCMST的相似性，我们可以证明G-DCMST（G，D，l，u，w）在l=0下的类似结果设（G，D，l，u，w）是G-DCMST的一个实例，其中l=0且D=D1<$D2<$722洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711ue1ve2QGpa1aκa 1aκe1e1e2e2p1 pκe1e1p1 pκe2e2e1e2(a) G′。(b) Gc.的1e1aκe1e1e2的1e2aκe2(c) D.图四、CCMST减少的图示... Dk是k个不相交的完全有向图的并集，也就是说，任何一对顶点之间都有两个方向的弧的有向图。此外，对于每个e∈V（D i），i∈ [k]，假设u（e）= u i−1，对于某些1 ≤u i≤|V（D i）|.从这个构造中，G-DCMST（G，D，l，u，w）的解可以有至多ui条来自Di的边，i∈[k]。我们表明，这样的实例对应于一个拟阵优化问题，可以在多项式时间内解决。寻找加权拟阵的最大权基的问题可以在多项式时间内解决[6]。由于图G的生成树对应于图G的图拟阵的基，因此经典的最小生成树问题（MST）可以在多项式时间内求解。若G按w：E（G）→ R+加权，则对于一个e ∈ E（G），我们认为wEJ=M−we，其中Mch假定wJ是一个正态函数.这样，MST（G，w）对应于找到G的由wJ加权的图拟阵的最大权基。一个分割拟阵M=（E，I）是基于一个分割E=E1<$E2<$. 它的元素和整数d i的k≤|E i|，i∈ [k]. E的子集S在I i i中，|SE i|对于每个i∈ [k]，这一定义来自[9]。文[7]证明了求两个加权拟阵M1和M2的由于G-DCMST（G，D，l，u，w）的解T对应于G的图拟阵的一个基，即M1，也对应于与D有关的一个分割拟阵的一个独立集和u，假设M2，T对应于M1和M2的公共独立集合。由于M1和M2都可以根据wJ加权，这导致了以下定理。定理3.7G-DCMST（G，D，l，u，w）可以在多项式时间内求解，如果l=0，洛杉矶Viana，M.Campêlo/电子笔记在理论计算机科学346（2019）711723我∈∅eeeeeeeeeva1a20 0vPvPeS10 eSVS0vieS我的1一个2eSeS我eSD= D1 D2. k是k个不相交的完全有向图的并集，对于每个e∈ V（D i），i ∈ [k]，u（e）= u i− 1，对于某些1 ≤ u i≤ |V（D i）|.3.2.2l >0当我们考虑G-DCMST的实例（G，D，l，u，w）时，其中l（e）>0，对于每个e∈E（G），我们允许边e∈E（G）参与解，仅当其D-依赖集depD（e）中的一定（正）数目的边也参与。在这种情况下，很容易建立G-DCMST的NP硬度。此外，我们进一步约束l以获得更强的硬度结果。让我们考虑从[15]中使用的集合覆盖问题（SCP）的简化来证明L-DCMST是APX-困难的。当然，这种约化也证明了L-DCST是NP-完全的。这样的约简构建了一个实例（G，D），如图5所示（除了人工顶点v、vP和vP之外，SCP实例的每个元素i由vi表示，每个子集S由vS表示;而且，i∈Si∈E（G））。观察到每个边e ∈ E（G）都有|D（e）部|∈ {0，1}。我们可以用弧（e，e）将D扩展到DJ，对于每个eE（G），depD（e）=，所以每条边都有一个DJ-依赖性.注意L-DCST（G，DJ）等价于L-DCST（G，D）。另外，由于每条边都有一个DJ依赖，所以T是L-DCST（G，DJ）的解当且仅当T是G-DCST（G，DJ，l，u）的解，其中l（e）=u（e）= 1，对每个e∈E（G）。由此，我们得出以下定理。(a)图G.（b）有向图D。图五、L-DCMST降低的图示，见[15]。定理3.8G-DCST（G，D，l，u）是NP完全的，即使l（e）=u（e）= 1，对每个e∈ E（G）.我们证明了当l（e）> u（e）时，G-DCST（G，D，l，u）无解，其中e∈E（G）.因此，为了补充定理3.8，我们考虑0

下载后可阅读完整内容，剩余1页未读，立即下载