<p>Problem 1 is an exercise in CLRS (2nd ed., page 617).</p>

CC BY-SA 3.0
2011-09-29T23:32:28.037Z
2011-09-29T23:32:28.037Z
zotachidil
<p>It sounds as though your first problem is the computation of the <em>maximum cycle mean</em>. I am no expert, but I know the problem is well studied. One paper on the subject that is not behind a paywall can be found <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.1131" rel="nofollow">here</a>.</p>

CC BY-SA 3.0
2011-09-29T23:07:06.320Z
2011-09-29T23:07:06.320Z
Aaron Sterling
<p>I have a couple of short but pleasing results. I was wondering (a) if they're original (b) if so whom should I tell?</p>

<p>I don't have easy access to any standard texts that would help me out here. Nor indeed do I work in the field (but it would still be advantageous as well as personally satisfying if I could get a note in some journal or other). Anyway, enough prolog, on with the results.</p>

<p>Consider these two closely related problems:</p>

<p>PROBLEM 1: A complete digraph has its edges labeled with numbers. The "average score" of a circuit (not necessarily a cycle) in the graph is defined as the sum of the numbers along the edges traversed divided by the number of edges in the circuit. Is there a non-self-intersecting circuit having an average score greater than a given number?</p>

<p>PROBLEM 2: The same problem, except with the additional constraint that the circuit must pass through a given vertex of the graph.</p>

<p>Problem 1 can be solved in polynomial time. Problem 2 is NP-complete.</p>

<p>Thank you for your comments.</p>

CC BY-SA 3.0
2011-09-29T23:03:24.650Z
What is a circuit?
Radu GRIGore
CC BY-SA 3.0
2011-09-30T00:28:25.450Z
@RaduGRIGore: a closed walk.
Niel de Beaudrap
CC BY-SA 3.0
2011-09-30T11:45:21.610Z
IMHO, this is not on-topic (checking if a theorem that is proven by a non-TCS researcher is already known). It might be suitable for Math.SE.
Kaveh
CC BY-SA 3.0
2011-10-06T17:54:04.157Z
In general it seems to me (no expert) that NP-completeness results are a dime a dozen -- basically anyone in CS can make up a problem and prove it NP complete. So proving some problem NP complete is only interesting if the problem is interesting for some other reason.
Max
<graph-algorithms><np-hardness>
Two Decision Problems About Graphs --- Original Results?
Tim
# Two Decision Problems About Graphs --- Original Results?

(Asked by: username_0 on 2011-09-29)

I have a couple of short but pleasing results. I was wondering (a) if they're original (b) if so whom should I tell?

I don't have easy access to any standard texts that would help me out here. Nor indeed do I work in the field (but it would still be advantageous as well as personally satisfying if I could get a note in some journal or other). Anyway, enough prolog, on with the results.

Consider these two closely related problems:

PROBLEM 1: A complete digraph has its edges labeled with numbers. The "average score" of a circuit (not necessarily a cycle) in the graph is defined as the sum of the numbers along the edges traversed divided by the number of edges in the circuit. Is there a non-self-intersecting circuit having an average score greater than a given number?

PROBLEM 2: The same problem, except with the additional constraint that the circuit must pass through a given vertex of the graph.

Problem 1 can be solved in polynomial time. Problem 2 is NP-complete.

Thank you for your comments.

**Tags:** graph-algorithms, np-hardness
> **Comments:**
> **username_1**: What is a circuit?  
> **username_2**: @RaduGRIGore: a closed walk.  
> **username_3**: IMHO, this is not on-topic (checking if a theorem that is proven by a non-TCS researcher is already known). It might be suitable for Math.SE.  
> **username_4**: In general it seems to me (no expert) that NP-completeness results are a dime a dozen -- basically anyone in CS can make up a problem and prove it NP complete. So proving some problem NP complete is only interesting if the problem is interesting for some other reason.  

---

## 2 answers

### Answer by username_5 on 2011-09-29. Score: 6

Problem 1 is an exercise in CLRS (2nd ed., page 617).


---

### Answer by username_6 on 2011-09-29. Score: 4

It sounds as though your first problem is the computation of the *maximum cycle mean*. I am no expert, but I know the problem is well studied. One paper on the subject that is not behind a paywall can be found [here](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.1131).


---

