Constrained hitting set problem with intervals: Hardness, FPT and approximation algorithms

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F24%3A00585147" target="_blank" >RIV/67985807:_____/24:00585147 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.tcs.2024.114402" target="_blank" >https://doi.org/10.1016/j.tcs.2024.114402</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.tcs.2024.114402" target="_blank" >10.1016/j.tcs.2024.114402</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Constrained hitting set problem with intervals: Hardness, FPT and approximation algorithms

Popis výsledku v původním jazyce

We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into pairwise 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, we must select all the points from that subset. 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. On the contrary, if each subset contains at most t points, where t >= 2, and the intervals are overlapping, we show that the problem becomes NP-Hard. Further, when each subset contains at most t points where t >= 3, and the intervals are disjoint, we prove that the problem is NP-Hard, and we provide two constant factor approximation algorithms for this problem. We also study the problem from the parameterized complexity perspective. If the intervals are disjoint, then 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.

Název v anglickém jazyce

Constrained hitting set problem with intervals: Hardness, FPT and approximation algorithms

Popis výsledku anglicky

We study a constrained version of the Geometric Hitting Set problem where we are given a set of points, partitioned into pairwise 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, we must select all the points from that subset. 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. On the contrary, if each subset contains at most t points, where t >= 2, and the intervals are overlapping, we show that the problem becomes NP-Hard. Further, when each subset contains at most t points where t >= 3, and the intervals are disjoint, we prove that the problem is NP-Hard, and we provide two constant factor approximation algorithms for this problem. We also study the problem from the parameterized complexity perspective. If the intervals are disjoint, then 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GJ19-06792Y" target="_blank" >GJ19-06792Y: Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

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

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

990

Číslo periodika v rámci svazku

1 April 2024

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

16

Strana od-do

114402

Kód UT WoS článku

001174592700001

EID výsledku v databázi Scopus

2-s2.0-85183578352