CP-nets: A Tool for Representing and Reasoning with Conditional Ceteris Paribus Preference Statements (d4-journals-jair-2004-0010)

Given a rational finite-support society
\{(N_t,\mu_t)\}_{t=1}^{\tau}
of binary-valued, directed-path singly connected CP-net types, two outcomes
o,o'\in\{0,1\}^n
, and a rational quota
\theta\in[0,1]
, decide whether
\sum_{t=1}^{\tau}\mu_t\mathbf{1}[N_t\models o\succ o']\ge\theta
.

Definitions

A binary CP-net is an acyclic dependency DAG whose conditional preference table assigns a strict preference between the two values of each variable for every assignment to its parents. An improving flip changes one variable to its locally preferred value, keeping all other variables fixed; write \(N\models o\succ o'\) iff an improving-flip sequence leads from \(o'\) to \(o\).
A dependency DAG is directed-path singly connected if every ordered pair of vertices has at most one directed path between them. A society is a rational finite-support distribution \(\{(N_t,\mu_t)\}_{t=1}^{\tau}\), where \(\mu_t\ge0\) and \(\sum_t\mu_t=1\).

Target

Is deciding whether \(\sum_{t=1}^{\tau}\mu_t\mathbf{1}[N_t\models o\succ o']\ge\theta\) for binary-valued, directed-path singly connected CP-net types in \(\mathrm{P}\), or is it NP-hard?

Nearest known results

For a single binary-valued, directed-path singly connected CP-net, dominance testing is NP-complete.
That result concerns one CP-net rather than a rational weighted society of CP-net types.

The problem is NP-complete, using the stated single-type NP-completeness result as a premise. In particular, allowing rational weighted societies preserves NP-hardness.

NP-hardness. Consider an instance \((N,o,o')\) of single-net dominance testing, where \(N\) is binary-valued and its dependency DAG is directed-path singly connected. Construct the society consisting of the single type \(N_1=N\), with weight \(\mu_1=1\), and set \(\theta=1\). Then
\[ \sum_{t=1}^{1}\mu_t\mathbf{1}[N_t\models o\succ o'] =\mathbf{1}[N\models o\succ o']. \]
Consequently, the society satisfies the threshold precisely when \(N\models o\succ o'\).

The construction copies the original instance and adds only constant-size rational data. It is therefore a polynomial-time many-one reduction, and it preserves both structural restrictions on the CP-net. The assumed NP-hardness of single-net dominance thus proves NP-hardness of the target problem, even for singleton societies.

Membership in NP. Assume the society is explicitly listed and rational numbers use binary numerator–denominator encodings. By the stated single-net NP-completeness premise, dominance on the prescribed class admits a polynomial-time verifier with polynomial-size certificates.

A certificate for the society problem specifies a subset \(S\subseteq\{1,\ldots,\tau\}\) and, for every \(t\in S\), a certificate that \(N_t\models o\succ o'\). The verifier checks these certificates and checks
\[ \sum_{t\in S}\mu_t\ge\theta. \]
There are at most as many selected types as explicitly listed types, so the total certificate length and verification time are polynomial in the input length. Exact rational summation and comparison also take polynomial time: a product of the input denominators has bit length at most the sum of their bit lengths.

For soundness, all certified types truly satisfy dominance, and nonnegativity of every weight gives
\[ \sum_{t=1}^{\tau}\mu_t\mathbf{1}[N_t\models o\succ o'] \ge\sum_{t\in S}\mu_t\ge\theta. \]
For completeness, whenever the target inequality holds, choose \(S\) to contain exactly the types satisfying dominance and provide their certificates.

Thus the problem is NP-complete under the usual explicit encoding, and a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The argument is correct. It establishes the requested NP-hardness and also establishes NP-completeness under the explicitly stated encoding assumptions. No major or minor issues were found.

• Use of the supplied single-net result.

The prover uses the NP-completeness premise supplied in USER_TASK: dominance testing for binary-valued, directed-path singly connected CP-nets is NP-complete. The class in this premise matches the class used throughout the reduction and the membership argument. No stronger structural or certificate assumption is introduced.

• Validity of the constructed society.

The construction sets \(\tau=1\), \(N_1=N\), \(\mu_1=1\), and \(\theta=1\). This is a valid rational finite-support distribution: its weight is nonnegative and sums to one. The CP-net is unchanged, so acyclicity, binary domains, and directed-path single connectivity are preserved.

• Correctness of the reduction.

For the constructed instance, the weighted sum equals \(\mathbf{1}[N\models o\succ o']\). This indicator is at least one exactly when dominance holds. Thus both yes-instances and no-instances are preserved. The direction of dominance is also preserved: the same ordered pair \((o,o')\) appears in both problems.

• Reduction complexity and NP-hardness.

Copying the original instance and adjoining a singleton-list wrapper and constant-size rational values takes polynomial time and space. The supplied single-net hardness result therefore proves NP-hardness of the society problem, already for singleton societies. This fully resolves the requested hardness alternative.

• Encoding assumptions for NP membership.

The prover expressly assumes an explicitly listed society and binary numerator–denominator encodings for rational data. Its NP-completeness conclusion is correspondingly qualified. These assumptions are sufficient for its input-length and arithmetic arguments; it does not claim membership for an unspecified succinct society representation.

• Certificate size and verification time.

The supplied single-net NP-membership premise provides a uniform polynomial-time verifier with polynomial-size certificates on the prescribed class. A selected subset contains at most \(\tau\) types. Under explicit listing, both \(\tau\) and every constituent instance length are bounded by the total input length. Consequently, the combined certificates and their verification have polynomial size and running time. There is no requirement to find the selected subset deterministically.

• Exact rational arithmetic.

The denominator bit-length bound is correct: the bit length of a product is bounded by the sum of the factor bit lengths. The corresponding numerator products, accumulated sum, and comparison with the rational threshold likewise have polynomial bit length. Thus exact summation and comparison can be performed in polynomial time.

• Soundness, completeness, and edge cases.

Soundness correctly uses nonnegative weights: omitting any types cannot increase the certified sum beyond the true sum. Completeness correctly selects all dominating types and uses their individual certificates; certificates of non-dominance are unnecessary.

Zero-weight types cause no difficulty. The empty subset is permitted, so nonpositive thresholds are handled. Thresholds above one cannot yield acceptance because the weights sum to one. None of these cases requires a change to the argument.

No additional clarification or repair is needed. The NP-hardness conclusion answers the target; the stronger NP-completeness conclusion holds under the stated explicit encoding.

⟨structured verdict parsed — rendered above⟩