I'm currently working on a research project that involves the analysis of a modified greedy algorithm on 3-regular random graphs. The algorithm works as follows: at time t = 0, any node is selected and all of its neighbors are discarded. At all subsequent times starting at t = 1, we find a node with the smallest remaining degree, include it in our independent set, and discard its neighbors. I am working in the setup of multi-graphs with clones that are paired uniformly at random. The setup is further described in: icholas C Wormald, Differential equations for random processes and random graphs, The annals of applied probability (1995).
My intuition tells me that the degrees of nodes in the graph after each step of the algorithm can be modeled using an ordinary differential equation (ODE). Since the initial graph is 3-regular, at any given time, a node can have a degree of 0, 1, 2, or 3. Therefore, a 4-dimensional ODE could be used to track the number of nodes of each degree over time.
Here's my initial thought:
Let x_i(t) denote the fraction of nodes with degree I at time t.
For x1, the rate of change should take into account the nodes of degree 1 being selected and removed, as well as nodes of degree 2 and 3 losing a neighbor and thus having their degree reduced by 1. Therefore, dx1/dt = -x1 + 3x2 + 6x3.
Similarly, for x2, the rate of change should reflect nodes of degree 2 being selected and removed or losing a neighbor and becoming nodes of degree 1, as well as nodes of degree 3 losing a neighbor and becoming nodes of degree 2. Therefore, dx2/dt = -2x2 - 6x3.
Finally, for x3, the rate of change should simply reflect nodes of degree 3 being selected or losing a neighbor. Therefore, dx3/dt = -3x3.
I believe this set of ODEs can model the evolution of the node degrees in the graph over time. The size of the independent set could then be estimated as the number of nodes removed from the graph, which can be calculated from the solution of this ODE system.
Does this formulation seem correct to you? I would greatly appreciate any feedback or suggestions to formalise this results as the asymptotic of it don't seem clear to me at this point. Thank you in advance for your help!