Combinatorics and Graph Theory

    

Detecting Whether a Graph Has a Fixed-Point-Free Automorphisms is in Polynomial Time

Authors: Yasunori Ohto

The problem of determining whether a graph has a fixed-point-free automorphism is NP-complete. We demonstrate that the problem can be solved efficiently within polynomial time. First, we obtain the automorphisms of an input graph G by using a spectral method. Next, we prove the Theorem used to detect whether there is a fixed-point free automorphism in G. Next, we construct an algorithm to detect whether G has a fixed-point-free automorphism using this result. The computational complexity of detecting whether a graph has a fixed-point-free automorphism is O(n^5). If fixed-point-free automorphism exist, the computational complexity of obtaining a fixed-point-free automorphism is O(n^6). Then, the complexity classes P and NP are the same.

Comments: 11 Pages.

Download: PDF

Submission history

[v1] 2024-04-23 13:42:18
[v2] 2024-04-28 02:46:53
[v3] 2024-05-19 07:17:18

Unique-IP document downloads: 760 times

Vixra.org is a pre-print repository rather than a journal. Articles hosted may not yet have been verified by peer-review and should be treated as preliminary. In particular, anything that appears to include financial or legal advice or proposed medical treatments should be treated with due caution. Vixra.org will not be responsible for any consequences of actions that result from any form of use of any documents on this website.

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus