Reducing Graph Reachability to Sitting (CNF) – Stack Overflow

So I stumbled upon this issue within my textbook. I’m wondering how you can create a reduction in the Graph Reachability problem to Sitting (CNF) problem. (i.e. formula is satisfiable iff there’s a path in graph G from begin to finish node)

1) I can not wrap my mind around how you can move from something that may be solved in polynomial time (Graph Reachability) to something which is NP (Sitting).

2) I can not appear to find away out to formulate these nodes/edges of Graph into actual clauses in CNF that match reachability.

I attempted to consider algorithms like Floyd-Warshall that determine whether a way exists from begin to finish node however i can’t appear to formulate that concept into actual CNF clauses. Help could be much appreciated!

3 Solutions

It most likely would not be way too hard to generate the type of answer you are expecting, but here’s the real answer rather:

“Reducing” an issue X to problem Y means transforming any demonstration of X to a clear case of Y so that the solution to Y provides the solution to X. Usually, we must have a P-time reduction, i.e., the transformation from the problem and also the extraction from the answer must both take place in polynomial time.

Graph Reachability is definitely solved in straight line time, that is certainly polynomial time, therefore the reduction from Graph Reachability to Sitting really is easy:

1. Given a graph reachability problem, solve it in straight line time
2. When the preferred path exists, create any satisfiable Sitting instance, like (A). Otherwise, create any unsatisfiable Sitting instance like (A)&(~A)

We did something such as your career a couple of years back. Our approach was based exactly on Floyd-Warshall (F.-W.) formula. Without effort, you want to something similar to this:

1. Generate all possible pathways using F.-W. for every set of nodes
2. Produce a clause representing each path. It is “if your path is chosen, then your following nodes should be selected”
3. Produce a clause that unites all pathways right into a single CNF. Probably it might be “exactly_one” clause.

A little more formally:

1. Assign a binary literal to every node inside a graph. The literal has value True iff. it is associated with a way between two nodes.
2. Run F.-W. for a set of nodes
3. Turn resulting road to a clause:

    nodes <- get_nodes_from_path(path)
    node_lits <- logical_and([n.literal for n in nodes])

1. Get new literal for any path path_lit <- get_new_literal()
2. Combine it with path a way: path_clause <- if_then_else(node_lits, path_lit)
3. Visit 2, enumerate all pairs

Finally, you can the next:

all_pathways <- exactly_one(all_path_clauses)
all_pathways <- True

Sitting solver would have to choose one of pathways which would result in selecting corresponding nodes.

Regarding the first question: Since you are only devising a method to reduce an issue in P right into a condition in NP (and never the other way round), this is not really an issue. You are able to turn any Graph Reachability problem right into a Sitting problem, however that does not mean you are able to turn any Sitting problem right into a Graph Reachability problem.