The fundamental task is to create a logical formula, $\varphi_G$, that is only true if a given directed graph, $G$, contains a "kernel". A kernel is a special subset of the graph's vertices. We can use a boolean variable, $v_i$, to represent the statement "vertex $i$ is in the kernel."

A set of vertices is a kernel if it satisfies two specific conditions:

Condition 1: Dominating SetRequiredRule

Every vertex that is not in the kernel must have an edge pointing to it from at least one vertex that is in the kernel.

Condition 2: Independent SetRequiredRule

No two vertices within the kernel are connected by an edge. If an edge goes from vertex $i$ to vertex $j$, they cannot both be in the kernel.

Our objective is to convert these two rules into a single logical expression in Conjunctive Normal Form (CNF), which is a series of clauses linked by AND ($\wedge$) operators.

How to Construct the Boolean Expression

This general method can be used to construct the boolean expression $\varphi_G$ for any directed graph.

1. Identify Vertices and Edges

   Begin by listing all vertices ($V$) and directed edges ($A$) of the graph. Each vertex $i \in V$ corresponds to a boolean variable $v_i$.

2. Formulate "Dominating Set" Clauses

   This step enforces the first condition. You must generate one clause for each vertex in the graph. The rule for any vertex $i$ is: "Vertex $i$ is in the kernel, OR at least one of its in-neighbours is in the kernel."

   This translates into the logical clause:

   $$(v_i \vee v_{j_1} \vee v_{j_2} \vee \dots)$$

   where $j_1, j_2, \dots$ are all the vertices that point to vertex $i$.

   Tips

   If a vertex $i$ has no incoming edges, its clause simplifies to just $(v_i)$. This logically forces it to be in the kernel to satisfy the condition.

3. Formulate "Independent Set" Clauses

   This step enforces the second condition. You must generate one clause for each edge in the graph. The rule for any edge from vertex $i$ to vertex $j$ is: "It is false that both vertex $i$ AND vertex $j$ are in the kernel."

   This translates into the logical clause:

   $$(\neg v_i \vee \neg v_j)$$

   A clause like this must be created for every edge in the graph.

4. Combine All Clauses

   The final expression, $\varphi_G$, is the logical AND ($\wedge$) of every clause generated in the previous two steps.

   $$\varphi_G = (\text{All Dominating Clauses}) \wedge (\text{All Independent Clauses})$$

Applying the Method to an Example Graph

Building an Expression for an Example Graph

Let's apply this method to the simple directed graph defined by 1 -> 2 <- 3.

1. Vertices and Edges

• Vertices $V$: $\{1, 2, 3\}$
• Edges $A$: $\{(1, 2), (3, 2)\}$

2. "Dominating Set" Clauses (One per vertex)

• Vertex 1 (In-neighbours: none): $(v_1)$
• Vertex 2 (In-neighbours: {1, 3}): $(v_2 \vee v_1 \vee v_3)$
• Vertex 3 (In-neighbours: none): $(v_3)$

3. "Independent Set" Clauses (One per edge)

• Edge (1, 2): $(\neg v_1 \vee \neg v_2)$
• Edge (3, 2): $(\neg v_3 \vee \neg v_2)$

4. Final Boolean Expression

By combining all five clauses, we get the complete logical expression for this graph.

Final Expression for the Example Graph

Boolean Expression $\varphi_G$

The complete CNF Boolean expression that is true if and only if the example graph has a kernel is:

$$\varphi_{G} = (v_1) \wedge (v_3) \wedge (v_2 \vee v_1 \vee v_3) \wedge (\neg v_1 \vee \neg v_2) \wedge (\neg v_3 \vee \neg v_2)$$

A General Method for Handling New Conditions

If a problem is modified with additional constraints, you can systematically update your logical formula without starting over. The modular nature of CNF is ideal for this.

Framework for Adding New Constraints

Translate each new rule into a CNF clause and append it to your main formula using an AND ($\wedge$) operator.

1. Deconstruct the New Rule

   State the new condition in plain English and identify which parts of the graph it affects.

   • Example Rule: "For our simple graph, vertex 2 is a special type that can never be in the kernel."

2. Translate to Propositional Logic

   Convert the English statement into a formal expression using your boolean variables ($v_i$).

   • Example Translation: The rule "vertex 2 can never be in the kernel" translates to:

     $$\neg v_2$$

3. Convert the Expression to a CNF Clause

   Ensure the expression is a disjunction (an OR) of literals. If it isn't, use logical equivalences to convert it.

   • Example Conversion: The expression $\neg v_2$ is already a literal, so its clause is simply:

     $$(\neg v_2)$$

4. Integrate the New Clause

   Append the new clause to your main formula using an AND ($\wedge$) operator. The entire expression, including the new constraint, must now be satisfied.

   • Example Integration: The formula for our example graph would be updated as follows:

     $$\varphi_{G}^{\text{new}} = \varphi_{G}^{\text{original}} \wedge (\neg v_2)$$

Changelog

9/7/25, 2:51 AM

View All Changelog

• 2d310-docs: understanding graphon 9/7/25

Copyright

Copyright Ownership:WARREN Y.F. LONG

License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)