Probabilistic Combinatorial Optimization on Graphs

Cécile Murat is Assistant Professor of Computer Science at the University of Paris-Dauphine. Her research interests include combinatorial and probabilistic combinatorial optimization, the design and analysis of efficient algorithms and the design of efficient solutions for hard combinatorial optimization problems. She is the author of over 20 research papers. Vangelis Th. Paschos is Professor of Computer Science at the University of Paris-Dauphine and Chairman of the LAMSADE (Laboratory for the Modeling and the Analysis of Decision Aiding Systems). His research interests include complexity theory, the theory of the polynomial approximation of NP-hard problems, probabilistic combinatorial optimization and on-line computation. He is the author of more than a 100 research papers and is a member of the editorial board of several international scientific journals.

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