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?

Meaning of L-reduction from Dominating set problem

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?

approximation algorithms computational complexity graph domination graph theory

Meaning of L-reduction from Dominating set problem

Add your own answers!

Related Questions

Examples of $aleph_0$-categorical nonhomogeneous structures

Extending a holomorphic vector bundle: a reference request

Applications of Set theory vs. model theory in mathematics

Closed walks on an $n$-cube and alternating permutations

Bounded non-symmetric domains covering a compact manifold

Residues in several complex variables

What kinds of papers does the Indiana University Mathematics Journal publish?

Is there a definable model of PA whose domain is a proper class and whose complete theory is not definable?

Which field extensions do not affect Chow groups?

Reference for topological graph theory (research / problem-oriented)

Is a direct sum of flabby sheaves flabby?

Algebraicity of a ratio of values of the Gamma function

Classification of subgroups of finitely generated abelian groups

An enumeration problem for Dyck paths from homological algebra

Circular track riddle

Fundamental group of a compact branched cover

When is a bi-Lipschitz homeomorphism smoothable?

How do you know that you have succeeded-Constructive Quantum Field Theory and Lagrangian

Does Morita theory hint higher modules for noncommutative ring?

Bounding the smallest eigenvalue of a matrix generated by a positive definite function

Ask a Question