On Minimum Maximal Distance-k Matchings
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1
Voir la notice de l'article provenant de la source Episciences
We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$-equipackable graphs. We prove that the recognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k \ge 2$. We provide a simple characterization for the class of strongly chordal graphs with equal $k$-packing and $k$-domination numbers. We also prove that for any fixed integer $\ell \ge 1$ the problem of finding a minimum weight maximal distance-$2\ell$ matching and the problem of finding a minimum weight $(2 \ell - 1)$-independent dominating set cannot be approximated in polynomial time in chordal graphs within a factor of $\delta \ln |V(G)|$ unless $\mathrm{P} = \mathrm{NP}$, where $\delta$ is a fixed constant (thereby improving the NP-hardness result of Chang for the independent domination case). Finally, we show the NP-hardness of the minimum maximal induced matching and independent dominating set problems in large-girth planar graphs.
@article{DMTCS_2018_20_1_a2,
author = {Kartynnik, Yury and Ryzhikov, Andrew},
title = {On {Minimum} {Maximal} {Distance-k} {Matchings}},
journal = {Discrete mathematics & theoretical computer science},
publisher = {mathdoc},
volume = {20},
number = {1},
year = {2018},
doi = {10.23638/DMTCS-20-1-3},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-3/}
}
TY - JOUR AU - Kartynnik, Yury AU - Ryzhikov, Andrew TI - On Minimum Maximal Distance-k Matchings JO - Discrete mathematics & theoretical computer science PY - 2018 VL - 20 IS - 1 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-3/ DO - 10.23638/DMTCS-20-1-3 LA - en ID - DMTCS_2018_20_1_a2 ER -
%0 Journal Article %A Kartynnik, Yury %A Ryzhikov, Andrew %T On Minimum Maximal Distance-k Matchings %J Discrete mathematics & theoretical computer science %D 2018 %V 20 %N 1 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-3/ %R 10.23638/DMTCS-20-1-3 %G en %F DMTCS_2018_20_1_a2
Kartynnik, Yury; Ryzhikov, Andrew. On Minimum Maximal Distance-k Matchings. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi: 10.23638/DMTCS-20-1-3
Cité par Sources :