Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs

2024/06/06 by Amihood Amir, Amir, Amihood, Michael Itzhaki +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2406.04507

openalex publication_date 2024/06/06 · openalex created_date 2024/06/11 · openalex updated_date 2026/07/28

Abstract

The palindromic fingerprint of a string S[1… n] is the set PF(S) = \(i,j)~|~ S[i… j] is a maximal 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 ⊆ [1… n] × [1… 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 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.

Related

• Tight Bound for the Number of Distinct Palindromes in a Tree
• Combinatorics of Palindromes
• Compact representation of maximal palindromes
• Small Space Encoding and Recognition of k-Palindromic Prefixes
• Palindromic Trees for a Sliding Window and Its Applications