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
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...
20页 免费 Skodinis NP-Completeness... 暂无评价 14页 免费搜你所想,读你... Practical Parallel Algorithms for Some Tree and Graph Problems byby隐藏>> ...
Skodinis NP-Completeness... 暂无评价 14页 免费...更多>>Graph clustering is the problem of ...We prove that the decision problems associated ...
Skodinis NP-Completene... 暂无评价 14页 免费 ...On #P-completeness of Some Counting Problems ... let x 2 be an encoding of the graph G = ...
Skodinis NP-Completeness... 暂无评价 14页 免费...更多>>Graph clustering is the problem of ...We prove that the decision problems associated ...
热门文档