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

2010/03/19 by Peiyush Jain, Jain, Peiyush · 1 citation
Computer Science · Engineering · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Manufacturing Process and Optimization #Optimization and Packing Problems #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1003.3704

openalex publication_date 2010/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 NP-Completeness results for problems on k-colourable graphs (k ≥ 5). We also prove the NP-Completeness of the Triangle-Free Cut problem.

Cited by

• Monotone 3-Sat-(2,2) is NP-complete

Related

• Graphs whose vertices of degree at least 2 lie in a triangle
• On planar variants of the monotone satisfiability problem with bounded\n variable appearances
• Partitioning H-Free Graphs of Bounded Diameter
• A note on Matching-Cut in P_t-free Graphs
• NP-complete variants of some classical graph problems