Preface 11
Chapter 1. A Short Insight into Probabilistic Combinatorial
Optimization 15
1.1. Motivations and applications 15
1.2. A formalism for probabilistic combinatorial optimization
19
1.3. The main methodological issues dealing with probabilistic
combinatorial optimization 24
1.3.1. Complexity issues 24
1.3.1.1. Membership in NPO is not always obvious 24
1.3.1.2. Complexity of deterministic vs. complexity of
probabilistic optimization problems 24
1.3.2. Solution issues 26
1.3.2.1. Characterization of optimal a priori solutions 26
1.3.2.2. Polynomial subcases 28
1.3.2.3. Exact solutions and polynomial approximation issues
29
1.4. Miscellaneous and bibliographic notes 31
FIRST PART. PROBABILISTIC GRAPH-PROBLEMS 35
Chapter 2. The Probabilistic Maximum Independent Set
37
2.1. The modification strategies and a preliminary result 39
2.1.1. Strategy M1 39
2.1.2. Strategies M2 and M3 39
2.1.3. Strategy M4 41
2.1.4. Strategy M5 41
2.1.5. A general mathematical formulation for the five
functionals 42
2.2. PROBABILISTIC MAX INDEPENDENT SET1 44
2.2.1. Computing optimal a priori solutions 44
2.2.2. Approximating optimal solutions 45
2.2.3. Dealing with bipartite graphs 46
2.3. PROBABILISTIC MAX INDEPENDENT SET2 and 3 47
2.3.1. Expressions for E(G, S, M2) and E(G, S, M3) 47
2.3.2. An upper bound for the complexity of E(G, S, M2) 48
2.3.3. Bounds for E(G, S, M2) 49
2.3.4. Approximating optimal solutions 51
2.3.4.1. Using argmax{_vi?S pi} as an a priori solution
51
2.3.4.2. Using approximations of MAX INDEPENDENT SET 53
2.3.5. Dealing with bipartite graphs 53
2.4. PROBABILISTIC MAX INDEPENDENT SET4 55
2.4.1. An expression for E(G, S, M4) 55
2.4.2. Using S? or argmax{_vi?S pi} as an a priori
solution 56
2.4.3. Dealing with bipartite graphs 57
2.5. PROBABILISTIC MAX INDEPENDENT SET5 58
2.5.1. In general graphs 58
2.5.2. In bipartite graphs 60
2.6. Summary of the results 61
2.7. Methodological questions 63
2.7.1. Maximizing a criterion associated with gain 65
2.7.1.1. The minimum gain criterion 65
2.7.1.2. The maximum gain criterion 66
2.7.2. Minimizing a criterion associated with regret 68
2.7.2.1. The maximum regret criterion 68
2.7.3. Optimizing expectation 70
2.8. Proofs of the results 71
2.8.1. Proof of Proposition 2.1 71
2.8.2. Proof of Theorem 2.6 74
2.8.3. Proof of Proposition 2.3 77
2.8.4. Proof of Theorem 2.13 78
Chapter 3. The Probabilistic Minimum Vertex Cover 81
3.1. The strategies M1, M2 and M3 and a general preliminary
result 82
3.1.1. Specification of M1, M2 and M3 82
3.1.1.1. Strategy M1 82
3.1.1.2. Strategy M2 83
3.1.1.3. Strategy M3 83
3.1.2. A first expression for the functionals 84
3.2. PROBABILISTIC MIN VERTEX COVER1 84
3.3. PROBABILISTIC MIN VERTEX COVER2 86
3.4. PROBABILISTIC MIN VERTEX COVER3 87
3.4.1. Building E(G, C, M3) 87
3.4.2. Bounds for E(G, C, M3) 88
3.5. Some methodological questions 89
3.6. Proofs of the results 91
3.6.1. Proof of Theorem 3.3 91
3.6.2. On the the bounds obtained in Theorem 3.3 93
Chapter 4. The Probabilistic Longest Path 99
4.1. Probabilistic longest path in terms of vertices 100
4.2. Probabilistic longest path in terms of arcs 102
4.2.1. An interesting algebraic expression 104
4.2.2. Metric PROBABILISTIC ARC WEIGHTED LONGEST PATH 105
4.3. Why the strategies used are pertinent 109
4.4. Proofs of the results 110
4.4.1. Proof of Theorem 4.1 110
4.4.2. Proof of Theorem 4.2 112
4.4.3. An algebraic proof for Theorem 4.3 114
4.4.4. Proof of Lemma 4.1 116
4.4.5. Proof of Lemma 4.2 117
4.4.6. Proof of Theorem 4.4 117
Chapter 5. Probabilistic Minimum Coloring 125
5.1. The functional E(G,C) 127
5.2. Basic properties of probabilistic coloring 131
5.2.1. Properties under non-identical vertex-probabilities
131
5.2.2. Properties under identical vertex-probabilities 131
5.3. PROBABILISTIC MIN COLORING in general graphs 132
5.3.1. The complexity of probabilistic coloring 132
5.3.2. Approximation 132
5.3.2.1. The main result 132
5.3.2.2. Further approximation results 137
5.4. PROBABILISTIC MIN COLORING in bipartite graphs 139
5.4.1. A basic property 139
5.4.2. General bipartite graphs 141
5.4.3. Bipartite complements of bipartite matchings 147
5.4.4. Trees 151
5.4.5. Cycles 154
5.5. Complements of bipartite graphs 155
5.6. Split graphs 156
5.6.1. The complexity of PROBABILISTIC MIN COLORING 156
5.6.2. Approximation results 159
5.7. Determining the best k-coloring in k-colorable graphs
164
5.7.1. Bipartite graphs 164
5.7.1.1. PROBABILISTIC MIN 3-COLORING 164
5.7.1.2. PROBABILISTIC MIN k-COLORING fork > 3 168
5.7.1.3. Bipartite complements of bipartite matchings 171
5.7.2. The complements of bipartite graphs 171
5.7.3. Approximation in particular classes of graphs 174
5.8. Comments and open problems 175
5.9. Proofs of the different results 178
5.9.1. Proof of [5.5] 178
5.9.2. Proof of [5.4] 179
5.9.3. Proof of Property 5.1 180
5.9.4. Proof of Proposition 5.2 181
5.9.5. Proof of Lemma 5.11 183
SECOND PART. STRUCTURAL RESULTS 185
Chapter 6. Classification of Probabilistic Graph-problems
187
6.1. When MS is feasible 187
6.1.1. The a priori solution is a subset of the initial
vertex-set 188
6.1.2. The a priori solution is a collection of subsets of the
initial vertex-set 191
6.1.3. The a priori solution is a subset of the initial edge-set
193
6.2. When application of MS itself does not lead to feasible
solutions 198
6.2.1. The functional associated with MSC 198
6.2.2. Applications 199
6.2.2.1. The a priori solution is a cycle 200
6.2.2.2. The a priori solution is a tree 201
6.3. Some comments 205
6.4. Proof of Theorem 6.4 206
Chapter 7. A Compendium of Probabilistic NPO Problems on
Graphs 211
7.1. Covering and partitioning 214
7.1.1. MIN VERTEX COVER 214
7.1.2. MIN COLORING 214
7.1.3. MAX ACHROMATIC NUMBER 215
7.1.4. MIN DOMINATING SET 215
7.1.5. MAX DOMATIC PARTITION 216
7.1.6. MIN EDGE-DOMINATING SET 216
7.1.7. MIN INDEPENDENT DOMINATING SET 217
7.1.8. MIN CHROMATIC SUM 217
7.1.9. MIN EDGE COLORING 218
7.1.10. MIN FEEDBACK VERTEX-SET 219
7.1.11. MIN FEEDBACK ARC-SET 220
7.1.12. MAX MATCHING 220
7.1.13. MIN MAXIMAL MATCHING 220
7.1.14. MAX TRIANGLE PACKING 220
7.1.15. MAX H-MATCHING 221
7.1.16. MIN PARTITION INTO CLIQUES 222
7.1.17. MIN CLIQUE COVER 222
7.1.18. MIN k-CAPACITED TREE PARTITION 222
7.1.19. MAX BALANCED CONNECTED PARTITION 223
7.1.20. MIN COMPLETE BIPARTITE SUBGRAPH COVER 223
7.1.21. MIN VERTEX-DISJOINT CYCLE COVER 223
7.1.22. MIN CUT COVER 224
7.2. Subgraphs and supergraphs 224
7.2.1. MAX INDEPENDENT SET 224
7.2.2. MAX CLIQUE 224
7.2.3. MAX INDEPENDENT SEQUENCE 225
7.2.4. MAX INDUCED SUBGRAPH WITH PROPERTY ? 225
7.2.5. MIN VERTEX DELETION TO OBTAIN SUBGRAPH WITH PROPERTY
? 225
7.2.6. MIN EDGE DELETION TO OBTAIN SUBGRAPH WITH PROPERTY ?
226
7.2.7. MAX CONNECTED SUBGRAPH WITH PROPERTY ? 226
7.2.8. MIN VERTEX DELETION TO OBTAIN CONNECTED SUBGRAPH WITH
PROPERTY ? 226
7.2.9. MAX DEGREE-BOUNDED CONNECTED SUBGRAPH 226
7.2.10. MAX PLANAR SUBGRAPH 227
7.2.11. MIN EDGE DELETION k-PARTITION 227
7.2.12. MAX k-COLORABLE SUBGRAPH 227
7.2.13. MAX SUBFOREST 228
7.2.14. MAX EDGE SUBGRAPH or DENSE k-SUBGRAPH 228
7.2.15. MIN EDGE K-SPANNER 228
7.2.16. MAX k-COLORABLE INDUCED SUBGRAPH 229
7.2.17. MIN EQUIVALENT DIGRAPH 229
7.2.18. MIN CHORDAL GRAPH COMPLETION 229
7.3. Iso- and other morphisms 229
7.3.1. MAX COMMON SUBGRAPH 229
7.3.2. MAX COMMON INDUCED SUBGRAPH 230
7.3.3. MAX COMMON EMBEDDED SUBTREE 230
7.3.4. MIN GRAPH TRANSFORMATION 230
7.4. Cuts and connectivity 231
7.4.1. MAX CUT 231
7.4.2. MAX DIRECTED CUT 231
7.4.3. MIN CROSSING NUMBER 231
7.4.4. MAX k-CUT 232
7.4.5. MIN k-CUT 233
7.4.6. MIN NETWORK INHIBITION ON PLANAR GRAPHS 233
7.4.7. MIN VERTEX k-CUT 234
7.4.8. MIN MULTI-WAY CUT 234
7.4.9. MIN MULTI-CUT 234
7.4.10. MIN RATIO-CUT 235
7.4.11. MIN b-BALANCED CUT 236
7.4.12. MIN b-VERTEX SEPARATOR 236
7.4.13. MIN QUOTIENT CUT 236
7.4.14. MIN k-VERTEX CONNECTED SUBGRAPH 236
7.4.15. MIN k-EDGE CONNECTED SUBGRAPH 237
7.4.16. MIN BICONNECTIVITY AUGMENTATION 237
7.4.17. MIN STRONG CONNECTIVITY AUGMENTATION 237
7.4.18. MIN BOUNDED DIAMETER AUGMENTATION 237
Appendix A. Mathematical Preliminaries 239
A.1. Sets, relations and functions 239
A.2. Basic concepts from graph-theory 242
A.3. Elements from discrete probabilities 246
Appendix B. Elements of the Complexity and the Approximation
Theory 249
B.1. Problem, algorithm, complexity 249
B.2. Some notorious complexity classes 250
B.3. Reductions and NP-completeness 251
B.4. Approximation of NP-hard problems 252
Bibliography 255
Index 261
