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 11Chapter 1. A Short Insight into Probabilistic Combinatorial Optimization 151.1. Motivations and applications 151.2. A formalism for probabilistic combinatorial optimization 191.3. The main methodological issues dealing with probabilistic combinatorial optimization 241.3.1. Complexity issues 241.3.1.1. Membership in NPO is not always obvious 241.3.1.2. Complexity of deterministic vs. complexity of probabilistic optimization problems 241.3.2. Solution issues 261.3.2.1. Characterization of optimal a priori solutions 261.3.2.2. Polynomial subcases 281.3.2.3. Exact solutions and polynomial approximation issues 291.4. Miscellaneous and bibliographic notes 31FIRST PART. PROBABILISTIC GRAPH-PROBLEMS 35Chapter 2. The Probabilistic Maximum Independent Set 372.1. The modification strategies and a preliminary result 392.1.1. Strategy M1 392.1.2. Strategies M2 and M3 392.1.3. Strategy M4 412.1.4. Strategy M5 412.1.5. A general mathematical formulation for the five functionals 422.2. PROBABILISTIC MAX INDEPENDENT SET1 442.2.1. Computing optimal a priori solutions 442.2.2. Approximating optimal solutions 452.2.3. Dealing with bipartite graphs 462.3. PROBABILISTIC MAX INDEPENDENT SET2 and 3 472.3.1. Expressions for E(G, S, M2) and E(G, S, M3) 472.3.2. An upper bound for the complexity of E(G, S, M2) 482.3.3. Bounds for E(G, S, M2) 492.3.4. Approximating optimal solutions 512.3.4.1. Using argmax{_vi∈S pi} as an a priori solution 512.3.4.2. Using approximations of MAX INDEPENDENT SET 532.3.5. Dealing with bipartite graphs 532.4. PROBABILISTIC MAX INDEPENDENT SET4 552.4.1. An expression for E(G, S, M4) 552.4.2. Using S∗ or argmax{_vi∈S pi} as an a priori solution 562.4.3. Dealing with bipartite graphs 572.5. PROBABILISTIC MAX INDEPENDENT SET5 582.5.1. In general graphs 582.5.2. In bipartite graphs 602.6. Summary of the results 612.7. Methodological questions 632.7.1. Maximizing a criterion associated with gain 652.7.1.1. The minimum gain criterion 652.7.1.2. The maximum gain criterion 662.7.2. Minimizing a criterion associated with regret 682.7.2.1. The maximum regret criterion 682.7.3. Optimizing expectation 702.8. Proofs of the results 712.8.1. Proof of Proposition 2.1 712.8.2. Proof of Theorem 2.6 742.8.3. Proof of Proposition 2.3 772.8.4. Proof of Theorem 2.13 78Chapter 3. The Probabilistic Minimum Vertex Cover 813.1. The strategies M1, M2 and M3 and a general preliminary result 823.1.1. Specification of M1, M2 and M3 823.1.1.1. Strategy M1 823.1.1.2. Strategy M2 833.1.1.3. Strategy M3 833.1.2. A first expression for the functionals 843.2. PROBABILISTIC MIN VERTEX COVER1 843.3. PROBABILISTIC MIN VERTEX COVER2 863.4. PROBABILISTIC MIN VERTEX COVER3 873.4.1. Building E(G, C, M3) 873.4.2. Bounds for E(G, C, M3) 883.5. Some methodological questions 893.6. Proofs of the results 913.6.1. Proof of Theorem 3.3 913.6.2. On the the bounds obtained in Theorem 3.3 93Chapter 4. The Probabilistic Longest Path 994.1. Probabilistic longest path in terms of vertices 1004.2. Probabilistic longest path in terms of arcs 1024.2.1. An interesting algebraic expression 1044.2.2. Metric PROBABILISTIC ARC WEIGHTED LONGEST PATH 1054.3. Why the strategies used are pertinent 1094.4. Proofs of the results 1104.4.1. Proof of Theorem 4.1 1104.4.2. Proof of Theorem 4.2 1124.4.3. An algebraic proof for Theorem 4.3 1144.4.4. Proof of Lemma 4.1 1164.4.5. Proof of Lemma 4.2 1174.4.6. Proof of Theorem 4.4 117Chapter 5. Probabilistic Minimum Coloring 1255.1. The functional E(G,C) 1275.2. Basic properties of probabilistic coloring 1315.2.1. Properties under non-identical vertex-probabilities 1315.2.2. Properties under identical vertex-probabilities 1315.3. PROBABILISTIC MIN COLORING in general graphs 1325.3.1. The complexity of probabilistic coloring 1325.3.2. Approximation 1325.3.2.1. The main result 1325.3.2.2. Further approximation results 1375.4. PROBABILISTIC MIN COLORING in bipartite graphs 1395.4.1. A basic property 1395.4.2. General bipartite graphs 1415.4.3. Bipartite complements of bipartite matchings 1475.4.4. Trees 1515.4.5. Cycles 1545.5. Complements of bipartite graphs 1555.6. Split graphs 1565.6.1. The complexity of PROBABILISTIC MIN COLORING 1565.6.2. Approximation results 1595.7. Determining the best k-coloring in k-colorable graphs 1645.7.1. Bipartite graphs 1645.7.1.1. PROBABILISTIC MIN 3-COLORING 1645.7.1.2. PROBABILISTIC MIN k-COLORING fork > 3 1685.7.1.3. Bipartite complements of bipartite matchings 1715.7.2. The complements of bipartite graphs 1715.7.3. Approximation in particular classes of graphs 1745.8. Comments and open problems 1755.9. Proofs of the different results 1785.9.1. Proof of [5.5] 1785.9.2. Proof of [5.4] 1795.9.3. Proof of Property 5.1 1805.9.4. Proof of Proposition 5.2 1815.9.5. Proof of Lemma 5.11 183SECOND PART. STRUCTURAL RESULTS 185Chapter 6. Classification of Probabilistic Graph-problems 1876.1. When MS is feasible 1876.1.1. The a priori solution is a subset of the initial vertex-set 1886.1.2. The a priori solution is a collection of subsets of the initial vertex-set 1916.1.3. The a priori solution is a subset of the initial edge-set 1936.2. When application of MS itself does not lead to feasible solutions 1986.2.1. The functional associated with MSC 1986.2.2. Applications 1996.2.2.1. The a priori solution is a cycle 2006.2.2.2. The a priori solution is a tree 2016.3. Some comments 2056.4. Proof of Theorem 6.4 206Chapter 7. A Compendium of Probabilistic NPO Problems on Graphs 2117.1. Covering and partitioning 2147.1.1. MIN VERTEX COVER 2147.1.2. MIN COLORING 2147.1.3. MAX ACHROMATIC NUMBER 2157.1.4. MIN DOMINATING SET 2157.1.5. MAX DOMATIC PARTITION 2167.1.6. MIN EDGE-DOMINATING SET 2167.1.7. MIN INDEPENDENT DOMINATING SET 2177.1.8. MIN CHROMATIC SUM 2177.1.9. MIN EDGE COLORING 2187.1.10. MIN FEEDBACK VERTEX-SET 2197.1.11. MIN FEEDBACK ARC-SET 2207.1.12. MAX MATCHING 2207.1.13. MIN MAXIMAL MATCHING 2207.1.14. MAX TRIANGLE PACKING 2207.1.15. MAX H-MATCHING 2217.1.16. MIN PARTITION INTO CLIQUES 2227.1.17. MIN CLIQUE COVER 2227.1.18. MIN k-CAPACITED TREE PARTITION 2227.1.19. MAX BALANCED CONNECTED PARTITION 2237.1.20. MIN COMPLETE BIPARTITE SUBGRAPH COVER 2237.1.21. MIN VERTEX-DISJOINT CYCLE COVER 2237.1.22. MIN CUT COVER 2247.2. Subgraphs and supergraphs 2247.2.1. MAX INDEPENDENT SET 2247.2.2. MAX CLIQUE 2247.2.3. MAX INDEPENDENT SEQUENCE 2257.2.4. MAX INDUCED SUBGRAPH WITH PROPERTY π 2257.2.5. MIN VERTEX DELETION TO OBTAIN SUBGRAPH WITH PROPERTY π 2257.2.6. MIN EDGE DELETION TO OBTAIN SUBGRAPH WITH PROPERTY π 2267.2.7. MAX CONNECTED SUBGRAPH WITH PROPERTY π 2267.2.8. MIN VERTEX DELETION TO OBTAIN CONNECTED SUBGRAPH WITH PROPERTY π 2267.2.9. MAX DEGREE-BOUNDED CONNECTED SUBGRAPH 2267.2.10. MAX PLANAR SUBGRAPH 2277.2.11. MIN EDGE DELETION k-PARTITION 2277.2.12. MAX k-COLORABLE SUBGRAPH 2277.2.13. MAX SUBFOREST 2287.2.14. MAX EDGE SUBGRAPH or DENSE k-SUBGRAPH 2287.2.15. MIN EDGE K-SPANNER 2287.2.16. MAX k-COLORABLE INDUCED SUBGRAPH 2297.2.17. MIN EQUIVALENT DIGRAPH 2297.2.18. MIN CHORDAL GRAPH COMPLETION 2297.3. Iso- and other morphisms 2297.3.1. MAX COMMON SUBGRAPH 2297.3.2. MAX COMMON INDUCED SUBGRAPH 2307.3.3. MAX COMMON EMBEDDED SUBTREE 2307.3.4. MIN GRAPH TRANSFORMATION 2307.4. Cuts and connectivity 2317.4.1. MAX CUT 2317.4.2. MAX DIRECTED CUT 2317.4.3. MIN CROSSING NUMBER 2317.4.4. MAX k-CUT 2327.4.5. MIN k-CUT 2337.4.6. MIN NETWORK INHIBITION ON PLANAR GRAPHS 2337.4.7. MIN VERTEX k-CUT 2347.4.8. MIN MULTI-WAY CUT 2347.4.9. MIN MULTI-CUT 2347.4.10. MIN RATIO-CUT 2357.4.11. MIN b-BALANCED CUT 2367.4.12. MIN b-VERTEX SEPARATOR 2367.4.13. MIN QUOTIENT CUT 2367.4.14. MIN k-VERTEX CONNECTED SUBGRAPH 2367.4.15. MIN k-EDGE CONNECTED SUBGRAPH 2377.4.16. MIN BICONNECTIVITY AUGMENTATION 2377.4.17. MIN STRONG CONNECTIVITY AUGMENTATION 2377.4.18. MIN BOUNDED DIAMETER AUGMENTATION 237Appendix A. Mathematical Preliminaries 239A.1. Sets, relations and functions 239A.2. Basic concepts from graph-theory 242A.3. Elements from discrete probabilities 246Appendix B. Elements of the Complexity and the Approximation Theory 249B.1. Problem, algorithm, complexity 249B.2. Some notorious complexity classes 250B.3. Reductions and NP-completeness 251B.4. Approximation of NP-hard problems 252Bibliography 255Index 261