The next problem in G&J is an “unpublished manuscript” problem. In looking for an actual reduction, I found a different paper that reduces from a new problem. So this week we’ll look at that problem so we can move on to the reduction next week.

**The problem: **Non-Minimal Feedback Arc Set. This problem is not in the appendix, but is related to the regular Feedback Arc Set problem (GT8).

**The description: **Given a directed graph G, and a subset S of the edges in G such that each cycle in G contains at least one edge in S (so S is a feedback arc set). Can we find another feedback arc set S’ with less edges than S?

**Example: **The difference between this problem and the “regular” Feedback Arc Set problem is that in this problem we’re given a set and asking “can we do better”, and in the regular Feedback Arc set problem, we’re given a K and asking “can we do it in K or less”? Here is an example graph we used for the Feedback Arc Set reduction:

Suppose we had the set S of {(f,d), (d,e), (e,c), (b,c)}. This is a feedback arc set, I’ve drawn it in blue:

In this case, we can build an S’ that is smaller: {(c,a), (e,a), (d,e)}:

Notice that S’ does *not* have to be a subset of S. It just needs to have less edges.

**Reduction: **The reduction for this problem and next week’s is from a paper by Paterson and Razborov from 1991. (As an aside, while I know that 1991 is over 25 years ago, I spend so much time with papers from the 1970’s working on these problems, that 1991 feels “modern”).

It feels like there should be an easy reduction from regular Feedback Arc set to this problem, but I couldn’t think of one. To do it, you’d need to take the K from the feedback arc set and create an *actual* feedback arc set (to make your S). Even for something like a Turing reduction, the requirement that you actually need to create a feedback arc set (which itself is hard to do) makes it hard for me to see an easy reduction in that direction.

So instead, the paper uses 3SAT. Given a formula, for each variable u and clause c add 4 vertices s: A_{u,i}, B_{u,i}, a_{u,j}, and b_{u,j}. Within each quartet of vertices, add edges (a_{u,i}, b_{u,i}), (A_{u,i}, B_{u,i}), (b_{u,i}, A_{u,i}), and (B_{u,i}, a_{u,i}):

Notice that this forms a cycle (and remember, there is one of these cycles for each pair of vertices and clauses- even if the vertex doesn’t appear in that clause. Though to be honest, I’m not sure you need a copy if the vertex doesn’t appear in the clause). The edges (a,b) or (A,B) will be chosen as the feedback edges, with the lowercase letters meaning setting the literal positively in the clause, and the capital letters meaning setting the literal negatively.

We still need to add edges that tie variables that occur in multiple clauses together. Each clause has 3 edges that make a cycle out of the 3 literals in the clause. the edges go from b->a, using the lowercase version of the letter if the literal is positive and the uppercase version if the literal is negative. The example in the paper is that if Clause i = {x_{3}, ~x_{4}, x_{6}}, we’d add the three edges (b_{3,i}, A_{4,i}), (B_{4,i}, a_{6,i}), and (b_{6,i}, a_{3,i}). Here are the three variable cycles for clause i with the new edges added:

Notice that the way we set a variable to make a literal true (for example, making x_{3} positive by adding the edge (a_{3}, b_{3}) to the feedback arc set) creates a feedback arc set both for the 4-vertex cycles, but also for the cycle for the clause.

The authors say that is “straightforward” that 3SAT is NP-Complete even when you give an assignment of the variables that satisfies all but one of the clauses. Mapping this assignment to the feedback edges in the graph will give us a feedback set for each cycle of 4 vertices, and for all clause cycles except for one Thus, we need an edge to “satisfy” this last clause. Call this set of edges (The edges corresponding to the all-but-one clause assignment, plus one edge in the last remaining cycle) S.

If we can find an S’ with *less* edges than S, it must have a way to set each variable to satisfy each clause, and thus the original formula is satisfiable. If we can’t, then the formula is unsatisfiable.

**Difficulty: **8. I don’t think the “satisfy all but one clause” thing is straigthforward. I guess if you give that version of 3SAT to the students, you can sort of see what you need to do with the edges in the graph. But this way of looking at the problem took me a while to wrap my head around.