

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

us say that the truth value true (resp. false ) is associated with [xt] (resp. [xf]). Then for every clause C i = ( lx Vly Vlz ) in F (where lx, ly, and lz are literals over variables x, y and z ), we add the 7 relation nodes typed C i , having as first argument [ xt ] or [ xf ], as sseeeeerrrrreeerrreeerreeerreeerreeerreeerreeerreeerreeerreeerreeerreeerreeerreeerreeerreeerreeerrreeerrreeerrreeerrreeerrreeerrreeerrreeerrrr evaluation of the clause to true (more precisely, if we replace in the clause C i each positive
(resp. negative) literal lj, 1 < j < 3, by the truth value (resp. the negation of the truth value) associated with the jth neighbor of the relation node, Cj is evaluated to true).

For clauses restricted to ( lx Vly ) or ( lx ), we proceed similarly, adding 3 binary relation nodes or one unary relation node. Note that having k -clauses, where k is a constant, is of primary importance to have a polynomial transformation, since we obtain 2 th - 1 relation nodes for each clause.

In the graph Q ( F ), two concept nodes [ x ] and [ xv ] are created for each variable x and a binary relation node (val) links [x] to [xv]. For each clause C i = ( x V ly V lz ), there is one relation (C i ) linked to [xv], [yv] and [zv] (and similarly for clauses with one or two literals). Q(F) represents the question "is there a valuation of the variables such that all clauses evaluate to true?"
This transformation from the 3-SAT formula ( a V b V ¬c) ∧ (¬a V c V ¬d ) is illustrated in Fig. 4. In the graph G, not all edges issued from the clauses have been drawn, for the sake of readability. It is immediate to check that, for a formula F, there is a valuation of its variables such that each clause is evaluated to true if and only if Q(F) can be projected into G(F).

□

## 2.4 A Note On Redundancy

Note that the subsumption relation induced by projection over SGs is a quasi-order, but not an order: it is a reflexive and transitive but not anti-symmetrical relation. Two SGs are said to be equivalent if they project to each other. A SG is said to be redundant if it is equivalent to one of its strict subgraphs (i.e. a subgraph not equal to G itself), otherwise it is said to be srredundant.

Theorem 3 (Chein & Mugnier, 1992) Redundancy checking is an NP-complete problem. Each equivalence class admits a unique (up to isomorphism) irredundant graph.

The irredundant form of a SG G is an irredundant subgraph of G equivalent to it (when G is irredundant, this graph is G itself, otherwise there may be several such subgraphs, but they are all isomorphic).