Table Of Content

Probabilistic Combinatorial Optimization on Graphs This page intentionally left blank Probabilistic Combinatorial Optimization on Graphs Cécile Murat and Vangelis Th. Paschos First published in Great Britain and the United States in 2006 by ISTE Ltd Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd ISTE USA 6 Fitzroy Square 4308 Patrice Road London W1T 5DX Newport Beach, CA 92663 UK USA www.iste.co.uk © ISTE Ltd, 2006 The rights of Cécile Murat and Vangelis Th. Paschos to be identified as the authors of this work has been asserted by them in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Cataloging-in-Publication Data Murat, Cecile. Probabilistic combinatorial optimization on graphs / Cécile Murat and Vangelis Th. Paschos. p. cm. Includes bibliographical references and index. ISBN-13: 978-1-905209-33-0 ISBN-10: 1-905209-33-9 1. Combinatorial probabilities. 2. Combinatorial optimization. 3. Random graphs. I. Paschos, Vangelis Th. II. Title. QA273.45.M87 2006 519.2--dc22 2006000868 British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library ISBN 10: 1-905209-33-9 ISBN 13: 978-1-905209-33-0 Printed and bound in Great Britain by Antony Rowe Ltd, Chippenham, Wiltshire. Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Chapter1.AShortInsightintoProbabilisticCombinatorialOptimization 15 1.1. Motivationsandapplications . . . . . . . . . . . . . . . . . . . . . . . 15 1.2. Aformalismforprobabilisticcombinatorialoptimization . . . . . . 19 1.3. The main methodological issues dealing with probabilistic combi- natorialoptimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.1. Complexityissues . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.1.1. MembershipinNPOisnotalwaysobvious . . . . 24 1.3.1.2. Complexityofdeterministicvs.complexityofpro- babilisticoptimizationproblems . . . . . . . . . . . 24 1.3.2. Solutionissues . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.3.2.1. Characterizationofoptimalapriorisolutions . . . 26 1.3.2.2. Polynomialsubcases . . . . . . . . . . . . . . . . . 28 1.3.2.3. Exactsolutionsandpolynomialapproximation issues . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4. Miscellaneousandbibliographicnotes . . . . . . . . . . . . . . . . . 31 FIRSTPART.PROBABILISTICGRAPH-PROBLEMS . . . . . . . . . . . . . . 35 Chapter2.TheProbabilisticMaximumIndependentSet . . . . . . . . . . 37 2.1. Themodificationstrategiesandapreliminaryresult . . . . . . . . . . 39 2.1.1. StrategyM1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.2. StrategiesM2andM3 . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.3. StrategyM4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.4. StrategyM5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.5. Ageneralmathematicalformulationforthefivefunctionals 42 2.2. PROBABILISTICMAXINDEPENDENTSET1 . . . . . . . . . . . . . . 44 6 ProbabilisticCombinatorialOptimization 2.2.1. Computingoptimalapriorisolutions . . . . . . . . . . . . . 44 2.2.2. Approximatingoptimalsolutions. . . . . . . . . . . . . . . . 45 2.2.3. Dealingwithbipartitegraphs . . . . . . . . . . . . . . . . . . 46 2.3. PROBABILISTICMAXINDEPENDENTSET2and3 . . . . . . . . . . . 47 2.3.1. ExpressionsforE(G,S,M2)andE(G,S,M3) . . . . . . . 47 2.3.2. AnupperboundforthecomplexityofE(G,S,M2) . . . . . 48 2.3.3. BoundsforE(G,S,M2) . . . . . . . . . . . . . . . . . . . . 49 2.3.4. Approximatingoptimalsolutions. . . . . . . . . . . . . . . . 51 2.3.4.1. Usingargmax{ vi∈Spi}asanapriorisolution 51 2.3.4.2. UsingapproximationsofMAXINDEPENDENTSET 53 P 2.3.5. Dealingwithbipartitegraphs . . . . . . . . . . . . . . . . . . 53 2.4. PROBABILISTICMAXINDEPENDENTSET4 . . . . . . . . . . . . . . 55 2.4.1. AnexpressionforE(G,S,M4) . . . . . . . . . . . . . . . . 55 2.4.2. UsingS∗orargmax{ vi∈Spi}asanapriorisolution . 56 2.4.3. Dealingwithbipartitegraphs . . . . . . . . . . . . . . . . . . 57 P 2.5. PROBABILISTICMAXINDEPENDENTSET5 . . . . . . . . . . . . . . 58 2.5.1. Ingeneralgraphs . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.5.2. Inbipartitegraphs . . . . . . . . . . . . . . . . . . . . . . . . 60 2.6. Summaryoftheresults . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.7. Methodologicalquestions . . . . . . . . . . . . . . . . . . . . . . . . 63 2.7.1. Maximizingacriterionassociatedwithgain . . . . . . . . . 65 2.7.1.1. Theminimumgaincriterion . . . . . . . . . . . . . 65 2.7.1.2. Themaximumgaincriterion . . . . . . . . . . . . 66 2.7.2. Minimizingacriterionassociatedwithregret . . . . . . . . . 68 2.7.2.1. Themaximumregretcriterion. . . . . . . . . . . . 68 2.7.3. Optimizingexpectation . . . . . . . . . . . . . . . . . . . . . 70 2.8. Proofsoftheresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.8.1. ProofofProposition2.1 . . . . . . . . . . . . . . . . . . . . . 71 2.8.2. ProofofTheorem2.6 . . . . . . . . . . . . . . . . . . . . . . 74 2.8.3. ProofofProposition2.3 . . . . . . . . . . . . . . . . . . . . . 77 2.8.4. ProofofTheorem2.13 . . . . . . . . . . . . . . . . . . . . . 78 Chapter3.TheProbabilisticMinimumVertexCover . . . . . . . . . . . . . 81 3.1. ThestrategiesM1,M2andM3andageneralpreliminaryresult . . . . 82 3.1.1. SpecificationofM1,M2andM3 . . . . . . . . . . . . . . . . . 82 3.1.1.1. StrategyM1 . . . . . . . . . . . . . . . . . . . . . . 82 3.1.1.2. StrategyM2 . . . . . . . . . . . . . . . . . . . . . . 83 3.1.1.3. StrategyM3 . . . . . . . . . . . . . . . . . . . . . . 83 3.1.2. Afirstexpressionforthefunctionals . . . . . . . . . . . . . . 84 3.2. PROBABILISTICMINVERTEXCOVER1. . . . . . . . . . . . . . . . . 84 3.3. PROBABILISTICMINVERTEXCOVER2. . . . . . . . . . . . . . . . . 86 3.4. PROBABILISTICMINVERTEXCOVER3. . . . . . . . . . . . . . . . . 87 3.4.1. BuildingE(G,C,M3) . . . . . . . . . . . . . . . . . . . . . 87 Contents 7 3.4.2. BoundsforE(G,C,M3) . . . . . . . . . . . . . . . . . . . . 88 3.5. Somemethodologicalquestions . . . . . . . . . . . . . . . . . . . . . 89 3.6. Proofsoftheresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.6.1. ProofofTheorem3.3 . . . . . . . . . . . . . . . . . . . . . . 91 3.6.2. OnthetheboundsobtainedinTheorem3.3 . . . . . . . . . . 93 Chapter4.TheProbabilisticLongestPath . . . . . . . . . . . . . . . . . . . 99 4.1. Probabilisticlongestpathintermsofvertices . . . . . . . . . . . . . 100 4.2. Probabilisticlongestpathintermsofarcs . . . . . . . . . . . . . . . 102 4.2.1. Aninterestingalgebraicexpression . . . . . . . . . . . . . . 104 4.2.2. MetricPROBABILISTICARCWEIGHTEDLONGESTPATH . . 105 4.3. Whythestrategiesusedarepertinent . . . . . . . . . . . . . . . . . . 109 4.4. Proofsoftheresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.4.1. ProofofTheorem4.1 . . . . . . . . . . . . . . . . . . . . . . 110 4.4.2. ProofofTheorem4.2 . . . . . . . . . . . . . . . . . . . . . . 112 4.4.3. AnalgebraicproofforTheorem4.3 . . . . . . . . . . . . . . 114 4.4.4. ProofofLemma4.1 . . . . . . . . . . . . . . . . . . . . . . . 116 4.4.5. ProofofLemma4.2 . . . . . . . . . . . . . . . . . . . . . . . 117 4.4.6. ProofofTheorem4.4 . . . . . . . . . . . . . . . . . . . . . . 117 Chapter5.ProbabilisticMinimumColoring . . . . . . . . . . . . . . . . . . 125 5.1. ThefunctionalE(G,C) . . . . . . . . . . . . . . . . . . . . . . . . . 127 5.2. Basicpropertiesofprobabilisticcoloring . . . . . . . . . . . . . . . . 131 5.2.1. Propertiesundernon-identicalvertex-probabilities . . . . . . 131 5.2.2. Propertiesunderidenticalvertex-probabilities . . . . . . . . 131 5.3. PROBABILISTICMINCOLORINGingeneralgraphs . . . . . . . . . . 132 5.3.1. Thecomplexityofprobabilisticcoloring . . . . . . . . . . . 132 5.3.2. Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.3.2.1. Themainresult . . . . . . . . . . . . . . . . . . . . 132 5.3.2.2. Furtherapproximationresults . . . . . . . . . . . . 137 5.4. PROBABILISTICMINCOLORINGinbipartitegraphs . . . . . . . . . 139 5.4.1. Abasicproperty . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.4.2. Generalbipartitegraphs . . . . . . . . . . . . . . . . . . . . . 141 5.4.3. Bipartitecomplementsofbipartitematchings . . . . . . . . . 147 5.4.4. Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 5.4.5. Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 5.5. Complementsofbipartitegraphs . . . . . . . . . . . . . . . . . . . . 155 5.6. Splitgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 5.6.1. ThecomplexityofPROBABILISTICMINCOLORING . . . . . 156 5.6.2. Approximationresults . . . . . . . . . . . . . . . . . . . . . . 159 5.7. Determiningthebestk-coloringink-colorablegraphs . . . . . . . . 164 5.7.1. Bipartitegraphs . . . . . . . . . . . . . . . . . . . . . . . . . 164 5.7.1.1. PROBABILISTICMIN3-COLORING. . . . . . . . . 164 8 ProbabilisticCombinatorialOptimization 5.7.1.2. PROBABILISTICMINk-COLORINGfork > 3 . . 168 5.7.1.3. Bipartitecomplementsofbipartitematchings . . . 171 5.7.2. Thecomplementsofbipartitegraphs . . . . . . . . . . . . . 171 5.7.3. Approximationinparticularclassesofgraphs . . . . . . . . 174 5.8. Commentsandopenproblems . . . . . . . . . . . . . . . . . . . . . . 175 5.9. Proofsofthedifferentresults. . . . . . . . . . . . . . . . . . . . . . . 178 5.9.1. Proofof[5.5] . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 5.9.2. Proofof[5.4] . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 5.9.3. ProofofProperty5.1 . . . . . . . . . . . . . . . . . . . . . . 180 5.9.4. ProofofProposition5.2 . . . . . . . . . . . . . . . . . . . . . 181 5.9.5. ProofofLemma5.11 . . . . . . . . . . . . . . . . . . . . . . 183 SECONDPART.STRUCTURALRESULTS . . . . . . . . . . . . . . . . . . . . 185 Chapter6.ClassificationofProbabilisticGraph-problems . . . . . . . . . . 187 6.1. WhenMSisfeasible . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6.1.1. Theapriorisolutionisasubsetoftheinitialvertex-set . . . 188 6.1.2. Theapriorisolutionisacollectionofsubsetsoftheinitial vertex-set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 6.1.3. Theapriorisolutionisasubsetoftheinitialedge-set . . . . 193 6.2. WhenapplicationofMSitselfdoesnotleadtofeasiblesolutions . . . 198 6.2.1. ThefunctionalassociatedwithMSC . . . . . . . . . . . . . . 198 6.2.2. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 6.2.2.1. Theapriorisolutionisacycle . . . . . . . . . . . 200 6.2.2.2. Theapriorisolutionisatree . . . . . . . . . . . . 201 6.3. Somecomments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 6.4. ProofofTheorem6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 Chapter7.ACompendiumofProbabilisticNPOProblemsonGraphs . . 211 7.1. Coveringandpartitioning. . . . . . . . . . . . . . . . . . . . . . . . . 214 7.1.1. MINVERTEXCOVER . . . . . . . . . . . . . . . . . . . . . . 214 7.1.2. MINCOLORING . . . . . . . . . . . . . . . . . . . . . . . . . 214 7.1.3. MAXACHROMATICNUMBER . . . . . . . . . . . . . . . . . 215 7.1.4. MINDOMINATINGSET . . . . . . . . . . . . . . . . . . . . . 215 7.1.5. MAXDOMATICPARTITION . . . . . . . . . . . . . . . . . . . 216 7.1.6. MINEDGE-DOMINATINGSET . . . . . . . . . . . . . . . . . 216 7.1.7. MININDEPENDENTDOMINATINGSET . . . . . . . . . . . . 217 7.1.8. MINCHROMATICSUM . . . . . . . . . . . . . . . . . . . . . 217 7.1.9. MINEDGECOLORING . . . . . . . . . . . . . . . . . . . . . . 218 7.1.10. MINFEEDBACKVERTEX-SET . . . . . . . . . . . . . . . . . 219 7.1.11. MINFEEDBACKARC-SET. . . . . . . . . . . . . . . . . . . . 220 7.1.12. MAXMATCHING . . . . . . . . . . . . . . . . . . . . . . . . . 220 7.1.13. MINMAXIMALMATCHING . . . . . . . . . . . . . . . . . . . 220 Contents 9 7.1.14. MAXTRIANGLEPACKING . . . . . . . . . . . . . . . . . . . 220 7.1.15. MAXH-MATCHING . . . . . . . . . . . . . . . . . . . . . . . 221 7.1.16. MINPARTITIONINTOCLIQUES . . . . . . . . . . . . . . . . 222 7.1.17. MINCLIQUECOVER . . . . . . . . . . . . . . . . . . . . . . . 222 7.1.18. MINk-CAPACITEDTREEPARTITION . . . . . . . . . . . . . 222 7.1.19. MAXBALANCEDCONNECTEDPARTITION . . . . . . . . . . 223 7.1.20. MINCOMPLETEBIPARTITESUBGRAPHCOVER . . . . . . . 223 7.1.21. MINVERTEX-DISJOINTCYCLECOVER . . . . . . . . . . . . 223 7.1.22. MINCUTCOVER . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.2. Subgraphsandsupergraphs. . . . . . . . . . . . . . . . . . . . . . . . 224 7.2.1. MAXINDEPENDENTSET . . . . . . . . . . . . . . . . . . . . 224 7.2.2. MAXCLIQUE . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.2.3. MAXINDEPENDENTSEQUENCE . . . . . . . . . . . . . . . . 225 7.2.4. MAXINDUCEDSUBGRAPHWITHPROPERTYπ . . . . . . . 225 7.2.5. MINVERTEXDELETIONTOOBTAINSUBGRAPHWITH PROPERTYπ . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 7.2.6. MINEDGEDELETIONTOOBTAINSUBGRAPHWITH PROPERTYπ . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 7.2.7. MAXCONNECTEDSUBGRAPHWITHPROPERTYπ . . . . . 226 7.2.8. MINVERTEXDELETIONTOOBTAINCONNECTED SUBGRAPHWITHPROPERTYπ. . . . . . . . . . . . . . . . . 226 7.2.9. MAXDEGREE-BOUNDEDCONNECTEDSUBGRAPH . . . . . 226 7.2.10. MAXPLANARSUBGRAPH . . . . . . . . . . . . . . . . . . . 227 7.2.11. MINEDGEDELETIONk-PARTITION. . . . . . . . . . . . . . 227 7.2.12. MAXk-COLORABLESUBGRAPH . . . . . . . . . . . . . . . 227 7.2.13. MAXSUBFOREST . . . . . . . . . . . . . . . . . . . . . . . . 228 7.2.14. MAXEDGESUBGRAPHorDENSEk-SUBGRAPH . . . . . . 228 7.2.15. MINEDGEK-SPANNER . . . . . . . . . . . . . . . . . . . . . 228 7.2.16. MAXk-COLORABLEINDUCEDSUBGRAPH . . . . . . . . . 229 7.2.17. MINEQUIVALENTDIGRAPH . . . . . . . . . . . . . . . . . . 229 7.2.18. MINCHORDALGRAPHCOMPLETION . . . . . . . . . . . . . 229 7.3. Iso-andothermorphisms . . . . . . . . . . . . . . . . . . . . . . . . . 229 7.3.1. MAXCOMMONSUBGRAPH . . . . . . . . . . . . . . . . . . . 229 7.3.2. MAXCOMMONINDUCEDSUBGRAPH. . . . . . . . . . . . . 230 7.3.3. MAXCOMMONEMBEDDEDSUBTREE . . . . . . . . . . . . 230 7.3.4. MINGRAPHTRANSFORMATION . . . . . . . . . . . . . . . . 230 7.4. Cutsandconnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.4.1. MAXCUT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.4.2. MAXDIRECTEDCUT . . . . . . . . . . . . . . . . . . . . . . 231 7.4.3. MINCROSSINGNUMBER . . . . . . . . . . . . . . . . . . . . 231 7.4.4. MAXk-CUT . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 7.4.5. MINk-CUT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 7.4.6. MINNETWORKINHIBITIONONPLANARGRAPHS . . . . . 233

ebook img

Probabilistic combinatorial optimization on graphs PDF

268 Pages·2006·1.491 MB·English
by  Cécile Murat, Vangelis Th. Paschos
#Mathematics #Graph Theory
Save to my drive
Quick download
Download
Upgrade Premium
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.

Preview Probabilistic combinatorial optimization on graphs

Probabilistic Combinatorial Optimization on Graphs This page intentionally left blank Probabilistic Combinatorial Optimization on Graphs Cécile Murat and Vangelis Th. Paschos First published in Great Britain and the United States in 2006 by ISTE Ltd Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address: ISTE Ltd ISTE USA 6 Fitzroy Square 4308 Patrice Road London W1T 5DX Newport Beach, CA 92663 UK USA www.iste.co.uk © ISTE Ltd, 2006 The rights of Cécile Murat and Vangelis Th. Paschos to be identified as the authors of this work has been asserted by them in accordance with the Copyright, Designs and Patents Act 1988. Library of Congress Cataloging-in-Publication Data Murat, Cecile. Probabilistic combinatorial optimization on graphs / Cécile Murat and Vangelis Th. Paschos. p. cm. Includes bibliographical references and index. ISBN-13: 978-1-905209-33-0 ISBN-10: 1-905209-33-9 1. Combinatorial probabilities. 2. Combinatorial optimization. 3. Random graphs. I. Paschos, Vangelis Th. II. Title. QA273.45.M87 2006 519.2--dc22 2006000868 British Library Cataloguing-in-Publication Data A CIP record for this book is available from the British Library ISBN 10: 1-905209-33-9 ISBN 13: 978-1-905209-33-0 Printed and bound in Great Britain by Antony Rowe Ltd, Chippenham, Wiltshire. Contents Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Chapter1.AShortInsightintoProbabilisticCombinatorialOptimization 15 1.1. Motivationsandapplications . . . . . . . . . . . . . . . . . . . . . . . 15 1.2. Aformalismforprobabilisticcombinatorialoptimization . . . . . . 19 1.3. The main methodological issues dealing with probabilistic combi- natorialoptimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.1. Complexityissues . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.1.1. MembershipinNPOisnotalwaysobvious . . . . 24 1.3.1.2. Complexityofdeterministicvs.complexityofpro- babilisticoptimizationproblems . . . . . . . . . . . 24 1.3.2. Solutionissues . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.3.2.1. Characterizationofoptimalapriorisolutions . . . 26 1.3.2.2. Polynomialsubcases . . . . . . . . . . . . . . . . . 28 1.3.2.3. Exactsolutionsandpolynomialapproximation issues . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4. Miscellaneousandbibliographicnotes . . . . . . . . . . . . . . . . . 31 FIRSTPART.PROBABILISTICGRAPH-PROBLEMS . . . . . . . . . . . . . . 35 Chapter2.TheProbabilisticMaximumIndependentSet . . . . . . . . . . 37 2.1. Themodificationstrategiesandapreliminaryresult . . . . . . . . . . 39 2.1.1. StrategyM1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.2. StrategiesM2andM3 . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.3. StrategyM4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.4. StrategyM5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.5. Ageneralmathematicalformulationforthefivefunctionals 42 2.2. PROBABILISTICMAXINDEPENDENTSET1 . . . . . . . . . . . . . . 44 6 ProbabilisticCombinatorialOptimization 2.2.1. Computingoptimalapriorisolutions . . . . . . . . . . . . . 44 2.2.2. Approximatingoptimalsolutions. . . . . . . . . . . . . . . . 45 2.2.3. Dealingwithbipartitegraphs . . . . . . . . . . . . . . . . . . 46 2.3. PROBABILISTICMAXINDEPENDENTSET2and3 . . . . . . . . . . . 47 2.3.1. ExpressionsforE(G,S,M2)andE(G,S,M3) . . . . . . . 47 2.3.2. AnupperboundforthecomplexityofE(G,S,M2) . . . . . 48 2.3.3. BoundsforE(G,S,M2) . . . . . . . . . . . . . . . . . . . . 49 2.3.4. Approximatingoptimalsolutions. . . . . . . . . . . . . . . . 51 2.3.4.1. Usingargmax{ vi∈Spi}asanapriorisolution 51 2.3.4.2. UsingapproximationsofMAXINDEPENDENTSET 53 P 2.3.5. Dealingwithbipartitegraphs . . . . . . . . . . . . . . . . . . 53 2.4. PROBABILISTICMAXINDEPENDENTSET4 . . . . . . . . . . . . . . 55 2.4.1. AnexpressionforE(G,S,M4) . . . . . . . . . . . . . . . . 55 2.4.2. UsingS∗orargmax{ vi∈Spi}asanapriorisolution . 56 2.4.3. Dealingwithbipartitegraphs . . . . . . . . . . . . . . . . . . 57 P 2.5. PROBABILISTICMAXINDEPENDENTSET5 . . . . . . . . . . . . . . 58 2.5.1. Ingeneralgraphs . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.5.2. Inbipartitegraphs . . . . . . . . . . . . . . . . . . . . . . . . 60 2.6. Summaryoftheresults . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.7. Methodologicalquestions . . . . . . . . . . . . . . . . . . . . . . . . 63 2.7.1. Maximizingacriterionassociatedwithgain . . . . . . . . . 65 2.7.1.1. Theminimumgaincriterion . . . . . . . . . . . . . 65 2.7.1.2. Themaximumgaincriterion . . . . . . . . . . . . 66 2.7.2. Minimizingacriterionassociatedwithregret . . . . . . . . . 68 2.7.2.1. Themaximumregretcriterion. . . . . . . . . . . . 68 2.7.3. Optimizingexpectation . . . . . . . . . . . . . . . . . . . . . 70 2.8. Proofsoftheresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 2.8.1. ProofofProposition2.1 . . . . . . . . . . . . . . . . . . . . . 71 2.8.2. ProofofTheorem2.6 . . . . . . . . . . . . . . . . . . . . . . 74 2.8.3. ProofofProposition2.3 . . . . . . . . . . . . . . . . . . . . . 77 2.8.4. ProofofTheorem2.13 . . . . . . . . . . . . . . . . . . . . . 78 Chapter3.TheProbabilisticMinimumVertexCover . . . . . . . . . . . . . 81 3.1. ThestrategiesM1,M2andM3andageneralpreliminaryresult . . . . 82 3.1.1. SpecificationofM1,M2andM3 . . . . . . . . . . . . . . . . . 82 3.1.1.1. StrategyM1 . . . . . . . . . . . . . . . . . . . . . . 82 3.1.1.2. StrategyM2 . . . . . . . . . . . . . . . . . . . . . . 83 3.1.1.3. StrategyM3 . . . . . . . . . . . . . . . . . . . . . . 83 3.1.2. Afirstexpressionforthefunctionals . . . . . . . . . . . . . . 84 3.2. PROBABILISTICMINVERTEXCOVER1. . . . . . . . . . . . . . . . . 84 3.3. PROBABILISTICMINVERTEXCOVER2. . . . . . . . . . . . . . . . . 86 3.4. PROBABILISTICMINVERTEXCOVER3. . . . . . . . . . . . . . . . . 87 3.4.1. BuildingE(G,C,M3) . . . . . . . . . . . . . . . . . . . . . 87 Contents 7 3.4.2. BoundsforE(G,C,M3) . . . . . . . . . . . . . . . . . . . . 88 3.5. Somemethodologicalquestions . . . . . . . . . . . . . . . . . . . . . 89 3.6. Proofsoftheresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.6.1. ProofofTheorem3.3 . . . . . . . . . . . . . . . . . . . . . . 91 3.6.2. OnthetheboundsobtainedinTheorem3.3 . . . . . . . . . . 93 Chapter4.TheProbabilisticLongestPath . . . . . . . . . . . . . . . . . . . 99 4.1. Probabilisticlongestpathintermsofvertices . . . . . . . . . . . . . 100 4.2. Probabilisticlongestpathintermsofarcs . . . . . . . . . . . . . . . 102 4.2.1. Aninterestingalgebraicexpression . . . . . . . . . . . . . . 104 4.2.2. MetricPROBABILISTICARCWEIGHTEDLONGESTPATH . . 105 4.3. Whythestrategiesusedarepertinent . . . . . . . . . . . . . . . . . . 109 4.4. Proofsoftheresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.4.1. ProofofTheorem4.1 . . . . . . . . . . . . . . . . . . . . . . 110 4.4.2. ProofofTheorem4.2 . . . . . . . . . . . . . . . . . . . . . . 112 4.4.3. AnalgebraicproofforTheorem4.3 . . . . . . . . . . . . . . 114 4.4.4. ProofofLemma4.1 . . . . . . . . . . . . . . . . . . . . . . . 116 4.4.5. ProofofLemma4.2 . . . . . . . . . . . . . . . . . . . . . . . 117 4.4.6. ProofofTheorem4.4 . . . . . . . . . . . . . . . . . . . . . . 117 Chapter5.ProbabilisticMinimumColoring . . . . . . . . . . . . . . . . . . 125 5.1. ThefunctionalE(G,C) . . . . . . . . . . . . . . . . . . . . . . . . . 127 5.2. Basicpropertiesofprobabilisticcoloring . . . . . . . . . . . . . . . . 131 5.2.1. Propertiesundernon-identicalvertex-probabilities . . . . . . 131 5.2.2. Propertiesunderidenticalvertex-probabilities . . . . . . . . 131 5.3. PROBABILISTICMINCOLORINGingeneralgraphs . . . . . . . . . . 132 5.3.1. Thecomplexityofprobabilisticcoloring . . . . . . . . . . . 132 5.3.2. Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.3.2.1. Themainresult . . . . . . . . . . . . . . . . . . . . 132 5.3.2.2. Furtherapproximationresults . . . . . . . . . . . . 137 5.4. PROBABILISTICMINCOLORINGinbipartitegraphs . . . . . . . . . 139 5.4.1. Abasicproperty . . . . . . . . . . . . . . . . . . . . . . . . . 139 5.4.2. Generalbipartitegraphs . . . . . . . . . . . . . . . . . . . . . 141 5.4.3. Bipartitecomplementsofbipartitematchings . . . . . . . . . 147 5.4.4. Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 5.4.5. Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 5.5. Complementsofbipartitegraphs . . . . . . . . . . . . . . . . . . . . 155 5.6. Splitgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 5.6.1. ThecomplexityofPROBABILISTICMINCOLORING . . . . . 156 5.6.2. Approximationresults . . . . . . . . . . . . . . . . . . . . . . 159 5.7. Determiningthebestk-coloringink-colorablegraphs . . . . . . . . 164 5.7.1. Bipartitegraphs . . . . . . . . . . . . . . . . . . . . . . . . . 164 5.7.1.1. PROBABILISTICMIN3-COLORING. . . . . . . . . 164 8 ProbabilisticCombinatorialOptimization 5.7.1.2. PROBABILISTICMINk-COLORINGfork > 3 . . 168 5.7.1.3. Bipartitecomplementsofbipartitematchings . . . 171 5.7.2. Thecomplementsofbipartitegraphs . . . . . . . . . . . . . 171 5.7.3. Approximationinparticularclassesofgraphs . . . . . . . . 174 5.8. Commentsandopenproblems . . . . . . . . . . . . . . . . . . . . . . 175 5.9. Proofsofthedifferentresults. . . . . . . . . . . . . . . . . . . . . . . 178 5.9.1. Proofof[5.5] . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 5.9.2. Proofof[5.4] . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 5.9.3. ProofofProperty5.1 . . . . . . . . . . . . . . . . . . . . . . 180 5.9.4. ProofofProposition5.2 . . . . . . . . . . . . . . . . . . . . . 181 5.9.5. ProofofLemma5.11 . . . . . . . . . . . . . . . . . . . . . . 183 SECONDPART.STRUCTURALRESULTS . . . . . . . . . . . . . . . . . . . . 185 Chapter6.ClassificationofProbabilisticGraph-problems . . . . . . . . . . 187 6.1. WhenMSisfeasible . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 6.1.1. Theapriorisolutionisasubsetoftheinitialvertex-set . . . 188 6.1.2. Theapriorisolutionisacollectionofsubsetsoftheinitial vertex-set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 6.1.3. Theapriorisolutionisasubsetoftheinitialedge-set . . . . 193 6.2. WhenapplicationofMSitselfdoesnotleadtofeasiblesolutions . . . 198 6.2.1. ThefunctionalassociatedwithMSC . . . . . . . . . . . . . . 198 6.2.2. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 199 6.2.2.1. Theapriorisolutionisacycle . . . . . . . . . . . 200 6.2.2.2. Theapriorisolutionisatree . . . . . . . . . . . . 201 6.3. Somecomments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 6.4. ProofofTheorem6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 Chapter7.ACompendiumofProbabilisticNPOProblemsonGraphs . . 211 7.1. Coveringandpartitioning. . . . . . . . . . . . . . . . . . . . . . . . . 214 7.1.1. MINVERTEXCOVER . . . . . . . . . . . . . . . . . . . . . . 214 7.1.2. MINCOLORING . . . . . . . . . . . . . . . . . . . . . . . . . 214 7.1.3. MAXACHROMATICNUMBER . . . . . . . . . . . . . . . . . 215 7.1.4. MINDOMINATINGSET . . . . . . . . . . . . . . . . . . . . . 215 7.1.5. MAXDOMATICPARTITION . . . . . . . . . . . . . . . . . . . 216 7.1.6. MINEDGE-DOMINATINGSET . . . . . . . . . . . . . . . . . 216 7.1.7. MININDEPENDENTDOMINATINGSET . . . . . . . . . . . . 217 7.1.8. MINCHROMATICSUM . . . . . . . . . . . . . . . . . . . . . 217 7.1.9. MINEDGECOLORING . . . . . . . . . . . . . . . . . . . . . . 218 7.1.10. MINFEEDBACKVERTEX-SET . . . . . . . . . . . . . . . . . 219 7.1.11. MINFEEDBACKARC-SET. . . . . . . . . . . . . . . . . . . . 220 7.1.12. MAXMATCHING . . . . . . . . . . . . . . . . . . . . . . . . . 220 7.1.13. MINMAXIMALMATCHING . . . . . . . . . . . . . . . . . . . 220 Contents 9 7.1.14. MAXTRIANGLEPACKING . . . . . . . . . . . . . . . . . . . 220 7.1.15. MAXH-MATCHING . . . . . . . . . . . . . . . . . . . . . . . 221 7.1.16. MINPARTITIONINTOCLIQUES . . . . . . . . . . . . . . . . 222 7.1.17. MINCLIQUECOVER . . . . . . . . . . . . . . . . . . . . . . . 222 7.1.18. MINk-CAPACITEDTREEPARTITION . . . . . . . . . . . . . 222 7.1.19. MAXBALANCEDCONNECTEDPARTITION . . . . . . . . . . 223 7.1.20. MINCOMPLETEBIPARTITESUBGRAPHCOVER . . . . . . . 223 7.1.21. MINVERTEX-DISJOINTCYCLECOVER . . . . . . . . . . . . 223 7.1.22. MINCUTCOVER . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.2. Subgraphsandsupergraphs. . . . . . . . . . . . . . . . . . . . . . . . 224 7.2.1. MAXINDEPENDENTSET . . . . . . . . . . . . . . . . . . . . 224 7.2.2. MAXCLIQUE . . . . . . . . . . . . . . . . . . . . . . . . . . . 224 7.2.3. MAXINDEPENDENTSEQUENCE . . . . . . . . . . . . . . . . 225 7.2.4. MAXINDUCEDSUBGRAPHWITHPROPERTYπ . . . . . . . 225 7.2.5. MINVERTEXDELETIONTOOBTAINSUBGRAPHWITH PROPERTYπ . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 7.2.6. MINEDGEDELETIONTOOBTAINSUBGRAPHWITH PROPERTYπ . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 7.2.7. MAXCONNECTEDSUBGRAPHWITHPROPERTYπ . . . . . 226 7.2.8. MINVERTEXDELETIONTOOBTAINCONNECTED SUBGRAPHWITHPROPERTYπ. . . . . . . . . . . . . . . . . 226 7.2.9. MAXDEGREE-BOUNDEDCONNECTEDSUBGRAPH . . . . . 226 7.2.10. MAXPLANARSUBGRAPH . . . . . . . . . . . . . . . . . . . 227 7.2.11. MINEDGEDELETIONk-PARTITION. . . . . . . . . . . . . . 227 7.2.12. MAXk-COLORABLESUBGRAPH . . . . . . . . . . . . . . . 227 7.2.13. MAXSUBFOREST . . . . . . . . . . . . . . . . . . . . . . . . 228 7.2.14. MAXEDGESUBGRAPHorDENSEk-SUBGRAPH . . . . . . 228 7.2.15. MINEDGEK-SPANNER . . . . . . . . . . . . . . . . . . . . . 228 7.2.16. MAXk-COLORABLEINDUCEDSUBGRAPH . . . . . . . . . 229 7.2.17. MINEQUIVALENTDIGRAPH . . . . . . . . . . . . . . . . . . 229 7.2.18. MINCHORDALGRAPHCOMPLETION . . . . . . . . . . . . . 229 7.3. Iso-andothermorphisms . . . . . . . . . . . . . . . . . . . . . . . . . 229 7.3.1. MAXCOMMONSUBGRAPH . . . . . . . . . . . . . . . . . . . 229 7.3.2. MAXCOMMONINDUCEDSUBGRAPH. . . . . . . . . . . . . 230 7.3.3. MAXCOMMONEMBEDDEDSUBTREE . . . . . . . . . . . . 230 7.3.4. MINGRAPHTRANSFORMATION . . . . . . . . . . . . . . . . 230 7.4. Cutsandconnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.4.1. MAXCUT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.4.2. MAXDIRECTEDCUT . . . . . . . . . . . . . . . . . . . . . . 231 7.4.3. MINCROSSINGNUMBER . . . . . . . . . . . . . . . . . . . . 231 7.4.4. MAXk-CUT . . . . . . . . . . . . . . . . . . . . . . . . . . . 232 7.4.5. MINk-CUT . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 7.4.6. MINNETWORKINHIBITIONONPLANARGRAPHS . . . . . 233

See more

The list of books you might like

Upgrade Premium
Most books are stored in the elastic cloud where traffic is expensive. For this reason, we have a limit on daily download.
DMCA & Copyright: Dear all, most of the website is community built, users are uploading hundred of books everyday, which makes really hard for us to identify copyrighted material, please contact us if you want any material removed.
Copyright @ PDFdrive.to, 2022 | We love our users