Polynomial Solvability of Cost-based Abduction

Document Type


Publication Date



In recent empirical studies we have shown that many interesting cost-based abduction problems can be solved efficiently by considering the linear program relaxation of their integer program formulation. We tie this to the concept of total unimodularity from network flow analysis, a fundamental result in polynomial solvability. From this, we can determine the polynomial solvability of abduction problems and, in addition, present a new heuristic for branch and bound in the non-polynomial cases.


The "Link to Full Text" on this page opens or saves the article PDF hosted at the publisher website, Elsevier ScienceDirect. The record of the article is available from the DOI link.

Source Publication

Artificial Intelligence