文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547
侵权投诉

Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547

Abstract A graph is a tree of paths (cycles), if its vertex set can be partitioned into clusters, such that each cluster induces a simple path (cycle), and the clusters form a tree. Our main result states that the problem whether or not a given graph is a

292FalkSchreiberandKonstantinos

Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547

Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547

Skodinis NP-Completeness of some tree-clustering problems. Graph Drawing `98, LNCS 1547

Skodinis

:C

(a)(b)(c) anditsdi erentpathclusteringsFigure2.GraphC

notformatreebecausetheyarepairwiseconnectedbyedgesfromG.Hence,P3andP2areidenticalinTandlbelongstoP2.Forsymmetrythesameholdsforvertexr.

Theorem1.TheToPproblemisNP-complete.

Proof.ObviouslytheToPproblemisinNP.WeshowthatitisNP-hard.Theproofisareductionfromther-ONE-IN-THREE3SATproblem.LetφbeaninstancewithnclausesC1,...,Cn.WeconstructagraphG(φ)andweshowthatφissatis ableifandonlyifG(φ)isatreeofpaths. ofFigure2.WecreatencopiesThekeytoourconstructionisthegraphC nofC sidebyside,oneforeveryclauseCi.Forconveniencewewill 1,...,CC ibyxi,yi,zi,li,ri,respectively.Ver-denotethecopiesofverticesx,y,z,l,rinCticesxi,yiandzicorrespondtotheliteralsoftheclauseCi.Wecreateanewvertexbandconnectitwithallverticesliandri.Thenweaddanedgebetweenverticesriandli+1,1≤i≤n 1.Finally,weaddanedgebetweentwover-ticesindi erentcopiesifandonlyiftheverticescorrespondtooppositeliterals.Figure3illustratestheconstruction.

Weclaimthatφissatis ableifandonlyifG(φ)isatreeofpaths.Inproof,supposethatthereisatruthassignmentsatisfyingφ.Thus,everyclausehas itheverticescorrespondingtotwofalseandonetrueliteral.IneverycopyCthefalseliteralsareapathinG(φ),denotedbyPi.TheverticesliandriandtheverticescorrespondingtothetrueliteralsintheclausesarealsoapathinG(φ),denotedbyP.Finally,thevertexbisatriviallysinglepathdenotedbyP .ByconstructionP isconnectedwithPwhichitselfisconnectedwitheveryPi.Sincethereisnoconnectionbetweentwodi erentpathsPiandPj(twofalseliteralscanneverbeoppositeandthusneverbeadjacent),P1,...,Pn,P,andP formatreeclusteringofG(φ).

Conversely,supposethatG(φ)isatreeofpathswhithatreeclusteringT.Ouraimistode neatruthassignmentforφ.First,takeacloserlookatthestructureofG(φ)toexploresomeimportantinformationaboutitsclusteringT.

上一页第5页

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email