Timeline for 1-in-k-SAT problem restricted to only positive literals and at most two occurrences of a variable
Current License: CC BY-SA 4.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 30 at 17:03 | vote | accept | Ajay | ||
| Jun 26 at 2:41 | comment | added | xskxzr | @Ajay "There is an edge between two vertices iff their corresponding clauses are both free clauses (we call such edges free edges for convenience) or they have common variables" the vertices corresponding to free clauses are connected to each other, so we can still add free edges to the matching in your example. | |
| Jun 26 at 1:20 | comment | added | Ajay | I think there’s a flaw in the proof. Suppose the max matching is not a perfect matching. And suppose all vertices not incident on matched edges correspond to free clauses. Then clearly there’s a solution to SAT instance. | |
| Jun 24 at 6:24 | history | answered | xskxzr | CC BY-SA 4.0 |