Yury Kartynnik ; Andrew Ryzhikov - On Minimum Maximal Distance-k Matchings

dmtcs:3271 - Discrete Mathematics & Theoretical Computer Science, January 11, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-3
On Minimum Maximal Distance-k MatchingsArticle

Authors: Yury Kartynnik ; Andrew Ryzhikov ORCID

    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.


    Volume: Vol. 20 no. 1
    Section: Graph Theory
    Published on: January 11, 2018
    Accepted on: December 19, 2017
    Submitted on: April 18, 2017
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Computational Complexity,Mathematics - Combinatorics,F.2.2,G.2.2

    Consultation statistics

    This page has been seen 787 times.
    This article's PDF has been downloaded 501 times.