On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem

Peiyush Jain

In this paper we define a restricted version of Monotone NAE-3SAT and show that it remains NP-Complete even under that restriction. We expect this result would be useful in proving…