• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
Solving the Identifying Code Set Problem with Grouped Independent Support.
Anna Latour, Arunabha Sen and Kuldeep S. Meel.
In Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), July 2023.
An important problem in network science is finding an optimal placement of sensors in nodes in order to uniquely detect failures in the network.This problem can be modelled as an identifying code set (ICS) problem, introduced by Karpovsky et al. in 1998. The ICS problem aims to find a cover of a set S, such that the elements in the cover define a unique signature for each of the elements of S, and to minimise the cardinality of that cover. In this work, we study a generalised identifying code set (GICS) problem, where a unique signature must be found for each subset of S that has a cardinality of at most k (instead of just each element of S). The concept of an independent support of a Boolean formula was introduced by Chakraborty et al. in 2014 to speed up propositional model counting, by identifying a subset of variables whose truth assignments uniquely define those of the other variables.In this work, we introduce an extended version of independent support, grouped independent support (GIS), and show how to reduce the GICS problem to the GIS problem. We then propose a new solving method for finding a GICS, based on finding a GIS. We show that the prior state-of-the-art approaches yield integer-linear programming (ILP) models whose sizes grow exponentially with the problem size and k, while our GIS encoding only grows polynomially with the problem size and k. While the ILP approach can solve the GICS problem on networks of at most 494 nodes, the GIS-based method can handle networks of up to 21363 nodes; a 40x improvement. The GIS-based method shows up to a 520x improvement on the ILP-based method in terms of average solving time. For the majority of the instances that can be encoded by both methods, the cardinality of the solution returned by the GIS-based method is less than 10% larger than the cardinality of the solution found by the ILP method.
@inproceedings{LSM23,
title={Solving the Identifying Code Set Problem with Grouped Independent Support},
author={Latour, Anna and Sen, Arunabha and Meel, Kuldeep S.},
abstract={
An important problem in network science is finding an optimal placement of sensors in nodes in order to uniquely detect failures in the network.
This problem can be modelled as an identifying code set (ICS) problem, introduced by Karpovsky et al. in 1998. The ICS problem aims to find a cover of a set S, such that the elements in the cover define a unique signature for each of the elements of S, and to minimise the cardinality of that cover. In this work, we study a generalised identifying code set (GICS) problem, where a unique signature must be found for each subset of S that has a cardinality of at most k (instead of just each element of S). The concept of an independent support of a Boolean formula was introduced by Chakraborty et al. in 2014 to speed up propositional model counting, by identifying a subset of variables whose truth assignments uniquely define those of the other variables.
In this work, we introduce an extended version of independent support, grouped independent support (GIS), and show how to reduce the GICS problem to the GIS problem. We then propose a new solving method for finding a GICS, based on finding a GIS. We show that the prior state-of-the-art approaches yield integer-linear programming (ILP) models whose sizes grow exponentially with the problem size and k, while our GIS encoding only grows polynomially with the problem size and k. While the ILP approach can solve the GICS problem on networks of at most 494 nodes, the GIS-based method can handle networks of up to 21363 nodes; a ~40x improvement. The GIS-based method shows up to a 520x improvement on the ILP-based method in terms of average solving time. For the majority of the instances that can be encoded by both methods, the cardinality of the solution returned by the GIS-based method is less than 10% larger than the cardinality of the solution found by the ILP method.},
publication_type={conference},
booktitle=IJCAI,
year={2023},
month=jul,
bib2html_rescat={Misc},
bib2html_pubtype={Refereed Conference},
bib2html_dl_pdf={../Papers/ijcai23-lsm.pdf},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Sun Apr 14, 2024 11:15:51