On approximating optimal weight “no”-certificates in weighted difference constraint systems

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 $$x_{i}-x_{j} \le b_{ij}$$ x i - x j ≤ b ij 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 \le -b$$ 0 ≤ - b , $$b> 0$$ 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 $$\mathbf{D: A\cdot x \le b}$$ D : A · x ≤ b is its constraint network $$\mathbf{G= \langle V,E, b \rangle }$$ G = ⟨ V , E , b ⟩ . It is well-known that $$\mathbf{D}$$ D is infeasible if and only if $$\mathbf{G}$$ G contains a simple, negative cost cycle. Previous research has established that every negative cost cycle of length k in $$\mathbf{G}$$ G corresponds exactly to a refutation of $$\mathbf{D}$$ D using k constraints. It follows that the shortest refutation of $$\mathbf{D}$$ D (i.e., the refutation which uses the fewest number of constraints) corresponds to the length of the shortest negative cycle in $$\mathbf{G}$$ G . The constraint network of a WDCS is represented by a constraint network $$\mathbf{G = \langle V, E, b, l \rangle }$$ G = ⟨ V , E , b , l ⟩ , where $$\mathbf{l}:\mathbf{E \rightarrow \mathbb {N}}$$ l : E → N represents a function which associates a positive, integral length with each edge in $$\mathbf{G}$$ 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).