2
$\begingroup$

Recently, I asked this question on TCS.SE, but it was closed on the pretext that it was not a research-level question. However, I don't understand what makes it "a not research-level question". It has got 6 upvotes, so at least 6 people find it interesting, and hopefully on-topic, though I know it's not a metric.

I am not asking a "do my homework" question like proving that Max-Cut is NP-complete. I am asking whether there exists a specific reduction, i.e. from Vertex Cover to Max-Cut. I suppose if such a reduction exists, then it might give some insights on how some seemingly unrelated problems are related (and also, reductions are almost always fun!).

So is there anyone else who feels that it's on-topic? Or at least give the specific reason why it was closed, rather than the hand-wavy "not a research-level question".

$\endgroup$
0

2 Answers 2

Reset to default
6
$\begingroup$

It's an exercise in a standard textbook. That would be a hint that it's not research-level.

$\endgroup$
1
  • $\begingroup$ If you read the details, the exercise just asks to prove that max cut is NP complete, which, I agree is an "easy" exercise. What I am asking in particular is that if Vertex Cover is reducible to Max Cut, the proof of which I couldn't think of, nor I could find anywhere. The proof I've come across involves: SAT -> 3SAT -> NAE-3SAT -> Max Cut. $\endgroup$
    – taninamdar
    Nov 11, 2015 at 23:05
4
$\begingroup$

If you want to understand the scope you can check our help/on-topic. It explains what we mean by research-level.

Your question is closed because 5 of users who can vote to close voted to close the question as off-topic. As Lev wrote questions at the level of typical undergraduate textbook exercises are off-topic here. The picture in the book is a hint that the way to show that Max-Cut is NPC is to reduce Vertex Cover to it. The question might be appropriate for Computer Science which has a broader scope but read check their help center to make sure you understand their policies.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .