0
$\begingroup$

Fedor Petrov has posed a notorious problem regarding the existence of a matching in this question: Resolution of multiple edges

As I see it the setting is a constrained bipartite matching and thus, because there is more than a single constraint, is an NP-complete problem (c.f. Itai, Rodeh, Itai and Tanimoto: Some Matching Problems for Bipartite Graphs)
leading to the following

Questions:

  • is Fedor's problem indeed NP-complete?
  • is being NP-complete sufficient to prove the existence of instances without solution?
Improve this question
$\endgroup$
3
  • $\begingroup$ A problem $P$ being NP-complete means that you can solve any NP problem using a hypothetical algorithm for $P$. An algorithm for $P$ with just positive instances is useless (it just always says "yes" no matter what you give it). So such a problem is NP-complete for Turing reductions iff P $=$ NP (for many-one reductions it is unconditionally not NP-complete). Does this solve your second question, or is it something more substantial? $\endgroup$
    – Ville Salo
    Commented Sep 9, 2022 at 9:39
  • $\begingroup$ @VilleSalo the problem I see is that we have a constrained matching problem, which is generally NP-complete; now, knowing that a problem is NP-complete means that every instance, including those that are not acceptable, of other NP-complete problems "translate" to instances of the original (constrained matching) problem and would thus prove that not every instance of the matching problem has a solution. In my "opinion" proving the NP-completeness of a problem would therefore also prove the existence of instances without valid matching --> $\endgroup$
    – Manfred Weis
    Commented Sep 9, 2022 at 13:49
  • $\begingroup$ @VilleSalo --> therefore Fedor Petrov's question would be answered in the negative if it could be shown that his problem is NP-complete; is that argument valid? $\endgroup$
    – Manfred Weis
    Commented Sep 9, 2022 at 13:51

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .