{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,17]],"date-time":"2026-03-17T00:47:25Z","timestamp":1773708445660,"version":"3.50.1"},"reference-count":35,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T00:00:00Z","timestamp":1574812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Charles University Student Grant","award":["SVV-2017-260452"],"award-info":[{"award-number":["SVV-2017-260452"]}]},{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","award":["---"],"award-info":[{"award-number":["---"]}],"id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006475","name":"Bergens Forskningsstiftelse","doi-asserted-by":"publisher","award":["810564"],"award-info":[{"award-number":["810564"]}],"id":[{"id":"10.13039\/501100006475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["274526d"],"award-info":[{"award-number":["274526d"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of parameterized complexity. This paradigm is aimed at addressing the loss of important side information which typically occurs during the abstraction process that models real-world problems as computational problems. We use two measures for the diversity of such a collection: the sum of all pairwise Hamming distances, and the minimum pairwise Hamming distance. We show that both problems are fixed-parameter tractable in     k + r     for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of \u2018base\u2019 solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.<\/jats:p>","DOI":"10.3390\/a12120254","type":"journal-article","created":{"date-parts":[[2019,11,27]],"date-time":"2019-11-27T11:07:00Z","timestamp":1574852820000},"page":"254","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["FPT Algorithms for Diverse Collections of Hitting Sets"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7869-0959","authenticated-orcid":false,"given":"Julien","family":"Baste","sequence":"first","affiliation":[{"name":"Institute of Optimization and Operations Research, Ulm University, 89081 Ulm, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Jaffke","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, 5008 Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8524-4036","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Masa\u0159\u00edk","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics of the Faculty of Mathematics and Physics, Charles University, 11800 Prague, Czech Republic"},{"name":"Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, 02-097 Warszawa, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0717-7303","authenticated-orcid":false,"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Chennai 603103, India"},{"name":"International Joint Unit Research Lab in Computer Science (UMI ReLaX), Chennai 603103, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0351-5945","authenticated-orcid":false,"given":"G\u00fcnter","family":"Rote","sequence":"additional","affiliation":[{"name":"Fachbereich Mathematik und Informatik, Freie Universit\u00e4t Berlin, D-14195 Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,11,27]]},"reference":[{"key":"ref_1","unstructured":"Ehrgott, M. (2005). Multicriteria Optimization, Springer."},{"key":"ref_2","unstructured":"Vela, A.E. (2011). Understanding Conflict-Resolution Taskload: Implementing Advisory Conflict-Detection and Resolution Algorithms in an Airspace. [Ph.D. Thesis, Georgia Institute of Technology]."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1002\/acs.1169","article-title":"Efficient air traffic conflict resolution by minimizing the number of affected aircraft","volume":"24","author":"Idan","year":"2010","journal-title":"Int. J. Adapt. Control Signal Process."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Gandhi, S., Buragohain, C., Cao, L., Zheng, H., and Suri, S. (2007, January 17\u201320). A general framework for wireless spectrum auctions. Proceedings of the 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, Dublin, Ireland.","DOI":"10.1109\/DYSPAN.2007.12"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"16:1","DOI":"10.1145\/2663496","article-title":"Approximation algorithms for secondary spectrum auctions","volume":"14","author":"Hoefer","year":"2014","journal-title":"ACM Trans. Internet Technol. (TOIT)"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.ic.2004.04.007","article-title":"Minimal-change integrity maintenance using tuple deletions","volume":"197","author":"Chomicki","year":"2005","journal-title":"Inf. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/S0304-3975(02)00737-5","article-title":"Scalar aggregation in inconsistent databases","volume":"296","author":"Arenas","year":"2003","journal-title":"Theor. Comput. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Pema, E., Kolaitis, P.G., and Tan, W.C. (2011, January 25). On the tractability and intractability of consistent conjunctive query answering. Proceedings of the 2011 Joint EDBT\/ICDT Ph. D. Workshop, Uppsala, Sweden.","DOI":"10.1145\/1966874.1966881"},{"key":"ref_9","first-page":"217","article-title":"Management of inconsistencies in data integration","volume":"Volume 5","author":"Ioannou","year":"2013","journal-title":"Data Exchange, Integration, and Streams"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/BF02219227","article-title":"Branch & sample: A simple strategy for constraint satisfaction","volume":"29","author":"Galle","year":"1989","journal-title":"BIT Numer. Math."},{"key":"ref_11","unstructured":"Fellows, M.R. (2018). Unpublished work."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02426650","article-title":"Measuring biological diversity","volume":"1","author":"Solow","year":"1994","journal-title":"Environ. Ecol. Stat."},{"key":"ref_13","first-page":"22:1","article-title":"Maximum Volume Subset Selection for Anchored Boxes","volume":"Volume 77","author":"Aronov","year":"2017","journal-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017)"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1162\/EVCO_a_00157","article-title":"Hypervolume Subset Selection in Two Dimensions: Formulations and Algorithms","volume":"24","author":"Kuhn","year":"2016","journal-title":"Evol. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Neumann, A., Gao, W., Doerr, C., Neumann, F., and Wagner, M. (2018, January 15\u201319). Discrepancy-based Evolutionary Diversity Optimization. Proceedings of the Genetic and Evolutionary Computation Conference, Kyoto, Japan.","DOI":"10.1145\/3205455.3205532"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Schaefer, R., Cotta, C., Ko\u0142odziej, J., and Rudolph, G. (2010). Defining and Optimizing Indicator-Based Diversity Measures in Multiobjective Search. Parallel Problem Solving from Nature, PPSN XI, Springer.","DOI":"10.1007\/978-3-642-15844-5"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Gabor, T., Belzner, L., Phan, T., and Schmid, K. (2018, January 3\u20137). Preparing for the Unexpected: Diversity Improves Planning Resilience in Evolutionary Algorithms. Proceedings of the 2018 IEEE International Conference on Autonomic Computing, ICAC 2018, Trento, Italy.","DOI":"10.1109\/ICAC.2018.00023"},{"key":"ref_18","unstructured":"Morrison, R.W., and Jong, K.A.D. (2001, January 29\u201331). Measurement of Population Diversity. Proceedings of the 5th International Conference, Evolution Artificielle, EA 2001, Le Creusot, France."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Louis, S.J., and Rawlins, G.J.E. (1992, January 26\u201329). Syntactic Analysis of Convergence in Genetic Algorithms. Proceedings of the Second Workshop on Foundations of Genetic Algorithms, Vail, CO, USA.","DOI":"10.1016\/B978-0-08-094832-4.50015-5"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Wineberg, M., and Oppacher, F. (2003, January 12\u201316). The Underlying Similarity of Diversity Measures Used in Evolutionary Computation. Proceedings of the Genetic and Evolutionary Computation-GECCO 2003, Genetic and Evolutionary Computation Conference, Chicago, IL, USA.","DOI":"10.1007\/3-540-45110-2_21"},{"key":"ref_21","unstructured":"Baste, J., Fellows, M., Jaffke, L., Masa\u0159\u00edk, T., de Oliveira Oliveira, M., Philip, G., and Rosamond, F. (2019). Diversity in Combinatorial Optimization. arXiv."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Tarjan, R.E. (1983). Data Structures and Network Algorithms, SIAM.","DOI":"10.1137\/1.9781611970265"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/S0097539791199334","article-title":"Improved algorithms for bipartite network flow","volume":"23","author":"Ahuja","year":"1994","journal-title":"SIAM J. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (1972). Reducibility among combinatorial problems. Complexity of Computer Computations, Springer.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"ref_26","unstructured":"Domshlak, C., and Hoffmann, J. (2006, January 6\u201310). Fast probabilistic planning through weighted model counting. Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling, Cumbria, UK."},{"key":"ref_27","unstructured":"Palacios, H., Bonet, B., Darwiche, A., and Geffner, H. (2005, January 5\u201310). Pruning conformant plans by counting models on compiled d-DNNF representations. Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling, Menlo Park, CA, USA."},{"key":"ref_28","unstructured":"Bacchus, F., Dalmao, S., and Pitassi, T. (2003, January 11\u201314). Algorithms and complexity results for #SAT and Bayesian inference. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, MA, USA."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1023\/A:1017584715408","article-title":"Stochastic Boolean satisfiability","volume":"27","author":"Littman","year":"2001","journal-title":"J. Autom. Reason."},{"key":"ref_30","unstructured":"Sang, T., Bearne, P., and Kautz, H. (2005, January 9\u201313). Performing Bayesian inference by weighted model counting. Proceedings of the 20th National Conference on Artificial Intelligence, Pittsburgh, PA, USA."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Apsel, U., and Brafman, R.I. (2012, January 22\u201326). Lifted MEU by weighted model counting. Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, ON, Canada.","DOI":"10.1609\/aaai.v26i1.8396"},{"key":"ref_32","unstructured":"Dechter, R., and Cohen, D. (2003). Constraint Processing, Morgan Kaufmann."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","article-title":"Faster deterministic Feedback Vertex Set","volume":"114","author":"Kociumaka","year":"2014","journal-title":"Inf. Process. Lett."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/j.orl.2003.10.009","article-title":"Finding odd cycle transversals","volume":"32","author":"Reed","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"ref_35","first-page":"1052","article-title":"Complexity and completeness of finding another solution and its application to puzzles","volume":"86","author":"Yato","year":"2003","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/12\/254\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:38:02Z","timestamp":1760189882000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/12\/254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,27]]},"references-count":35,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2019,12]]}},"alternative-id":["a12120254"],"URL":"https:\/\/doi.org\/10.3390\/a12120254","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,27]]}}}