Department of Computer Science, Bar Ilan University, Ramat Gan 52900, Israel;
and Georgia Tech, College of<EMAIL_ADDRESS>supported by ISF grant 168/23 and BSF grant 2018-141. Department of Computer
Science, Bar Ilan University, Ramat Gan 52900,
<EMAIL_ADDRESS>supported by ISF grant 168/23.
Amihood Amir and Michael Itzhaki

# Explicit Combinatoric Structures of Palindromes and Chromatic Number of
Restriction Graphs

Amihood Amir  Michael Itzhaki

###### Abstract

The palindromic fingerprint of a string $S[1\ldots n]$ is the set
$PF(S)=\\{(i,j)\leavevmode\nobreak\ |\leavevmode\nobreak\ S[i\ldots j]\textit{
is a maximal }\\\ \textit{palindrome substring of }S\\}$. In this work, we
consider the problem of string reconstruction from a palindromic fingerprint.
That is, given an input set of pairs $PF\subseteq[1\ldots n]\times[1\ldots n]$
for an integer $n$, we wish to determine if $PF$ is a valid palindromic
fingerprint for a string $S$, and if it is, output a string $S$ such that
$PF=PF(S)$. I et al. [SPIRE2010] showed a linear reconstruction algorithm from
a palindromic fingerprint that outputs the lexicographically smallest string
over a minimum alphabet. They also presented an upper bound of
$\mathcal{O}(\log(n))$ for the maximal number of characters in the minimal
alphabet.

In this paper, we show tight combinatorial bounds for the palindromic
fingerprint reconstruction problem. We present the string $S_{k}$, which is
the shortest string whose fingerprint $PF(S_{k})$ cannot be reconstructed
using less than $k$ characters. The results additionally solve an open problem
presented by I et al.

###### keywords:

Lower bound,Palindrome,String

##  1 Introduction

One of the methods for understanding the essence of data structures is by
analyzing a candidate to decide whether it is a legal instance of the data
structure. Suppose, for example, one is given a permutation $P$ and needs to
decide if a string $S$ exists such that $P$ is its suffix array. Another
example, given a matrix, decide if it is an adjacency matrix of a planar
graph. We henceforth refer to this problem as recognizing or reconstructing a
data structure.

There are several reasons for wanting to recognize data structures. 1) From a
purely theoretical point of view, there is a clear theoretical combinatorial
interest in this endeavor. 2) From a practical point of view, general graph
problems are known to be hard [9]. Nevertheless, a subset of these problems
are efficiently computable on special graphs, such as planar graphs, interval
graphs, etc. Quickly recognizing these special graphs can provide us with
efficient algorithms in specialized cases. 3) Understanding the nature of data
structures may lead to more efficient ways of constructing them. 4)
Understanding the nature of a data structure may aid in ways of efficiently
maintaining it in a dynamic environment.

The intriguing line of research into efficiently recognizing data structures
has a long history in pattern matching and is an ongoing topic of interest [1,
3, 5, 7, 15, 18, 6, 14, 4, 17, 22, 13, 2, 20].

Syntactic regularities in strings play a pervasive role in many facets of data
analysis. Searching for repeated patterns, periodicities, symmetries, and
other similar forms or unusual patterns in objects is a recurrent task in the
compression of data, symbolic dynamics, genome studies, intrusion detection,
and countless other activities. A palindrome is a string that is equal to its
reverse. Palindromes are a basic syntactic regularity that has been explored
for thousands of years. In addition to its myriad theoretical virtues, the
palindrome also plays an important role in nature. Because the DNA is double-
stranded, its base-pair representation offers palindromes in hairpin
structures, for example. A variety of restriction enzymes recognize and cut
specific palindromic sequences. In addition, palindromic sequences play roles
in methyl group attachment and T cell receptors. For examples of the varied
roles of palindromes in biology see, e.g. [12, 8, 19, 23].

Consider, now, the problem of reconstructing a string from its palindromic
fingerprint. We formally define the problem as follows.

######  Definition 1.1 (Palindromic Fingerprint).

Let $S$ be a string and $(i,j)$ be a palindromic descriptor of $S$ using
start-end representation, i.e., $S[i..j]$ is a palindrome. $(i,j)$ is a
maximal palindrome if and only it cannot be extended, meaning that the
palindromic descriptor $(i-1,j+1)$ is either not defined, or is not a
palindrome. We refer to a nonempty maximal palindrome as a palindromic
substring.

The palindromic fingerprint of $S$, or simply a Fingerprint, is a list of all
pairs of indices $(i,j)$, where $S[i\ldots j]$ is a maximal palindrome. We
denote this fingerprint by $PF(S)$.

The problem of reconstructing a string from its palindromic fingerprint is:

######  Problem 1.2 (The palindromic fingerprint reconstruction problem).

Input: A natural number $n$ and a list $F$ of pairs of indices $(i,j)$, where
$i<j$ and $1\leq i,j\leq n$.
Output: A string $S$ of length $n$ where $PF(S)=F$, or report that there can
not exist a string $S$ of length $n$ whose palindromic fingerprint is $F$.

An example can be found at Example C.2.

###  1.1 Related Work

I et al. [16] talk in their paper about problem 1.2 and solve it in linear
time with the minimum alphabet by using a greedy approach that introduces the
lexicographically smallest character to the reconstruction on demand. To the
best of our knowledge, the paper by I et al. talks about a lexicographically
minimal string but does not provide proof that their algorithm produces the
minimal alphabet size. In this paper we prove that their algorithm indeed
produces a minimal alphabet size.

Gawrychowski et al. [11] present a general linear-time algorithm for
reconstructing a string satisfying a set of positive-only constraints, in
particular from runs or palindromes. A positive-only constraint is a
constraint of the form $T[i\ldots i+\ell]=T[j\ldots j+\ell]$. Such a set of
constraints can present palindromes, but cannot describe maximal palindromes,
as maximal palindromes also introduce a negative constraint. The general
reconstruction problem over the minimal alphabet, using both negative and
positive constraints on a string is known to be $\mathcal{NP}$-hard (Shown at
1), as it is equivalent to the graph-coloring problem, even when the negative
constraint length is at most 1, i.e., only constraints of the form $a[i]\neq
a[j]$. It is well known that calculating the chromatic number of a general
graph is hard [10].

###  1.2 Our Contribution

In this paper, we discuss problem 1.2. We present an explicit structure of a
fingerprint that needs at least $k$ characters to reconstruct and provide a
method to reconstruct any palindromic fingerprint with exactly $k$ different
characters, where $k$ is an algorithm’s argument. By doing so, we solve the
open problem presented by I et al. [16], of finding a string with a
fingerprint that contains exactly $k$ different alphabet symbols.

Our main results show a careful analysis of palindromic fingerprints - tight
bounds on the relation between the fingerprint size and the minimal alphabet
size of a string reconstructing it. We also analyze different types of
palindromes and show an explicit structure of the shortest palindromic
fingerprint that requires $k$ characters to reconstruct. We also present
problem 1.2 as a graph coloring problem, which, combined with the algorithm of
I et al., can produce all possible alphabet sizes for a given palindromic
fingerprint.

Our main result implies the following theorem:

######  Theorem 1.3.

Let $IPF(k)$ be the shortest length $n$ of a palindromic fingerprint that can
not be reconstructed with less than $k$ characters. The function is the
following:

$IPF(k)=\begin{cases}1,&\text{if $k=1$}\\\
2^{k-2}+1,&\text{otherwise.}\end{cases}$

A corollary of the theorem is that any fingerprint $F$ of length $n$ can be
reconstructed with an alphabet of size at most $\log(n-1)+2$.

##  2 Preliminaries

Let $S=S[1]S[2]\ldots S[n]$ be a string. We denote the length of $S$ as
$|S|=n$. The empty string with $|S|=0$ is denoted as $\varepsilon$. For two
integers $i,j\in\\{1\ldots n\\}$, we denote as $S[i\ldots j]$ the substring of
$S$ starting at index $i$ and ending at index $j$, i.e., $S[i\ldots
j]=S[i]S[i+1]\ldots S[j]$. If $j<i$, $S[i\ldots j]$ is the empty string
$\varepsilon$. A prefix of $S$ is a substring $S[1\ldots i]$ starting at index
$1$, and a suffix of $S$ is a substring $S[i\ldots n]$ ending at index $n$.

For two strings $S$ and $T$, we denote the concatenation of $S$ and $T$ as
$ST=S[1]S[2]\ldots S[|S|]T[1]T[2]\ldots T[|T|]$. For an integer
$i\in\mathbb{N}$, we denote as $S^{i}$ the concatenations of a string to
itself $i$ times, i.e., $S^{1}=S$, and $S^{i}=S^{i-1}\cdot S$, for any $i\geq
2$.

$S$ is called a palindrome or palindromic if $\forall_{1\leq
i<|S|}S[i]=S[|S|-i+1]$. For example, $S=abcba$, or $S=abccba$ are palindromes.
However, $S=abcbaa$ is not a palindrome. A nonempty substring $P=S[i\ldots j]$
is called a maximal palindrome of $S$ if $P$ is a palindrome, and either
$i=1$, $j=n$, or $S[i-1]\neq S[j+1]$. The center of $P$ is
$c_{P}=\frac{i+j}{2}$ and its radius is $r_{P}=\frac{j-i}{2}$. Note that there
are $2n-1$ centers in $S$, each of which is the center of at most one maximal
palindrome substring. 111When counting maximal palindromes of length 0, there
is exactly one palindrome at each center.

######  Definition 2.1.

Let $S$ be a string. We say that a character $c$ occurs in $S$ if and only if
$\exists i$ s.t. $S[i]=c$.

######  Definition 2.2 (Trivial palindrome).

A trivial palindrome is a palindrome of length at most 1.

######  Definition 2.3 (Palindromic descriptor).

A maximal palindromic descriptor is a pair of integers $(i,j)$ inside a
palindromic fingerprint $F$ that describes a palindrome between indices $i$
and $j$.

An example to a palindromic fingerprint can be found at Example C.3.

######  Definition 2.4.

Let $G=(V,E)$ be a graph. The function $\psi:V\to\mathbb{N}$ is a graph
coloring if and only if $\forall(i,j)\in E,\psi(i)\neq\psi(j)$.

######  Definition 2.5.

A palindromic fingerprint $F$ is valid if and only if there exists a string
$S$ such that $F=PF(S)$. Any string $S$ that satisfies $PF(S)=F$ is called a
preimage of $F$.

######  Example 2.6.

Let $S=(abc)^{n}$. There are no non-trivial palindromes in $S$, thus the
fingerprint is $\\{\\}$.

##  3 The Alphabet Upper Bound Theorem

We are now ready to prove the main theorem, which we repeat below: See 1.3

######  Example 3.1.

Let $k=5$. By the theorem, $IPF(5)=9$, which means that the shortest
fingerprint that cannot be reconstructed with less than 5 characters is of
length 9. The fingerprint $A=(\\{(2,8),(2,4),(6,8)\\},9)$ can be described as
a restriction graph that is a clique of size 5, hence $IPF(5)\leq 9$. However,
all fingerprints of length 8 can be recovered with four or fewer characters.
222Will be proven later and can be checked manually.

From now on, we represent the input as a pair: $(F,n)$, where $F$ is the
palindromic fingerprint, and $n$ is the length of the string we aim to
reconstruct.

The proof overview can be found at Section B.1, and is a suggested reading.

###  3.1 The Restriction Graph

In this subsection we will present the Restriction Graph superficially. The
restriction graph is an important tool to understand the palindromic
fingerprint reconstruction in depth. The in-depth details of restriction
graphs can be found at Section A.1.

######  Definition 3.2 (Restriction graph).

The restriction graph of a palindromic fingerprint and length $(F,n)$ is a
graph $G=(V,E)$ where there is a bijection between the reconstruction of
$(F,n)$ and a coloring of $G$.

Let $(F,n)$ be a palindromic fingerprint. We define $G=(V,E)$, where $V$ is a
partition of $\\{1,\ldots,n\\}$, i.e.,

  1. 1.

$\forall v\in V,$ $v\subseteq\\{1,\ldots,n\\}$ and $v$ is not empty.

  2. 2.

$\underset{v\in V}{\bigcup v}=\\{1,\ldots,n\\}$

  3. 3.

$\forall v_{1},v_{2}\in V,v_{1}\cap v_{2}=\emptyset$

Every node in $V$ presents symbols of $F$ that must be equal. Every edge in
$E$ presents two different symbol groups in $V$ that must not be equal.
Formally:

  1. 1.

$\forall i,j<n$, if there exists a palindromic restriction $F[i]=F[j]$, then
$i,j$ are members of the same vertex in $G$.

  2. 2.

$\forall i,j<n$, where $i$ is in $v_{i}$ and $j$ is in $v_{j}$, if there
exists a palindromic restriction $F[i]\neq F[j]$, then $(v_{i},v_{j})\in E$.

The graph has a self-loop, i.e., $(v_{i},v_{i})\in E$ for some $v_{i}$ if and
only if the palindromic fingerprint is not reconstructible.

###  3.2 Proof Setup

In this subsection, we refer to a palindromic fingerprint $F$ of length $n$
without declaring it. We include the more general definitions that will be
used throughout both parts of the proof in this subsection.

######  Definition 3.3 (Reconstruction degree).

The reconstruction degree $k$ of a fingerprint $F$ of length $n$ is the
minimal number of characters required to reconstruct $(F,n)$, and is denoted
by $\sigma(F,n)$, or simply $\sigma(F)$.

######  Definition 3.4 (Optimal fingerprint).

A fingerprint $(F,n)$ is called optimal if $\forall F^{\prime},n^{\prime}<n$
$\sigma(F^{\prime})<\sigma(F)$.

######  Definition 3.5 (Optimal string).

A string $S$ is called optimal if $PF(S)$ cannot be reconstructed with fewer
characters than $S$ has.

######  Definition 3.6.

The symbol $F[i]$ denotes the character at position $i$ in any string
reconstructing $F$. Unlike standard strings, in a fingerprint, it is possible
that neither $F[i]=F[j]$ nor $F[i]\neq F[j]$. For example, an empty
palindromic fingerprint of length four can be reconstructed both as $abca$ and
$abcd$. Therefore, $F[1]$ and $F[4]$ comparison is not defined by $F$.
However, $F[1]\neq F[2]$ and $F[1]\neq F[3]$. We use standard string notations
on palindromic fingerprints.

######  Definition 3.7 (Palindromic restrictions).

Let $P$ be a palindromic descriptor $(i,j)$ inside $F$. The palindromic
restrictions of $P$ are:

  1. 1.

$\forall r$ where $0\leq r\leq j-i$, $F[i+r]=F[j-r]$.

  2. 2.

$F[i-1]\neq F[j+1]$.

######  Definition 3.8.

Let $i,j$ be indices in $F$. We say that index $i$ affects index $j$ if and
only $F[i]=F[j]$ or $F[i]\neq F[j]$. If $F[i]=F[j]$ and $F[j]=F[k]$, index $i$
does not necessarily affect index $k$.

[Adjacent relations] For every index $i\leq n+2$, $F[i]$ affects both $F[i+1]$
and $F[i+2]$.

######  Definition 3.9.

Let $P$ be a palindromic descriptor in $F$. We define
$start(P)=i,end(P)=j,center(P)=(i+j)/2$.

######  Definition 3.10 (Crossing palindromes).

Let $P_{1},P_{2}$ be palindromic descriptors in $F$. If
$start(P_{1})<start(P_{2})\land end(P_{1})<end(P_{2})$, then $P_{1},P_{2}$ are
crossing palindromes.

We call a palindromic fingerprint with no crossing palindromes a non-crossing
palindromic fingerprint. An example can be found at Example C.1.

######  Definition 3.11.

Let $P_{1},P_{2}$ be two crossing palindromes. We say $P_{2}$ is dominated by
$P_{1}$ if the center of $P_{2}$ is part of $P_{1}$.

Note that it is possible for $P_{1}$ to dominate $P_{2}$ and $P_{2}$ to
dominate $P_{1}$ simultaneously.

######  Definition 3.12.

Let $P_{1},P_{2},\ldots,P_{n}$ be a set of palindromes such that $P_{i}$ and
$P_{i+1}$ are crossing, $i=1,\ldots,n-1$. We call
$F[start(P_{1})..end(P_{n})]$, the substring defined by
$P_{1},P_{2},\ldots,P_{n}$ on $F$ and denote it by $P_{1..n}=\bigcup_{i\leq
n}P_{i}$.

######  Definition 3.13.

Let $P_{1},P_{2}$ be two crossing palindromes. The intersection between
$P_{1},P_{2}$ is the substring $F[start(P_{2})..end(P_{1})]$ and denoted by
$P_{1}\cap P_{2}$.

######  Definition 3.14 (Standalone reconstruction).

Let $I$ be a palindromic island $(j,\ell)$ in a fingerprint $(F,n)$. A
standalone reconstruction of $I$ is the process of reconstructing $(F,n)$,
where only restriction inside $I$ must be addressed in the reconstruction
procedure.

An example can be found at Example C.6.

There are multiple ways to represent a palindrome, such as the start-length
and center-radius notation. For ease of discourse, we use the start-length
notation, i.e., $(i,\ell)$ stands for the palindrome $S[i..i+\ell-1]$.

##  4 Proof for Non-crossing Palindromes

In this section, we will prove the following restricted lemma.

######  Lemma 4.1.

Let $k\geq 3$ be an integer, and let $P_{k}$ be the Zimin word, i..e,
$P_{1}=1$, $P_{k}=P_{k-1}kP_{k-1}$.

Considering only palindromic fingerprints that do not describe crossing
palindromes, the palindromic fingerprint of $xP_{k-2}y$, where $x,y\notin
P_{k-2}$ is the shortest palindromic fingerprint that can not be reconstructed
with less than $k$ characters and is unique.

###  4.1 Induction Hypothesis

Let $F_{k}$ be the shortest palindromic fingerprint that cannot be
reconstructed with fewer than $k$ characters, and let $S_{k}$ be a preimage
with an alphabet of size $k$, i.e., $|\Sigma_{S_{k}}|=k$.

The structure of $S_{k}$ is defined as $xLtLy$, where $L$ is a palindrome, and
$x,t,y$ are letters not appearing in $L$. In addition, $xLt,tLy$ are the
recursive instances $S_{k-1}$, for $k\geq 4$. We additionally claim that all
strings reconstructing $F_{k}$ parameterize match to $S_{k}$.

The base of the induction is $S_{3}=123,S_{4}=12324$. Any palindromic
fingerprint of length four can be reconstructed using three characters or
less.

Any empty palindromic fingerprint can be reconstructed with three characters -
a prefix of $(abc)^{\infty}$. As a result, we can assume that for $k\geq 4$,
and that we have a palindrome of length $\geq 2$. Moreover, any palindrome of
length $\leq 2$ consists of one character and, therefore, can be reconstructed
with the string $(abc)^{\infty}$, where characters are doubled where a
palindrome of length 2 occurs. Consequently, we will assume fingerprints to be
of length at least four and contain a palindrome of length $\geq 3$.

###  4.2 Maximal Islands

We now define the palindromic islands, a key definition for the rest of the
proof.

######  Definition 4.2 (Palindromic island).

Let $i\in\mathbb{N}$ be an index. Then the maximal palindromic island for
index i, $I^{\prime}_{i}=(j^{\prime}_{i},\ell^{\prime}_{i})$ is the longest
maximal palindrome in $F$ such that $j^{\prime}_{i}\leq
i<j^{\prime}_{i}+\ell^{\prime}_{i}$. If $i$ participates in no palindrome,
then $I^{\prime}_{i}=(i,1)$.
The palindromic islands of a string are the set
$\mathcal{I}=\\{I_{1},I_{2},\ldots\\}$, where $\forall i\exists j$ s.t.
$I^{\prime}_{i}=I_{j}$.

An example can be found at Example C.5.

The name islands is used because of the absence of palindromes between two
distinct islands. We will now state and prove this property.

######  Lemma 4.3.

Let $I_{i}=(j_{i},\ell_{i}),I_{m}=(j_{m},\ell_{m})\in\mathcal{I}$ be two
distinct islands, $i<m$. $I_{i},I_{m}$ do not share a palindrome, i.e., there
does not exist a palindrome $(i,j)\in F$ such that $i<j_{i}+\ell_{i},j\geq
j_{m}$.

######  Proof 4.4.

If $i<m$ then $j_{i}<j_{m}$, as otherwise $I_{m}$ is contained in $I_{i}$, and
is not an island. Moreover, because maximal palindromes are not allowed to
cross each other, we know that $j_{i}+\ell_{i}\leq j_{m}$. To show that
$I_{i}$ and $I_{m}$ are not crossing, it is enough to show that there is no
palindrome starting at the interval of $I_{i}$ and ending at the interval of
$I_{m}$. However, such a palindrome would both cross $I_{i}$ and $I_{m}$,
hence does not exist.

######  Corollary 4.5 (Maximal intervention).

Let $I=(j,\ell)$ be a palindromic island where $\ell\geq 2$. The island $I$
shares no palindromes with any other island, but the first and last two
characters of the island can still be influenced by other islands. The
influence is an inequality relation (Definition 3.8).

[Refined maximal intervention] Let
$I_{i}=(j_{i},\ell_{i}),I_{i+1}=(j_{i+1},\ell_{i+1})$ be two neighboring
islands. The only explicit relation between index $j_{i+1}+1$ and any index
within $I_{i}$ is the inequality $S_{k}[j_{i+1}+1]\neq S_{k}[j_{i+1}-1]$. A
similar claim is true for index $j_{i}+\ell_{i}-2$.

######  Definition 4.6.

Let us consider any arbitrary algorithm $\mathcal{A}$ reconstructing
palindromic fingerprints optimally, i.e., with the fewest possible characters.
Let $I\in\mathcal{I}$ be an island, $I\in F$. $\Sigma_{I}$ is the set of
characters used to reconstruct $I$ stand-alone using $\mathcal{A}$, and
$\Sigma_{S}$ is the set of characters used to reconstruct the whole
fingerprint.

######  Lemma 4.7.

Let $m=\max(|\Sigma_{I_{1}}|,|\Sigma_{I_{2}}|,\ldots)$, then
$|\Sigma_{S_{k}}|\leq m+2$.

######  Proof 4.8.

We will begin by proving that $|\Sigma_{S_{k}}|\leq m+4$.

Let $I_{i}=(j_{i},\ell_{i})$ be the island with maximal $m=|\Sigma_{I_{i}}|$.
To simplify the analysis, we initially assume that for all $i$, $\ell_{i}\geq
2$. We will address the general case later on.

Due to the maximality of $I_{i}$, each of the other islands can be
reconstructed stand-alone using at most $m$ distinct characters. At Corollary
4.5 we showed that the only indices sharing palindromic restrictions with
$I_{i}$ are $j_{i}-1,j_{i}-2,j_{i}+\ell_{i},j_{i}+\ell_{i}+1$. At Definition
3.8 we claimed that the reconstruction of adjacent characters is
predetermined. As a result, the reconstruction of $I_{i-1}$ and $I_{i+1}$ can
still be performed using only $m$ characters, possibly introducing new
characters on the margins.

Consequently, reconstructing $I_{i+1},I_{i-1}$ requires at most $m$ distinct
characters at each island, each using at most 2 new characters that weren’t
used in the reconstruction of $I_{i}$.

To reconstruct $I_{i+2}$, two additional characters not present in
$\Sigma{I_{i+1}}$ might be required. However, assuming that the reconstruction
of $I_{i+1}$ and $I_{i-1}$ introduced four new characters, it means that there
are two characters in the reconstruction of $I_{i}$ that do not occur in the
reconstruction of $I_{i+1}$ and on the last two indices of $I_{i}$, and we can
use as the new characters required. It can be seen that even if $I_{i+1}$
introduced less than two new characters, an overall of 4 new characters will
not be exceeded.

We now consider islands of length one or trivial islands. In the first part of
the proof, we labeled the islands individually. However, if there are islands
of length one, we do not color them. Since the index of a trivial island has
an explicit palindromic restriction with no more than four other indices, and
because $|\Sigma_{S_{k}}|\geq 5$, we always have an existing color that the
index can use as a valid label.

Let us prove the tighter restriction $|\Sigma_{S_{k}}|\leq m+2$.

Similar to the beginning of the proof, let $I_{i}$ be the heaviest island,
describing $F[j_{i}..j_{i}+\ell_{i}-1]$, or simply $F[I_{i}]$. We now consider
explicitly the two characters adjacent to $F[I_{i}]$ as
$x_{1},x_{2},x_{3},x_{4}$, where
$x_{1}=F[j_{i}-2],x_{2}=F[j_{i}-1],x_{3}=F[j_{i}+\ell_{i}],x_{4}=F[j_{i}+\ell_{i}+1]$.
By the definition of islands, the maximal island $I_{i}$ describes a maximal
palindrome, which implies $x_{2}\neq x_{3}$. As a consequence of $x_{1},x_{4}$
having only one inequality relation with $I_{i}[1]=I_{i}[\ell_{i}]$, and since
we assumed that both $x_{2},x_{3}$ received new characters, we are left with
two options:

  1. 1.

$x_{1}=x_{2}$, in which case a new character is not added to the
reconstruction.

  2. 2.

$x_{1}\neq x_{2}$, in which case an existing character from $S_{k}$ can be
chosen because the number of distinct characters in $T_{i}$ is at least 2.

The same arguments can be made for $x_{3},x_{4}$, proving we need no more than
$m+2$ distinct characters for the entire string.

In the proof of Lemma 4.7, we used a greedy labeling approach; such an
approach is not yet proven to output the minimal alphabet size. This
observation can help the reader understand why we do not specify a coloring
algorithm but rather prove properties for all possible algorithms.

######  Corollary 4.9.

The palindromic fingerprint $F_{k}$ is either of the form $P$, $xP$, or $xPy$,
where $P$ is a descriptor of the maximal palindrome.

For the rest of the non-crossing proof, we will be using the symbol $P$ to
identify the middle palindrome from Corollary 4.9.

######  Lemma 4.10.

The length of the palindrome $P$ is odd.

The proof is at Section B.2.

######  Lemma 4.11.

Let $P=LtR$ and assume the structure of $F_{k}$ is $xPy$, then $L=R$ are
palindromes.

######  Proof 4.12.

If $L$ is not a palindrome, then we can either choose $x=t$ or $t\in L$.
333o/w, there cannot be a restriction $x\neq t$.

As the structure $F_{k}$ has no crossing palindromes, its middle character $t$
does not participate in any palindromes other than $P$. Consequently, if we
have the restriction $x\neq t$, it means $t$ is inside a palindrome bordering
with $x$, which cannot be $L$ as it is not a palindrome. In both cases, the
fingerprint of $xLRy$ cannot be reconstructed with fewer characters than
$xLtRy$, but is shorter, contradicting that $F_{k}$ optimal (shortest
possible).

Otherwise, we can set $x=t$ without violating any palindromic restriction.
Again, the fingerprint of $tLtRy$ can be reduced to $tLRy$, and $tLRy$ cannot
be reconstructed with less than $k$ characters.

######  Lemma 4.13.

The string $S$ reconstructing $F$ is either of the form $P$, $xP$ or $xPy$,
where $x,y\notin P$.

The proof is at Section B.2.

######  Lemma 4.14.

An optimal string is of the form $xPy$ where $x,y\notin P$, and $P$ is a
palindrome.

The proof is at Section B.2.

###  4.3 Recursive Structure

We have seen at Lemma 4.14 the structure of an optimal string. And now, we
show that the middle palindrome $P$ is recursive.

######  Lemma 4.15 (Explicit structure).

The string $S_{k}$ can be written as $xLtLy$, where $L$ is a palindrome, and
$x,t,y$ are distinct characters that satisfy $x,t,y\notin L$.

######  Proof 4.16.

All of the essential pieces were proven before, and this proof will just glue
them all together. First, by Lemma 4.14 we know that $F_{k}=xPy$, and
$x,y\notin P$. Using Lemma 4.10 we know that there exists a middle character
$t$. We proved at Lemma 4.11 that $L$ is a palindrome, and therefore the
overall structure is $xLtLy$, and both $x,y$ are unique. However, if $t\in L$,
then swapping $x$ and $t$ does not violate the fingerprint’s restrictions -
but contradicts Lemma 4.13.

######  Corollary 4.17.

The string $S=S_{k}=xPy$ can be written as $xLtLy$ where $xLt$ and $tLy$
correspond to $S_{k-1}$.

We have thus shown a clear recursive structure that matches the original
theorem, and the proof is completed for palindromic fingerprints with no
crossing palindromes.

##  5 Proof for General Fingerprints

In this section, we will not forbid crossing palindromes from participating in
the fingerprint.

######  Lemma 5.1.

Let $k\geq 3$ be an integer, and let $P_{k}$ be the Zimin word, i..e,
$P_{1}=1$, $P_{k}=P_{k-1}kP_{k-1}$.

The palindromic fingerprint of $xP_{k-2}y$, where $x,y\notin P_{k-2}$ is the
shortest palindromic fingerprint that can not be reconstructed with less than
$k$ characters and is unique.

###  5.1 String Ordering

Before beginning the proof, we will explain how a palindromic fingerprint can
be consistently split into substrings.

######  Definition 5.2 (Palindromic representative).

Let $i$ be an index within $S$. The representative palindrome for index $i$ is
the palindrome $P$ that:

  1. 1.

Contains index $i$.

  2. 2.

Is not contained within any other palindrome.

  3. 3.

Has the minimal ending index.

######  Lemma 5.3.

All palindromes are either contained in or are palindromic representatives,
and there are no two possible representatives for a single index.

######  Proof 5.4.

Let $P_{1},P_{2},\ldots,P_{m}$ be all palindromes that are not contained
within any other palindromes, such that $start(P_{i})<start(P_{i+1})$. For any
palindrome $P=F[i..j]$, the palindrome $P$ contains index $j$, and has a
minimal index $j$ of all palindromes that contain index $j$. According to our
definition, $P$ is not contained in any other palindrome, hence a valid
representative for index $j$. However, if there are two possible
representatives for index $j$, it means that both end at index $j$ and are not
of the same length, and therefore, one contains the other, contradicting the
way $P$ was defined.

Any fingerprint $F$ can be split into a series of palindromic representatives.

At Definition 4.2, we have defined palindromic islands. The concept can be
extended to palindromic representatives. We generalize an island to be a
series of non-foreign palindromes. Every two palindromic islands are foreign.

######  Lemma 5.5.

Let $F$ be a palindromic fingerprint split into palindromic islands
$I_{1}I_{2}\ldots I_{m}$. The minimal number of characters required to
reconstruct $F$ is either:

  1. 1.

$\max(\sigma(I_{i}))+2$ if $I_{i}$ is a palindrome, or

  2. 2.

$\max(\sigma(I_{i}))+1$ if $I_{i}$ is not a palindrome.

The proof is at Section B.2.

If the maximal degree island $I_{i}$ is not a palindrome, then the shortest
palindromic fingerprint with reconstruction degree $\sigma(F)$ is of length at
most $|I_{i}|+1$.

###  5.2 Proof

The proof process is incremental. We first partition the island $I$ into
crossing palindromes $P_{1},P_{2},\ldots,P_{m}$. We then prove many local
lemmas about reconstructing consecutive palindromes from within $I$, and then
logically "merging" consecutive crossing palindromes $P_{i},P_{i+1}$ into one
palindromic substring $P_{i..i+1}$, and showing that the lemmas also hold for
these substrings. By showing that, we iteratively prove our lemmas on all $I$,
as we can keep on merging new palindromes into the substring until it contains
all $I$.

######  Lemma 5.6.

Let $P_{1},P_{2}$ be crossing palindromes such that $P_{1}$ contains $P_{2}$.
The fingerprint $F^{\prime}=P_{1..2}$ satisfies
$\sigma(F^{\prime})\leq\sigma(P_{1})$.

The proof is at Section B.2

The following lemma is a key lemma for the rest of the proof.

######  Lemma 5.7.

Let $P_{1},P_{2}$ be crossing palindromes where neither $P_{1}$ is contained
in $P_{2}$ or the other way around, and let $F^{\prime}=P_{1..2}$, then
$\sigma(F^{\prime})\leq\max(\sigma(P_{1}),\sigma(P_{2}))+1$, and the number of
distinct characters used to reconstruct $P_{2}$ and $P_{1}$ is at most $m$ in
the reconstruction of $F^{\prime}$.

######  Proof 5.8.

We assume w.l.o.g that $\sigma(P_{1})\geq\sigma(P_{2})$. Let’s assume $P_{1}$
is reconstructed, and let $K$ denote the shared part of $P_{1}$ and $P_{2}$,
i.e., $K=P_{1}\cap P_{2}$.

Let $C_{1},\ldots,C_{m}$ be all of the crossing palindromes between $K$ and
$P_{2}$, such that for any $i,j\leq m$, $C_{i}$ is not contained in $C_{j}$.
First, we ignore all palindromes dominated by $P_{1}$, as they can not
introduce any new characters to the reconstruction. Let $C_{i}$ be a
palindrome that is not dominated by $P_{1}$. If $end(C_{i})\geq center(P_{2})$
then reconstructing $C_{i}$ suffices for the reconstruction of $P_{2}$. In
this case, we can reconstruct $C_{i}$ instead of $P_{2}$ in the lemma, and all
characters in $P_{2}$ will be reconstructed thereafter. Thus, let us assume
that such a descriptor does not exist and choose two crossing palindromes
$C_{i},C_{j}$ ($start(C_{i})<start(C_{j})$).

As we required before, both
$center(C_{i})>end(P_{1}),center(C_{j})>end(P_{1})$. Also, we required that
$C_{i}$ is not contained in $C_{j}$ and vice versa, therefore
$start(C_{i})<start(C_{j})$ and $end(C_{i})<end(C_{j})$. However, since
$start(C_{j})<end(P_{1})$ and $center(C_{i})>end(P_{1})$, we have
$start(C_{j})<center(C_{i})$, and $C_{i}$ is dominated by $C_{j}$. Let us call
the crossing palindrome with maximal end index $C$. After $C$ is
reconstructed, all other crossing palindromes $C_{i}$ do not have any free
symbols. The only index in $C$ that is not reconstructed and has inequality
palindromic relations with $P_{1}$ is $end(P_{1})+1$.

We now consider the reconstruction degree of $C$. We know that
$\sigma(C)\leq\sigma(P_{2})\leq m$. If $C$ introduces a new character at
$end(P_{1})+1=end(K)+1$, then $C$ has inequality relations with $m$ different
characters. In palindromic fingerprints, inequality relations can only result
from palindromes. Therefore, $m-1$ of the inequality relations occur within a
palindrome. If $K$ is not this palindrome, then $K$ contains this palindrome,
and the two characters next to it introduce two new characters, which implies
that $m+1\leq\sigma(P_{2})\leq\sigma(P_{1})=m$, and that’s a contradiction.
Therefore, in order for $C$ to introduce a new character, $K$ must be a
palindrome of reconstruction degree $m-1$.

We now consider $P_{2}$ again. We showed that $P_{2}$ has no crossing
palindromes with $K$ except for the palindrome $C$ (if it exists). For the
reconstruction degree of $P_{2}$ to be $m+1$, we need a symbol with $m$
inequality relations. If $C$ does not exist, we showed that there are at most
$m$ distinct symbols in $P_{2}$ in the latter paragraph. If $C$ exists, then
the index $end(C)+1$ might have many inequality relations with elements in
$C$, and the index $end(P_{1})+1$ is the new character $\$$ introduced at $C$.
For $P_{2}$ to have an inequality relation with the new character at
$end(P_{1})+1$, there must exist a maximal palindrome bordering with $\$$.
Still, if this maximal palindrome has $m-1$ characters and all have an
inequality relation with the bordering characters, then the reconstruction
degree of $P_{2}$ is $m+1$, which is a contradiction.

######  Lemma 5.9.

Let $P_{1},P_{2},P_{3}$ be crossing palindromes, and let
$\sigma(P_{1})\geq\max(\sigma(P_{2}),\sigma(P_{3}))$, then
$\sigma(P_{1..3})\leq\sigma(P_{1})+1$.

The proof is at Section B.2.

######  Corollary 5.10.

Let $P_{1},P_{2},\ldots,P_{n}$ be crossing palindromes.
$\sigma\left(\underset{i\leq
n}{\bigcup}P_{i}\right)\leq\max\left(\sigma(P_{i})\right)+2$

######  Lemma 5.11.

If $\sigma(P_{1}\cup P_{2}\cup P_{3})=\sigma(P_{2})+2$, the there exists a
fingerprint $F^{\prime}$ of length $|P_{2}|+2$ satisfying
$\sigma(P_{2})=\sigma(F^{\prime})$.

######  Proof 5.12.

At Corollary 5.10, we showed that the reconstruction of a palindromic island
requires at most $\sigma(P_{1}\cup P_{2}\cup P_{3})+2$ characters. Moreover,
at Lemma 5.7, we showed that new characters can only be introduced on indices
adjacent to the heaviest palindrome $P_{2}$. As a consequence, it implies that
if the indices adjacent to $P_{2}$ could have been reconstructed from the
existing characters, the reconstruction degree would be lower. Consequently,
they must have been introduced as new characters. Therefore, the heaviest
palindrome with its two adjacent indices cannot be reconstructed with less
than $\sigma(P_{2})+2$ characters.

######  Corollary 5.13.

The number of characters required to reconstruct a fingerprint $F$ is the
number of characters required to reconstruct its heaviest palindrome plus, at
most, two.

The last corollary concludes the vital components of the proof, as it shows
that any fingerprint can be reduced to a fingerprint with no crossing
palindromes. The methodology of converting such a string without reducing the
reconstruction degree or increasing the length of the fingerprint is as
follows:

  1. 1.

At Lemma 5.5 we show that the whole fingerprint is dominated by the heaviest
island, so the fingerprint can be reduced to one island, with up to two
additional characters.

  2. 2.

At Corollary 5.10 we show that a single island is dominated by the heaviest
representative, so we can only keep the representative.

  3. 3.

Use this method recursively on the last representative, omitting the two
additional characters added in step (1). Eventually, we will conclude that the
optimal string has no crossing palindromes, as the crossing palindromes can
always be removed, as shown at Lemma 5.11.

And since the overall fingerprint has no crossing palindromes, we achieve the
relaxed requirement of Lemma 4.1, and the proof of Theorem 1.3 is completed ∎.

##  6 Properties of the Results

In this section, we present the general properties of our result, show that
the algorithm presented by I et al. indeed outputs a globally minimal
alphabet, and present applications on real-world data.

######  Lemma 6.1.

Let $F_{k}$ be a minimal-length palindromic fingerprint that cannot be
recovered with less than $k$ characters. The restriction graph of $F_{k}$ is a
clique.

The proof is at Section B.2.

######  Lemma 6.2.

The palindromic fingerprint reconstruction algorithm of [16] produces a
minimal alphabet.

######  Proof 6.3.

At Lemma 5.7 we analyzed the positions that can introduce new characters to a
reconstruction. We showed that these positions only occur on the edge of other
palindromes, and we showed they cannot increase the overall reconstruction
degree of a single palindrome. Therefore, instead of analyzing the
reconstruction algorithm as if it started from the heaviest palindrome, the
analysis can start from the first possible index, and Lemma 5.7 will still
hold, and since the reconstruction algorithm [16] reconstructs the string from
the first index, and since it only introduces new characters when necessary,
its settings are the same as Lemma 5.7 and it outputs a minimal alphabet.

######  Lemma 6.4 (Open Problem by [16]).

Finding a string that has a given set of maximal palindromes $(F,n)$ and
contains exactly $k$ characters, where $k$ is a predefined parameter can be
achieved in time proportional to the construction of the restriction graph.

######  Proof 6.5.

Let us build the restriction graph $G$ of the input fingerprint $(F,n)$ and
run the algorithm by [16] to achieve a coloring of $G$ using a minimal number
of colors. The maximal number of characters in the resulting string $S$ is the
number of vertices in $G$. The minimal number is the number of distinct
characters returned by the algorithm. Any number not in this range is not
achievable. To increase the number from the minimal number to the maximal, we
can take two vertices that were colored with the same color, and color one of
them with a new color. When all vertices have a distinct color, the maximal
number is reached.

######  Corollary 6.6.

Let $(F,n)$ be an arbitrary palindromic fingerprint. Let $G$ be the
restriction graph of $F$. The chromatic number of the graph $\chi(G)$
satisfies $\chi(G)\leq\log(n-1)+2$.

######  Corollary 6.7.

For every string $S$ over finite alphabet $\Sigma$, $k=|\Sigma|$, $PF(S)$
cannot have $PF(S_{k+1})$ as a subset with regard to any offset.

More specifically, we know that $S_{5}=512131214$ is only 9 characters long,
but its fingerprint cannot appear in any fingerprint describing a DNA
sequence, at any offset.

##  7 Conclusion and Future Work

We have defined a graph representation of palindromic fingerprints, the
restriction graph, where the chromatic number of the graph equals the alphabet
size of the preimage of a given palindromic fingerprint.

We have also defined the combinatorial structure of the shortest preimage for
a valid palindromic fingerprint over an alphabet of size $k$.

While this study has provided valuable insights into palindromic fingerprints,
several avenues remain unexplored. Future work on the topic includes:

  1. 1.

Finding an efficient algorithm to construct the restriction graph.

  2. 2.

Exploring the minimal presentation of a palindromic fingerprint as a method of
data compression.

## References

  * [1] A., E. Kondratovsky, and A. Levy.  On suffix tree detection.  In Proc. 30th Int. Symp. on String Processing and Information Retrieval (SPIRE), volume 14240 of Lecture Notes in Computer Science, pages 14–27. Springer, 2023.  doi:10.1007/978-3-031-43980-3\\_2.
  * [2] A. Amir, I. Boneh, M. Itzhaki, and E. Kondratovsky.  Analysis of the period recovery error bound.  In F. Grandoni, G. Herman, and P. Sanders, editors, Proc. 28th Annual European Symposium on Algorithms (ESA), volume 173 of LIPIcs, pages 5:1–5:21, 2020.
  * [3] A. Amir, E. Kondratovsky, G. M. Landau, S. Marcus, and D. Sokol.  Reconstructing parameterized strings from parameterized suffix and LCP arrays.  Theor. Comput. Sci., 981:114230, 2024.  URL: https://doi.org/10.1016/j.tcs.2023.114230, doi:10.1016/J.TCS.2023.114230.
  * [4] J. Clément, M. Crochemore, and G. Rindone.  Reverse engineering prefix tables.  In Proc. 26th Intl. Symp. on Theoretical Aspects of Computer Science STACS, volume 3 of LIPIcs, pages 289–300. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009.
  * [5] J.-P. Duval, T. Lecroq, and A. Lefebvre.  Border array on bounded alphabet.  J. Autom. Lang. Comb., 10(1):51–60, 2005.
  * [6] J.P. Duval, T. Lecroq, and A. Lefebvre.  Efficient validation and construction of border arrays and validation of string matching automata.  RAIRO Theor. Informatics Appl., 43(2):281–297, 2009.
  * [7] F. Franek, S. Gao, W. Lu, P. J. Ryan, W. F. Smyth, Y. Sun, and L. Yang.  Verifying a border array in linear time.  J. Comb. Math. Comb. Comput, 42:223–236, 2000.
  * [8] A. Fuglsang.  Distribution of potential type ii restriction sites (palindromes) in prokaryotes.  Biochemical and Biophysical Research Communications, 310(2):280–285, 2003.
  * [9] M. R. Garey and D. S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  New York: W. H. Freeman and Co., 1979.
  * [10] M. R. Garey, D. S. Johnson, and L. J. Stockmeyer.  Some simplified np-complete problems.  In R. L. Constable, R. W. Ritchie, J. W. Carlyle, and M. A. Harrison, editors, Proceedings of the 6th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1974, Seattle, Washington, USA, pages 47–63. ACM, 1974.
  * [11] P. Gawrychowski, T. Kociumaka, J. Radoszewski, W. Rytter, and T. Walen.  Universal reconstruction of a string.  Theor. Comput. Sci., 812:174–186, 2020.
  * [12] M.S. Gelfand and E.V. Koonin.  Avoidance of palindromic words in bacterial and archaeal genomes: a close connection with restriction enzymes.  Nucleic Acids Res, 25:2430–2439, 1997.
  * [13] K. Gelle and S. Iván.  Recognizing union-find trees is np-complete, even without rank info.  Int. J. Found. Comput. Sci., 30(6-7):1029–1045, 2019.
  * [14] Bannai H, S. Inenaga, A. Shinohara, and M. Takeda.  Inferring strings from graphs and arrays.  In Proc. 28th Intl. Symp. on Mathematical Foundations of Computer Science (MFCS), volume 2747 of LNCS, pages 208–217. Springer, 2003.
  * [15] T. I, S. Inenaga, H. Bannai, and M. Takeda.  Inferring strings from suffix trees and links on a binary alphabet.  Discret. Appl. Math., 163:316–325, 2014.
  * [16] Tomohiro I, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Counting and verifying maximal palindromes.  In Edgar Chavez and Stefano Lonardi, editors, String Processing and Information Retrieval, pages 135–146, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
  * [17] J. Kärkkäinen, M. Piatkowski, and S. J. Puglisi.  String inference from longest-common-prefix array.  In Proc. 44th Intl. Coll. on Automata, Languages, and Programming, ICALP, volume 80 of LIPIcs, pages 62:1–62:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [18] G. Kucherov, L. Tóthmérész, and S. Vialette.  On the combinatorics of suffix arrays.  Inf. Process. Lett., 113(22-24):915–920, 2013.
  * [19] B. Lisnic, I.K. Svetec, H. Saric, I. Nikolic, and Z. Zgaga.  Palindrome content of the yeast Saccharomyces cerevisiae genome.  Curr Genetics, 47:289–297, 2005.
  * [20] Michael G Main and Richard J Lorentz.  An o(n log n) algorithm for finding all repetitions in a string.  Journal of Algorithms, 5(3):422–432, 1984.  URL: https://www.sciencedirect.com/science/article/pii/019667748490021X, doi:10.1016/0196-6774(84)90021-X.
  * [21] G. Manacher.  A new linear-time “on-line” algorithm for finding the smallest initial palindrome of a string.  Journal of the ACM, 22(3):346–351, 1975.
  * [22] Y. Nakashima, T. Okabe, T. I, S. Inenaga, H. Bannai, and M. Takeda.  Inferring strings from lyndon factorization.  Theor. Comput. Sci., 689:147–156, 2017.
  * [23] S. K. Srivastava and H.S. Robins.  Palindromic nucleotide analysis in human t cell receptor rearrangements.  PLOS one, 7(12):e52250, 2012.

##  Appendix A Graphs and Reconstructions

######  Claim 1.

Reconstructing a general string with positive and negative constraints over a
minimal alphabet is NP-hard, even when negative constraints are limited to the
form $A[i]\neq A[j]$.

######  Proof A.1.

Let us show a reduction from graph coloring: Given a graph $G=(V,E)$, for
every $(v_{i},v_{j})\in E$, we add the restriction $T[i]\neq T[j]$. We add no
positive restrictions to the set of restrictions.

Any string $S$ satisfying our restrictions is a valid coloring, with $v_{i}$
being colored with $S[i]$, and we never have two neighboring vertices with the
same color, because we have the restriction $S[i]\neq S[j]$ for every edge
$(v_{i},v_{j})$. For similar reasons, every coloring of $G$ is a possible
reconstruction of the given restriction set. Hence, the alphabet size of the
reconstructed string is equal to the number of colors, and hence,
reconstructing using a minimal alphabet is equivalent to coloring with a
minimal number of colors and is NP-hard.

###  A.1 Palindromic Fingerprint Reconstruction and the Restriction Graph

The restriction graph $G$ of a palindromic fingerprint $(F,n)$, is a graph
whose coloring is bijective to a reconstruction of $(F,n)$.
The equivalence between restriction graph coloring and palindromic fingerprint
reconstruction gives us trivial bounds on the number of labels required to
reconstruct a given palindromic fingerprint - the lowest possible number is
the chromatic number of the graph $\chi(G)$, and the highest possible number
is the number of nodes in $G$, $|V|$.

Before starting, we remind the reader that Manacher’s algorithm [21] finds all
maximal palindromes in a string in linear time, hence converting a string $S$
to its corresponding palindromic fingerprint $PF(S)$ is done in linear time.

Let $(i,j)\in F$. The pair $(i,j)$ imposes a set of equality and inequality
constraints that a source text $S$ must satisfy. Namely, for $S[i\ldots j]$ to
be a palindrome, we must have $S[i+r]=S[j-r]$ for every
$r\in\\{0\ldots(j-i)\\}$. Furthermore, for $S[i\ldots j]$ to be a maximal
palindrome, we must have $S[i-1]\neq S[j+1]$ (if these indices are well
defined). We say that these constraints are derived from the pair $(i,j)$. We
say that a constraint is derived from $F$ if it is derived from one of the
pairs in $F$.

######  Definition A.2 (Equality Graph).

The equality graph of a fingerprint $(F,n)$ denoted as $G_{=}(F,n)=(V,E)$ is
an undirected graph defined as follows:
$V=\\{i\\}_{i=1}^{n}$, and $(i,j)\in E\iff S[i]=S[j]$ is a constraint derived
from $F$, where $1\leq i<j\leq n$.

The following directly follows from the definition of $G_{=}(F,n)$. Let
$A_{1},A_{2},\ldots,A_{\ell}$ to be the connected components of $G_{=}(F,n)$.
Every source text $S$ with $PF(S)=F$ must have $S[i]=S[j]$ if $i,j\in A_{k}$,
for any $1\leq k\leq\ell$.

We now define the restriction graph of $(F,n)$.

######  Definition A.3 (Restriction Graph).

Let $G^{\prime}$ be the restriction graph of a palindromic fingerprint $A$,
i.e., $G^{\prime}=G_{=}(F,n)=(V^{\prime},E^{\prime})$. The restriction graph
$G=(V,E)$ is defined as follows:

  * •

$V=\\{A_{k}\\}_{k=1}^{\ell}$, where $A_{k}$ is a connected component of
$G^{\prime}$.

  * •

$E=\\{(A_{k_{1}},A_{k_{2}})\leavevmode\nobreak\ |\leavevmode\nobreak\ \exists
i\in A_{k_{1}}\exists j\in A_{k_{2}}\leavevmode\nobreak\
s.t.\leavevmode\nobreak\ (i+1,j-1)\in F\\}$. In words, it means that index $i$
cannot have the same symbol as index $j$ because of a palindromic restriction.

Let $G=(V,E)$ be a restriction graph for a palindromic fingerprint $(F,n)$.
The vertices $V=(v_{1},v_{2},\ldots)$ form a partition of
$[n]=\\{1,2,\ldots,n\\}$, i.e., $\forall v_{i},v_{i}\subseteq[n]$, $\bigcup
V=[n],\forall v_{i}\neq v_{j},\text{ }v_{i}\cap v_{j}=\emptyset$.

If there is an edge $(A_{k_{1}},A_{k_{2}})$, then every string $S$
reconstructing $(F,n)$ satisfies $\forall i\in A_{k_{1}},\forall j\in
A_{k_{2}},S[i]\neq S[j]$.

From Definition A.3, there is an edge between each pair of connected
components which has an inequality constraint from $F$. The next step is to
color the restriction graph such that there are no connected vertices colored
in the same color.

######  Lemma A.4.

Let $\psi$ be a coloring of the restriction graph $G$ on input $(F,n)$, one
can reconstruct a string
$S=\psi^{\prime}(1)\psi^{\prime}(2)\ldots\psi^{\prime}(n)$, where
$\psi^{\prime}(i)=\psi(A_{k})\iff i\in A_{k}$, and $A_{k}$ is a vertex of $G$.
Then, the translation from $G$ to $S$ is a bijection.

######  Proof A.5.

Converting a coloring to a parameterized string is straightforward. Let $\psi$
be the coloring of $G$. Define $\psi^{\prime}:V\to\mathbb{N}$ as $\forall
v^{\prime}\in V^{\prime}\leavevmode\nobreak\ \forall v\in
v^{\prime},\psi^{\prime}(v)=\psi(v^{\prime})$. Now,
$S=\psi(1)\psi(2)\ldots\psi(n)$ is a string, satisfying all the restrictions
of $(F,n)$. $V^{\prime}$ is the vertex set of the equality graph, i.e., each
vertex represents an index.

Converting a parameterized string to a coloring can be done similarly. Let $S$
be a preimage of $(F,n)$. $\forall A\in V^{\prime},i\in A,\psi(i)=S[i]$. The
previous definition is well defined, since by the construction of the graph,
$\forall A\in V^{\prime},\forall i,j\in A,S[i]=S[j]$. $\psi$ is a valid
coloring, as shown by observation A.1.

######  Corollary A.6.

Lemma A.4 implies that there is at least one preimage for a given palindromic
fingerprint if and only if the restriction graph does not have self-loops.

A detailed example can be found at Example C.4.

##  Appendix B Proof Supplementary Components

###  B.1 Proof Overview

This section highlights the proof for Theorem 1.3.

The proof is divided into two parts. We first prove that a fingerprint that
allows no crossing palindromes satisfies our requirements. Based on that
lemma, we prove that the theorem is also true for a general string.

To prove the lemma on restricted fingerprints that do not allow crossing
palindromes, we use an inductive approach where we establish that an optimal
string is formed by combining two smaller optimal strings. The form we assume
for strings of length $\geq 3$ is $xLtLy$, where $L$ is a palindrome, all
$x,t,y$ are unique characters, i.e., characters that do not occur in $L$, and
both $xLt$ and $tLy$ are of the same recursive form.

In the first part of the proof, we introduce palindromic islands. A
palindromic island is a palindrome not contained in a longer palindrome. Using
the new definition, we prove a key lemma - that every two islands can be
reconstructed almost independently, that is to say, the number of characters
required to reconstruct a string is the number of characters required to
reconstruct its heaviest island plus up to two additional characters, where
heaviest refers to the island that requires more characters to reconstruct.
Using the previous key observation, we analyze these two additional characters
and prove that they must be introduced on the indices adjacent to the
previously mentioned island.

After proving that the overall number of characters in the reconstructed
string is the same as the number of characters in its heaviest island and the
two surrounding indices, we conclude that an optimal fingerprint (as defined
at Definition 3.4) must contain at most one island of length $>1$.
Knowing that there can only be one island of length $>1$, we show that there
must be two other islands of length one and that both of these new islands
present a new character to the reconstructed string. The overall structure of
an optimal fingerprint at this point is $xPy$, where $x\neq y,x,y\notin P$,
and $P$ is a palindrome.
Lastly, we show that $P$ can be rewritten as $P^{\prime}tP^{\prime}$, where
$P^{\prime}$ is a palindrome and $t\notin P^{\prime}$, supporting the
induction hypothesis.

We conclude the first part of the proof by showing that the reconstructed
string has a unique fingerprint and that its restriction graph is a clique
and, hence, has a unique parameterized reconstruction.

The second part of the proof generalizes the theorem to a general string.
Similar to the first proof, we will subdivide the string into islands and the
islands into locally maximal palindromes. Almost identical to the first part,
we will show that different islands can be reconstructed almost independently.
Later, We will discuss the prerequisites of a palindrome to introduce a new
character to the reconstruction and will show that some crossing palindromes
don’t change the overall reconstruction degree. The last part shows that
reconstructing two adjacent crossing palindromes does not introduce many more
characters than reconstructing the heavier of the two and will generalize it
to any sequence of crossing palindromes.

In conclusion, we will show that the number of characters required to
reconstruct a general string is very close to the number of characters
necessary to reconstruct the heaviest palindrome within, eventually reducing
the problem to that of a string with no crossing palindromes and concluding
the proof.

Some of the lemmas are rather technical and are left in the appendix.

Before starting the proof, we will introduce some definitions that will be
used throughout the proof.

###  B.2 Technical Proofs

  * Proof for Lemma 4.10.

Assume that $|P|$ is even. Denote the even-sized palindromic descriptor $P$ as
$LttR$, where $L,R,t$ are symbols representing indices of $P$.

Let $P^{\prime}$ be the longest maximal sub-palindrome of $P$ that contains
the middle symbol $t$. $P^{\prime}$ might be of length one (i.e., containing
only $t$). Let us rewrite $P=L^{\prime}P^{\prime}P^{\prime}R^{\prime}$. We can
reduce $P$ to $P^{\prime\prime}=L^{\prime}P^{\prime}R^{\prime}$, and
$P^{\prime\prime}$ has an isomorphic restriction graph - all inequalities are
kept, as $L$ can only share palindromic restrictions with the first instance
of $P^{\prime}$, and $R$ with the second instance. As a result, squashing them
into one instance can not lift any labeling restriction on either
$L,P^{\prime}$ or $R$.

Also, there cannot be a palindrome $L^{\prime}pref(P^{\prime})$ where
$|pref(P^{\prime})|>|P^{\prime}|/2$, as it would imply that $P^{\prime}$ has
an internal crossing palindrome. Because the longest possible palindrome
prefix is at most $|P^{\prime\prime}|/2$, it is kept as a non-crossing
palindrome after the reduction.

Thus, we found $P^{\prime\prime}$ with the same restriction graph; therefore,
$PF(P)$ is not optimal. ∎

  * Proof for Lemma 4.13.

Because of the maximality of $P$, $x\neq y$.

If $x\in P$, then the form $xP$ is not optimal, as it could be reduced by one
character to the string $P$ without losing any restrictions. The same can be
claimed for $xPy$, where $x,y\in P$.
We now look at the case where $x\in P$ but $y\notin P$.

We observe that $x$ is the only possible character in $P$ that could have been
chosen because if there were two options, we could use the second for $y$.

By Lemma 4.11, we claim that $L=R$ must be palindromes. The number of distinct
characters labeled for $xLt$ cannot go below $k-1$, but we assumed that
$F_{k-1}$ is both optimal and unique, hence $xLt$ is either longer than
$S_{k-1}$ or equal to it, which implies $x,t\notin L$, and that is a
contradiction. ∎

  * Proof for Lemma 4.14.

As we have seen at Lemma 4.7, when $|\Sigma|\geq 5$, the optimal string can be
represented with one island and at most one adjacent character on each side,
leaving us with the following three possible structures to examine:
$xPy,xP$ and $P$. In all cases, $x,y\notin P$, due to Lemma 4.13.

Let us assume $xP$ is possibly the optimal form. Since $x\notin P$ and because
the reconstruction is optimal, we learn that we could not have chosen $x$ to
be equal to any character $c\in P$. Rewrite $P=LtR$, we know that all
palindromic inequality restrictions on $x$ can be derived from $Lt$ as well,
which disqualifies $xP$ from being optimal.
Similarly, let us assume $P$ is the optimal form. Let us split $P=LtR$, due to
the palindromic fingerprint not having crossing palindromes, rewriting
$P^{\prime}=Lt$ will not change the restrictions for any character in $Lt$,
hence, $P$ is not optimal. ∎

  * Proof for Lemma 5.5.

We already proved at Lemma 4.7 that the statement holds if $I_{i}$ is a
palindrome. So, we only consider the case where $I_{i}$ is not a palindrome.
In this case, $I_{i}$ is of length at least four and contains at least two
different characters, as if it only had one character, it was a palindrome,
and if it was of length three or less, then the two crossing palindromes are
of length 2, which can only occur if the string is $aaa$.

After showing that $I_{i}$ is of length four or more and contains at least two
different characters, let us assume to the contrary that $\sigma(I_{i})+2$
characters are required to reconstruct $PF$. As we showed at Lemma 4.7, only
four characters have inequality relations with $I_{i}$ \- the two adjacent
characters on each side of the island. The characters in positions
$end(I_{i})+2,start(I_{i})-2$ (if exist) only have an inequality relation with
the last and first characters of $I_{i}$ accordingly, hence can be chosen for
the other character in $I_{i}$. However, the characters next to $I_{i}$ can
have an unbounded number of inequality restrictions. Let us assume a new
character $\$$ is added to the left of $I_{i}$. Since $I_{i}$ is not a
palindrome, the character on the right can also be $\$$, as $\$$ is a new
character that cannot violate any palindromic restriction within $I_{i}$.
Since $I_{i}$ is not a palindrome, it neither violates a restriction with the
previously assigned new character $\$$. Neither equals any further characters,
as they were chosen as characters inside $I_{i}$. ∎

  * Proof for Lemma 5.6.

By definition of crossing palindromes, $start(P_{1})<start(P_{2})$ and
$end(P_{1})<end(P_{2})$. Therefore, the inequalities defined by the
palindromes $P_{1},P_{2}$ do not interfere with the reconstruction of $P_{1}$
or $P_{2}$. Also, by definition of contained palindromes, after reconstructing
$P_{1}$, we already reconstructed all characters in $P_{2}$, but no new
character inequality restriction was introduced. ∎

  * Proof for Lemma 5.9.

To the contrary - we should reconstruct $P_{1}$ first, by Lemma 5.7, $P_{2}$
can only introduce one new character to the reconstruction. At Lemma 5.7, we
showed that $P_{2}$ has at most one new character and at most $\sigma(P_{1})$
distinct characters overall. We now need to show that $P_{3}$ does not
introduce another character. Because $P_{2}$ is ordered before $P_{3}$, we
know that $start(P_{2})<start(P_{3})$ and $end(P_{2})<end(P_{3})$. Therefore,
all characters common to $P_{1}$ and $P_{3}$ are also common to $P_{1}$ and
$P_{2}$. We showed that either $P_{2}$ introduced no new characters, or a
character exists in $P_{1}$ but not in $P_{2}$. If $P_{2}$ introduced no new
characters, then the previous lemma applies directly to $P_{3}$. Otherwise,
there exist two characters $\$_{1},\$_{2}$ in $P_{1}$ and $P_{2}$ (resp.) that
are unique. The character $\$_{1}$ does not have any palindromic inequality
with characters in $P_{3}$ that are not reconstructed, therefore whenever a
new character needs to be introduced, $\$_{1}$ can be chosen. We previously
showed that no more than one character will be needed, keeping an overall of a
single added character. ∎

  * Proof for Lemma 6.1.

The proof is simple and inductive. The induction claim is that the restriction
graph of $F_{k}$ is a clique. Note that the restriction graph of a string and
the graph of its fingerprint produce the same graph.

We know that $S_{3}=123$, and by Definition 3.8, the restriction graph of
$S_{3}$ is a clique.

We now prove for $k+1$: By the recursive structure of $F_{k+1}$, we know that
if $S_{k}=xP_{k}t$, then $S_{k+1}=xP_{k}tP_{k}y$. By the induction claim,
$S_{k}=xP_{k}t$ has a clique restriction graph. Moreover, because of the
recursive structure, we know that $y$ must be connected to all nodes in the
restriction graph representing $P_{k}$ and $t$. What is left is to show that
$x$ and $y$ are connected, which is trivial, as $P_{k}tP_{k}$ is a palindrome.
∎

##  Appendix C Supplementary Examples

######  Example C.1 (Crossing Palindromes - Definition 3.10).

Let $S=1213431211$ be a string. The non-trivial palindromes in the string are
$(1,3),(1,9),(7,9),(9,10)$. By the definition of crossing palindromes, $(1,3)$
and $(1,9)$ do not cross because the palindromes share the same starting
point. For similar reasons, $(1,9)$ and $(7,9)$ are not crossing. However, the
palindromes $(i_{1}=1,i_{2}=9),(i_{1}=9,i_{2}=10)$ are crossing, because
$i_{1}<i_{2}\land i_{2}\leq j_{1}<j_{2}$.

######  Example C.2 (Main problem - Problem 1.2).

Let $F=(\\{\\},10)$ be a palindromic fingerprint. A possible reconstruction of
$F$ is the string $S_{1}=0123456789$. Another possible reconstruction is
$S_{2}=0120120120$.

Let $F=(\\{(2,4)\\},5)$ be a palindromic fingerprint. A possible
reconstruction for this fingerprint is $S=01213$. Later in the paper, we prove
that all possible reconstructions for $F$ parameterize match to $S$.

Let $F=(\\{(1,4),(2,4),(2,5)\\},5)$ be a palindromic fingerprint. No string
$S$ exists such that $PF(S)=F$. Proof:

$\begin{split}(1,4)=>S[1]=S[4],S[2]=S[3]\\\ (2,4)=>S[2]=S[4]\\\
(2,5)=>S[2]=S[5],S[3]=S[4]\end{split}$

hence, $S[1]=S[5]$, but by maximality of $(2,4)$, $S[1]\neq S[5]$.

######  Example C.3 (Palindromic fingerprint - Definition 1.1).

Let $S=abacabada$. The maximal palindromes of $S$ are

$\\{(1,7),(1,3),(5,7),(7,9)\\}\cup$ $\\{(1,1),(3,3),(5,5),(7,7),(9,9)\\}$

and thus the palindromic fingerprint is $PF(S)=\\{(1,7),(1,3),(5,7),(7,9)\\}$.
Palindromes are visualized at Figure 1

Figure 1: The palindromes in $S$

The example above presents the fingerprint as a union of two sets. The set on
the bottom of the equation consists of trivial maximal palindromes -
palindromes of length one 444Some authors refer to empty palindromes as well,
in this paper we do not regard them at all., hence we ignore them in the
fingerprint. The set on top consists of the rest of the maximal palindromes.
Non-maximal palindromes, like $(2,2)$, were omitted.

It is worthwhile to mention that either $(1,3)$ or $(5,7)$ could have been
omitted because each, in addition to the $(1,7)$ palindrome, implies the
other. However, we do not omit such palindromes from the fingerprint. Such
palindromes are called implied maximal palindromes.

An example of a valid palindrome that must not participate in the fingerprint
is $(2,6)$, because it is not maximal.

######  Example C.4 (Restriction graph - Definition A.3).

Consider the string $S=41213121566757$.

The fingerprint of the string is
$PF(S)=\\{(2,4),(2,8),(6,8),(10,11),(12,14)\\}$, which is all the maximal
palindromes.

The equality graph, $G_{=}$, is a graph where each index in the original
string is assigned to a node. In the graph, we only connect nodes that ought
to be connected by a palindromic restriction. The equality graph is
illustrated at Figure 2.

1589101112131423467 Figure 2: The equality graph of $S$.

The restriction graph $G$ shrinks every connected component to only one node.
We labeled the nodes with their original indices, comma separated. In the
restriction graph, we draw an edge between two nodes that should be
reconstructed using another label. Note that although we omitted trivial
palindromes in the fingerprint, we still know they are there, and when
considering the restriction graph we also consider the restrictions of trivial
palindromes. For example, we can see that there is no palindrome centered at
10, which means that the palindrome centered at ten is trivial, hence
$S[9]\neq S[11]$. The restriction graph is at Figure 3(a).

Our last step towards reconstruction is coloring the graph. We can see that
the subgraph with nodes $\\{(1),(2,4,6,8),(3,7),(5),(9)\\}$ is the complete
graph $K_{5}$, hence there is no coloring with less than five colors. Also,
there are only eight nodes, implying no coloring with more than eight colors
exists.

Our original string $S$, is a valid coloring using 7 colors. The string
$S=41213121566787$ is the naïve coloring that assigns each node with another
color. The string $S=45253525133212$ represents an optimal coloring of the
graph, i.e., coloring with the fewest possible colors. The coloring is
presented at Figure 3(b).

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$ (a) The restriction
graph of $S$, biggest clique is highlighted

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$v_{8}$ (b) Optimal coloring
of $G$

Figure 3:
$v_{1}=\\{9\\},v_{2}=\\{12,14\\},v_{3}=\\{13\\},v_{4}=\\{5\\},v_{5}=\\{1\\},v_{6}=\\{10,11\\},v_{7}=\\{2,4,6,8\\},v_{8}=\\{3,7\\}$

######  Example C.5 (Palindromic islands - Definition 4.2).

Let $S$ be a string, $S=eaabbaadeed$, with its palindromes highlighted. The
islands are maximal palindromes not contained in any other palindromes, and
they are highlighted in blue at Figure 4.

Figure 4: The palindromes and islands of $S$

######  Example C.6 (Standalone reconstruction - Definition 3.14).

Let $S$ be a string, $S=eaabbaadeed$. The palindromic islands of $S$ in start-
length notations are $\\{(1,1),(2,6),(8,4)\\}$, or
$I_{1}=(1,1),I_{2}=(2,6),I_{3}=(8,4)$. A standalone reconstruction of $I_{1}$
can be $aaaaaaaaaaa$, and can also be $a**********$. A standalone
reconstruction of $I_{2}$ can be $aaabbaaaaaa$, and can also be $*ccaacc****$,
but cannot be $eacbbcadeed$, because the violated palindromic restriction
$(2,2)$ is within $I_{2}$.

Using a general reconstruction algorithm $A$, it is straightforward to
independently reconstruct an island $I=(j,\ell)$. All that needs to be done is
to reconstruct the fingerprint of $T[j..j+\ell-1]$, where $T$ represents the
reconstructed original fingerprint. It is important to note that this
explanation is informal and provided solely to give an intuitive
understanding.