ALCOMFT-TR-01-19

Giorgio Ausiello, Paolo G. Franciosa, Daniele Frigioni and Roberto Giaccio
Decremental Maintenance of Minimum Rank Hyperpaths and Minimum Models of Horn Formulae
Rome. Work package 4. February 2001.

Abstract: We present a decremental algorithm for maintaining minimum rank hyperpaths in a directed hypergraph from a source node s to all other nodes, under the assumption of unit hyperarc weights. Given a hypergraph H with n nodes and m hyperarcs, the total time needed to perform a sequence of hyperarc deletions is O(n· \fsize H), where \fsize H is the sum of the sizes of the hyperarcs of H; the total space needed is O(\fsize H). In the case of integer hyperarc weights in [1,C] our solution requires O(C· n·\fsize H) total time and O(C + \fsize H) space to handle any sequence of hyperarc deletions and weight increase operations. This improves over the recomputation from scratch after each deletion, that requires O(m· \fsize H) worst case time over the sequence.

The only algorithm proposed in the literature for the fully dynamic maintenance of minimum weight hyperpaths has been proposed in a more general framework. When applied to our restricted case, it may take O(n²·\fsize H) total time to handle a sequence of hyperarc deletions. In this case, our algorithm gives an n speedup factor for the amortized time per deletion.

Our algorithm can be used to maintain the satisfiability and the minimum model of a Horn formula F with n propositional symbols in O(n·<=n F) total time over a sequence of clause deletions. Here, <=n F is the sum of the number of literals in the clauses of F.

Postscript file: ALCOMFT-TR-01-19.ps.gz (201 kb).