FPT Algorithms for Diverse Collections of Hitting Sets

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10404212" target="_blank" >RIV/00216208:11320/19:10404212 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=k-Bqq.u7Ca" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=k-Bqq.u7Ca</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/a12120254" target="_blank" >10.3390/a12120254</a>

Result language

angličtina

Original language name

FPT Algorithms for Diverse Collections of Hitting Sets

Original language description

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 for both diversity measures. A key ingredient in our algorithms is a (problem independent) network flow formulation that, given a set of &apos;base&apos; solutions, computes a maximally diverse collection of solutions. We believe that this could be of independent interest.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

S - Specificky vyzkum na vysokych skolach

Publication year

2019

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Algorithms

ISSN

1999-4893

e-ISSN

—

Volume of the periodical

12

Issue of the periodical within the volume

12

Country of publishing house

CH - SWITZERLAND

Number of pages

18

Pages from-to

1-18

UT code for WoS article

000505741500024

EID of the result in the Scopus database

2-s2.0-85079697264