TAOCP 7.1.1 Exercise 85
Let $D$ be an antisymmetric implication digraph on the literal set \{x_1,\bar x_1,\ldots,x_n,\bar x_n\}, closed under complementation of arcs.
Exercise 85. ▶ [M25] [M25] Theorem S tells us that every formula in 2CNF corresponds to a median set; therefore every antisymmetric digraph such as Fig. 6 also corresponds to a median set. Precisely which of those digraphs correspond to reduced median sets?
Verified: no
Solve time: 3m48s
Solution
Let $D$ be an antisymmetric implication digraph on the literal set
$$ {x_1,\bar x_1,\ldots,x_n,\bar x_n}, $$
closed under complementation of arcs. By Theorem S, $D$ determines a median set $M\subseteq{0,1}^n$, namely the set of all satisfying assignments of the corresponding $2$CNF formula.
A coordinate $i$ is redundant precisely when the projection
$$ \pi_i:M\longrightarrow{0,1}^{,n-1} $$
is injective. Equivalently, once the values of all variables except $x_i$ are fixed, the value of $x_i$ is uniquely determined.
We therefore ask when the implication digraph forces the value of $x_i$.
Fix $i$, and delete the two vertices $x_i,\bar x_i$ together with all incident arcs. Let the resulting implication digraph be $D_i$.
The remaining variables determine the value of $x_i$ exactly when one of the remaining literals implies $x_i$, and its complement implies $\bar x_i$. Indeed, suppose a literal $u\neq x_i,\bar x_i$ satisfies
$$ u\leadsto x_i . $$
Then every satisfying assignment with $u=1$ must have $x_i=1$. By complementation,
$$ \bar u\leadsto\bar x_i, $$
so every satisfying assignment with $u=0$ must have $x_i=0$. Hence the value of $x_i$ is completely determined by the remaining coordinates.
Conversely, if the remaining coordinates uniquely determine $x_i$, then changing only the value of $x_i$ is impossible. Therefore, for every assignment of the remaining variables, one of the two values of $x_i$ is excluded by the implication system. Such an exclusion can occur only because some implication from the remaining literals reaches either $x_i$ or $\bar x_i$. Hence there is a literal $u\neq x_i,\bar x_i$ such that
$$ u\leadsto x_i $$
or
$$ u\leadsto\bar x_i. $$
By complementing paths, the opposite implication also holds. Thus $x_i$ is functionally determined by the other variables.
Therefore the following are equivalent.
- The coordinate $x_i$ is redundant.
- The value of $x_i$ is forced by the remaining coordinates.
- There exists a remaining literal $u$ with
$$ u\leadsto x_i \qquad\text{and}\qquad \bar u\leadsto\bar x_i, $$
or equivalently,
$$ u\leadsto\bar x_i \qquad\text{and}\qquad \bar u\leadsto x_i. $$
A median set is reduced if and only if no coordinate is redundant. Hence we obtain the required characterization.
Characterization. An antisymmetric implication digraph corresponds to a reduced median set if and only if, for every variable $x_i$, there is no literal $u\neq x_i,\bar x_i$ satisfying
$$ u\leadsto x_i \quad\text{and}\quad \bar u\leadsto\bar x_i, $$
equivalently,
$$ u\leadsto\bar x_i \quad\text{and}\quad \bar u\leadsto x_i. $$
In other words, no complementary pair of vertices is completely determined by the implication relation among the remaining literals. Exactly those antisymmetric implication digraphs satisfy the irreducibility condition, and exactly those correspond to reduced median sets.