@COMMENT This file was generated by bib2html.pl <https://sourceforge.net/projects/bib2html/> version 0.94
@COMMENT written by Patrick Riley <http://sourceforge.net/users/patstg/>
@COMMENT This file came from Kuldeep S. Meel's publication pages at
@COMMENT http://www.comp.nus.edu.sg/~meel/publications/
@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},
}