Counting, Approximate Counting and Approximate Uniform Generation of Solutions tothe Feasible Differential Problem

摘要

We consider the Feasible Differential Problem (FDP), which is the problem oflabeling the vertices of a directed graph with numbers such that the difference between the labels of two adjacent vertices lies within a specified interval. In particular we are interested in the integral version, i.e. we restrict ourselves to integral solutions. Then counting the number of solutions has a straightforward meaning and we show that this task is delta P-complete. Motivated by the negative result were describe a fully polynomial randomized approximation scheme (fpras) for the number of solutions and show that it requires O(P3N6 epsilon -2ln(delta -1)) calls to an almost uniform generator (aug) to approximate