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.

$\endgroup$
  • 1
    $\begingroup$ What is a circuit? $\endgroup$ – Radu GRIGore Sep 29 '11 at 23:03
  • 2
    $\begingroup$ @RaduGRIGore: a closed walk. $\endgroup$ – Niel de Beaudrap Sep 30 '11 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 '11 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 '11 at 17:54
6
$\begingroup$

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

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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