Parametrized Complexity of Weak Odd Domination Problems

Abstract

Given a graph $G=(V,E)$, a subset $B\subseteq V$ of vertices is a weak odd dominated (WOD) set if there exists $D\subseteq V\setminus B$ 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 ${\kappa }^{\prime }(G)$ the size of the smallest non-WOD set. The maximum of $\kappa (G)$ and $|V|-{\kappa }^{\prime }(G)$, denoted ${\kappa }_Q(G)$, plays a crucial role in quantum cryptography. In particular deciding, given a graph $G$ and $k>0$, whether ${\kappa }_Q(G)\le k$ is of practical interest in the design of graph-based quantum secret sharing schemes. The decision problems associated with the quantities $\kappa$, ${\kappa }^{\prime }$ and ${\kappa }_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 ${\kappa }_Q$, $\kappa$ and ${\kappa }^{\prime }$ admit a constant factor approximation algorithm, and that $\kappa$ and ${\kappa }^{\prime }$ have no polynomial approximation scheme unless P=NP.

16 pages, 5 figures

References in corpus (4)

• The Parameterized Complexity of Domination-type Problems and Application to Linear Codes
• New Protocols and Lower Bound for Quantum Secret Sharing with Graph States
• On Weak Odd Domination and Graph-based Quantum Secret Sharing
• On the Minimum Degree up to Local Complementation: Bounds and Complexity

Cited by in corpus (3)

• The Parameterized Complexity of Domination-type Problems and Application to Linear Codes
• Minimum Degree up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms
• Access structure in graphs in high dimension and application to secret sharing