patternMinor
MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?
Viewed 0 times
satxorarehardminmaxandthey
Problem
What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$? Are they in P? Are they NP-hard?
To formalize this more precisely, let
$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$$
where $\mathbf{x} = (x_1,\dots,x_m)$ and each clause $C_i$ is of the form $(x_i \oplus x_j)$ or $(x_i \oplus \neg x_j)$.
The $\text{2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that satisfies $\Phi$. This problem is in $P$, as it corresponds to a system of linear equations mod $2$.
The $\text{MAX-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that maximizes the number of clauses that are satisfied. The $\text{MIN-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that minimizes the number of clauses that are satisfied. What are the complexities of these problems?
Inspired by Is MIN or MAX-True-2-XOR-SAT NP-hard?
To formalize this more precisely, let
$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$$
where $\mathbf{x} = (x_1,\dots,x_m)$ and each clause $C_i$ is of the form $(x_i \oplus x_j)$ or $(x_i \oplus \neg x_j)$.
The $\text{2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that satisfies $\Phi$. This problem is in $P$, as it corresponds to a system of linear equations mod $2$.
The $\text{MAX-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that maximizes the number of clauses that are satisfied. The $\text{MIN-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that minimizes the number of clauses that are satisfied. What are the complexities of these problems?
Inspired by Is MIN or MAX-True-2-XOR-SAT NP-hard?
Solution
Sorry for answering an old post
The problem of determining if a MONOTONE-2-XOR-SAT (all clauses are of the kind $({x_i}\oplus x_j)$) instance is satisfiable can be reduced to the problem of determining if a graph is bipartite, see this.
To do that we create a graph $G$ with a node for each literal of the formula and we connect each literal with another if they are in the same clause (edges are clauses)
For instance:
If we have an unsatisfiable formula that is $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_3) \wedge({x_2}\oplus x_3) \wedge ({x_1}\oplus x_4) $
We have a graph like this:
that is not bipartite
There are three clauses that are satisfiable and so we have just to eliminate an edge
Now, we can reduce the problem of determining if we can find a maximum bipartite subgraph with $k$ vertex to the problem of determining if we can satisfy $k$ clauses in a MONOTONE-MAX-2XOR-SAT formula, see this. And the maximum bipartite subgraph problem is equivalent to max cut
To do the reduction we simply create a new literal for each vertex and we create a clause for each edge connecting two literals
For instance:
We have this graph,
We create the follwing formula $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_4) \wedge({x_2}\oplus x_4) \wedge ({x_2}\oplus x_3) \wedge ({x_4}\oplus x_5) \wedge ({x_3}\oplus x_5) $
So, if we can find an assignment that satisfies $k$ clauses that will mean that there is a bipartite subgraph with at least $k$ edges.
The problem of determining if a MONOTONE-2-XOR-SAT (all clauses are of the kind $({x_i}\oplus x_j)$) instance is satisfiable can be reduced to the problem of determining if a graph is bipartite, see this.
To do that we create a graph $G$ with a node for each literal of the formula and we connect each literal with another if they are in the same clause (edges are clauses)
For instance:
If we have an unsatisfiable formula that is $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_3) \wedge({x_2}\oplus x_3) \wedge ({x_1}\oplus x_4) $
We have a graph like this:
that is not bipartite
There are three clauses that are satisfiable and so we have just to eliminate an edge
Now, we can reduce the problem of determining if we can find a maximum bipartite subgraph with $k$ vertex to the problem of determining if we can satisfy $k$ clauses in a MONOTONE-MAX-2XOR-SAT formula, see this. And the maximum bipartite subgraph problem is equivalent to max cut
To do the reduction we simply create a new literal for each vertex and we create a clause for each edge connecting two literals
For instance:
We have this graph,
We create the follwing formula $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_4) \wedge({x_2}\oplus x_4) \wedge ({x_2}\oplus x_3) \wedge ({x_4}\oplus x_5) \wedge ({x_3}\oplus x_5) $
So, if we can find an assignment that satisfies $k$ clauses that will mean that there is a bipartite subgraph with at least $k$ edges.
Context
StackExchange Computer Science Q#16691, answer score: 7
Revisions (0)
No revisions yet.