Updating zigzag representatives efficiently

Computation of zigzag persistence has progressed in recent years, with results showing that complexities of many problems closely align with those in the non-zigzag setting.

The major efficiency gap now lies in the updating of zigzag representatives.

In this paper, we propose efficient algorithms for updating zigzag representatives based on a recent algorithm for extracting zigzag representatives from a $R=DV$ decomposition of a constructed non-zigzag.

The main difficulty for designing our update algorithms lies in the adjacency change occurring in two operations that elongate or shorten a filtration.

Despite the adjacency change, we find that the update can still be done efficiently in quadratic time.