文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

NP-CompletenessofSomeTree-ClusteringProblems291

3MainResults

InthissectionwedealwiththeproblemswhetherornotagraphGisatreeofpaths(ToPproblem)andwhetherornotGisatreeofcycles(ToCproblem).Theproblemsareformallyde nedasfollows:

Name:ToPproblem.

Instance:AgraphG.

Question:IsGatreeofpaths?andName:ToCproblem.Instance:AgraphG.Question:IsGatreeofcycles?

Ifthelengthofthepaths,respectivelythelengthofthecyclesisboundedbysomeintegerk,thenwecalltheseproblemsk-ToP,respectivelyk-ToC.

ForourpurposeweneedavariantoftheONE-IN-THREE3SATproblem(see[9],L04)inwhichtheinstancesmeetthefollowingrequirements:(i)noclausecontainsoppositeliterals,and(ii)ifavariablexappearsmorethanonce,anyofitsliteralsxandxappearsinatleasttwoclauses.Wecallthisrestrictedvariantther-ONE-IN-THREE3SATproblem.

Proposition1.Ther-ONE-IN-THREE3SATproblemisNP-complete.

Proof.Theproofisasimplereductionfromthe”positive”ONE-IN-THREE3SATproblem,whichisalsoNP-complete,see[9].Inthisproblemtheinstancesarerestrictedtocontainonlyclauseswithpositiveliterals.Letφbesuchaninstance.Foreveryvariablexappearingmorethanonceinφweaddtheclauses(x∨ax1∨ax2),(x∨ax3∨ax4),(x∨ax5∨ax6),and(x∨ax7∨ax8)toφ,whereax1,...,ax8arenewvariables.Byconstructiontheobtainedexpressionφ meetsthedesiredrequirements.Moreoveritiseasytoshowthatφissatis ableifandonlyifφ issatis able(inthesenseofONE-IN-THREE3SAT).

3.1TreeofPaths

Inthissubsectionwe rstshowthattheToPproblemisNP-complete.Thenwegiveapolynomialalgorithmsolvingthek-ToPproblem.Thealgorithmcanbemodi edeasilytooutputatreeclusteringTkifitexists. showninFigure2.C ThekeytoprovetheNP-completenessisthegadgetChasanimportantpropertywhichissummarizedbythenextlemma.

thegraphLemma1.LetGbeatreeofpaths,TatreeclusteringofG,andC isaninducedsubgraphofGthentheverticesofC belongshowninFigure2.IfCtoexactlytwodi erentpathsP1andP2ofT,suchthatP1containstwovertices

ofx,y,zandP2containstheverticesl,randtheremainingvertexofx,y,z.Proof.Aneasyinspectionshowsthattheverticesx,y,andzmayneitherbelongtothesamepathnortothreedi erentpathsofT.Thusx,y,andzbelongtoexactlytwodi erentpathsP1andP2ofT.WithoutlossofgeneralityweassumethatP1containsxandyandpathP2containsz,seeFigure2(a).

Nowconsidervertexl.LetP3bethepathofTcontainingl.Obviously,P3isdi erenttoP1.IfP3isalsodi erenttoP2,thenthepathsP1,P2,andP3would

上一页第4页

热门文档

相关文档

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