tvan's blog

Help with version of satisfiability problem
By tvan, history, 4 years ago, In English

During the latest USACO plat I managed to reduce the 2nd problem to the following:

You are given N restrictions and M truth/false variables. Restrictions are : given a1, a2... ak, at least one of them must be true for the restriction to be met ( so a1 or a2 or ... or ak == true). Each variable appears in at most 2 restrictions. What is the minimum number of variables which have to be true so that all restrictions are met?

Is there any (polynomial) solution to this problem ?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i guess there exists a randomised solution to this, but i am not sure if we can do that, but
this seems similar to this, https://codeforces.net/contest/1492/problem/E , give it a try, still i am not sure!!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It can be reduced to Minimum Edge Cover, which in turn can be reduced to General Max Matching. To reduce it to edge cover, construct a graph with $$$n$$$ nodes. If a variable exists in two clauses, draw an edge between the nodes of those corresponding clauses. Draw a self loop from every node back to itself if and only if one of the variables in it's clause occurs in only one clause. The answer is exactly the minimum edge cover (try to see why). This can be solved in polynomial time.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can't see the reason for the self loop on each node. Wouldn't it then be possible in the minimum edge cover for only the self loop to be activated, while all the others are false? That would translate to having all those variables set to false which wouldn't make the clause true

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I updated my comment to be more clear (it's easier to explain why it works). However, my original claim was true as well (and it makes implementation more efficient/easier). If you use a self-loop in the edge cover, imagine just turning on any variable in the clause. That will instantly satisfy the clause. It doesn't matter whether the variable you turn on exists in any other clauses — if it does, you would just take the edge between those two clauses instead of the self loop in your edge cover. Essentially, after choosing edges that are not self-loops that you need in your edge cover, you can go to every clause that is still unsatisfied and turn any of those variables on (for a cost of 1). Implementation note: you don't actually have to add the self-loops when building the graph, as using a self-loop is always worse than using an edge that spans across two different nodes, so after finding the max-matching, just use a self loop for every unmatched clause.

      → Reply