GraphClassesASurvey 張貿翔中正大學資訊工程學系 MeetingRoomReservation OnemeetingroomReservation Gary10 00 11 00Mary10 30 12 00Jones13 30 14 30Amy14 00 15 30David11 00 12 30Tom12 00 14 30Tosatisfyasmanyaspossible Theconflictgraph ThemaximumIndependentSetProbleminGraphs Anindependentset Anotherindependentset Amaximumindependentset Themeetingroomreservationproblemisreducedtothemaximumindependentsetproblemingraphs ThemaximumindependentsetproblemingeneralgraphsisNP hard MostofoptimizationproblemsingraphsareNP hard Itturnsoutthattheconflictgraphofameetingroomreservationproblemisanintervalgraph ThemaximumindependentsetproblemcanbesolvedinO n timeinintervalgraphsifendverticesaresorted GraphClasses Agraphiscalleda graphifitsatisfiesproperty Forexample agraphhavingnoinducedcycleoflengthgreaterthan3iscalledachordalgraph 4 Achordofcycle5 7 8 6 4 5 Intervalgraphs 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 CircleGraphs 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 PlanarGraphs K5andK3 3arenotplanargraphs Toomanygraphclasses Therearealmost200graphclassesdescribedinthebook GraphClasses ASurvey byBrandst dt Le andSpinrad publishedin1999 D S Johnsonremarkedthat manygraphtheoristshavemadecareersoutofinventingandcharacterizingnewclassesofgraphs therearebynowfartoomanyclassesforasinglecolumntosurvey in TheNP completenesscolumn anongoingguide J Algorithm 6 1985 Distance Hereditary SomeGraphClasses TheIntervalgraphRecognitionProblem GivenagraphG testwhetherthereexistsanintervalmodel 官兵捉強盜 TheGraphSearchingProblem Thegraphsearchingproblemisagraph theoreticalgameplayedonanundirectedgraphconsideredasasystemoftunnelsinwhichallthetunnelsareinitiallycontaminatedbyagas Therearethreekindsofmovesinedgesearching 1 placingasearcheronavertex 2 removingasearcherfromavertex and 3 clearanedgebyeither 3 1 movingasearcherfromonevertextoanotheralonganedgeor 3 2 placingtwosearchersonthetwoendpointsoftheedge Aclearededgemayberecontaminatedoncethereisapathwithoutanysearchersconnectingtheedgewithacontaminatedone Thegoalofthisgameistodiscoverasequenceofmoves calledstrategy clearthegraphwiththeleastnumberofsearchers TheGraphSearchingProblem Cont Thegraphsearchingproblemispolynomial timesolvableonintervalgraphsandsplitgraphs etc LongestIncreasingSubsequences Input asequence 12 3 10 9 8 13 14 1 11 Output alongestsubsequenceSubsequences 3 10 9or10 13 14etc Increasingsubsequences 3 8 11or12 13 14 or3 10 13 14Longestincreasingsubsequence 3 10 13 14or3 9 13 14etc 12 3 10 9 8 13 14 1 11 1 12 2 3 3 10 4 9 5 8 6 13 7 14 8 1 9 11 1 2 3 4 5 6 7 8 9 1 3 8 9 10 11 12 13 14 Thelongestincreasingsubsequencecanbereducedtothemaximumindependentsetprobleminpermutationgraphs ApermutationgraphG AmatchingdiagramofG AnApproachtoDesigningGraphAlgorithms MostofproblemsingraphsareNP hard Manyproblemsingraphsbecomepolynomial timesolvableifthegraphsconsideredsatisfysomeniceproperty Forexample themaximumindependentsetproblemisNP hardingeneralgraphsbutpolynomial timesolvableinchordalgraphs intervalgraphs andpermutationgraphs etc Chromosome Cutrelativelysmall randompiecesofthechromosome Runchemicalexperimentsonthesmallpiecestogetaccurateinformationaboutthese Thisallowsresearcherstogetinformationaboutfragmentsandfrequenciesoftypesoffragments butlossinformationabouthowthefragmentsareorderedonthechromosome Eachfragmentshouldformanintervalonthechromosome itisnaturaltomodelthisproblemasanintervalgraphproblemwithfragmentscorrespondingtovertices Forthismodeltobeuseful theremustbeawaytodeterminewhichfragmentsshouldoverlapinthechromosome correspondingtowhichverticesshouldbeadjacentintheintervalmodel Suchtestshavebeendeveloped whichmakesitseemsimpletouseintervalgraphtechniquestosolvethegenereconstructionproblem Thetestsmayproduceerrors Errorscomeintwoforms Falsepositive Thetestssaythatfragmentsoverlapwhentheydonot Falsenegative Thetestssaythatfragmentsdonotoverlapwhentheyreallydo Dependingonwhichtestisusedandwhatthresholdsareset falsepositivesmaybemuchmorecommonthatfalsenegatives muchlesscommon orbothmayoccurwithrelativelyequalprobability Ifweassumethatallerrorsarefalsenegatives wewanttoknowtheminimumnumberofedgeswecanaddtomakethegraphintervalgraph Thisproblemiscalledtheintervalgraphcompletionproblem Ifweassumeallerrorsarefalsepositives wewanttoknowtheminimumnumberofoverlapswecandeletefromthetestresultstogetanintervalgraph thisiscalledthemaximumintervalsubgraphproblem Iferrorscanbefalsepositivesorfalsenegatives wewanttominimizethenumberofedgedeletionsandadditionssothattheresultisanintervalgraph thisiscalledtheintervalgraphmodificationproblem Assumethattherearenoerrorsinthetests Ifwehavenfragments andwewanttoreconstructtheentireintervalgraph themethoddescribedcallsfor n2 chemicalteststodeterminewhetherfragmentsoverlap Asubsetofthefragmentsareselectedtobe probes andtheremainingfragmentsarecallednonprobes Insteadoftestingoverlaprelationshipsbetweenpairsoffragments testsareonlymadebetweenaprobeandanotherfragment Theoverlapgraphoffragmentsobtainedinthiswaycanbemadeintoanintervalgraphbyaddingedgesbetweensomenonprobes ThePartitionedProbeG