The width k of a directed acyclic graph (DAG) =(,) equals the largest number of pairwise non-reachable vertices. Computing the width dates back to Dilworth’s and Fulkerson’s results in the 1950s, and is doable in quadratic time in the worst case. Since k can be small in practical applications, research has also studied algorithms whose complexity is parameterized on k. Despite these efforts, it is still open whether there exists a linear-time (()(||+||)) parameterized algorithm computing the width . We answer this question affirmatively by presenting an (24||+2||) time algorithm, based on a new notion of frontier antichains. As we process the vertices in a topological order, all frontier antichains can be maintained with the help of several combinatorial properties, paying only f(k) along the way. The fact that the width can be computed by a single f(k)-sweep of the DAG is a new surprising insight into this classical problem. Our algorithm also allows deciding whether the DAG has width at most w in time ((min(,))(||+||)).

A Linear-Time Parameterized Algorithm for Computing the Width of a DAG

Cairo, Massimo;Rizzi, Romeo;
2021

Abstract

The width k of a directed acyclic graph (DAG) =(,) equals the largest number of pairwise non-reachable vertices. Computing the width dates back to Dilworth’s and Fulkerson’s results in the 1950s, and is doable in quadratic time in the worst case. Since k can be small in practical applications, research has also studied algorithms whose complexity is parameterized on k. Despite these efforts, it is still open whether there exists a linear-time (()(||+||)) parameterized algorithm computing the width . We answer this question affirmatively by presenting an (24||+2||) time algorithm, based on a new notion of frontier antichains. As we process the vertices in a topological order, all frontier antichains can be maintained with the help of several combinatorial properties, paying only f(k) along the way. The fact that the width can be computed by a single f(k)-sweep of the DAG is a new surprising insight into this classical problem. Our algorithm also allows deciding whether the DAG has width at most w in time ((min(,))(||+||)).
978-3-030-86837-6
Directed acyclic graph Maximum antichain DAG width Posets Parameterized algorithms Reachability queries
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/11562/1057342
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact