2013/12/23 by Pawan Tamta, Tamta, Pawan, Bhagwati Prasad Pande +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1312.6492
openalex publication_date 2013/12/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Cardinality Maximum Flow Network Interdiction Problem (CMFNIP) is known to be strongly NP-hard problem in the literature. A particular case of CMFNIP has been shown to have reduction from clique problem. In the present work,an effort is being made to solve this particular case of CMFNIP in polynomial time. Direct implication of this solution is that the clique problem gets solved in polynomial time. 3-CNF Satisfiability and Vertex Cover problems, having reductions to and from the Clique Problem respectively, are also being solved in polynomial time by same algorithm. The obvious conclusion of the work is P = NP.