On Approximating Optimal Weight “no”-Certificates in Weighted Difference Constraint Systems

Abstract

This paper is concerned with the design and analysis of approximation algorithms for the problem of determining the least weight refutation in a weighted difference constraint system. Recall that a difference constraint is a linear constraint of the form xi- xj≤ bij and a conjunction of such constraints is called a difference constraint system (DCS). In a weighted DCS (WDCS), a positive weight is associated with each constraint. Every infeasible constraint system has a refutation, which attests to its infeasibility. In the case of a DCS, this refutation is a subset of the input constraints, which when added together produces a contradiction of the form 0 ≤ - b, b> 0. It follows that every refutation acts as a “no”-certificate. The length of a refutation is the number of constraints used in the derivation of a contradiction. Associated with a DCS D: A· x≤ b is its constraint network G= ⟨ V, E, b⟩. It is well-known that D is infeasible if and only if G contains a simple, negative cost cycle. Previous research has established that every negative cost cycle of length k in G corresponds exactly to a refutation of D using k constraints. It follows that the shortest refutation of D (i.e., the refutation which uses the fewest number of constraints) corresponds to the length of the shortest negative cycle in G. The constraint network of a WDCS is represented by a constraint network G= ⟨ V, E, b, l⟩ , where l: E→ N represents a function which associates a positive, integral length with each edge in G. In the case of a WDCS, the weight of a refutation is defined as the sum of the lengths of the edges corresponding to the refutation. The problem of finding the minimum weight refutation in a WDCS is called the weighted optimal length resolution refutation (WOLRR) problem and is known to be NP-hard. In this paper, we describe a pseudo-polynomial time algorithm for the WOLRR problem and convert it into a fully polynomial time approximation scheme (FPTAS). © 2018, Springer Science+Business Media, LLC, part of Springer Nature.