On the Complexity of Problems on Graphs Defined on Groups

We study the complexity of graph problems on graphs defined on groups, especially power graphs. We observe that an isomorphism invariant problem, such as Hamiltonian Path, Feedback Vertex Set, Partition into Cliques, Subgraph Isomorphism, etc., cannot be NP-complete for power graphs, commuting graphs, enhanced power graphs, directed power graphs, and bounded-degree Cayley graphs, assuming the Exponential Time Hypothesis (ETH). Analogously, no isomorphism invariant group problem can be NP-complete, under ETH. We show that the Weighted Max-Cut problem is NP-complete in power graphs. We also show that, unless ETH is false, the Graph Motif problem cannot be solved in quasipolynomial time on power graphs, even for power graphs of cyclic groups. We study the recognition problem of power graphs when the adjacency matrix or list is given as input and show that for abelian groups and some classes of nilpotent groups, it is solvable in polynomial time.