Revista de la
Unión Matemática Argentina
On the maximum weighted irredundant set problem
Ricardo D. Katz and Daniel Severín

Volume 68, no. 1 (2025), pp. 187–203    

Published online (final version): May 20, 2025

https://doi.org/10.33044/revuma.3349

Download PDF

Abstract

We present a generalization of a well-known domination parameter, the upper irredundance number, and address its associated optimization problem, namely the maximum weighted irredundant set (MWIS) problem, which models some service allocation problems. We establish a polynomial-time reduction to the maximum weighted stable set (MWSS) problem that we use to find graph classes for which the MWIS problem is polynomial, among other results. We formalize these results in the proof assistant Coq. This is mainly convenient in the case of some of them due to the structure of their proofs. We also present a heuristic and an integer programming formulation for the MWIS problem and check that the heuristic delivers good quality solutions through experimentation.

References

  1. C. Bazgan, L. Brankovic, K. Casel, and H. Fernau, Domination chain: Characterisation, classical complexity, parameterised complexity and approximability, Discrete Appl. Math. 280 (2020), 23–42.  DOI  MR  Zbl
  2. A. Boyacı and J. Monnot, Weighted upper domination number, in LAGOS'17—IX Latin and American Algorithms, Graphs and Optimization, Electron. Notes Discrete Math. 62, Elsevier, Amsterdam, 2017, pp. 171–176.  DOI  MR  Zbl
  3. E. J. Cockayne, S. T. Hedetniemi, and D. J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 no. 4 (1978), 461–468.  DOI  MR  Zbl
  4. B. Courcelle, J. A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 no. 2 (2000), 125–150.  DOI  MR  Zbl
  5. M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized algorithms, Springer, Cham, 2015.  MR  Zbl
  6. C. Doczkal and D. Pous, Graph theory in Coq: minors, treewidth, and isomorphisms, J. Automat. Reason. 64 no. 5 (2020), 795–825.  DOI  MR  Zbl
  7. R. G. Downey, M. R. Fellows, and V. Raman, The complexity of irredundant sets parameterized by size, Discrete Appl. Math. 100 no. 3 (2000), 155–167.  DOI  MR  Zbl
  8. O. Favaron, T. W. Haynes, S. T. Hedetniemi, M. A. Henning, and D. J. Knisley, Total irredundance in graphs, Discrete Math. 256 no. 1-2 (2002), 115–127.  DOI  MR  Zbl
  9. G. Gonthier, Formal proof—the four-color theorem, Notices Amer. Math. Soc. 55 no. 11 (2008), 1382–1393.  MR  Zbl
  10. G. Gonthier and A. Mahboubi, An introduction to small scale reflection in Coq, J. Formaliz. Reason. 3 no. 2 (2010), 95–152.  DOI  MR  Zbl
  11. J. Harrison, Formal proof—theory and practice, Notices Amer. Math. Soc. 55 no. 11 (2008), 1395–1406.  MR  Zbl
  12. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of domination in graphs, Monogr. Textbooks Pure Appl. Math. 208, Marcel Dekker, New York, 1998.  MR  Zbl
  13. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (eds.), Domination in graphs: Advanced topics, Monogr. Textbooks Pure Appl. Math. 209, Marcel Dekker, New York, 1998.  MR  Zbl
  14. IBM ILOG CPLEX Optimizer. Available at https://www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimizer.
  15. R. D. Katz and D. Severín, Coq/Ssreflect for large case-based graph theory proofs, 2021, The 12th Coq Workshop, online, affiliated with ITP 2021. Abstract available at https://coq-workshop.gitlab.io/2021/abstracts/Coq2021-04-02-graph-theory-proofs.pdf
  16. V. V. Lozin and R. Mosca, Independent sets in extensions of $2K_2$-free graphs, Discrete Appl. Math. 146 no. 1 (2005), 74–80.  DOI  MR  Zbl
  17. A. A. McRae, Generalizing NP-completeness proofs for bipartite graphs and chordal graphs, Ph.D. thesis, Clemson University, 1994. Available at https://open.clemson.edu/arv_dissertations/1682.
  18. G. J. Minty, On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B 28 no. 3 (1980), 284–304.  DOI  MR  Zbl
  19. G. L. Nemhauser and G. Sigismondi, A strong cutting plane/branch-and-bound algorithm for node packing, J. Oper. Res. Soc. 43 (1992), 443–457.  DOI  Zbl
  20. P. R. J. Östergård, A new algorithm for the maximum-weight clique problem, Nordic J. Comput. 8 no. 4 (2001), 424–436.  MR  Zbl
  21. P. Pinacho Davidson, C. Blum, and J. A. Lozano, The weighted independent domination problem: Integer linear programming models and metaheuristic approaches, European J. Oper. Res. 265 no. 3 (2018), 860–871.  DOI  MR  Zbl
  22. D. E. Severín, Formalization of the domination chain with weighted parameters, in 10th International Conference on Interactive Theorem Proving, LIPIcs. Leibniz Int. Proc. Inform. 141, Schloss Dagstuhl. Leibniz-Zentrum für Informatik, Wadern, 2019, article no. 36.  DOI  MR  Zbl