AnswerBun.com

Meaning of L-reduction from Dominating set problem

We are working in a variation of Locating dominating sets. Recently, we realized that the reduction from dominating set to our problem in proving its NP-completeness turns out to be also an L-reduction. This would mean that there is no PTAS for our problem since the dominating set problem does not have PTAS. Now we have two questions:

  1. since the dominating set problem is W[2]-complete, does that follow to our problem because of the L-reduction?
  2. we have proved that our problem is in XP (i.e, piecewise polynomial) and also in APX (there is a 2-approximation polynomial algorithm). But dominating set problem is known to be not in APX. Does this mean somewhere we might have gone wrong or is this perfectly alright?

MathOverflow Asked by Venugopal K on August 7, 2020

0 Answers

Add your own answers!

Related Questions

Toposes with only preorders of points

1  Asked on February 1, 2021 by matthias-hutzler

 

How badly can the GCH fail globally?

1  Asked on January 24, 2021 by sam-roberts

       

Nonseparable Hilbert spaces

6  Asked on January 23, 2021 by truebaran

     

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved.