I am interested in special graph constructions that have the smallest diameter. We have a path graph $P_n$ ($N$ is even). We add new set of edges $C$ between path nodes such that set $C$ forms a perfect matching. The output graph is the union of path $P_n$ and perfect matching $C$ on the path nodes.
What is the fastest deterministic algorithm that produces graphs with the smallest possible diameter if the input is $P_n$ path?
I suspect that the problem has intermediate complexity (neither in $P$ nor in NP-complete).
This was motivated by this post on CSTheory.
P.S. I also posted on Mathematics StackExchange which asks for the diameter of a greedy construction.