11 citations · 18 across the 6 of their papers we have counts for
19 papers · 1 filter
The Complexity of Kings
Edith Hemaspaandra, Lane A. Hemaspaandra, Osamu Watanabe
A king in a directed graph is a node from which each node in the graph can be reached via paths of length at most two. There is a broad literature on tournaments (completely orient…
Isomorphic Implication
Michael Bauland, Edith Hemaspaandra
We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set…
All Superlinear Inverse Schemes are coNP-Hard
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
How hard is it to invert NP-problems? We show that all superlinearly certified inverses of NP problems are coNP-hard. To do so, we develop a novel proof technique that builds diago…
Complexity Results in Graph Reconstruction
Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski +1
We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs…
Dichotomy Theorems for Alternation-Bounded Quantified Boolean Formulas
Edith Hemaspaandra
In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems, showed that a…
Complexity of Cycle Length Modularity Problems in Graphs
Edith Hemaspaandra, Holger Spakowski, Mayur Thakur
The even cycle problem for both undirected and directed graphs has been the topic of intense research in the last decade. In this paper, we study the computational complexity of \e…