PaperlayerView exact revision on arXiv

Source-linked AI summary

Lettericity Is NP-Complete

Henning Fernau, Samuel German, Kevin Mann, Nils Morawietz

arXiv:2609.28023v3cs.CCcs.DM

TL;DR

Whether lettericity can be computed in polynomial time remained an open question despite sustained study of the parameter. This paper proves NP-completeness for lettericity and its three extension variants, and establishes conditional ETH lower bounds alongside an FPT algorithm for the dual parameter.

  • Problem

    Whether lettericity can be computed in polynomial time remained an open question in recent literature.

    Source: §1 · p. 2

  • Method

    The paper proves hardness for lettericity and its constrained extension variants, reuses its hardness reduction for an ETH lower bound, and gives an algorithm parameterized by n−k.

    Source: §1 · pp. 2–3

  • Results

    Lettericity and the coloring, word, and decoder extension problems are NP-complete; unless ETH is false, no deterministic 2^o(n)-time decision algorithm exists even when n = 6k.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The results clarify the hardness of fixing individual parts of a letter representation, while Lettericity is also fixed-parameter tractable for the dual parameter n−k.

    Source: §1 · pp. 2–3

    The subexponential-time lower bound is conditional on ETH, using the assumed 2^o(m) lower bound for Monotone-NAE3-SAT.

    Source: §5.1 · p. 15

Abstract

from arXiv · show

The lettericity of a graph $G$ is the smallest size of a set $\Sigma$ such that there exist $w_1, \ldots, w_{|V(G)|} \in \Sigma$ and a so-called decoder $D \subseteq \Sigma^2$ for which $G$ is isomorphic to the letter graph $(\{1, \ldots, |V(G)|\}, \{ij : 1 \le i < j \le |V(G)|, w_iw_j \in D\})$. It took around two decades of the study of lettericity for, in the simpler case of paths, a closed-form expression for its lettericity to be derived; this suggests that the question of whether the lettericity of an arbitrary graph can be computed in polynomial time is nontrivial. Indeed, this question has been raised repeatedly as an open problem in recent literature. We solve this problem by showing that the lettericity problem on arbitrary graphs is NP-complete. We also show that each of the natural ways in which a single part of a structure $(\Sigma, w_1, \ldots, w_{|V(G)|}, D)$ witnessing the lettericity could be constrained corresponds to an NP-complete problem, which resolves an additional three open problems from the literature; in particular, we show that the coloring extension, word extension, and decoder extension problems are NP-complete. Additionally, we use the reduction in the NP-completeness proof to give a lower bound on algorithms for lettericity under the Exponential Time Hypothesis (ETH): unless the ETH is false, there cannot exist a deterministic algorithm to decide whether the lettericity of an $n$-vertex graph is at most $k$ in time $2^{o(n)}$, even when $n = 6k$. Finally, we complement the known result that Lettericity is fixed-parameter tractable when parameterized by the standard parameter $k$ by providing a fixed-parameter algorithm with respect to the dual parameterization by $n-k$ running in $2^{\mathcal{O}((n-k)^2)} + \mathcal{O}(n)$ time.

1 Introduction

Lettericity has meaningful algorithmic applications, but whether it can be computed in polynomial time remained an open question. This paper proves NP-completeness for lettericity and three extension problems, gives an ETH lower bound, and establishes fixed-parameter tractability for the dual parameter.

1 Introduction

  • Lettericity also provides compact graph descriptions with algorithmic applications, including tests for fixed MSO-definable hereditary properties in f(k)n^3 time when lettericity is at most k.Source: §1 · p. 2
  • Lettericity is NP-complete on general graphs, resolving a repeatedly raised open problem.Source: §1 · p. 2
  • Coloring extension, word extension, and decoder extension are also NP-complete, resolving three additional open problems.Coloring extension remains NP-complete when each color is assigned to exactly two vertices.Source: §1 · pp. 2–3
  • Unless ETH is false, no deterministic 2^o(n)-time algorithm decides whether lettericity is at most k, even when n = 6k.Source: §1 · p. 3
  • Parameterized by n−k, Lettericity has an FPT algorithm running in 2^O((n−k)^2) + O(n) time.This complements the known FPT result for parameter k.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the graph and satisfiability terminology used in the paper, formalize letter representations and coloring extension, and give a criterion for when an order and coloring admit a decoder.

2.1 General Notions

  • For disjoint vertex sets, graph union combines vertices and edges; induced subgraphs retain edges within a set, and Monotone-NAE3-SAT asks for each 3-variable clause to contain both truth values.Source: §2.1 · p. 3

2.2 Notation for the Lettericity Problem

  • A letter representation orders the vertices, assigns each a letter, and uses a decoder to determine adjacency; lettericity is the minimum alphabet size.The decision problem asks whether ℓ(G) ≤ k.Source: §2.2 · p. 4

2.3 Coloring Extension

  • Coloring extension asks whether a graph has a letter representation whose letters respect a given vertex-to-letter map.A coloring here need not be proper; unused colors or letters can be discarded.Source: §2.3 · p. 4

2.4 Distinguishers and Intervals

  • For vertices of the same color, all distinguishers must lie between them in the order; this condition is equivalent to existence of a decoder for that order and coloring.A distinguisher is a vertex adjacent to exactly one of the pair.Source: §2.4 · pp. 4–5

3 Reduction from Monotone-NAE3-SAT to a Specialized Coloring Extension Problem

The section reduces Monotone-NAE3-SAT to Coloring Extension and proves NP-hardness even when the coloring is proper and every color class has two vertices. Pair-class orientations and gadget-induced digraphs encode assignments, with satisfiability equivalent to the constructed instance being a yes-instance.

3 Reduction from Monotone-NAE3-SAT to a Specialized Coloring Extension Problem

  • Coloring Extension is NP-hard even when the given coloring is proper and every color class contains exactly two vertices.The reduction starts from Monotone-NAE3-SAT.Source: §3 · p. 5

3.1 Pair Classes

  • Pair classes encode truth values through the relative order of their 0- and 1-labeled vertices.τ(P) = 1 prescribes that p0 precedes p1 in the letter representation's linear order.Source: §3.1 · p. 5

3.2 Digraphs Lτ(G) and Rτ(G)

  • A letter representation respecting χ and consistent with pair-class orientations τ exists exactly when both Lτ(G) and Rτ(G) are acyclic.The two digraphs encode order constraints on the left and right endpoints of pair classes.Source: §3.2 · p. 6

3.3 Constructed Gadgets

  • For each NAE clause gadget, both orientation digraphs are acyclic exactly when each X_i and Y_i orientation matches and the three X_i orientations are not all equal.The pair classes encode the clause's not-all-equal condition.Source: §3.3 · p. 7

3.4 The Reduction Itself

  • The reduction builds a polynomial-size graph with a proper coloring whose pair classes each contain exactly two vertices.It combines one NAE clause gadget per clause with equality gadgets linking variable-occurrence classes to variable classes.Source: §3.4 · p. 9

Example Monotone NAE-3-SAT instance

  • In the illustrated formula, each clause has its own NAE gadget, while occurrences of a shared variable connect to the same variable pair class through equality-gadget edges.Figure 2 depicts C1 = (a, b, c) and C2 = (c, d, e), sharing c.Source: Figure 2 · p. 10, Example Monotone NAE-3-SAT instance · p. 10

3.5 Correctness

  • The constructed instance is a yes-instance of Coloring Extension if and only if the source formula is satisfiable.A satisfying assignment makes variable pair classes sources or sinks, while clause-gadget acyclicity follows from the NAE condition; conversely, a valid representation yields a satisfying assignment.Source: §3.5 · pp. 10–11

4 Reduction from Specialized Coloring Extension to Lettericity

The reduction converts a properly colored graph into a graph H whose lettericity is at most 2k exactly when the source has a letter representation respecting its coloring. Independent vertex sets encode the source graph, while paired clique halves enforce color identities; the correctness proof recovers a coloring-respecting representation from any small representation of H.

4 Reduction from Specialized Coloring Extension to Lettericity

  • A polynomial-time construction maps (G, χ) to H with K = 2k and preserves whether G has a letter representation respecting χ.The theorem states that this holds exactly when ℓ(H) ≤ K.Source: §4 · p. 11

4.1 Construction of the Graph H

  • For each source vertex v, H contains an independent set Xv of size N = 2k+1, with edges between X-sets matching adjacency in G.Each color class Ci is nonempty and independent; its clique Mi has two halves, with Xv adjacent to the half selected by whether v's color is i.Source: §4.1 · p. 11

4.2 Correctness Proof

  • In any representation of H using at most K letters, pigeonhole arguments and the gadget structure yield a χ-respecting representation of G.The proof extracts one representative xv from each Xv and uses the paired clique sets to establish distinct letters for the color classes.Source: §4.2 · pp. 13–14

5 Complexity Results for Lettericity and Other Problems

The paper establishes NP-completeness for Lettericity and three extension problems, and proves an ETH-based subexponential-time lower bound. It also gives a fixed-parameter algorithm for the dual parameter n−k.

5.1 Lettericity Complexity Results

  • Lettericity is NP-complete, with a letter representation serving as a polynomially checkable certificate.The certificate check verifies the edge condition for each ordered vertex pair.Source: §5.1 · p. 14
  • Unless ETH is false, no deterministic 2^o(n)-time algorithm decides whether ℓ(G) ≤ k, even when n = 6k.The reduction can produce instances with |V(H)| = 6K while preserving a parameter K proportional to the source formula size.Source: §5.1 · pp. 14–15
  • For the dual parameter k = n−k, Lettericity can be solved in 2^O(k^2) + O(n) time.The algorithm enumerates colorings and orders of vertices in nonsingleton color classes, then checks extensions in polynomial time.Source: §5.1 · p. 15

5.2 Complexity Results for Other Problems

  • Coloring Extension is NP-complete even for proper colorings whose color classes all have size exactly two.The proof uses the reduction from Section 3 and verifies certificates using the Lettericity verifier.Source: §5.2 · p. 15
  • Word Extension is NP-complete even when the input graph is a disjoint union of equally sized cliques.Source: §5.2 · p. 16
  • Decoder Extension is NP-complete, strengthening the previously established GI-hardness result.The reduction from Coloring Extension uses the decoder to enforce the prescribed color classes.Source: §5.2 · p. 16

6 Conclusions

The paper concludes that Lettericity is NP-complete, while remaining fixed-parameter tractable in the solution-size parameter. It identifies open questions about graph classes, algorithms, and related parameters.

6 Conclusions

  • Lettericity is NP-complete, but its decision problem is fixed-parameter tractable in k, so fixed-k NP-hardness would imply P = NP.The conclusion also points to understanding the structure of graphs with lettericity at most k.Source: §6 · p. 16
  • Cographs and other special graph classes remain candidates for complexity study, and any potentially NP-hard class must contain graphs of arbitrarily large lettericity.The conclusion also notes connections to permutation classes and to complexity studies of thinness.Source: §6 · p. 16
  • An open algorithmic question is whether the 2^O(k^2 2^k)n^3 algorithm can be improved to 2^O(k)n^O(1), which would yield a 2^O(n)-time algorithm.Such a bound would match the ETH lower bound up to constant factors in the exponent.Source: §6 · p. 16
  • The complexity of decision problems for generalized lettericity, uniformicity, and distinguishing number remains open.Source: §6 · p. 16

A.1 Proof of Lemma 5

The lemma specifies the arc sets associated with equality and containment gadgets under an orientation assignment. Its equality-gadget cases are tabulated by the two assigned orientations.

A.1 Proof of Lemma 5

  • The orientation assignment τ maps the pair classes A and B to 0 or 1, and the lemma describes the resulting arc sets for Lτ and Rτ.Source: §A.1 · p. 19
  • For the equality gadget, the four possible (τ(A), τ(B)) pairs determine the arc sets of Lτ and Rτ.The listed cases are (1,1), (0,0), (0,1), and (1,0).Source: §A.1 · p. 19
  • For the containment gadget, Lτ contains only A → B, while Rτ contains only B → A.Source: §A.1 · p. 19

A.2 Full Proof of Lemma 7

Lemma 7 establishes how the constructed graph separates clause gadgets and how its orientation digraphs decompose after designated vertices are removed.

A.2 Full Proof of Lemma 7

  • After removing VM, GI is the disjoint union of the clause graphs N(PC), and each clause's vertices have the prescribed color classes.The NAE gadgets do not add edges within or between clause vertex sets.Source: §A.2 · pp. 19–20
  • For each gadget vertex set MzC,i, its induced graph together with XC,i is exactly the single-edge gadget E(MzC,i, XC,i).Every edge incident to a vertex in Mz comes from one of these gadgets.Source: §A.2 · pp. 19–20
  • After deleting the Mz vertices, the left and right digraphs have no arcs between distinct clause families PC.Within a clause, the digraphs agree with the corresponding constructions on N(PC).Source: §A.2 · pp. 19–20

A.3 Full Proof of Theorem 10

Theorem 10 is proved by showing that Lettericity belongs to NP and combining that membership with NP-hardness. The proof encodes a proposed letter representation as a polynomial-size certificate and verifies it in polynomial time.

A.3 Full Proof of Theorem 10

  • Theorem 10 states that Lettericity is NP-complete.The proof obtains the result by combining membership in NP with NP-hardness.Source: §A.3 · pp. 20–21
  • A certificate records a vertex order, each vertex's letter, and a Boolean matrix specifying the decoder.These lists and the n × n matrix have size polynomial in the instance encoding.Source: §A.3 · p. 20
  • The verifier checks that the certificate uses at most k letters and that every ordered vertex pair is an edge exactly when its letters belong to the decoder.The checks run in polynomial time, and a valid certificate exists exactly for yes-instances.Source: §A.3 · pp. 20–21

A.4 Full Proof of Theorem 11

Theorem 11 derives an ETH-based prohibition on deterministic subexponential-time algorithms for Lettericity, including when the graph size is six times the target bound. The proof preserves the reduction's correctness while controlling its output size.

A.4 Full Proof of Theorem 11

  • Unless ETH is false, no deterministic 2^o(h)-time algorithm decides whether ℓ(H) ≤ K, even when h = 6K.The reduction would otherwise give a 2^o(m)-time algorithm for Monotone-NAE3-SAT, contradicting its ETH lower bound.Source: §A.4 · pp. 21–22
  • The reduction is postprocessed by trimming each Xv and Mᵢᵇ set to exactly three vertices, without changing K.The construction ensures these sets have at least three vertices, and the graph has 6K vertices.Source: §A.4 · p. 21
  • Trimming preserves lettericity because vertices within each Xv or Mᵢᵇ set are twins, and repeated twin-class reductions leave ℓ(H′) = ℓ(H).This preserves a valid Karp reduction from Monotone-NAE3-SAT to Lettericity.Source: §A.4 · p. 21
  • The output parameter satisfies K = 2(n′ + 6m) = Θ(m), using the assumption that unused variables can be deleted so n′ ≤ 3m.The postprocessing step does not modify K.Source: §A.4 · p. 21

A.5 Proof of Theorem 12

Theorem 12's algorithm enumerates colorings and partial orders on vertices in nonsingleton color classes, then checks whether they extend to a letter representation. A lemma reduces the extension check to separate tests for singleton-class vertices.

A.5 Proof of Theorem 12

  • Lemma 16 says a coloring and order of nonsingleton-class vertices extend to a representation exactly when each remaining vertex can be added individually.Each individual order must extend the fixed partial order, and each induced graph must have a compatible decoder.Source: §A.5 · p. 22
  • For each coloring and partial order, the extension test is polynomial, using Lemma 16 when there is a singleton color class.If all vertices lie in nonsingleton classes, the test instead checks condition (1).Source: §A.5 · pp. 22–23
  • The algorithm enumerates at most n^{2k} colorings and (2k)! partial orders on vertices in nonsingleton color classes.These choices yield (2k)! · n^{2k} = n^{O(k)} cases.Source: §A.5 · p. 23
  • When the target is high enough, the algorithm answers yes in O(n) time; otherwise the enumeration yields a 2^{O(k^2)} + O(n) bound.The stated high-target condition is k ≥ n − ⌊1/2 log2(n)⌋.Source: §A.5 · p. 23

A.6 Proof of Theorem 14

The proof establishes Word Extension’s NP-completeness by reducing unary 3-Partition to it and showing the constructed instance is solvable exactly when the original partition exists.

A.6 Proof of Theorem 14

  • A certificate for Word Extension is an enumeration of the graph’s vertices and a decoder, verifiable in polynomial time using a Lettericity verifier.The alphabet can be taken to be the letters appearing in the fixed word, so its size is at most the number of vertices.Source: §A.6 · p. 23
  • The reduction maps unary 3-Partition integers to a disjoint union of m cliques of size B and a word consisting of consecutive blocks σ_i repeated a_i times.The construction has mB vertices and mB edges, and is polynomial-time for unary-encoded input.Source: §A.6 · pp. 23–24
  • A valid 3-partition yields a Word Extension representation by assigning each block’s letter to a subset of a clique, ordering subsets by their word blocks, and decoding pairs of letters assigned within the same clique as edges.The chosen subsets partition each clique and have sizes matching their corresponding integer values.Source: §A.6 · p. 24
  • Conversely, each letter’s contiguous block in the fixed word forces its vertices into one connected component, and the component sizes then give a partition of the integers summing to B.Consecutive vertices assigned the same letter are twins; since components are cliques of size B>1, each letter class lies in one component.Source: §A.6 · p. 24

A.7 Proof of Theorem 15

The proof converts Coloring Extension instances into Decoder Extension instances and argues that the constructed decoder forces the original color classes. It also establishes ETH bounds for Decoder Extension, describes supplementary figures, and notes limits and open directions.

A.7 Proof of Theorem 15

  • The reduction from Coloring Extension builds a fixed alphabet and decoder with auxiliary cliques so that any representation preserves the original pair classes’ color choices.Each pair class’s vertices must receive the same letter, while the equality and containment gadgets constrain their relative order.Source: §A.7 · pp. 24–25
  • The constructed instance is equivalent: a Coloring Extension solution extends to a Decoder Extension representation, and any such representation recovers a solution to the original instance.The proof verifies the required edge relation for pairs within classes, between auxiliary cliques and classes, and between gadget-linked classes.Source: §A.7 · pp. 26–27
  • Under ETH, Decoder Extension has no 2^o(√n) or 2^o(|Σ′|) algorithm, via a reduction whose graph has Θ(n′²) vertices and whose alphabet has Θ(n′) letters.Here n′ is the number of vertices in the Coloring Extension instance.Source: §A.7 · p. 27
  • The authors cannot derive a comparable ETH lower bound for Word Extension from their 3-Partition reduction because the constructed instance’s size multiplies the source measures m and B.They note that 3-Partition itself admits a subexponential algorithm in the sum of its input integers.Source: §A.7 · p. 28

B Supplementary Figures

C Additions to the Conclusions

  • The additions to the conclusions identify generalized lettericity’s complexity as an open question requiring new gadgets, and note uniformicity and distinguishing number as related parameters whose complexity was not discussed.Lettericity and thinness are stated to generalize neighborhood diversity.Source: C Additions to the Conclusions · p. 29
Loading 2609.28023v3…