2
$\begingroup$

I read in a paper showing that it can be implemented by reducing induced matching problem on bipartite graphs to fooling set. But the proof was omitted in that paper and I cannot find answer by myself.

Thank you.

Edit: The fooling set technique is defined by the following theorem:

$\endgroup$
  • 2
    $\begingroup$ Can you please identify the paper? $\endgroup$ – Mark Reitblatt Dec 4 '10 at 20:50
  • $\begingroup$ Finding lower bounds for Nondeterministic state complexity is hard $\endgroup$ – Handman Dec 4 '10 at 21:00
  • $\begingroup$ @Michael: I did not find a good reduction to reduce a NP-hard to fooling set. I thought CLIQUE may be a good idea, but I failed to find the gardget. $\endgroup$ – Handman Dec 4 '10 at 21:34
  • 2
    $\begingroup$ @Handman: Please define the problem! $\endgroup$ – Michael Blondin Dec 4 '10 at 21:35
  • 3
    $\begingroup$ @Handman: But what is the fooling set problem? $\endgroup$ – Michael Blondin Dec 4 '10 at 21:38
7
$\begingroup$

The proof is given in Section 6 the full version of the paper. I bring an excerpt, since there was originally much confusion about what "fooling set" means.

Basically, the notion of fooling set was introduced by Jean-Camille Birget in Intersection and union of regular languages and state complexity.

To prove that fooling set problem (as defined below) is NP-hard, the authors reduced the NP-complete induced matching problem on bipartite graphs to it.

Here's an excerpt of the paper, which defines the problem and proves the theorem.


excerpt of the paper

$\endgroup$
  • $\begingroup$ Thank you very much! I see the version from google book of the proceeding papers, and seems they omitted the proof part. $\endgroup$ – Handman Dec 4 '10 at 22:31
  • $\begingroup$ @Handman: Since this is exactly the answer you were looking for, I think you should accept it! $\endgroup$ – Michael Blondin Dec 4 '10 at 23:24
  • $\begingroup$ @Handman: You're welcome, but you misunderstood me. What I meant is that you should click on the green arrow next to the answer. $\endgroup$ – Michael Blondin Dec 5 '10 at 1:00
  • $\begingroup$ @Handman: That was funny dude :) $\endgroup$ – M.S. Dousti Dec 5 '10 at 1:13
  • $\begingroup$ @Michael, sorry for misunderstanding you. This is the first time I asked question. $\endgroup$ – Handman Dec 5 '10 at 1:43

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.