creating regular subgraph through edge deletion

Question

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).

Answer 1

In this article, the authors provide a way to transform a special Q-regular graph to a Q-1 - regular one in O(n^3), which implies your problem is solvable in O(n^4) for some special cases. You might want to take a look at the article and see if it's any help for you.

Answer 2

An alternative approach would be to construct a maximum matching (e.g. using Edmond's Blossom algorithm).

This constructs a set of edges such that each vertex is connected to at most one edge.

This may be more efficient than finding a Hamiltonian path and more likely to work (e.g. for disconnected graphs).

Deleting the edges in the maximum matching will result in a Q-1 regular graph if and only if every vertex is connected to exactly one edge in the matching. (It is impossible for a vertex to be connected to more than one edge, but it may be possible for some vertices to be connected to 0 edges. However, I believe this will only happen if it is impossible to have a Q-1 regular subgraph.)

To make it randomized you could consider using a weighted matching algorithm and use random weights.