6 papers
Lettericity Is NP-Complete
Henning Fernau, Samuel German, Kevin Mann +1
The lettericity of a graph is the smallest size of a set such that there exist and a so-called decoder for which is is…
Exact Accepting-State Spectrum for Reversal of Permutation Automata
Samuel German
We determine the accepting-state spectrum of reversal for permutation automata exactly, thereby proving the Rauch--Holzer conjecture on this operation. For every and ever…
Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
Samuel German
A vertex-coloring of a connected graph is a strong conflict-free vertex-connection coloring if every two distinct vertices are joined by a shortest path on which some color app…
Layer-Based Width for PAFP
Samuel German
The Path Avoiding Forbidden Pairs problem (PAFP) asks whether, in a directed graph with terminals and a set of forbidden vertex pairs, there is an - p…
A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
Samuel German
This paper resolves the open larger-alphabet quotient case in the accepting-state complexity theory of permutation automata. Rauch and Holzer showed that, in the unary setting, the…
The Path-Extremal Conjecture for Zero Forcing: Distance-Hereditary Graphs and a Split-Decomposition Reduction
Samuel German
For an -vertex graph , let denote the number of zero forcing sets of size . A conjecture of Boyer et al. asserts that the path maximizes these numbers coeff…