Constrained Hitting Set Problem with Intervals

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F21%3A00548662" target="_blank" >RIV/67985807:_____/21:00548662 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/978-3-030-89543-3_50" target="_blank" >http://dx.doi.org/10.1007/978-3-030-89543-3_50</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-030-89543-3_50" target="_blank" >10.1007/978-3-030-89543-3_50</a>

Result language

angličtina

Original language name

Constrained Hitting Set Problem with Intervals

Original language description

We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into disjoint subsets, and a set of intervals. The objective is to hit all the intervals with a minimum number of points such that if we select a point from a subset then we must select all the points from that subset. In general, when the intervals are disjoint, we prove that the problem is in FPT, when parameterized by the size of the solution. We also complement this result by giving a lower bound in the size of the kernel for disjoint intervals, and we also provide a polynomial kernel when the size of all subsets is bounded by a constant. Next, we consider two special cases of the problem where each subset can have at most 2 and 3 points. If each subset contains at most 2 points and the intervals are disjoint, we show that the problem admits a polynomial-time algorithm. However, when each subset contains at most 3 points and intervals are disjoint, we prove that the problem is NP-Hard and we provide two constant factor approximations for the problem.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Structural properties of visibility in terrains and farthest color Voronoi diagrams</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2021

Confidentiality

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

Article name in the collection

Computing and Combinatorics: 27th International Conference, COCOON 2021 Proceedings

ISBN

978-3-030-89542-6

ISSN

0302-9743

e-ISSN

—

Number of pages

13

Pages from-to

604-616

Publisher name

Springer

Place of publication

Cham

Event location

Tainan

Event date

Oct 24, 2021

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000767965300050