1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What is a circuit? $\endgroup$
    – Radu GRIGore
    Sep 29, 2011 at 23:03
  • 2
    $\begingroup$ @RaduGRIGore: a closed walk. $\endgroup$
    – Niel de Beaudrap
    Sep 30, 2011 at 0:28
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Sep 30, 2011 at 11:45
  • $\begingroup$ 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. $\endgroup$
    – Max
    Oct 6, 2011 at 17:54

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.