The problem: Given a Q-regular undirected graph, I'm looking for an algorithm to identify an N-regular undirected subgraph through edge deletion. N < Q (obviously), and it's important that some degree of randomness can be implemented in the algorithm, since I need to sample the space of N-regular subgraphs.
What I've tried: So far, my best method has been finding a Hamiltonian cycle, and deleting every other edge on the cycle. This nicely creates a (Q-1)-regular subgraph and can in principle be repeated until the desired degree of regularity has been reached, or I inadvertently create a graph with no Hamiltonian cycle. However, this approach is slow (this is my main issue) and it's a bit problematic that it relies on the otherwise completely unnecessary restriction of a Hamiltonian cycle.
My Question: Can anyone suggest an alternative to the Hamiltonian cycle approach, or perhaps simply tell me that the problem is inherently hard and that a faster solution than Hamiltonian cycle detection is unlikely? I realize that I'm flirting with some graph theory concepts here, but I'm afraid that I don't have the expertise to frame it more formally.
Thank you for your time :)
EDIT: I forgot to mention that the number of vertices (= L) in the original network is even. I have made this restriction to ensure that a regular graph can be created, since this is impossible if both L and Q are odd, and I wish to have as few restrictions on Q as possible. Second, I do indeed wish to retain all vertices (hence I only mentioned edge deletion).