A zero-forcing set of a graph is a set for which, after regarding each of its vertices as being blue, and applying the rule that a blue vertex with exactly one white neighbor forces said neighbor to become blue, all of the vertices in the graph are blue. Let $z(G;k)$ denote the number of zero forcing sets of size $k$. A conjecture of Boyer et al.\ asserts that the path $P_n$ maximizes these numbers coefficientwise among all $n$-vertex graphs. We prove this path-extremal conjecture for distance-hereditary graphs, which is the class of all graphs $G$ such that for each of the connected induced subgraphs of $G$, the distances between any two vertices in that subgraph are the same as they are in $G$. This extends the previously known tree case in which the path-extremal conjecture was known to be true to a much larger class that includes, in particular, all trees and all cographs. We then use canonical split decomposition to push the argument we used to show the distance-hereditary result into the more general setting of a connected graph with at most one prime bag in its canonical split decomposition. Specifically, we show that if a split-prime graph $H$ and all of its induced subgraphs are path-extremal, then every connected graph whose canonical split decomposition has a unique prime bag whose label graph is isomorphic to $H$ is also path-extremal. As a corollary of this result, for each fixed $m$, if every induced subgraph of every split-prime graph on at most $m$ vertices is path-extremal, then so is every connected graph whose canonical split decomposition has a unique prime bag of size at most $m$. Additionally, we prove that the path-extremal conjecture holds when all prime bags have order at most six, without restricting their number; under the preceding hereditary hypothesis, one additional prime bag labelled by $H$ is also allowed.
In this paper we determine the accepting-state spectrum of the reversal operation on permutation automata, and moreover prove the conjecture conjectured by Rauch and Holzer in so doing. Namely, we show that reversal satisfies the spectrum $g^{\operatorname{asc}}_{R,\mathrm{PFA}}(0)=\{0\}$, $g^{\operatorname{asc}}_{R,\mathrm{PFA}}(1)=\{1\}$, and $g^{\operatorname{asc}}_{R,\mathrm{PFA}}(m)=\mathbb{N}_{\ge 2}$ for $m\ge 2$. We do this by, for every $m\ge 2$ and every $α\ge 2$, constructing a binary permutation automaton $A_{m,α}$ such that $ \operatorname{asc}(L(A_{m,α}))=m$ and $ \operatorname{asc}(L(A_{m,α})^{R})=α$. The spectrum above follows from this (combined with the trivial cases $m=0$ and $m=1$ and the fact that $1$ is magic for every $m\ge 2$). Thus our result shows that for $m \ge 2$, the reversal operation in permutation automaton attains ever single value positive value in the accepting-state complexity except for $1$.
The Path Avoiding Forbidden Pairs problem (PAFP) asks whether, in a directed graph $G$ with two of its vertices labeled $s,t$ and a set $\mathcal F$ of forbidden vertex pairs, there is an $s$--$t$ path that contains at most one endpoint from each pair in $\mathcal F$. We initiate the study of PAFP through a layer-based width measure. We first look at the directed union digraph $G\cup\mathcal F$, which is obtained by adding one arc per forbidden pair to $G$, oriented according to a fixed reachability-compatible order. Let the BFS layer $L_d$ be the set of vertices at directed shortest-path distance $d$ from $s$, and define the BFS-width from $s$ as $\max_d |L_d|$. We show that if $G\cup\mathcal F$ has BFS-width $b$ from $s$, and $p$ is the maximum, over BFS-layer cuts, of the smaller of the numbers of distinct heads and distinct tails of backward arcs crossing the cut, then PAFP is FPT parameterized by $b+p$. Here a backward arc goes from a later BFS layer to an earlier one. In contrast, we show that bounded BFS-width alone does not suffice: PAFP remains $\mathsf{NP}$-complete when the union digraph has BFS-width 2. We also study layer-based width parameters on the input graph. We show that if the input DAG has BFS-width at most $2$ and only $k$ backward input arcs, then PAFP can be decided in $2^k |I|^{O(1)}$ time, with unrestricted forbidden pairs, and this result is tight. Moreover, we study exact-length layers in the input graph, where the $d$-th exact-length layer consists of the vertices reachable from $s$ by a directed path of length exactly $d$. We show that for DAGs of exact-length width at most $2$, PAFP is polynomial-time decidable by a $2$-SAT encoding of fixed-length paths. Unlike previously known polynomial-time regimes our 2 input -graph tractability results simultaneously allow unrestricted forbidden pairs and input graphs with exponentially many $s$--$t$ paths.
This paper determines the accepting-state spectrum of the right-quotient operation for permutation automata, solving an open problem posed by Rauch and Holzer. They showed that in the unary case in which the languages whose right quotient we consider are languages over an alphabet with but one symbol, the accepting state complexities which could ensue for automata recognizing their quotient is exactly all integers between $1$ and $mn$ inclusive when $m,n \ge 1$; we show that for arbitrary alphabets the accepting-state spectrum is $g^{\operatorname{asc}}_{-1,\mathrm{PFA}}(m,n)=\{0\}$ if $m=0$ or $n=0$, and $g^{\operatorname{asc}}_{-1,\mathrm{PFA}}(m,n)=\mathbb{N}_{>0}$ if $m,n\ge 1$. Our result shows that every positive accepting-state complexity ensues for right quotient as long as both of the languages of which we consider the right quotient are nonempty. $0$ becomes the only unavoidable magic value. Moreover, we show that an alphabet with just two letters can witness any arbitrary $α\ge 1$ when $m,n \ge 1$, in that languages can be defined over a binary alphabet with accepting-state complexity $m$ and $n$ respectively for which their right quotient has accepting-state complexity $α$. What ultimately happens in our proof is that we construct $(A^{\mathrm q}_{m,α},B^{\mathrm q}_{n,α})$ such that the words accepted by $B^{\mathrm q}_{n,α}$ induce a point stabilizer in a symmetric group, and the standard quotient construction giving an automaton recognizing the quotient language then saturates the original final set of $A^{\mathrm q}_{m,α}$ to a full orbit; this gives a minimal quotient automaton with exactly $α$ final states. The complete spectrum which is our result follows from this, solving the open question of what the right quotient's accepting-state complexity for permutation automata is.
A strong conflict-free vertex connection coloring of a graph is a graph coloring for which, for every two distinct vertices of the graph, there exists a shortest path between them in which some color in said coloring appears only once. The strong conflict-free vertex connection number, denoted by $\operatorname{svcfc}(G)$, is the number of colors in the strong conflict-free vertex connection coloring with the smallest amount of colors out of all such colorings of $G$. We study the problem of deciding whether this number is at most some threshold together with the parameter twin cover. Our first result is that when we have given $(G,k)$ in which $k$ is some target number of colors and given some twin cover $X$ of $G$ which is of size $t$, there is a polynomial time reduction to an equivalent instance which has at most $\max\{2,t+k2^t\}$ vertices. This result allows us to give a kernel for Strong CFVC Number which is parameterized by $\operatorname{tc}(G)+k$, which implies that Strong CFVC Number is FPT w.r.t. the twin-cover number of $G$ so long as $k$ is fixed. Our second result is that if $G$ is a connected graph for which there exists a twin cover of size $t$, then $χ(G)\le \operatorname{svcfc}(G)\le χ(G)+t$. Our last result is an an exact expression for the chromatic number of graphs whose twin cover number is bounded. Namely, we show that for every proper coloring $\varphi$ of $G[X]$, the minimum number of colors needed to extend $\varphi$ to all of $G$ is $K_\varphi=\max_{S\subseteq X}(|\varphi(S)|+m(S))$, and hence $χ(G)=\min_{\varphi\text{ proper on }G[X]} K_\varphi$. Our results indicate that twin cover is a meaningful parameter in the context of strong conflict-free vertex-connection, and show that once we have a fixed twin cover, the only difficulty left is in some additive threshold above the chromatic number.