An irredundant set of a hypergraph G = (V,H) is a subset S of its nodes such that removing any node from S decreases the number of hyperedges it intersects. The concept is deeply related to that of dominating sets, as the minimal dominating sets of a graph correspond exactly to the dominating sets which are also maximal irredundant sets. In this paper we propose an FPT-delay algorithm for listing maximal irredundant sets, whose delay is O(2dΔd+1n2), where d is the degeneracy of the hypergraph and Δ the maximum node degree. As d ≤ Δ,, we immediately obtain an algorithm with delay O(2ΔΔΔ+1n2) that is FPT for bounded-degree hypergraphs. This result opens a gap between known bounds for this problem and those for listing minimal dominating sets in these classes of hypergraphs, as the known running times used to be the same, hinting at the idea that the latter may indeed be harder.

Maximal irredundant set enumeration in bounded-degeneracy and bounded-degree hypergraphs / Conte A.; Kante M.M.; Marino A.; Uno T.. - STAMPA. - 11638:(2019), pp. 148-159. (Intervento presentato al convegno 30th International Workshop on Combinatorial Algorithms, IWOCA 2019 tenutosi a ita nel 2019) [10.1007/978-3-030-25005-8_13].

Maximal irredundant set enumeration in bounded-degeneracy and bounded-degree hypergraphs

Marino A.;
2019

Abstract

An irredundant set of a hypergraph G = (V,H) is a subset S of its nodes such that removing any node from S decreases the number of hyperedges it intersects. The concept is deeply related to that of dominating sets, as the minimal dominating sets of a graph correspond exactly to the dominating sets which are also maximal irredundant sets. In this paper we propose an FPT-delay algorithm for listing maximal irredundant sets, whose delay is O(2dΔd+1n2), where d is the degeneracy of the hypergraph and Δ the maximum node degree. As d ≤ Δ,, we immediately obtain an algorithm with delay O(2ΔΔΔ+1n2) that is FPT for bounded-degree hypergraphs. This result opens a gap between known bounds for this problem and those for listing minimal dominating sets in these classes of hypergraphs, as the known running times used to be the same, hinting at the idea that the latter may indeed be harder.
2019
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
30th International Workshop on Combinatorial Algorithms, IWOCA 2019
ita
2019
Conte A.; Kante M.M.; Marino A.; Uno T.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1176861
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact