The P vs. NP Problem and Attempts to Settle It via Perfect Graphs State-of-the-Art Approach

Heal, Maher; Dashtipour, Kia; Gogate, Mandar

Abstract

The P vs. NP problem is a major problem in computer science. It is perhaps the most celebrated outstanding problem in that domain. Its solution would have a tremendous impact on different fields such as mathematics, cryptography, algorithm research, artificial intelligence, game theory, multimedia processing, philosophy, economics and many other fields. It is still open since almost 50 years with attempts concentrated mainly in computational theory. However, as the problem is tightly coupled with np-complete class of problems theory, we think the best technique to tackle the problem is to find a polynomial time algorithm to solve one of the many np-completes problems. For that end this work represents attempts of solving the maximum independent set problem of any graph, which is a well known np-complete problem, in a polynomial time. The basic idea is to transform any graph into a perfect graph while the independence number or the maximum independent set of the graph is twice in size the maximum independent set or the 2nd largest maximal independent set of the transformed bipartite perfect graph. There are polynomial time algorithms for finding the independence number or the maximum independent set of perfect graphs. However, the difficulty is in finding the 2nd largest maximal independent set of the bipartite perfect transformed graph. Moreover, we characterise the transformed bipartite perfect graph and suggest algorithms to find the maximum independent set for special graphs. We think finding the 2nd largest maximal independent set of bipartite perfect graphs is feasible in polynomial time.

Citation

Heal, M., Dashtipour, K., & Gogate, M. (2023). The P vs. NP Problem and Attempts to Settle It via Perfect Graphs State-of-the-Art Approach. In Advances in Information and Communication: Proceedings of the 2023 Future of Information and Communication Conference (FICC), Volume 2 (328-340). https://doi.org/10.1007/978-3-031-28073-3_23

• Conference Name: 2023 Future of Information and Communication Conference (FICC)
• Conference Location: San Francisco, CA
• Start Date: Mar 2, 2023
• End Date: Mar 3, 2023
• Online Publication Date: Mar 2, 2023
• Publication Date: 2023
• Deposit Date: Jul 20, 2023
• Publisher: Springer
• Pages: 328-340
• Series Title: Lecture Notes in Networks and Systems
• Series Number: 652
• Series ISSN: 2367-3389
• Book Title: Advances in Information and Communication: Proceedings of the 2023 Future of Information and Communication Conference (FICC), Volume 2
• ISBN: 978-3-031-28072-6
• DOI: https://doi.org/10.1007/978-3-031-28073-3_23