0
$\begingroup$

One proof for $2-SAT$ being in $P$ uses the implication graph, i.e. one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor b)$, one from $\neg a$ to $b$ and one from $\neg b$ to $a$, respectively representing the implications $\neg a \implies b$ and $\neg b \implies a$. Finally, (assuming a solution exists) one sorts the connected components in topological order and traverses these in reverse order. Now for the important part :
For every literal $a$ encountered, set variable $a = true$, and for every literal $\neg a$ encountered, set variable $a = false$.
Don't change variables already set. The resulting assignment is a solution.

My question is : Do other assignments work as well, as long as the underlying implications stay $true$ ? For example :
For every literal $a$ encountered, set variable $a = false$, and for every literal $\neg a$ encountered, set variable $a = true$.
since $false \implies false$, or even some combination :
For every literal $a$ encountered, if it points to some literal that equals $false$, set $a = false$, otherwise set it to either $false$ or $true$. For every literal $\neg a$ encountered, if it points to some literal that equals $false$, set $a = true$, otherwise set it to either $false$ or $true$.
since $true \implies true$, $false \implies true$, and $false \implies false$?

$\endgroup$
1
$\begingroup$

You have to understand that $a \implies b$ cannot be interpreted as $\neg a \implies \neg b$. Only the contraposition $b \implies a$ is true, but this one is already in the implication graph by construction.

Thus, with your algorithm, you will make abrirtrary assignments. This will probably leads to an impossibility even if the problem does have a solution. Of course, on trivial examples, one can see that this algorithm may produce a solution.

Also note that $a \implies b \implies c$ means there is elsewhere in the graph $\neg c \implies \neg b \implies \neg a$. So when you decide to assign false in order to $a, b, c$, you are reading the graph and the strongly connected components reversly.

$\endgroup$
3
  • $\begingroup$ If you have $a \implies b$ in the implication graph, then by construction you must also have $\neg b \implies \neg a$ somewhere in the implication graph (and not $b \implies a$ as you stated). I don't see a contradiction assigning either $(1, 1)$, $(0, 0)$, or $(0, 1)$ to $(a, b)$ respectively. $\endgroup$
    – J. Schmidt
    Oct 5 '20 at 10:40
  • 1
    $\begingroup$ What are you looking for ? A means to get other solutions for the 2-SAT problem or an example for which your algorithm fail ? Take for instance an implication graph containing the subgraph $\neg a \implies b \implies a$. $\endgroup$
    – Optidad
    Oct 5 '20 at 15:17
  • $\begingroup$ I found out why different assignments are not a good idea and found a minimal counterexample to illustrate a potential failure (see other answer). $\endgroup$
    – J. Schmidt
    Oct 5 '20 at 15:27
0
$\begingroup$

(Example below)
Following anything other than :
For every literal $a$ encountered, set variable $a = true$, and for every literal $\neg a$ encountered, set variable $a = false$.
might set to $true$ a literal higher up in the DAG of strongly connected components (which you're traversing in reverse topological order), which can cause a chain reaction downwards obtaining a $true \implies false$, which is not allowed.

An example is the following : $(a \lor b) \land (a \lor \neg b)$
Indeed, traversing the created implication graph in reverse topological order makes you start at literal $a$, which you need to set to $true$, as setting it to $false$ would set literal $\neg a$ to $true$ higher up in the DAG, creating said contradiction of $true \implies false$ somewhere in between. Also, one can trivially see why $a$ needs to be set to $true$ in the example.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.