# 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:

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?

## Related Questions

### Fundamental ring of a circle

0  Asked on January 1, 2022 by tegiri-nenashi

### Reference request: extendability of Lipschitz maps as a synthetic notion of curvature bounds

1  Asked on January 1, 2022 by lawrence-mouill

### Should cohomology of $mathbb{C} P^infty$ be a polynomial ring or a power series ring?

1  Asked on January 1, 2022 by powertothepeople

### Non-degenerate simplexes in a Kan complex

2  Asked on December 29, 2021 by lao-tzu

### How to find a rational $mathbb{F}_{!q}$-curve on a quite classical Calabi–Yau threefold?

1  Asked on December 29, 2021 by dimitri-koshelev

### Eigenvectors of random unitary matrices

1  Asked on December 29, 2021

### Exceptional divisor of the Hilbert-Chow morphism of the punctual Hilbert scheme

1  Asked on December 27, 2021

### Reference request: Gauge natural bundles, and calculus of variation via the equivariant bundle approach

1  Asked on December 27, 2021 by bence-racsk

### How to solve numerically a system of 3 interdependent non-linear ordinary differential equations?

1  Asked on December 27, 2021

### Non existence of stable vector bundles on $mathbb{P}^4$ with $c_1=0$ and $c_2=1$

1  Asked on December 27, 2021 by mcjr

### If $f:U_1tomathcal L^p(mu;E_2)$ is Fréchet differentiable, can we say anything about the Fréchet differentiability of $umapsto f(u)(omega)$?

0  Asked on December 27, 2021

### Convergence properties of related series

1  Asked on December 27, 2021

### If $A$ is a cofibrant commutative dg-algebra over a commutative ring of characteristic $0$, then its underlying chain complex is cofibrant

2  Asked on December 27, 2021 by francesco-genovese

### Rowmotion for general lattices

0  Asked on December 27, 2021

### Is $mathrm{End}-{0}=mathrm{Aut}$ for derivation Lie algebra?

0  Asked on December 25, 2021

### Explicit transitive flow on disc

1  Asked on December 25, 2021

### Multiplicative and additive groups of the field $(prod_{ninomega}mathbb{Z}/p_nmathbb{Z})/simeq_{cal U}$

2  Asked on December 25, 2021

### Which mathematical definitions should be formalised in Lean?

28  Asked on December 21, 2021 by kevin-buzzard

### Does the Riemann Xi function possess the universality property?

1  Asked on December 21, 2021

### Convex hull of prefix sum of $n$ ordered random points

0  Asked on December 21, 2021 by yupbank

Get help from others!