8 citations · 19 across the 10 of their papers we have counts for
11 papers
The Complexity of Domatic Criticality
Holger Spakowski
The domatic number dom(G) of a graph G is the maximum number of dominating sets in a partition of its vertex set. A graph is domatically critical if deleting any edge lowers its do…
Closing the Complexity Gap for Exact Domatic Number at Three and Four
Holger Spakowski
The exact domatic-number problem asks, for a fixed integer k, whether a given graph G satisfies dom(G) = k. Riege and Rothe proved DP-completeness for every fixed k >= 5, while the…
Team Diagonalization
Lane A. Hemaspaandra, Holger Spakowski
Ten years ago, Glaßer, Pavan, Selman, and Zhang [GPSZ08] proved that if P NP, then all NP-complete sets can be simply split into two NP-complete sets. That advance might nat…
The Robustness of LWPP and WPP, with an Application to Graph Reconstruction
Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski +1
We show that the counting class LWPP [FFK94] remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossibl…
Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
Gabor Erdelyi, Lane A. Hemaspaandra, Joerg Rothe +1
We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-ti…
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
Gabor Erdelyi, Lane A. Hemaspaandra, Joerg Rothe +1
We investigate issues related to two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former, Chri…