On the maximum weighted irredundant set problem

• Ricardo D Katz ^[2] ; Daniel Severín ^[1]
  1. [1] Universidad Nacional de Rosario

     Universidad Nacional de Rosario

     Argentina

     
  2. [2] CIFASIS-CONICET, Argentina
• Localización: Revista de la Unión Matemática Argentina, ISSN 0041-6932, ISSN-e 1669-9637, Vol. 68, Nº. 1, 2025, págs. 187-203
• Idioma: inglés
• DOI: 10.33044/revuma.3349
• Enlaces
  • Texto completo
• Resumen

  • 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.

• Referencias bibliográficas
  • C. Bazgan, L. Brankovic, K. Casel, and H. Fernau, Domination chain: Characterisation, classical complexity, parameterised complexity and approximability,...
  • A. Boyacı and J. Monnot, Weighted upper domination number, in LAGOS’17—IX Latin and American Algorithms, Graphs and Optimization, Electron....
  • E. J. Cockayne, S. T. Hedetniemi, and D. J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 no. 4 (1978),...
  • B. Courcelle, J. A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput....
  • M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized algorithms, Springer,...
  • 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
  • R. G. Downey, M. R. Fellows, and V. Raman, The complexity of irredundant sets parameterized by size, Discrete Appl. Math. 100 no. 3 (2000),...
  • 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),...
  • G. Gonthier, Formal proof—the four-color theorem, Notices Amer. Math. Soc. 55 no. 11 (2008), 1382–1393. MR Zbl
  • 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
  • J. Harrison, Formal proof—theory and practice, Notices Amer. Math. Soc. 55 no. 11 (2008), 1395–1406. MR Zbl
  • T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of domination in graphs, Monogr. Textbooks Pure Appl. Math. 208, Marcel Dekker,...
  • T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (eds.), Domination in graphs: Advanced topics, Monogr. Textbooks Pure Appl. Math. 209, Marcel...
  • IBM ILOG CPLEX Optimizer. Available at https://www.ibm.com/products/ilog-cplex-optimization-studio/cplex-optimizer.
  • 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...
  • V. V. Lozin and R. Mosca, Independent sets in extensions of 2K2-free graphs, Discrete Appl. Math. 146 no. 1 (2005), 74–80. DOI MR Zbl
  • A. A. McRae, Generalizing NP-completeness proofs for bipartite graphs and chordal graphs, Ph.D. thesis, Clemson University, 1994. Available...
  • 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
  • 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....
  • P. R. J. Ostergård, A new algorithm for the maximum-weight clique problem, Nordic J. Comput. 8 no. 4 (2001), 424–436. MR Zbl
  • P. Pinacho Davidson, C. Blum, and J. A. Lozano, The weighted independent domination problem: Integer linear programming models and metaheuristic...
  • D. E. Severín, Formalization of the domination chain with weighted parameters, in 10th International Conference on Interactive Theorem Proving,...