MathOverflow Asked by Venugopal K on August 7, 2020

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:

- since the dominating set problem is W[2]-complete, does that follow to our problem because of the L-reduction?
- 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?

Get help from others!

Recent Answers

- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP