Search

Given an edge-weighted graph where all weights are nonnegative reals, an edge reweighting is an assignment of nonnegative reals to edges such that, for each vertex, the sums of given and new weights assigned to the edges incident on the vertex do coincide. An edge is then said to be invariant if its weight is the same for any edge reweighting. We show that the set of invariant edges of an arbitrary edge-weighted graph can be determined in time linear in the size of the underlying graph. Moreover, an application to the security of statistical data is discussed.

In response to queries asked to a statistical database, the query system should avoid releasing summary statistics that could lead to the disclosure of confidential individual data. Attacks to the security of a statistical database may be direct or indirect and, in order to repel them, the query system should audit queries by controlling the amount of information released by their responses. This paper focuses on sum-queries with a response variable of nonnegative real type and proposes a compact representation of answered sum-queries, called an information model in “normal form,” which allows the query system to decide whether the value of a new sum-query can or cannot be safely answered. If it cannot, then the query system will issue the range of feasible values of the new sum-query consistent with previously answered sum-queries. Both the management of the information model and the answering procedure require solving linear-programming problems and, since standard linear-programming algorithms are not polynomially bounded (despite their good performances in practice), effective procedures that make a parsimonious use of them are stated for the general case. Moreover, in the special case that the information model is “graphical.” It is shown that the answering procedure can be implemented in polynomial time.