没有合适的资源?快使用搜索试试~ 我知道了~
⊆⊆⊆可在www.sciencedirect.com在线获取理论计算机科学电子笔记346(2019)393-400www.elsevier.com/locate/entcs禁导子图三明治问题的一种通用方法NP完全性1Simone Dantas2IME,巴西弗鲁米嫩塞联邦大学。塞丽娜·M H. de Figueiredo2COPPE,巴西里约热内卢联邦大学Priscila Petito2FFP,巴西里约热内卢州大学拉斐尔湾Teixeira2ICE,巴西里约热内卢联邦农村大学摘要我们考虑三明治问题,这是Golumbic和Shamir(1993)引入的识别问题的推广,关于通过排除诱导子图定义的图 图的三明治问题是对一对图G1=(V,E1)和G2=(V,E2)且E1E2,是否存在一个图G=(V,E)且E1EE2满足所有权。我们认为,是H-free的,其中H是一个固定图。使用SAT问题的一个新变体,我们提出了一个通用的框架建立了几类无H图的三明治问题的NP-完全性,推广了以前的策略,为类的遗传campaign-Helly图。我们还提供了有限个3-连通的特殊禁止诱导子图族,其中每个禁止诱导子图的三明治问题是NP-完全的。关键词:算法和计算复杂性,图三明治问题,满足性,线性CNF公式,3-SAT,禁止诱导子图1本研究部分由CoordenapecuchaodeAperfeipecuchoamentodePessoaldeN′pecuvelSuperior-Brasil(CAPES)-FinanceCode 001、CNPq和FAPERJ(巴西研究机构)资助。2电邮地址:sdantas@id.uff.br,celina@cos.ufrj.br,ppetito@uerj.br,rafaelbt@ufrrj.brhttps://doi.org/10.1016/j.entcs.2019.08.0351571-0661/© 2019作者。出版社:Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章(http://creativecommons.org/licenses/by-nc-nd/4.0/)。394S. Dantas等人/理论计算机科学电子笔记346(2019)3931引言这里考虑的所有图都是有限且无向的。给定一个图的性质,图的三明治问题定义如下:输入:一对(G1,G2)图,其中G1=(V,E1),G2=(V,E2),E1<$E2;问题:是否存在满足性质n的图G=(V,E),其中E1<$E<$E2图三明治问题是由Golumbic和Shamir [6]提出的。注意,当G1=G2时,问题是确定G1是否满足性质1。因此,图三明治问题推广了决定图是否满足给定性质的问题特别地,如果决策问题是NP完全的,那么三明治问题也是NP完全的。当属性要属于某个类时,我们称这个问题为C图三明治问题。 Golumbic,KaplanShamir[7,8]证明了区间图、单位区间图、置换图和相似图三明治问题都是NP完全问题,而分裂图、阈值图和余图三明治问题都是P完全问题对于图三明治问题的一个例子(G1,G2),其中G1=(V,E1),G2=(V,E2),E1≠E2,我们说E1中的任何元素是强制边,E2\E1中的任何元素是可选边,V×V中的任何其他对是禁止边.每个图G=(V,E),其中E1<$E<$E2被称为三明治图,对(G1,G2).在这种情况下,E由所有强制边加上一些(可能为零)可选边组成,没有禁止边。如果图G的某个导出子图与图H同构,则称图G包含图H。一个图G是H-自由的,如果它不包含H. Dantas,de Figueiredo,da Silva和Teixeira [2]以及Dantas,de Figueiredo,Ma Sirray和Teixeira [3]研究了无H图三明治问题,确定了对于任意固定p≥4的几个图H(paw和(Kp\e)在P中;而Cp,对于任意固定p≥4,claw和bull是NP-完全的).最近,Couto,Faria,Gravier和Klein [1],de Figueiredo和Spirkl [5]进一步研究了无H图三明治问题,并将其复杂性与探测问题进行了比较,探测问题是三明治问题的一种变体,其中可选边出现在V的一个特殊子集的顶点之间。Dourado,Petito,Teixeira和de Figueiredo [4]证明了遗传case-Helly图三明治问题的NP-完全性,其中遗传case-Helly图类由一组四个禁止诱导子图定义,即所谓的眼图。 在这里,我们通过提供一个一般的方法来证明NP-完全性,这推广了他们的策略,对于无限家族的禁止子图,来发展这项研究。为 了完 成 这 个任 务 , 我 们引 入 了 NP- 完 全线 性 合 取范 式3-SAT 问 题(LCNF3-SAT)[9]的一个合适的变体,我们称之为k-围长LCNF2-3-SAT。S. Dantas等人/理论计算机科学电子笔记346(2019)393395我我∈2k-围长LCNF 2-3-SAT我们在本节开始时提出了NP完全LCNF3-SAT[9]的一个合适的变体,我们称之为k-围长线性合取范式2-3-SAT问题(k-围长LCNF2-3-SAT)。根据[9],在线性合取范式3-SAT问题(LCNF3-SAT)中,子句的大小为3,并且每对不同的子句有0或1个公共变量。设I=(X,C)是3-SAT的一个实例,其中X表示变量的集合,C表示子句的集合。子句和变量的二分图B(I)=(VI,EI)是由3-SAT的一般实例I=(X,C)构造的图,如下所示。 对于C的每个子句c,存在属于VI的顶点c。对于X的每个变量x,存在属于VI的顶点x。 如果子句c包含文字x或x,则边cx属于E I。我们注意到,两个不同的子句有0或1个共同变量的线性性质意味着B(I)的围长大于4。拟议变式如下:k-围长线性CNF2-3-SAT(k-围长LCNF2-3-SAT)实例:设置X={v1,...,v n}的变量,集合C={c1,.,c m}的子句满足ch,且c∈C的子句的大小为2 ≤|C|≤3,且对所有c,CJ∈C,c=/cJ,|≤1,并且子句和变量的二分图的围长大于| ≤ 1, and the bipartite graph of clausesand variables has girth greater thanK.问题:是否存在X的真值赋值,使得C中的每个子句至少有一个真值?定理2.12 -3-SAT问题的k围长是NP-完全的。证明:给定LCNF3-SAT的实例(X,C),我们构造k围长LCNF2-3-SAT的实例(XJ,CJ)如下。令X={v1,.,v n}是变量的集合,C={c1,. c m}是X上的子句的集合,使得每个子句c∈C具有大小|C|=3,且对所有c,CJ∈C,cj = CJ,|ccJ| ≤1。最后一个约束确保子句和变量B(I)=(V,E)的二分图的围长g大于4。为了增加g的值,我们进行如下操作。设XJ:=X和CJ:=C。对于每个子句cj={l1,l2,l3} ∈C,1 ≤j≤m,我们引入两个新的辅助变量Xj:=Xj<${xcj,ycj},并用三个新子句cjj,cjjJ和cjJjj代替cj,CJ:=(CJ\cj)<${{l1,xcj},{l2,xcj,ycj},{l3,ycj}}。很容易看出,这种转换是在多项式时间内完成的。 线性性质意味着子句集合C具有在n中线性的大小,这意味着子句的结果集合CJ具有在n中线性的大小,因为前面的集合的子句在n中是线性的,并且每个子句cj C被三个子句替换,这些子句具有至多一个变量与新CJ的所有子句的成对交集(因为这些新子句不复制cj的变量,并且为每个子句cj ∈ C添加不同的附加辅助变量,1 ≤j≤ m)。我们主张实例(X,C)是可满足的,当且仅当(XJ,CJ)是可满足的,因为子句{l1,l2,l3}在逻辑上等价于子句集合{l1,xcj},{l2,xcj,ycj},{l3,ycj}。396S. Dantas等人/理论计算机科学电子笔记346(2019)393我我我我3 33 31我1我2我2我HC高x图1.一、子句子图Hc,变量子图Hx,以及它们的联系.这个过程在更新的二分图B(I)中反映如下。设C是B(I)中包含子句顶点cj的圈.在应用上述过程之后,子句顶点cj被三个新的子句顶点替换,比如cJj、cJjJ和Cj j j。我们还将两个新的辅助变量顶点xc和ycj。Letl1= x或l1= x是子句c j={l1,l2,l3}的文字。 因此,边xcj为由路径x,cJj,xcj,cJjJ替换。因此,B(I)中包含cj的ny圈的大小至少增加2个顶点。很明显,通过重复这个过程最多k/2次,我们保证在多项式时间内构建一个实例IB(I)的围长g大于k,因为k是一个固定数。Q无3H图三明治问题我们对禁止图的一种特殊结构感兴趣。禁止图H需要具有大小为2的匹配,比如A ={a1aJ1,a2aJ2},并且具有大小为3的反匹配(即,补图H中的匹配),比如B={b1bJ1,b2bJ2,b3bJ3}。给定一个k-围长LCNF2-3-SAT的实例(X,C),构造一个实例(G1,G2)的无H图三明治问题的解如下(见图1).在下文中,每个导出变量子图H x和每个导出子句子图H c是H的副本。对于X的每个变量x,在G2中存在一个导出变量子图HX使得边ax aJx和ax aJx是集合中Hx的唯一可选边E2\E1。1 1 2 2对于C的每个三重子句c ={l1,l2,l3},在G1中存在一个导出子句子图Hc,使得对于每个文字li,i∈ {1,2,3},我们在集合E2\E1中包含额外的可选边bcb′c.对于C的每个两个大小的子句c={l1,l2},在G1中存在一个导出子句子图Hc,使得对于每个文字li,i∈{1, 2},我们包含附加的集合E2\E1中的任意边bcb'c注意,在这种情况下,边bcb′c为禁止,即, bcb′cE2.当一个变量x出现为正数时(否定)子句中的文字lic,则边ax aJx(分别ax aJx)等价于边bc bJc,1 1 22i ia x= b c和aJx= bJc(分别为 a x= b c和aJx= bJc),i ∈ {1,2,3}(分别 i ∈{1,2} in(二)条款的效力)。JS. Dantas等人/理论计算机科学电子笔记346(2019)393397这就给出了无H图三明治问题的特例(G1,G2)通过研究图H的一些性质和问题k-围长LCNF2-3-SAT的结构,我们认为这种构造给出了分析无H图三明治问题NP-完全性的充分条件.定理3.1设H是一个图,它含有一个大小为2的匹配和一个大小为3的反匹配.如果上面构造的特定实例(G1,G2)允许一个H-free三明治图G,则存在一个真值分配,满足k围长LCNF2-3-SAT的实例(X,C)。证明:设G是一个无H的三明治图.因此,G1的每一个Hc子句子图都被B的至少一条可选边销毁然而,没有Hx可变子图是通过添加A的两条边来创建的。我们现在定义(X,C)的真值分配:如果B的一条边属于G\G1然后将相应文字的真值设置为true。 假设两条边对应于同一个变量x的正负文字。这在G中生成了一个H诱导子图,对应于x的Hx变量子图,这是一个矛盾。Q逆定理不是那么简单,它需要更深入地研究图H和子句和变量的二分图B(I)的结构。为了从k围长LCNF2-3-SAT的真值分配构造三明治图,我们使用的每一个规则都需要确保没有生成边射H子图。很容易给出一个规则,使G1的所有Hc子句子图都被销毁,而不产生G2的Hx可变子图.我们的尝试在于给出一个简单的规则(每个可选的边对应对一个真文字加到G1上形成一个三明治图G),然后寻找一个边连通的H三明治子图。我们注意到所构造的实例(G1,G2)的每个顶点都属于一个Hc子句子图或一个Hx可变子图,并且可能既属于一个Hc子句子图又属于一个Hx可变子图. 虽然一个顶点最多只能属于一个Hx可变子图,但也可能属于多个Hc子句子图.一个边射H是某个三明治图G的一个导出子图,它同构于H,使得H既不与一个Hc子句子图也不是一个Hx变量子图。在禁止图H的特殊结构中,为了得到逆定理,我们进一步要求禁止图H是3-连通的。定理3.2设H是一个3连通图,其中包含一个大小为2的匹配和一个大小为3的反匹配。 如果存在满足实例的真值赋值,(X,C)的k围长LCNF2-3-SAT,则特殊情况(G1,G2)con-上面构造的图G是一个H-free三明治图。证明:设H是一个3连通图,包含一个大小为2的匹配和一个大小为3的反匹配,设l是H的最大无弦圈的大小。让398S. Dantas等人/理论计算机科学电子笔记346(2019)393| | ≤高xHax我a′x我图二、 顶点ax和a′x的恢复使H断开,这是一个矛盾。我我参数k= 2l.假设存在一个真值赋值,满足实例I=(X,C),k-围长LCNF2-3-SAT,并考虑简单的规则,增加到G1,每为了定义一个三明治图G,需要一个与真文字对应的可选边。由于简单规则破坏了G1的所有Hc子句子图而没有产生G2的Hx可变子图,因此还需要证明三明治图G不包含既不与Hc子句子图也不与Hx可变子图相关联的边射诱导子图H 假设得到一个矛盾,G包含这样的一个边射诱导子图H。通过构造,存在一个变量x,使得边连通子图H必须包含两个顶点中的至少一个ax和aJx,可选边ax aJx的端点。 两个顶点ax和aJx是伊伊利用线性性质,给出了Hc子句子图与HX变量子图之间或Hcj与Hcj′之间的唯一联系注意可选边ax aJx属于唯一可变子图Hx。进一步注意我我可选边ax aJx必须与至少一个子句子图关联我我Hc. 假设首先移除两个顶点ax和aJx,我我边射诱导子图H,这给出了一个矛盾,因为H是3-连通的图(见图2)。因此,边射子图H必须包含一个无弦圈S,它包含:x或Jx中的至少一个(参见图3)。 注意,S的大小小于或等于我我到H的最大无弦周期的大小,即Sl。自从取消了两个顶点ax和aJx不断开边射诱导子图H,我我圈S具有至少两个不同的可变子图的顶点。 我们声称,B(I)中由S通过取S的变式子图和子句子图的对应顶点而构造的导出子图具有圈RI。否则,这个子图是B(I)中的一棵树,且存在一个可变顶点xi,它有两个相邻的子句顶点cj和cj′,使得相应的顶点Hcj 和Hcj′ 在瑞典,通过移除两个顶点ax和aJx而断开,这又是一个矛盾。我我我们观察到圈RI的大小至多为2l,因为在最坏的情况下,每个S的边与两个不同的可变子图关联。在这种情况下,RI具有对应于HX可变子图的l个顶点和对应于Hc子句子图的l个顶点。这与事实相矛盾,根据定义,B(I)的围长大于2l,这结束了证明。QS. Dantas等人/理论计算机科学电子笔记346(2019)393399多共享顶点H的循环S图3.第三章。H的循环S的例子。注意两个子句子图可能共享的顶点我们通过考虑两个特殊的图H给出了下面的两个应用。用Kp表示p个顶点上的完全图,用3K2表示由一个有三条边的诱导匹配组成的图,称p轮为由p个顶点上的一个无弦圈和一个与该圈上所有p个顶点相邻的附加顶点u用E[3K2]表示3K2图的边集.推论3.3如果H是Kp\E [3 K2],当p≥ 6时,则无H图三明治问题是NP-完全的.证明:Kp\E[3K2]的任何两条非关联边都缺少的3K2是大小为3的反匹配。最后,Kp\E[3K2]是3-连通的。 因此,定理3.1和3.2可以应用。Q推论3.4如果H是p-轮,当p≥ 6时,则无H图三明治问题是NP-完全的。证明:一个p轮的p圈的任意两条非关联边是大小为2的匹配.任何诱导的p-圈,p≥6,包含大小为3的反匹配。最后,一个p-轮,p≥6,是3-连通的.因此,定理3.1和3.2可以应用。Q4结束语在目前的工作中,我们提供了一个新的变体SAT称为k-girthLCNF2-3-SAT,它产生的分类图三明治问题的H-无图类,使禁止图H是3-连通的,H包含一个反匹配(即H包含一个匹配)的大小为3和H包含一个匹配的大小为2。特别地,我们证明了,当H是Kp\E[3K2]或p轮时,对于p≥6,无H图三明治问题是NP完全问题。此外,委员会认为,我们的结果建立了一个有趣的二分法:对于任意固定p≥6,(Kp\e)-free图三明治问题在P[2]中,而(Kp\E[3K2])-free图三明治问题(来自推论3.3)和(Kp\E[2K2])无图三明治问题是NP完全的。 的NP完全性(Kp\E[2K2])-free图三明治问题是由C4-free图三明治问题的NP-完全性所隐含的[2].400S. Dantas等人/理论计算机科学电子笔记346(2019)393\6n用于证明这些结果的策略提供了一种工具,将由禁止诱导子图定义的几个图族的图三明治问题分类为NP-完全。例如,我们注意到K6E[3K2]是iso-同构于圈C2的幂,当H是圈Cp的幂时,当n≥6且p <[n/2]时,无H图三明治问题是NP-完全的.引用[1] F.库托湖Faria,S. Gravier,S.克莱恩关于禁止诱导子图探针和三明治问题。离散应用数学、234(2018)56[2] S.丹塔斯,C.M.H. de Figueiredo,M.V.G. da Silva,R.B.特谢拉关于禁止诱导子图三明治问题。离散应用数学、159(2011)1717[3] S.丹塔斯,C.M.H. de Figueiredo,F. Ma Bagray,R.B.特谢拉禁止子图三明治问题和斜剖分三明治问题的复杂性。离散应用数学、182(2015)15[4] M.C. Dourado,P. Petito,R. B. Teixeira,C.M.H.德·菲格雷多。Helly性质、团图、补图类与三明治问题。J. 布拉茨。Comput. 索科,14(2008)45[5] 厘米de Figueiredo,S.斯皮克尔排除路径的三明治和探针问题。离散应用数学,251(2018)146[6] M.C.戈隆比奇河沙米尔时间推理的复杂性和算法:图论方法。J. Assoc. Comp. 马赫,40(1993)1108[7] M.C. Golumbic,H.卡普兰河,巴西-地沙米尔DNA物理图谱的复杂性。高级应用数学,15(1994)251[8] M.C. Golumbic,H.卡普兰河,巴西-地沙米尔图三明治问题。J. Algorithms,19(1995)449[9] S. Porschen,E. Speckenmeyer,X.赵线性CNF公式和可满足性离散应用数学,157(2009)1046
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功