Parameterized complexity of weak odd domination problems

DOI10.1007/978-3-642-40164-0_13MaRDI QIDQ2842778zbMATH OpenOpenAlexFDO

Authors David Cattanéo, Simon Perdrix

Publication date 16 August 2013

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.4081

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Given a graph $G=(V,E)$, a subset $BsubseteqV$ of vertices is a weak odd dominated (WOD) set if there exists $DsubseteqVsetminusB$ such that every vertex in $B$ has an odd number of neighbours in $D$. $kappa(G)$ denotes the size of the largest WOD set, and $kapp{a}^{\prime }(G)$ the size of the smallest non-WOD set. The maximum of $kappa(G)$ and $|V|-kapp{a}^{\prime }(G)$, denoted $kapp{a}_Q(G)$, plays a crucial role in quantum cryptography. In particular deciding, given a graph $G$ and $k>0$, whether $kapp{a}_Q(G)lek$ is of practical interest in the design of graph-based quantum secret sharing schemes. The decision problems associated with the quantities $kappa$, $kapp{a}^{\prime }$ and $kapp{a}_Q$ are known to be NP-Complete. In this paper, we consider the approximation of these quantities and the parameterized complexity of the corresponding problems. We mainly prove the fixed-parameter intractability (W$[1]$-hardness) of these problems. Regarding the approximation, we show that $kapp{a}_Q$, $kappa$ and $kapp{a}^{\prime }$ admit a constant factor approximation algorithm, and that $kappa$ and $kapp{a}^{\prime }$ have no polynomial approximation scheme unless P=NP.

Recommendations

• On weak odd domination and graph-based quantum secret sharing
• The parameterized complexity of domination-type problems and application to linear codes
• Parameterized complexity of generalized domination problems
• Parameterized Complexity of Generalized Domination Problems
• On parameters related to strong and weak domination in graphs

This page was built for publication: Parameterized complexity of weak odd domination problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842778)