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$
11
  • 2
    $\begingroup$ Can you please identify the paper? $\endgroup$ 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$ Dec 4 '10 at 21:35
  • 3
    $\begingroup$ @Handman: But what is the fooling set problem? $\endgroup$ 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$
6
  • $\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$ 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$ Dec 5 '10 at 1:00
  • $\begingroup$ @Handman: That was funny dude :) $\endgroup$ 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.