P3凸Helly数计算的复杂性

⊆可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）285-297www.elsevier.com/locate/entcs关于P_3及相关凸性中Helly数的计算复杂性莫伊塞斯T.卡瓦略a，2西蒙娜·丹塔斯b，2米特雷C。Douradoc，2Daniel F.D. Posnerd，2 Jayme L.Szwarc fiterc，d，e，2aInstituto Benjamin ConstantRio de Janeiro - RJ，巴西cInstituto de Matemáticad系统和计算工程学院巴西里约热内卢联邦大学BInstituto de Matemática e EstatísticaUniversidade Federal FluminenseNiterói - RJ，BrazileInstituto de Matemática e EstatísticaUniversidade do Estado do Rio deJaneiro Rio de Janeiro - RJ，巴西摘要设G是一个图，则P3-c凸hul（分别为. P3-C-凸形hull）of asetCV（G）是通过对C内至少有两个邻点的C个顶点进行迭代加法得到的。C内的至少两个不相邻的邻居）。一个P3-He Ily-inde endent（resp.图G的P3凸-Helly-inde p∈t）是一个集S∈V（G），满足S ∈ V（G）的P3-凸-凸-壳（P3-凸-凸-壳）的交是空的. We表示为yP3-Hellynumber（分别为 P3-Helly-inde pnt（resp. P3-Helly-独立）。 这两个P3-Helly-独立的边对应物遵循应用于其边的相同限制。vp3 HI（resp. vsp 3 HI，Ep3 HI，ESp3 HI）问题的目的是确定P3-Helly数（分别为P3-Hellynumber，边P3-Hellynumber，边P3-Hellynumber）。 我们建立了一组图类的计算复杂性，包括二分图，分裂图和图的连接，vp 3 HI，vsp 3 HI，ep 3 HI和ESp 3 HI。保留字：算法和计算复杂性;集团，支配和独立集;P3-Helly-independent。1介绍研究P3-凸性的Helly性质的一个自然应用是验证网络对一组级联故障错误的安全性。 图1描述了一个网格网络。令S={a，b，c，d}是一组可能的有缺陷的站，1本研究由Coordenação de Pessoal de Nível Superior -巴西（CAPES）-金融代码001、CNPq和FAPERJ（巴西研究机构）提供2电子邮件：moises. gmail.com，sdantas@id.uff.br网站，mitre@nce.ufrj.br网站，posner@cos.ufrj.br、jayme@nce.ufrj.br。https://doi.org/10.1016/j.entcs.2019.08.0261571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。286M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285||−P NP图形类vp3HIEp3HIVSp3HIESp3HI二部NP-硬[Thm3.1]NP-硬[Thm3.3]NP-硬[Cor3.4]NP-硬[Cor3.6]线（BinaryStarI）NP-硬[Thm3.11]NP-硬[Thm3.11]P[Thm3.12]开放线（哈密尔顿）NP-硬[Cor5.6]P[Rem4.5]NP-hard[Thm4.6]开放分裂NP-hard[Thm4.1]P[Cor4.2]P[Thm4.3]P[Thm4.4]两个图P[Cor5.1]NP-硬[Thm5.2]NP-硬[Thm5.3]NP-hard[Thm5.4]加入（团G）P[Thm5.8]NP-hard[Thm5.8]P[Thm5.8]P[Thm5.8]4K1-freeP[Cor5.5]P[Cor5.5]NP-硬[Cor5.5]开放（q，q−4）固定qP[[1]]P[[1]]P[[1]]P[[1]]表1vp3HI、vsp3HI、EP3HI和ESp3HI的复杂性。网络和SJ是S的四个大小为S1的真子集。这个网络中的级联故障会影响到与其他两个故障站共享信息的每个站。每个级联故障可以看作是一个层的P3-凸包应用到一个集在SJ。如果S是一个P3-Helly独立集，那么没有一个站是S={a，b，c，d}P3-凸壳一BDCS {a}S\{b}S\{c}S d图1.一、网格网络中的一组级联故障错误a由SJ的集合给出的所有四个级联故障错误所决定。因此，我们可以设计车站，使他们继续在安全模式下工作，考虑到他们 不会被完全的严重故障所影响图上的不同凸性由于其广泛的应用而被广泛研究[2，4，5]，包括分布式系统[14]，社交网络和营销策略[9]。此外，图的Helly性质在过去的研究中也得到了相当深入的研究[3]。我们解决的问题认为Helly属性的P3-凸的图。本文首次系统地研究了P3-Helly-independent问题的计算复杂性我们提出了图类，其中vp3hi，ep3hi，vsp3hi的计算复杂性在相对硬二分法方面完全不同（见表1）。对于任意图G，我们还建立了P3中的Helly数参数与已知图参数的相关凸性之间的关系：最大独立集α（G），最小控制集γ（G），最小独立控制集I（G），最大诱导匹配βI（G）和最大团ω（G）的大小.本文的组织结构如下。第2节包含符号，限制和性质的P3-Helly独立的问题，在我们的证明。第3、4和5节分别包含了关于二分图、分裂图和图的连接的所有四个vp3hi、ep3hi、vsp3hi和esp3hi问题的计算复杂性的25个结果（详细描述见表1本文将任意图G的参数α（G）与二部图的一个子类（第三节）和分裂图的一个子类（第四节）的hP3，任意图G的参数γ（GG的一个子图类，且HJP3（第3节）;以及任意图h G的一个子图类，且HJP3和hP3均为图s的joi的子图类，β ∈（G）和ω（G）（第5节）。M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285287⊆3332P3-Helly-independent problems在本文中，我们只考虑简单图。给定一个图G，P3-凸包（分别为P3-凸包）是一个集CV（G）的一个凸壳，它是通过迭代地将C中至少有两个邻域的C个顶点相加得到的。C内的至少两个不相邻的邻居）。图G的顶点集S∈V（G）是 P3-Helly-独立的（或P3-Helly-independent）当且仅当（限制（i）） P3-凸包（分别为（对所有v∈S）是空的，即，v∈S（P3-凸包S\ {v}）=P[resp.v∈S（P3）凸壳S\{v}）= S]。为了方便起见，我们还考虑一个较弱的限制：如果S是P3-Helly-independent集（P3-Helly-independent集），则（限制（ii））P3-凸包（分别为P3-凸包）不包含v.在下文中，我们表示 P3-Helly-独立集的限制（i）（ P3-Helly-independentset）通过顶点限制1（resp. 对P3-Helly独立集（分别为：P3-Helly-independentset）通过顶点限制2（resp. 启动限制2）。我们用P3-Helly数（P3-He lly_number_ber）最大值P3-He lly-独立集的大小（分别为：P3-Helly-independent set）。 这两个P3的边缘对应物-Helly-independent问题遵循应用于其边缘的相同限制vp3hi（vsp3 hi，ep 3hi和esp 3 hi）问题的目的是确定P3-Hellynumberh P3（resp. P3-HellynumberhP3，边P3-HellynumberhjP3，边P3-HELLYNUMBERHJP3graph.注意，ep3hi（resp.esp3hi）直接与图G的vp3hi（resp.esp3hi）对于L（G），G. 因此，HJP3（G）=hP3（L（G））（resp. hJP（G）=hP3（L（G）. 在整个本文只考虑简单连通图，因为hP3（分别为p. hP3，HJP3，hjP3）是不连通图G的连通分支上的参数之和.注2.1ep3hi（resp. esp3hi）与vp3hi（resp. vsp3hi）的一个图类CJ的线图组成的图C.当我们说一个配置是禁止的，我们不仅考虑子图，而且考虑在P3-Helly独立问题中使用的子图的元素。图2中显示了一些不重要的禁用配置（所选元素由红色/粗体表示）。在（a.1）v1不尊重顶点限制1;（a.2）v2不尊重顶点限制2;（a.3）v3不尊重顶点限制1;（a.4）v4和v5都不尊重顶点限制1。在（b.1）v2不尊重星限制2;（b.2）无论如果选择了v4，它在所有情况下都不遵守起始限制1在（c.1）e1不尊重边缘限制2;（c.2）e2不尊重边缘限制1;（c.3）e3也是如此;（c.4）e4不尊重边缘限制2。在（d. 1）中，e1不考虑星边限制2;（d. 2）e2不考虑星边限制1;（d. 3）e3不考虑星边限制2。请注意，P3-Helly-independent集的禁止配置是唯一需要导出图的配置，即，的288M.T. Carvalho等人/理论计算机科学电子笔记346（2019）28533NP--联系我们{}∪∪≥P3- 独立(a.1)（a.2）（a.3）（a.4）P*3-地狱独立（b.1）（b.2）任意边边P3-Helly独立edgeP*3-地狱独立(d.1)（d.2）（草3）(c.1)（c.2）（c.3）（c.4）图二、 P3的前级配置（分别为 P3，边P3，和边P3）-Helly-inde pnt集.将边缘添加到其它禁止配置导致另一禁止配置。边P3-Helly-independent集具有一些有趣的性质：（性质ESP 3 HI 1）一个没有禁止配置（d.1），（d.2）和（d.3）的集是边P3-Helly-independent集;（性质ESP3 HI2）一个边P3-Helly-independent集M有G[M]作为星形图和三角形的并（物业ESP3HI 3）若G1=K3，则存在一个极大边P3， 它是不含三角形的Helly无关集;（证明ESP3H14）|V（G）| −γ（G）≥hJP3<$（G）≥|V（G）| -i（G），且（Property ESP3HI 5）hJP 在导出子图下是闭的。我们也有讨论了图G的P3-Helly无关问题的Helly数的界的性质：（Proper ty界1）β（G）≤HJP3（G）;（Proper ty界2）若G是大 小 为 w 0 的 无极大团，则 HJP3（G）=max{2，β（G）};（Proper ty界3）HJP3（G）≤14β（G）. （假设边界4）如果hP3（G）（分别 hP3hi（G）、hP3hi（G）或HP3HI（G））为常数，则vp3hi（分别为.ep3hi、vsp3hi或esp3hi）在P中。（性质界5）hP3（G）≤2α（G）;（性质界6）HJP3（G）≤2α（G）;（性质界7）α（G2）≤hP（G）（其中G2是G的平方图）.3二部图设GJ是由图G中的每一个度为1的顶点加一个真孪生点而得到的图。注意GJ的最小度至少为2，并且α（G）=α（GJ），γ（G）=γ（GJ）。在下文中，只考虑每度一个顶点增加一个真孪生顶点的定理3.1 vp 3 hi对二部图是NP -难的。证据 我们证明了一个多项式时间的转换，从困难的M是问题[7]到vp3hi的二部图。它的构造类似于二部图的平方m的硬度证明 [6]。考虑一个图G，α（G）为5，是Mis问题的一个修正实例设H是满足V（H）=V（G）E（G）u1，u2，u3，u4;uv E（G），在E（H）中添加边uv，vuv;添加H的u1和E（G）-顶点之间的所有边;添加H的u2和E（G）-顶点之间的所有边;添加边u1u3，u2u4.存在H的一个P3-Helly独立集，其大小为α（G）+2，利用u3，u4（它们到所有V（G）-顶点的距离为3）和G的一个最大独立集的V（G）-顶点在H中的距离为4.在H的任意最大P3-Helly无关S中，至多有u1，u2，u3，u4E（G）的四个顶点，或者存在一个禁止构形（a.1）或（a.2）.以来M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285289≥≥≥≥≥NP{}≤ − 100{}NPh P3（H）α（G）+27，则S中至少有3个V（G）-点. 没有S中的三个E（G）-点或其中之一蕴涵点限制2矛盾.另外，u1或u2不属于S中有另外三个V（G）-顶点的S，否则，S中的两个V（G）-顶点与同一个E（G）-顶点相关联，我们有一个禁止构形（a.1），或者S中的两个V（G）-顶点包含P3-凸壳中的所有E（G）-顶点，这意味着S中的第三个V（G）-顶点与顶点限制2矛盾，因为V（G）-顶点的度至少为2。其余的情况发生在S中有两个或一个E（G）-顶点的时候。在第一种情况下，这两个顶点包括P3-凸包中的所有E（G）-顶点，这意味着顶点限制2矛盾。在第二种情况下，如果u3和u4不在S中，则由于hP3（H）α（G）+ 2，则S中有两个V（G）-顶点与同一个E（G）-顶点关联，这些顶点包括P3-凸包中的所有E（G）-顶点，这意味着顶点限制2矛盾.否则，考虑S中的顶点u3或u4。在任何情况下，它包括u1或u2在P3-凸包，并在下一次迭代，所有E（G）-顶点，这意味着一个顶点限制2矛盾。因此，S必须由u3，u4和V（G）-顶点组成为了矛盾起见，假设hP3（H）α（G）+ 3.有：（i）两个顶点u3和u4和一对V（G）-顶点在距离2内的S;（ii）一个顶点u3或u4和两对V（G）-顶点在距离2内的S与不同的E（G）-顶点关联（由于禁止构型（a.1））;（iii）三对V（G）-顶点在距离2内的S与不同的E（G）-顶点关联。在所有情况下，所有的E（G）-顶点都包含在P3-凸包中，这意味着S的另一个V（G）-顶点存在顶点限制2矛盾. 因此，hP3（H）=α（G）+2.Q注3.2图G的子图是一个二部图，它有ι（G）=γ（G）[17].此外，Ko和Shepherd [10]证明了β<$（G）+γ（G）= β<$（G）+ γ（G）= |V（G）|.定理3.3ep3hi是- 对二部图是困难的（对二部图的线图也是困难的）证据 考虑一个困难问题mds [7]的修改实例图G，其中γ（G）n图7和H是满足V（H）=V（G）的图E（G）u1，u2;uv E（G），在E（H）中添加边uv，vuv;添加u1与E（G）-顶点之间的所有边和u2与V（G）-顶点之间的所有边.设M是H的极大边P3-Helly-inde p nt集，且HJP3（H）第七章这里没有两个或更多的边缘M中的u1或u2的事件。否则，这些边包括与u1关联的所有边（分别）u2），它包含M中所有与端点在V（G）-顶点和E（G）-顶点的边的端点相关联的边（用中边表示），并且存在边限制2矛盾.此外，不存在与u1或u2相关联的边，也不存在与同一个V（G）-顶点相关联的两条中间边（ E（G）-顶点）。 否则，它包括u1的另一条边（分别为u2），它包含了H的所有边。因此，它也意味着在M的中间边中的边限制2矛盾。290M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285NPNPNP NP联系我们因此，在M中只有中间边，并且这些边在V（G）-顶点中不共享公共顶点（分别是，E（G）-顶点）。此外，没有边关联到两个选定边的两个端点。否则，这些边包括与u1（resp.u2）在边P3-凸包中，我们处理的是前一种情况。因此，M中的边是H的诱导匹配，并且该诱导匹配是最大的，因为如果我们选择与u1（resp.u2）的最大诱导匹配，则E（G）-顶点（分别为V（G）-顶点）且没有与其他端点相关联的边这些边缘。因此，例如，我们可以将边{u1de}或边{u2a}交换为中间边{dde}和{aab}（对于E （G）-顶点中的a n yab）。通过注3.2，γ（G）+β（（G））= |V（G）|. 因此，确定γ（G）等价于确定β（SUB（G））=β（H）=HJP3（H）.Q由于一个无三角形图G的所有P3都 在P）中，vsp3hi也是如此。推论3.4 vsp 3 hi对于二部图是NP -难的。备注3.5由专业ESP 3 HI4，|V（G）|−γ（G）≥hJP3<$（G）≥|V（G）|−i（G）. 因此，对于具有图G的任何图类C，其中i（G）=γ（G），C中的Mds的计算复杂度与esp3hi相同。由注3.5，3.2得到的下一个推论是MiM（MAXIMUM诱导匹配）是-hard的[7]，这意味着Mds对于二部图（特别是MiM的推论3.6esp 3 hi对于二部图是-困难的（vsp 3 hi对于二部图的线图也是如此）。构造3.7从二分图G =（X，Y，E）得到二分图H（用双星I或双星II图表示）如下。V（H）= V（G）u1，u2（我们用泛星顶点表示u1和u2）;（i）二叉星I图：添加u1和X-顶点之间的所有边，u2和Y-顶点之间的所有边，并添加所需数量的与u1或u2关联的1度顶点;（ii）二叉星II图：添加u1和u2之间的所有边到X-顶点，并添加所需数量的与u1或u2关联的1度顶点;构造3.7的双星I类包含定理3.3的图H，双星II类包含定理3.1的图H。推论3.8接着定理3.1和3.3，以及vp3hi和vsp3hi在无三角形图上具有相同的计算复杂度的事实。此外，推论3.9还遵循性质界2，因为如果G没有2度顶点，则L（G）没有大小为2的极大团最后，推论3.10由推论3.9推出。以及β∈（L（G））=P3-part（G）[13].推论3.8vp 3 hi和vsp 3 hi对于双星II图是-困难的，ep 3 hi对于双星I图也是-困难的。推论3.9一个没有2度顶点的图G的线图L（G）HJP3（L（G））=β∈（L（G））.M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285291P3∪≥NP≤≤∪∪∪NP≥≥≥C CNPPCP3- 部分的目标是获得P3-部分，即覆盖其顶点所需的最少的点不相交P3推论3.10如果对于一个没有2度顶点的图类，J，由以下图的线图组成：是- 硬（分别为），那么ep3hi也是如此。定理3.11vp 3 hi和ep 3 hi对双星I图的线图是-困难的。证据vp3hi的证明由注释2.1和推论3.8得出。对于具有δ（G）的实例二部图G，P3-PARTIAL是-hard的2[12]。 设GJ是由G的两个泛星点相加得到的双星I图，其中每个泛星点都有两个1度点关联. 显然，GJ没有2度顶点，且P3-part（GJ）=P3-part（G）+2.现在，ep3hi结果由推论3.10得出。Q定理3.12esp3hi对于双星I是成立的（vsp3hi对于双星I的线图也 是 成 立的 ）。证据设H是由构造式3.7得到的图。考虑H的任意边P3-Helly-independentM.通过性质ESP3HI 1，可以将与两个星顶点相关的所有边拾取为M的一部分，因为不存在强制配置（d.1）、（d.2）和（d.3）。另一方面，H没有唯一的顶点，并且通过属性ESP3HI 4，这是最好的可能。因此，hJP3<$（H）=hP3<$（L（H））=|V（G）|.Q4分裂图设G =（IK ，E）是一个分裂图，其中I是一个独立集，K诱导一个团. 我们需要两个性质：（性质SPLIT 1）α（G2）hP（G）α（G2）+1和（性质SPLIT 2）一个顶点为K或两个顶点为I且距离为2的极大P3-Helly无关集S在S中至多有两个顶点为I且度大于1.定理4.1 vp 3 hi对分裂图是NP-难的。证据本文给出了一个多项式时间变换，从图G [7]的NP -难mis问题（α（G）4）到分裂图H的vp 3 hi（hP3（H）4），如下所述. V（H）=V（G）V（G）E（G）（我们用V2（G）表示第二个V（G））.（E（G）V2（G））-顶点构成H中的团.如果v是G中e的端点之一，则V（G）-顶点v和E（G）-顶点e之间存在边;如果V（G）-顶点v和V2（G）-顶点v2表示G中的同一个顶点，则V（G）-顶点v和V2（GG. 注意，如果uv∈E（G），则u和v在H中的距离为2。否则uv/∈E（G），则它们在H中的距离为3。通过构造，H的最小度至少为2。因此，根据性质SPLIT 2，由于hP3（H）4，在最大P3-Helly独立集中，292M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285≤P≥≤≤H的S。因此，S只有H的独立集合的顶点，它们之间的距离至少为3，即，hP3（H）=α（H2）=α（G）.考虑G的一个极大独立S集，其顶点为α（G）利用性质界7，可以选取与S的顶点相关的相同的V（G）-顶点属于H的一个P3-Helly无关集，其中α（H2）=α（G）.反之，考虑H的一个极大P3-Helly无关集Sj，其顶点数为h个P3（H）由于SJ中的所有顶点在H中的距离至少为3，因此G中的相关V（G）-顶点在G中的距离至少为2。因此，hP3（H）=α（G）.Q设G是一个分裂图。证明了G的至少有两条边的任意集的边P3-凸包是E（G）. 因此，我们得到P3（G）2或我们有一个边缘限制2矛盾。下一个推论遵循性质界限4，因为hJP3（G）是常数：推论4.2ep3hi适用于分裂图（vp3hi适用于分裂图的线图）。定理4.3 vsp3hi在P中。证据设S是分裂图G =（I ∈ K，E）的最大P3-Helly-独立集. 为了避免矛盾，假设P3∈G.ω（G）+2。 考虑这样的情况，我们有两对不同的顶点，它们在S中的距离为2。无论如果在K中这两对顶点和它们共享邻域之间存在边，则这些顶点和它们的共享邻域意味着星形限制1矛盾。因此，在S中至多有一对距离为I的顶点，I在S中的其他顶点与团的不同顶点相邻。因此，hP3<$（G）≥ω（G） + 2意味着S中团的至少一个顶点.现在考虑没有距离为2的顶点对的情况，我在S。S中至少有两个团的顶点，并且S中至多有一个I的顶点与S中K的一个顶点相邻。否则，如果S中I的两个顶点与S中的一个顶点K相邻，则它们必须与S中K的所有顶点相邻，以避免禁用配置（b.1），这也迫使禁用配置（b.1）。因此，S中的I和S中的K的其他顶点必须不相邻。现在，S中I的每个顶点vi都与K中的一个不同的顶点wi相关，其中wi一定不在S中。这意味|S|≤ω（G）+ 1，一个矛盾。最后，考虑这样的情况，我们有一对距离为2的顶点，S.注意，在S中至少有一个K的顶点，在S中没有顶点I与S中的顶点K相邻，并且至少有ω（G）+1个这样的顶点（不包括S中I的顶点对）。由于S中I的每个顶点都与S中K的一个不同顶点相关，这意味着S中I的一个顶点与K中的一个顶点相邻，S.然而，为了避免星形限制1矛盾，距离为2的顶点对中的一个必须与K的这个顶点相邻，这也意味着禁止配置（b.1）。因此，ω（G）P3（G）ω（G） +1，它可以在p多项式时间内确定.QM.T. Carvalho等人/理论计算机科学电子笔记346（2019）285293P3∈∈∈NPNP||−|| ≥NP||||||−定理4.4esp3hi对分裂图成立（vsp3hi对分裂图的线图成立）。证据设M是分裂图G的一个无三角形边P3-Helly独立集，v是G的一个最大度顶点.显然，V是集团的一部分有可能将v中的边作为M的可能集合。 根据ESP3HI2和ESP3HI3的性质，G[M]是一个中心间无边且叶子多于两个的星图的并.在团的顶点上没有两个以上叶的恒星中心，或者我们有一个禁止的构形（d. 2）。因此，只有一个团的顶点v与M的多条边关联。这意味着M的所有不与v关联的边都是团的顶点与独立集之间的匹配。然而，对于这种匹配的每条边，在v和边的端点之一之间存在缺失边，否则存在禁止配置（d.1）。因此，我们需要V（G）Δ（G）（v的度）星划分G的顶点与至少有两片叶子的星的不相邻的中心。根据性质ESP3HI 4，每颗星使hJP（G）和V（G）之间的差增加一个单位。也就是说，|为|V（G）|-（|V（G）|−Δ（G））= Δ（G）。|−Δ(G)) = Δ(G).利用ESP 3 HI 3性质，G的所有三角形为Mj的极大边P3-Helly-inde pnt集有|MJ| ≤|M|. Q注4.5注意推论3.10和对于Hamilton图的线图MiM在P中的事实[11]意味着对于δ≥3的Hamilton图的线图ep3hi在P中。定理4.6esp3hi是- Hard对于哈密尔顿图（vsp 3 hi对于哈密尔顿图的线也是如此）。证 据 这 一 证 明 是 基 于 2 P3-free 图 的 M_id （ M_inim_umm_INDEPENDENT-DOMINATING set）的完全性证明[16]。设J=（U，C）是著名的完全问题3-sat [7]的一个例子，其中U=p，C=q.我们从实例J构造图G如下：对于每个变量uU，我们将具有标签u和u的P 2添加到G;对于每个子句c C，我们将具有标签c的顶点添加到G;我们将子句顶点和之间的所有边添加;对于每个子句c C（例如，c=（x，y，z）我们在文字和c之间添加边（例如，边缘xc、yc、zc）。我们假设没有子句连接到一个变量的两个字面量，因为这个子句总是真的，它可以从C中删除，并且U2（因为验证只有一个变量的子句的真值赋值是微不足道的）。现在，复制（即，添加真双胞胎）为每个子句顶点2p次。本文证明了G的最大边P3-Helly无关集M有大小V（G）它使用最小独立控制的相同顶点设G的ID为它的星的中心当且仅当i（G）=p。 为了对抗-假设M中有一个三角形。注意G的任何三角形在团中至少有两个顶点。通过禁止配置（d.3），所有与此三角形是M中的孤立星。此外，我们还需要用以这些顶点为中心的其他p星覆盖其余的P2顶点因此，我们认为，|M| ≤ |V（G）|−q−p，一个满足hhJP3<$p（G）=|V（G）| -p。假设M有一个恒星中心294M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285−∧∧≤≥NP联系我们3|| −≥ NP||−||−在小句团顶点中。它们在P2因此，它至少需要p个以上的恒星中心，即，|≤ |V（G）|-p-1，也是一个矛盾。|− p − 1, also a contradiction.现在，我们证明了至少需要p个不相邻的星中心来划分G的顶点，并且这些顶点与C的真值分配有关。因为在团中没有中心的星，所以所有的星都在P2的顶点上有中心，我们需要至少p个这样的星来覆盖P2的如果我们用一个顶点 以P2为高次星的中心，P2的另一端为一个度为1的星的中心，我们仍然需要P2的至少另外的p1个顶点来将G的顶点划分成不相邻的星，这与hjP（G）= V（G）p是矛盾的。考虑C的真值赋值。选择一组与此真值赋值相关的顶点M作为星的中心。每颗星都覆盖着变星因为它是一个真值赋值，所以所有子句顶点都由一个星中心到达。 恒星的这些p中心是不相邻的。 因此，M是G的一个极大边P3-Helly-inde p∈G|M|=hJP3（G）=|V（G）| -p。反之，考虑G的任意最大边P3-Helly-independent M，其大小为M=HJP3（G）=V（G）p。恒星的p个中心必须在P2每个P2中有一个。此外，由于它们到达所有子句顶点，所以使用M中具有真值的顶点的相关文字的赋值是J的真值赋值。Q5联图连接图G=G1G2有h P3（G）二、因此，推论5.1如下：第四.推论5.1vp3hi是多项式可解的，G = G1G2，两个图G1和G2的连接。定理5.2ep 3 hi对于两个图的并是 -困难的（vp 3 hi对于两个图的并的线图也是-困难的）。证据 考虑一个图G，其中β∈（G）6、一个实例- 硬prob-lemMiM问题[15].设H=Gv，M是H的极大边P3-Helly无关集.在M中没有与v相关联的边。否则，由于β∈（G）6，M中至少还有三条边，这意味着边限制2与这三条边中的一条矛盾。在M中也不存在两条边与G的同一顶点w相关联，或者边vw包含在边P3-凸包的下一次迭代中，我们处理的是前一种情况.此外，没有边M外共享两个端点与两个边缘M或我们包括一个边缘事件到v中的边缘P3-凸包M，我们再次处理以前的情况。因此，M是诱导匹配，即， HJP3（H ）=β（G）.Q定理5.3 vsp 3 hi是NP-难的。证据考虑图G是NP -难问题的一个例子. 设H为图，|V（G）|G的+1个拷贝，所有可能的边都在M.T. Carvalho等人/理论计算机科学电子笔记346（2019）2852952|| ≤||NP|||||| ≥ ||{||||}3333≤3≥NP3||NP不同副本的顶点和S_n是H的一个极大P3-Helly-独立集。考虑一个集合SJ，其顶点是G在H中的每个拷贝的最大团的顶点。因此，Sj=（V（G）+1）ω（G）是P3<$-Helly-indepnt，且SJ =（V（G）+1）ω（G）是SJ。为了避免矛盾，假设我们从一个副本中选取两个不相邻的顶点，G是H的一部分。 我们不能选择G的其他副本的任何其他顶点作为S的一部分，或者这个顶点隐含了一个星限制2矛盾。 因此，SV（G），这与S是最大值的事实相矛盾。 因此，我们只能在G的每个副本中挑选一个最大团的顶点作为S的一部分，并且对于副本y只能挑选一个最大团。也就是说，10-12-2000（|V（G）|+1）ω（G）。Q定理5.4esp3hi是- 对于图的连接是困难的（对于图的连接的线图也 是如此）。是的 。设 M 是 G = G1 <$G2的无 三 角 形边 P3<$Helly-inde pnt 集. 本 文 证 明 了HJP<$（G）=max=maxV（G1）+HJP<$（G2），V（G2）+HJP<$（G1）. G1或G2至少有一个顶点是M中至少有两片叶子的星。否则，M是G1和G2的顶点之间的一个矩阵，且hJP3∈G≤|+|V（G 2）|，其小于最大值，因为属性ESP3HI 4和|, which is smaller than max, because of PropertyESP3HI 4 andi（H）≥ |V（H）|对任意H，hJ∈（G2）≥ |V（G2）|且hJ∈（G1）≥ |V（G1）|，a2矛盾P32请注意，有一个M，|M|为|V（G1）|+hJP3（G2）（resp. |M|为|V（G2）|+HJP（G1）），因为我们可以选择G 1的最大边P3-Helly-inde pt（resp. G2）和添加到G 1的恒星的中心之一（resp. G2）的所有边都与G2的顶点关联（分别为G1）。因此，hJP（G）max。此外，在G1或G2中没有具有两个以上叶的恒星的中心，或者我们有一个被禁止的配置（d.2）。为了矛盾起见，假设HJP3（G）>max.W.l.o.g.， 让|V（G1）|+hJP3<$（G2）≥|V（G2）|+HJP3（G1）. 因此，我们使用只与G2的顶点相关联的HJP（G2）条边，并且我们需要至少V（G1）+1条边与G1的顶点相关联。然而，它意味着G1的至少一个顶点是具有两个以上叶子的星，这是一个矛盾。 由地产ESP3HI 3，所有边缘G的三角形Mj的P3-Helly-inde pnt集有|MJ| ≤|M|. 所以hjP3<$=max. 考虑esp3hi为- 硬（例如， 推论3.6）。硬度结果直接从通过将先前NP-困难情况的实例G j与其自身G=G j<$GJ连接而获得的图类得出，其中hJP3<$（G）=max{|V（GJ）|+hJP3（GJ），|V（GJ）|+HJP3<$（GJ）}.Q无4K1图的联仍然是无4K1图.推论5.5的第一个结果由定理5.3得出，并且事实上，4K1-free图[8].第二个结果如下，因为α（G）4的4K1-free图，性质界4，5，和6。此外，推论5.6由定理5.2的证明得出，定理5.2支持通过添加泛顶点而得到的哈密尔顿图推论5.5vsp 3 hi对于4K1-free图是NP-难的，而 vp 3 hi和 ep 3 hi对于4在P。296M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285NP||∧||3推论5.6ep 3 hi对哈密尔顿图是-困难的（vp 3 hi对哈密尔顿图的线图也 是如此）。构造5.7从一个图G构造一个图H，用（团G）表示如下。将G的一个副本加到H上;将大小为V（G）的团加到H上，并;加一个泛顶点u。定理5.8 vp 3 hi，vsp 3 hi，esp 3 hi在P中，而ep 3 hi是NP-困难的.证据由推论5.1可知，对于图的联，vp3hi在P中。 考虑H的一个极大边P3-Helly-independent集M.如果我们选择u作为恒星的中心，|为|V（H）|-1，最好是ESP 3 HI 1属性。|− 1, which is best possible by PropertyESP3HI 1. 现在考虑H的一个极大P3-Helly-independent集S。在S中不存在两个大团的顶点和两个G的顶点，或者我们有一个禁止的构型（b.2）。此外，u不能是S的一部分，如果在S中存在大团的顶点和G的顶点，或者我们有一个禁止的构型（b. 1）。因此，S中至多有V（G）+1个顶点。这样的S可以被挑选为大团和u的顶点。考虑H的一个极大边P3-Helly独立集MJ.如果我们选取团的多条边到MJ，则边P3-凸包是E（H），并且我们有一个边限制二、 因此，HJP3（cli que<$G）≤HJP3（G<${u}） +1。 存在具有团的一条边和G∈ { u }的最大边P3-Helly-independent MJ（这是诱导匹配）的suc h Mj。硬度结果由定理5.2在G∈ {u}上得出。Q6最后发言本文给出了P3的Helly数及相关凸性的一些结果.为了对vp3hi、ep3hi和vsp3hi的计算复杂性进行比较研究（见表1），我们致力于研究二分图、分裂图和图的连接的子类。esp3hi问题开始是为了支持线图的vsp3hi证明边P3-Helly独立集只有三种最小禁止配置，而其他P3-Helly独立集有无限类型。因此，我们建立了esp3hi与一个变分的定分问题之间的关系。由专业ESP 3 HI4，|V（G）|−γ（G）≥hJP3<$（G）≥|V（G）|−i（G）.当一个谜题的各个部分禁止子图是一类图G，对G的任何导出子图H，有i（H）=γ（H）.令人惊讶的是，它们是完全相同的子图在禁止配置（d. 2）。 因此，对于无三角形图G，其中i（G）=γ（G），存在无禁用配置（d.2）。此外，hJP 被导出子图（属性ESP3HI 5）。因此，对于无三角形图G的任意导出子图H，满足i（G）=γ（G），hJP3（H）=|V（H）| −γ（H）。作为未来的工作，我们的目标是建立缺失的计算复杂性，esp3hi在表1中。我们也有部分结果的计算复杂性的所有四个P3-Helly独立的问题，平面图，弦图，区间图，网格图。M.T. Carvalho等人/理论计算机科学电子笔记346（2019）285297引用[1] 卡瓦略，M。T.，S. Dantas，M. C.多拉多Szwarc fiter和D. F. D. Posner，P3-Helly数图与几个P4，第八届拉丁美洲研讨会的会议记录在图的集团- LAWCG 2018。[2] Coelho ， E. M. M. ， M. C. 多 拉 多 湾 Raute