Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am not even sure of how to search for an answer to this, or how to approach the problem myself, so I thought I would try to ask it here.

Consider an n-vertex hypergraph where the vertices are numbered from 1 to n. Each edge is given a "score" based on the lowest numbered vertex it contains.

Is it possible to efficiently renumber the vertices in a way that maximizes the sum of all the edge scores?

I'm not really seeing any way to do this short of the naive method of trying every permutation. I'd appreciate a shove in the right direction.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.