ALGORITHMS · EMPIRICAL GRAPH RESEARCH
Local choices, global tradeoffs
Can a local greedy search preserve nearly all the solution quality of a global greedy method while requiring less runtime?
Maximum Weight Independent Set asks for valuable vertices that do not touch one another. We compared practical greedy heuristics across two random-graph families, corrected an invalid experimental protocol, and treated impossible-looking theory ratios as a reason to question the measurement.
Poster title: Approximating the Maximum Weighted Independent Set Problem Empirically
The public study was organized around these questions.
They are preserved here from the October 2025 research poster rather than replaced with a cleaner but different story.
- RQ 1
Is NNC better than PQ and naive greedy for finding weighted independent sets in E-R and/or B-A graphs?
- RQ 2
How close to optimal are greedy algorithms in B-A graphs?
- RQ 3
Can we recover planted independent sets with a fast, simple algorithm?
THE PROBLEM
Choose value without choosing conflicts.
An independent set contains vertices with no edge between any selected pair. A maximal independent set cannot accept another vertex. A maximum-weight independent set has the greatest possible total weight. Greedy methods easily produce the first; finding the second is NP-hard on general graphs.
value of the vertex
÷
its current local footprint
Global bookkeeping or a local improvement walk?
Both methods use the same changing score. They differ in how they search for the next vertex.
Keep the globally best current choice.
A heap maintains the best score across the remaining graph and updates affected priorities after deletions.
Follow improving neighbors to a locally dominant choice.
The chain avoids global heap maintenance, but a locally dominant vertex need not be the graph's global best choice.
The paper analyzes PQ at roughly (n + m) log n. NNC's dynamic cost depends on neighborhood structure and maximum degree, so the research does not claim a universal linear bound.
Controlled density beside hub-heavy structure.
Erdős-Rényi
Each potential edge is sampled independently. It provides a controlled random baseline for changing graph density.
Barabási-Albert
Preferential attachment creates hubs and a heavier-tailed degree pattern. It tests whether local and global choices behave similarly around unequal connectivity.
These are synthetic graph models. Neither is presented as a complete model of a real social network.
Three heuristics across size, structure, density, and weighting.
The poster compares PQ, NNC, and Naive on weighted and unweighted ER and BA graphs from 500 to 5,000 vertices, increasing by 500, with vertex weights from 1 to 10,000 in the weighted experiments.
of PQ solution quality
while PQ took approximately 2-3× longer
NNC empirically stayed close to the global PQ heuristic while avoiding some of its bookkeeping cost.
WHAT THIS DOES NOT MEANIt is not 98% to 99% of the true optimum, not a worst-case approximation ratio, and not a universal speed guarantee.
The overlap appeared across both graph families.
These earlier plots include four algorithms: PQ, NNC, Naive Weighted Greedy (NWG), and Naive Greedy. They support the algorithmic foundation, but they are not silently blended into the later three-algorithm poster experiment.
When the comparison was invalid, the right result was to rerun it.
Algorithms ran sequentially on the same graph even though each run mutated it.
The selected vertex itself was not correctly removed with its neighborhood.
Use equivalent graph copies, remove the closed neighborhood correctly, discard invalid comparisons, and rerun.
The source material verifies the team's correction. It does not provide enough evidence to assign the discovery or fix to one individual.
ratio > 1?
A comparison against a theoretical independence-number expression produced ratios above one. That cannot mean a heuristic beat the true optimum.
When the result looked impossible, we questioned the measurement rather than celebrating it.
The remaining explanation may involve the formula, its asymptotic assumptions, the finite-size regime, or parameter interpretation. The supplied record does not establish one final cause.
Can a fast heuristic recover known planted structure?
The poster reports stronger recovery as the planted set becomes larger and compares behavior with a theoretical threshold on the order of √(N log N). Recovering a planted set is a controlled test, not the same as proving the full MWIS optimum.
ATTRIBUTION + LIMITS
A published research artifact, with open methodological questions.
The supplied sources verify Sue as paper coauthor and the poster's student researcher. The poster credits Luke Fanguna for substantial experimental-design contributions and Daniel Frishberg as advisor.
The current archive does not verify granular ownership of individual algorithms, scripts, plots, bug fixes, or analysis steps. It also does not include the final raw result table, seeds, hardware, or exact aggregation behind the 98% to 99% and 2 to 3 times headline.
The public case study therefore explains the research as team work and avoids assigning uncertain implementation details to one person.