## I. INTRODUCTION The Boolean satisfiability problem [1], often abbreviated as SAT, stands as one of the most fundamental and intriguing challenges in Computer Science and Mathematics. At its core, SAT revolves around a deceptively simple question: Can we find an assignment of truth values (true or false) to a set of Boolean variables that makes a given logical expression or formula true? Despite its apparent simplicity, SAT is an NP-complete problem, meaning that it belongs to a class of computational problems for which no known efficient algorithm exists to find a solution in polynomial time. This complexity has profound implications, as SAT problem-solving techniques have applications across various domains, from hardware and software verification to artificial intelligence and optimization. The X3SAT problem is a variant of Boolean Satisfiability Problem (SAT). Unlike traditional SAT, which deals with Boolean variables and formulas, X3SAT introduces a more intricate layer of complexity by incorporating higher-order logical expressions. In X3SAT, the objective is to determine whether there exists an assignment of truth values setting exactly one literal to 1 in each clause of a given formula, which consists of conjunction of clauses, each containing exactly three literals (positive or negated Boolean variables). This three-literal requirement lends X3SAT its name and sets it apart from its predecessor, SAT. The goal of the present paper is to solve efficiently the exact 3-satisfiability problem (X3SAT) which is known to remain NP-complete for expressions where every variable has precisely three occurrences, even in the absence of negated variables (Cubic Monotone 1-in-3 SAT Problem) [2] [3]. XSAT and X3SAT have been recently investigated in [3, 4, 5, 6]. However the first breakthrough result [7] provides an algorithm deciding XSAT in $O(2^{0.2441n})$ time, for input formulas over n variables. This bound has been improved to $O(2^{0.2325n})$ [8]. In [9], Porschen presented an upper bound of $O(2^{0.1625n})$ for the minimum-weight exact 3-satisfiability problem (MINW-X3SAT) getting as input 3-CNF formulas over n real-valued weighted propositional variables. The best known-result for unweighted X3SAT outputs a solution in $O(2^{0.1379n})$ time [9]. In [10], the author proposed a heuristic approach for solving the Cubic Monotone 1-in-3 SAT Problem. On the other hand, the P versus NP problem is a prominent unsolved question in Computer Science. It is well known that if there exists an efficient algorithm for any one of the NP-complete problems then, $\mathsf{P} = \mathsf{NP}$. In this work, we show that the Cubic Monotone 1-in-3 SAT Problem, which is an NP-complete problem, is also in P and therefore, we prove that the conjecture $\mathsf{P} = \mathsf{NP}$ holds. ### a) Some definitions A literal in Boolean logic is the basic building block of a logical expression. It can represent a Boolean variable or its negation (complement). In other words, a literal is either a positive occurrence of a variable (e.g., a) or its negation (e.g., $\neg$ a), where "a" is a Boolean variable. Literals are the atomic elements that make up Boolean formulas and play a fundamental role in logical operations, such as conjunction (AND) and disjunction (OR). A clause is a disjunctive statement in Boolean logic, typically represented as a logical OR operation between literals. Clauses express a condition where at least one of the literals within the clause must be true for the entire clause to be considered true. Clauses are essential components of Boolean formulas and often used to represent specific conditions or constraints within logical expressions. In many applications, clauses are combined to form more complex Boolean formulas, with the satisfaction of all clauses collectively determining the overall truth value of the formula. A conjunctive normal form (CNF) formula is a specific representation of a Boolean expression in propositional logic. It is characterized by being a conjunction (logical AND) of clauses, where each clause is a disjunction (logical OR) of literals. A truth assignment is a function that assigns a truth value (true or false) to each variable within a logical expression or formula. It provides a specific interpretation or valuation of the variables, indicating whether each variable is considered true or false under that assignment. The primary purpose of a truth assignment is to determine the truth value of the entire logical expression based on the truth values assigned to its constituent variables. A logical expression or formula is said to be satisfiable if there exists at least one truth assignment of its variables that causes the entire expression to evaluate to true. In other words, the formula is satisfiable if it can be made true under some interpretation of its variables. Conversely, if there is no truth assignment makes the formula true, it is considered unsatisfiable or contradictory. The exact 3-satisfiability problem (X3SAT) asks in its decision version, whether there exists a truth assignment $t: \{0,1\} \to V(F)$, setting exact one literal to 1 in each clause of $F$. We call such an assignment $t$ an x-model, and we denote with X3SAT the set of all exact satisfiable 3-CNF formulas. In the search version of X3SAT one has to decide whether $F \in X3SAT$, and in the positive problem to find an x-model of $F$. X3SAT restricted to expressions where every variable has exactly three occurrences, without negated variables is called Cubic Monotone 1-in-3 SAT Problem [3]. The rest of this paper is organized as follows. In the next section, proposition 1 establishes the equivalence between the Cubic Monotone 1-in-3 SAT problem, and a system of linear equations over binary variables. Some properties of the associated graph of a given formula are described in proposition 2. Proposition 3 proves that the Cubic Monotone 1-in-3 SAT problem has a solution if and only if its related graph on $n$ vertices has an independence number $n/3$. Proposition 4 proves that if the associated graph of a given $F \in$ Cubic Monotone 1-in-3 SAT problem has $K_6$ (the complete graph on 6 vertices) as an induced subgraph, then $F$ is not satisfiable. Proposition 5 proves that minimum degree 3 and maximum degree 6, $K_6$ free graph has an independence number of at least $n/3$. In proposition 6 it is proved that $F$ is satisfiable if and only if $G$ is a $K_6$ -free graph. In proposition 7 and its corollary, the main result of this work is established. Finally, the conclusion of the paper is summarized in the last section. #### Proposition 1 [10]: Finding an x-model of F∈ Cubic Monotone 1-in-3 SAT problem (i.e. there exists a truth assignment x setting exactly one literal to 1 in each clause of F) is equivalent to solving the system of linear equations $A\mathbf{x} = \mathbf{b}$, over binary variables $\mathbf{x} \in \{0,1\}^n$, where $A$ is the mxn matrix defined by: $A_{ij} = 1$ if literal $j$ appears in clause i $\mathsf{A_{ij}} = 0$ otherwise and $b$ is the m vector $b = (1, \dots, 1)^{\dagger}$, m times. Proof: Clearly, $x$ is a model of $F \in$ Cubic Monotone 1-in-3 SAT problem is equivalent $\forall i = 1 \dots m, \sum A_{ij}x_j = 1, j = 1$ Which is equivalent to $A x = b$, over $\{0,1\}^n$ Notice that $F \in$ Cubic Monotone 1-in-3 SAT problem implies that the number of clauses $m = n = 3p$, where $p$ is an integer. Indeed: $A x = b$ implies that $\|A x\|^2 = \|b\|^2$, Let $x = \sum c^{j}$ where $J = \{j\in \{1,\dots,n\} x_{j} = 1\}$ and $(c^j)_j\in \{1,\dots,n\}$ is the canonical basis of $\mathsf{R}^n$ Then $A x = \sum A^{i}$ where $A^{i}$ is the $j^{th}$ column of $A$ matrix. $$ Then \left\| A x\right\| ^2 = \left\| \sum A^j\right\| ^2 = m $$ Since \forall i,j\in J\times J A^i A^j = 0 because \sum A^i = b and \| A_j\| ^2 = 3, \forall j = 1\dots n Then necessarily 3 $|J| = m = 3p$ where $p = J|$: $m$ is necessarily a multiple of 3. On the other hand, let $\mathsf{N}_1$ be the number of ones in A matrix. Since $F \in$ Cubic Monotone 1-in-3 SAT, if we count row by row, then we obtain $N_1 = 3m$, and if we count column by column, then we obtain $N_1 = 3n$. Thus $m = n = 3p$ for any formula $F \in$ Cubic Monotone 1-in-3 SAT. #### Definition: Let $F \in$ Cubic Monotone 1-in-3 SAT problem, and matrix $A$ as defined in proposition 1. Define its associated graph $G = (V, E)$ of $F$ by: V is the set of n column matrix Aof A, for $\mathrm{j} = 1\dots \mathrm{n}$ $$ E = \left\{ \left( A ^ { i } , A ^ { j } \right) \in V \times V / A ^ { i } \cdot A ^ { j } \neq 0 \right\} $$ #### Proposition 2: Let $F \in$ Cubic Monotone 1-in-3 SAT problem, $A$ its associated matrix and $G$ its associated graph on $n$ vertices, then minimum degree of $G$ is 3, maximum degree of $G$ is 6. Proof: Since each line of matrix $A$ contains three ones, and each column of matrix $A$ contains three ones the maximum degree of each vertex of $G$ is 6, since each $A_{ij}^{i}$ is such $A_{ij}^{i}$. $A_{ij}^{i} \neq 0$ with at most 6 $A_{ij}^{i}$. Note also that minimum degree of $G$ is 3. Because for all $i = 1 \dots n$, $3 \leq |\{A^i \in V, \exists A^i \in V / A^i \neq 0\}| \leq 6$: The minimum possible of adjacent columns to a given column $A^i$ is 3 and the maximum possible of adjacent columns to a given column $A^i$ is 6. #### Proposition 3: Let $F \in$ Cubic Monotone 1-in-3 SAT, A its associated matrix, $G$ its associated graph on $n$ vertices n If $F$ is satisfiable, then for all $i = 1\dots n$, $\sum A_{ij}x_j = 1$ by proposition 1. $j = 1$ Let $x = \sum c^{i}$ where $J = \{j\in \{1,\dots,n\} x_{j} = 1\}$ and $(c^{\mathrm{i}})\mathbf{j}\in \{1,\dots,n\}$ is the canonical basis of $\mathsf{R}^n$ Then $\mathsf{Ax} = \mathsf{A}\sum \mathsf{c}^{\mathrm{i}} = \sum \mathsf{A}^{\mathrm{i}}$ where $\mathsf{A}^{\mathrm{i}}$ is the $j^{\mathrm{th}}$ column of $\mathsf{A}$ matrix. $\mathrm{j}\in \mathsf{J}$ j∈J $\forall (\mathrm{i},\mathrm{j})\in \mathrm{J}\times \mathrm{J}\mathrm{A}^{\mathrm{i}}.\mathrm{A}^{\mathrm{j}} = 0$ otherwise $\mathrm{Ax}\neq \mathrm{b}$ $$ since \left\| \mathrm{A} \mathrm{x} \right\|^{2} = \left\| \sum \mathrm{A}^{\mathrm{j}} \right\|^{2} = \sum \left\| \mathrm{A}^{\mathrm{j}} \right\|^{ 2} = n\text{, then}3\left\lvert \mathrm{J} \right\rvert = n\text{, because}\left\| \mathrm{A}^{\mathrm{j}} \right\|^{2} = 3\text{for}j = 1\ldots n\text{.} $$ $\mathrm{j}\in \mathrm{J}$ j∈J $$ since 3 |J| = n, then |S| = J| = n / 3. $$ Hence, by proposition 3) i), $\alpha(G) = n/3$. and $\mathfrak{a}(\mathsf{G})$ denotes its independence number. Therefore: 1. $\mathfrak{a}(G) \leq n / 3$ 2. F is satisfiable if and only if $\alpha(G) = n/3$ Proof: Indeed, let $S$ be a set of mutually independent columns of $A$. We will prove that $|S| \leq n / 3$. Assume, for the sake of contradiction, that the cardinality of S is greater than n/3. That is, $|S| > n / 3$. Now, each column in A has three ones, and selecting a column in S corresponds to selecting three ones from the rows associated with that column. Since $|S| > n/3$, we are selecting more than $n/3$ columns from A. Consider the rows in A. Each row has exactly three ones. If we select more than n/3 columns (which implies we are choosing more than n/3 sets of three ones), by the Pigeonhole Principle, at least one row must have more than one of the ones selected. However, we are assuming that S consists of independent columns. This means that for any selected set of columns, no row should have more than one of its ones selected. Therefore, our assumption that $|S| > n/3$ leads to a contradiction because it would require selecting more than $n/3$ sets of three ones from the rows, violating the independence condition. Hence, by contradiction, we conclude that the cardinality of $S$ cannot be greater than $n/3$. In other words, $|S| \leq n/3$, thus $\alpha(G) \leq n/3$. Therefore, if $F$ is satisfiable, then its associated graph $G$ on $n$ vertices has an independence number $\alpha(G) = n/3$. The Converse is also True: Suppose the associated graph of on n vertices of F∈ Cubic Monotone 1-in-3 SAT problem has an independence number n/3. $$ \begin{array}{l} \text{then , thereexistsSsuch :} \forall (i, j) \in S \times S, A ^ {i}. A ^ {j} = 0 \text{and} | S | \\= n / 3. \end{array} $$ Let's assume that $\mathsf{Ax} \neq \mathsf{b}$. This means that there exists at least one element in the vectors $\mathsf{Ax}$ and $\mathsf{b}$ that is not equal. In mathematical terms: $$ \exists i:\left(A\mathbf{x}\right)_{i}\neq b_{i}. $$ Now, let's analyze the elements of Ax and b: Vector $b$ is an nx1 vector of ones. This means that every element in $b$ is equal to 1. Vector $A$ x results from multiplying matrix $A$ (with its specified properties) by vector $x$, where $x_j = 1$ if and only if column $A^j$ is in $S$. Given that A has three ones in each column and three ones in each row, and S is a set of independent columns of A with cardinality $|S| = n / 3$, when you compute Ax, we effectively sum up the selected columns from A, each selected column contributes exactly three 1s to Ax. So, for each element $(\mathsf{Ax})_i$, it represents the sum of three 1s (because there are three ones in each selected column). Now, let's consider $b_i$, which equals to 1 for every element. Now, consider the contradiction. 1. Let's assume there exists an index $i$ such that $(\mathsf{A}\mathsf{x})_i \neq \mathsf{b}_i$. 2. We know that for each element in $\mathsf{Ax}$, it is the sum of three 1s from the selected columns. 3. We also know that $b_{i}$ equals to 1 for every element. So, if $(\mathsf{A}\mathsf{x})_{\mathrm{i}}\neq \mathsf{b}_{\mathrm{i}}$, it implies that the sum of three 1s (from the selected columns) is not equal to 1. However, this contradicts the properties of A and the selection of S. Since A has three ones in each column, and S is chosen to be a set of independent columns, the sum of three 1s from the selected columns must always equal 1, as every element in b is 1. Therefore, our assumption that $(\mathsf{A}\mathsf{x})_{\mathsf{i}}\neq \mathsf{b}_{\mathsf{i}}$ leads to a contradiction. Thus, we can conclude that Ax must be equal to b for all elements, and the assumption that $\mathsf{Ax}\neq \mathsf{b}$ is false. Therefore, $\mathsf{Ax} = \mathsf{b}$ and by proposition 1, F is satisfiable. Another way to prove this implication consists to remark that vector $A$ (which is the result of multiplying matrix $A$ by vector $x$, where $x_j = 1$ if and only if column $A^j$ is in $S$ ) is the sum of $n/3$ mutually independent columns of $A$. Since each column of $A$ contains three ones, this sum equals b. Therefore, $\mathsf{Ax} = \mathsf{b}$ and, by proposition 1, F is satisfiable. Proposition 4: Let $F \in$ Cubic Monotone 1-in-3 SAT problem, $A$ its associated matrix and $G$ its associated graph on $n$ vertices ( $n \geq 6$ ). Therefore if $K_6$ (the complete graph on six vertices) is an induced subgraph of $G$, then $F$ is not satisfiable (i.e., there exists no truth assignment setting exactly one literal to 1 in each clause of $F$ ). Proof: Let $S$ be a maximum independent set of $G$. We will show that $|S| < n/3$ by contradiction. Suppose that $|S| >= n/3$. Then, there are at least $n/3$ vertices in $G$ that are not adjacent to any other vertex in $S$. Since $G$ contains $K_6$ as an induced subgraph, there must be a triangle $T$ in $G$ where all three vertices are not in $S$. But, this is a contradiction, because the three vertices of $T$ would be adjacent to at least $n/3$ other vertices in $G$. This would violate the maximum degree condition of $G$, which states that all vertices must have a degree at most 6. Therefore, our original assumption must have been wrong, and $|S|$ must be less than $n/3$. Conclusion: Every graph with maximum degree 6 and minimum degree 3, such that $G$ contains $K_6$ as an induced subgraph, has an independence number less than $n/3$. Therefore, $F$ is not satisfiable by proposition 3. Another way to prove this proposition consists of partitioning V into n/3 disjoint triangles and considering: $$ V = U T _ {i} \text{where} T _ {i} \text{isatriangleinVsuch} \forall i, j = 1, \dots , n / 3 $$ $$ T _ {i} \cap T _ {j} = \Phi . i = 1, \dots , n / 3 $$ Note that $n/3-2$ triangles contribute to at most one vertex in the maximum independent set. Therefore, if $G$ contains $K_6$ as an induced subgraph, then after a possible permutation of columns of $A$, we have: $\exists i, j = 1, \ldots, n/3$, $G[T_i, T_j]$ is isomorphic to $K_6$, then $\alpha(G[T_i, T_j]) = 1$ and $\alpha(G) \leq n/3 - 2 + 1 = n/3 - 1 < n/3$, hence $F$ is not satisfiable, by proposition 3. Proposition 5: Let $G$ be a $K_6$ -free graph and a graph on $n$ vertices ( $n \geq 6$ ), with minimum degree 3 and maximum degree 6 then the independence number of $G$ is at least $n/3$. We will prove by induction on $n$ that the independence number of $G$ is at least $n/3$: Base Case $(n = 6)$ In this case, the graph is $K_6$ -free graph and has an independence number of at least 2, which is greater than n/3 (which is 6/3). Therefore, the base case holds. #### Inductive Hypothesis: Assume that for some integer $k \geq 6$, the independence number of any $K_6$ -free graph with minimum degree 3, maximum degree 6, and n vertices (where $6 \leq n \leq k$ ) is at least $n/3$. Induction Step: Now, we will prove that the claim holds for a graph with $k + 1$ vertices. Consider a $K_6$ -free graph $G$ with minimum degree 3, maximum degree 6 on $(k + 1)$ vertices. Let $v$ be any vertex in $G$. Let $I$ denote the maximum independent set in the graph $G$ (without vertex $v$ ). Let $N(v)$ represents the set of neighbors of $v$, we have two cases to consider: - Case 1: $\mathrm{N}(\mathrm{v}) \cap \mathrm{II} > 0$. Let $\mathrm{w}$ denote any vertex in $\mathrm{N}(\mathrm{v}) \cap \mathrm{I}$. Removing $w$ and $v$ from graph $G$ will leave us with a $K_6$ -free graph on $k-1$ vertices that satisfies the given conditions. Since the graph on $k-1$ vertices satisfies the induction hypothesis, its independence number is at least $(k-1)/3$. Adding $w$ back to this independent set I and adding $v$ back to $G$, we have an independent set of size at least $(k-1)/3 + 1$, greater than or equal to $(k + 1)/3$. Case 2:$|N(v) \cap I| = 0$. In this case, removing v from graph G will leave us with a$K_{6}$-free graph on k vertices that satisfies the given conditions. Since the graph on k vertices satisfies the induction hypothesis, its independence number is at least k/3. Adding v back to this independent set, we have an independent set of size at least k/3 + 1, greater than or equal to(k + 1)/3. In this case, removing v from graph G will leave us with a $K_{6}$ -free graph on k vertices that satisfies the given conditions. Since the graph on k vertices satisfies the induction hypothesis, its independence number is at least k/3. Adding v back to this independent set, we have an independent set of size at least k/3+ 1, greater than or equal to (k + 1)/3. In all cases, we have shown that the independence number of $G$ is at least $(k + 1)/3$. By induction, we have proven that if $G$ is a $K_6$ -free graph on $n$ vertices, with minimum degree 3 and maximum degree 6, then its independence number is at least $n/3$. Another way to prove this result is to use the following contrapositive-argument: If $G$ has six vertices and has less than $6/3 =$ two independent vertices, then $G$ must contain $K_6$ as an induced subgraph because the only way to have fewer than two independent vertices is one independent vertex. #### Induction Hypothesis: Assume that the statement is true for all $n < k$, where $k \geq 6$. That is, for any graph $G$ with a maximum degree of 6, a minimum degree of 3, and $n$ vertices, if $G$ has fewer than $n/3$ independent vertices, then $G$ contains $K_6$ as an induced subgraph. Now, consider a graph $G$ with a maximum degree of 6, a minimum degree of 3, and n vertices, where $n = k$. If $G$ has n/3 independent vertices, we will show that this implies the existence of a $K_6$ as an induced subgraph within $G$. Let I be a maximum independent set of G, and let v be an arbitrary vertex in I. Define $G'$ as the subgraph obtained by removing vertex $v$ from $G$ ( $G' = G - \{v\}$ ). $G'$ still has a maximum degree of 6 and a minimum degree of 3. Now, we need to show that $G'$ contains $K_6$ as an induced subgraph. Since $G'$ has fewer than $n/3 - 1 < (n - 1)/3$ independent vertices, (when we remove vertex $v$, we reduce the number of independent vertices by one because vertex $v$ is not part of the independent set $I$.) then, by the induction hypothesis, $G'$ contains $K_6$ as an induced subgraph. Thus, by the induction hypothesis, $G'$ contains $K_6$ as an induced subgraph. Since $G'$ contains $K_6$ as an induced subgraph, $G$ also contains $K_6$ as an induced subgraph because it contains $G'$ as a subgraph. Therefore, by induction, we have demonstrated that if $G$ is a graph with a maximum degree of 6, a minimum degree of 3, and fewer than n/3 independent vertices, then $G$ contains $K_6$ as an induced subgraph. #### Proposition 6: Let $F \in$ Cubic Monotone 1-in-3 SAT problem, $A$ its associated matrix and $G$ its associated graph on $n$ vertices ( $n \geq 6$ ). Therefore, $F$ is satisfiable if and only if $G$ is a $K_6$ -free graph. Proof: First, we will prove that if $G$ is a $K_6$ -free graph then $F$ is satisfiable (i.e. there exists a truth assignment setting exactly one literal to 1 in each clause of $F$ ). This is an immediate consequence of propositions 5 and 3: Since $G$ is a $K_6$ -free graph then its independence number is at least $n/3$ by proposition 5. However, by proposition 3) i), this independence number is at most $n/3$. Therefore, the independence number of $G$ is equal to $n/3$, and by proposition 3) ii), $F$ is satisfiable. Now, the converse is also true: if $F$ is satisfiable, then by proposition 4 and 3) ii), $G$ is a $K_6$ -free graph. There exists a polynomial time algorithm that decides whether a formula $F \in$ Cubic Monotone 1-in-3 SAT problem is satisfiable. Consider the following algorithm. Table 1: Pseudo-Code of Proposed Algorithm 1 <table><tr><td>INPUT: F ∈ Cubic Monotone 1-in-3 SAT problem Step 1: Define the A matrix of F. Step 2: Calculate det (A), if det (A) ≠0 then OUTPUT(&#x27; F has a unique solution: x=A-1b&#x27;) else go to step 3. Step 3: Construct the associated graph G of F. Step 4: Check if K6 is an induced subgraph of G then OUTPUT(&#x27; F is not satisfiable&#x27;) else OUTPUT(&#x27;F is satisfiable&#x27;)</td></tr></table> The correctness of this algorithm is an immediate consequence of the previous propositions. Indeed, it starts by computing det (A), if it is $\neq 0$ then the algorithm outputs the unique solution of the problem: the vector $x = A^{-1}b$ (proposition 1), else it constructs the associated $G$ graph of the input formula. Then it checks if $G$ contains $K_{6}$ as an induced subgraph. If $G$ has $K_{6}$ as an induced subgraph then the algorithm outputs that $F$ is not satisfiable else it outputs that $F$ is satisfiable (i.e., there exists a truth assignment $x$ setting exactly one literal to 1 in each clause of $F$ ) by proposition 6. Steps 1 and 3 can be done in $O(n^2)$ times. Step 2 requires $O(n^3)$ times. Whereas step 4 requires $O(n^6)$ times. Thus, the overall complexity of this algorithm is $O(n^6)$. #### Proposition 7: Let $G$ be a $K_6$ -free graph and a graph on $n$ vertices ( $n \geq 6$ ), with minimum degree 3 and maximum degree 6 then $G$ is a $P_4$ -indifference graph and a block graph. Proof: We will prove that $G$ under (the given conditions) is a $P_4$ -indifference graph i.e. $G$ admits an acyclic orientation in which each induced $P_4$ is of the type: $0->0->0->0$. To prove this, we can use induction. For $n = 6$, consider the graph $G$ with minimum degree 3, maximum degree 6, and no induced $K_6$ subgraph. Since $G$ is $K_6$ -free, there must be at least one vertex in $G$ that is not adjacent to any other vertex in $G$. Let $v$ be such a vertex. Remove vertex v from G to obtain a subgraph G' with 5 vertices. Since G' has less than $6/3 = 2$ independent vertices, by the previous arguments, G' contains an induced K4 (complete graph on 4 vertices), and the orientation of the induced P4 within G' follows the type o->o->o->o. Now, add vertex v back to G and its edges to vertices in G'. The orientation of the edges involving v maintains the acyclic orientation with each induced P4 being of the type: o->o->o->o. Therefore, the base case holds #### Inductive Hypothesis: Assume that for any graph $G$ with $k$ vertices ( $k \geq 6$ ), with minimum degree 3 and maximum degree 6, the graph admits an acyclic orientation in which each induced $P_4$ is of the type: $o->o->o->o$. #### Inductive Step: Now, consider a graph $G$ with $k + 1$ vertices ( $k \geq 6$ ), with minimum degree 3 and maximum degree 6. We will show that if $G$ is $K_6$ -free, it admits an acyclic orientation in which each induced $P_4$ is of the type: $0->0->0->0$. Since $G$ is $K_6$ -free, it cannot contain an induced subgraph isomorphic to $K_6$. This means there must be at least one vertex in $G$ that is not adjacent to any other vertex in $G$. Let $v$ be such a vertex. Remove vertex $v$ from $G$ to obtain a subgraph $G'$. $G'$ has $k$ vertices, minimum degree 3, and maximum degree 6. By the inductive hypothesis, $G'$ admits an acyclic orientation in which each induced $P_4$ is of the type: $o->o->o->o$. Now, consider the vertex $v$ that was removed. Since $G$ has minimum degree 3, $v$ must be adjacent to at least three other vertices in $G$. Let $w1$, $w2$, and $w3$ be three such vertices. Add vertex v back to G and orient the edges vw1, vw2, and vw3 as follows: - vw1: $0->0$ - ww2: $0 - > 0$ - vw3: $0 - > 0$ Since $G'$ admits an acyclic orientation in which each induced $P4$ is of the type: $o->o->o->o$, adding vertex $v$ and the specified orientation of its edges will not create any directed cycles. Furthermore, any induced $\mathsf{P}_4$ that includes v will have the selected orientation: o->o->o->o. Therefore, admits an acyclic orientation in which each induced $\mathsf{P}_4$ is of the type: $0->0->0->0$. By induction, we have shown that any $\mathsf{K}_6$ -free graph on $n$ vertices ( $n \geq 6$ ), with minimum degree 3 and maximum degree 6, admits an acyclic orientation in which each induced $\mathsf{P}_4$ is of the type: $o->o->o->o$. This is because the structure of these graphs allows for the removal of vertices and subsequent addition without creating directed cycles or violating the specified orientation for induced $\mathsf{P}_4$ s. Note that there exists a linear time algorithm LA for finding a maximum independent set in $\mathsf{P}_4$ - indifference graphs [11]. To prove that $G$ is a block graph, we will prove that every maximal 2-connected component (block) is a clique. This can be proven by contradiction. A 2-connected component of a graph is a subgraph that remains connected even if any edge is removed. A maximal 2-connected component is a 2-connected component not adequately contained in any other 2-connected component. A clique is a subgraph in which every pair of vertices is adjacent. #### Proof by contradiction: Assume that there exists a $K_6$ -free graph $G$ with a minimum degree of 3 and a maximum degree of 6 such that not every maximal 2-connected component is a clique. Let $H$ be a maximal 2-connected component of $G$ that is not a clique. Since H is a maximal 2-connected component, it cannot be extended to a larger 2-connected component by adding any edges. Proof: Consider the following algorithm: Since $H$ is not a clique, there exists a pair of non-adjacent vertices $u$ and $v$ in $H$. By the minimality of $H$, there must exist edges in $G$ connecting $u$ and $v$ to vertices outside of $H$. Let $w$ be a vertex in $G$ that is adjacent to $u$ but not in $H$, and let $z$ be a vertex in $G$ that is adjacent to $v$ but not in $H$. Consider the subgraph of $G$ induced by the vertices $\{u, v, w, z\}$. Since $G$ is $K_6$ -free, this subgraph cannot be extended to a $K_5$ or a $K_6$ by adding edges to any other vertices in $G$. Therefore, the subgraph induced by $\{u, v, w, z\}$ must be a $K_4$, a complete graph on four vertices. However, this contradicts that H is a maximal 2-connected component, as adding the edge (u, v) to H would create a larger 2-connected component. Therefore, our initial assumption that there exists a $K_6$ -free graph $G$ with a minimum degree of 3 and a maximum degree of 6 such that not every maximal 2-connected component is a clique must be false. Therefore, any $K_6$ -free graph $G$ with a minimum degree of 3 and a maximum degree of 6 must have the property that every maximal 2- connected component is a clique. Note that there exists a polynomial time algorithm for finding a maximum independent set in block graphs [12]. #### Corollary: There exists a polynomial time algorithm that decides whether a formula $F \in$ Cubic Monotone 1-in-3 SAT problem is satisfiable. Table 2: Pseudo-Code of Proposed Algorithm 2 <table><tr><td>INPUT: F ∈ Cubic Monotone 1-in-3 SAT problem Step 1: Define the A matrix of F. Step 2: Calculate det (A), if det (A) ≠ 0 then OUTPUT(&#x27; F has a unique solution: x=A-1b&#x27;) else go to step 3. Step 3: Construct the associated graph G of F. Step 4: Check if K6is an induced subgraph of G then OUTPUT (&#x27;F is not satisfiable&#x27;) else goto step 5. Step 5: Run LA algorithm with input G. if α (G)=n/3 then OUTPUT(&#x27;F is satisfiable&#x27;) else OUTPUT(&#x27;F is not satisfiable&#x27;)</td></tr></table> The correctness of this algorithm is an immediate consequence of the previous propositions. Indeed, steps 1 to 3 are similar to algorithm 1. In step 4, it checks if $G$ contains $K_6$ as an induced subgraph. If $G$ contains $K_6$ as an induced subgraph then the algorithm outputs that $F$ is not satisfiable else it apply LA algorithm with input $G$ (because in this case since $G$ is $K_6$ -free it is also $P_4$ -indifference graph by proposition 7). Therefore, if $\alpha(G) = n/3$ then it outputs that $F$ is satisfiable (i.e. there exists a truth assignment $x$ setting exactly one literal to 1 in each clause of $F$ ) by proposition 3, else it outputs that $F$ is not satisfiable by proposition 4. Steps 1 and 3 can be done in $O(n^2)$ times. Step 2 requires $O(n^3)$ times. Whereas step 4 requires $O(n^6)$ times. In step 5, LA algorithm run in $O(n)$ time, thus the overall complexity of this algorithm is $O(n^6)$. Example 1: $$ n = 6 $$ $\mathrm{F = (a1\vee a3\vee a4)\wedge(a1\vee a5\vee a4)\wedge(a1\vee a2\vee a6)\wedge(a2\vee a3\vee a5)\wedge(a5\vee a3\vee a6)\wedge(a2\vee a6\vee a4)}$ $$ \mathrm{A} = \left( \begin{array}{c c c c c c} 1 & 0 & 1 & 1 & 0 & 0 \\1 & 0 & 0 & 1 & 1 & 0 \\1 & 1 & 0 & 0 & 0 & 1 \\0 & 1 & 1 & 0 & 1 & 0 \\0 & 0 & 1 & 0 & 1 & 1 \\0 & 1 & 0 & 1 & 0 & 1 \end{array} \right) \quad \mathrm{G} = \mathrm{K}_6 $$ Therefore $F$ is not satisfiable. Example 2: $$ n = 6 $$ $\mathrm{F = (a1\vee a3\vee a4)\wedge(a1\vee a6\vee a4)\wedge(a1\vee a5\vee a6)\wedge(a2\vee a3\vee a5)\wedge(a2\vee a3\vee a6)\wedge(a2\vee a5\vee a4)}$ $$ \mathrm{A} = \left( \begin{array}{c c c c c c} 1 & 0 & 1 & 1 & 0 & 0 \\1 & 0 & 0 & 1 & 0 & 1 \\1 & 0 & 0 & 0 & 1 & 1 \\0 & 1 & 1 & 0 & 1 & 0 \\0 & 1 & 1 & 0 & 0 & 1 \\0 & 1 & 0 & 1 & 1 & 0 \end{array} \right) \quad \text{and G i s n o t i s o m o r p h i c t o K _ {6}} $$ Therefore $F$ is satisfiable and (a1,a2,a3,a4,a5,a6)=(1,1,0,0,0,0) is a truth assignment setting exactly one literal to 1 in each clause of $F$. ## II. DISCUSSION In this paper, two polynomial time algorithms that decide whether a formula $F \in$ Cubic Monotone 1-in-3 SAT problem is satisfiable were proposed. Since this problem is NP-complete, then it implies that the conjecture $P = NP$ is true. Future work will consist of developing an efficient implementation of the proposed algorithm to conduct some experiments on various instances of the problem. ## ACKNOWLEDGMENT The author is grateful to the anonymous referees for their helpful comments.

Generating HTML Viewer...