Parameterized complexity, introduced to efficiently solve NP-hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity ((Formula presented.)) for several graph theoretic problems in (Formula presented.) : Maximum (Formula presented.) -Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular-width ((Formula presented.)) and consequently—as (Formula presented.) is a special case of (Formula presented.) —by (Formula presented.). However, the proposed novel algorithms allow for improving the computational complexity from time (Formula presented.) —where (Formula presented.) and (Formula presented.) denote, respectively, the number of vertices and edges in the input graph—to time (Formula presented.) which is only additive in the size of the input. Then we consider some classical NP-hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.

Getting linear time in graphs of bounded neighborhood diversity

Cordasco G.;Gargano L.;Rescigno A. A.
2024-01-01

Abstract

Parameterized complexity, introduced to efficiently solve NP-hard problems for small values of a fixed parameter, has been recently used as a tool to speed up algorithms for tractable problems. Following this line of research, we design algorithms parameterized by neighborhood diversity ((Formula presented.)) for several graph theoretic problems in (Formula presented.) : Maximum (Formula presented.) -Matching, Triangle Counting and Listing, Girth, Global Minimum Vertex Cut, and Perfect Graphs Recognition. Such problems are known to admit algorithms parameterized by modular-width ((Formula presented.)) and consequently—as (Formula presented.) is a special case of (Formula presented.) —by (Formula presented.). However, the proposed novel algorithms allow for improving the computational complexity from time (Formula presented.) —where (Formula presented.) and (Formula presented.) denote, respectively, the number of vertices and edges in the input graph—to time (Formula presented.) which is only additive in the size of the input. Then we consider some classical NP-hard problems (Maximum independent set, Maximum clique, and Minimum dominating set) and show that for several classes of hereditary graphs, they admit linear time algorithms for sufficiently small—nonnecessarily constant—values of the neighborhood diversity parameter.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4879591
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact