Exact minimum degree greedy outcomes found for interval graphs
Exact Tie-Breaking and Tight Degree Bounds for Minimum-Degree Greedy on Interval Graphs
Data Structures and Algorithms
Summary
Finding the largest or smallest sets of points in a certain kind of overlapping interval graph can be tricky. This paper figures out exactly how well a simple method called minimum-degree greedy works when you pick points one-by-one by their smallest number of connections. The authors give a way to compute the best and worst results fast and prove tight limits on how small or large those sets can be depending on graph connections. They also show special families of graphs where these limits are met exactly.
What this means in practice
- •For graph algorithm engineers: Implement and optimize greedy selection on interval graphs knowing exact output size bounds for scheduling and resource allocation tasks.
- •For network planners: Use tight guarantees on greedy vertex removal to design robust interval-based communication or sensor networks with known performance limits.
Authors
Ruize Zhao
Abstract
Minimum-degree greedy repeatedly selects a vertex of minimum current degree and deletes its closed neighborhood; let $B(G)$ and $W(G)$ be its largest and smallest output sizes over complete legal executions. Given a closed interval representation of an $n$-vertex graph, we compute both values and construct attaining executions in $O(n^3)$ time and $O(n^2)$ space using endpoint-window dynamic programming and legal interleaving. For interval graphs with $Δ(G)\le4$, we prove the tight bound $B(G)\ge3α(G)/4$ by reduction to unit interval graphs and induction with virtual boundary vertices. A connected unit interval family $J_t$ attains equality, with $B(J_t)=W(J_t)=3t$ and $α(J_t)=4t$. For each degree bound $d\ge5$, a degree-five family $H_t$ approaches the known $2/3$ lower bound, giving infimum $2/3$. Together with known optimal favorable tie-breaking for $d\le3$, these results determine the favorable guarantee for every degree bound.