Parametrized Complexity of Weak Odd Domination Problems
arXiv:1206.4081 · doi:10.1007/978-3-642-40164-0_13
Abstract
Given a graph , a subset of vertices is a weak odd dominated (WOD) set if there exists such that every vertex in has an odd number of neighbours in . denotes the size of the largest WOD set, and the size of the smallest non-WOD set. The maximum of and , denoted , plays a crucial role in quantum cryptography. In particular deciding, given a graph and , whether is of practical interest in the design of graph-based quantum secret sharing schemes. The decision problems associated with the quantities , and 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-hardness) of these problems. Regarding the approximation, we show that , and admit a constant factor approximation algorithm, and that and have no polynomial approximation scheme unless P=NP.
arXiv comment16 pages, 5 figures
References in corpus (5)
- Graph States for Quantum Secret Sharing
- 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