On the Maximum Weighted Irredundant Set Problem
DOI:
https://doi.org/10.33044/revuma.3349Abstract
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.
Downloads
References
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
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
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
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
M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh, Parameterized algorithms, Springer, Cham, 2015. MR Zbl
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), 155–167. DOI MR Zbl
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
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, New York, 1998. MR Zbl
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
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 2021. Abstract available at https://coq-workshop.gitlab.io/2021/abstracts/Coq2021-04-02-graph-theory-proofs.pdf
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
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.
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. DOI Zbl
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
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
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
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Ricardo D. Katz, Daniel Severín
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.
