Computing Heegaard Genus is NP-Hard

Abstract

We show that Heegaard Genus ≤ g, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to g, is NP-hard. The result follows from a quadratic time reduction of the NP-complete problem CNF-SAT to Heegaard Genus ≤ g.

Dedicated to the memory of Jiří Matoušek

The authors would like to thank Martin Tancer, whose guidance was instrumental at the genesis of this project, and Iyad Kanj and Marcus Schaefer for helpful conversations along the way.

1 Introduction

While there is a tradition of studying decision problems in 3-manifold topology, the historical focus has been showing that problems are decidable [9, 13–15, 20, 21, 31, 37]. More recently, the computational complexity of these and related problems has gained attention [1, 5–7, 10, 18, 34]. Here we show that one of the most basic decision problems for 3-manifolds, the problem of determining Heegaard genus, is NP-hard.

Every closed, orientable 3-manifold M has a Heegaard surface: a closed surface that splits the manifold into a pair of handlebodies (i.e., thickened graphs). The Heegaard genus, g(M), is the minimal genus of a Heegaard surface for M, and is one of the most basic 3-manifold invariants. Because Heegaard surfaces are generic, they have been studied extensively and have been effectively classified for large classes of manifolds [16, 23]. It is thus natural to ask (phrased as a decision problem):

Problem 1.1

Heegaard Genus ≤ g: Given a triangulated 3-manifold M and a natural number g, does M have a Heegaard surface of genus ≤ g?

Heegaard Genus ≤ g was shown to be decidable (computable) by Johannson [14, 15] in the Haken case and by Li in the non-Haken case [20]. Our main result is the following:

Theorem 1.2

Heegaard Genus ≤ g is NP -hard.

One way of obtaining a Heegaard surface in certain 3-manifolds is to amalgamate Heegaard surfaces in submanifolds. This approach allows us to relate Heegaard genus to satisfiability of Boolean formulas in conjunctive normal form, that is Boolean formulas stated as a conjunction of disjunctions, for example:

$$\displaystyle{Q = (a \vee c) \wedge (\neg a \vee b) \wedge (b \vee c)}$$

We will let | Q |  denote the length of Q without counting parentheses, e.g. | Q | = 12 for the above example.

Problem 1.3

CNF-SAT: Given Q, a Boolean formula in conjunctive normal form, is there a satisfying assignment (i.e., an assignment of truth values to the variables) that makes the formula true?

CNF-SAT is well known to be NP-complete. We prove Theorem 1.2 by giving a polynomial (quadratic) time reduction of CNF-SAT to Heegaard Genus ≤ g. Our reduction will proceed in two steps, first proving that there are manifolds M _Q that encode a formula Q:

Proposition 3.1

Let Q be an instance of CNF-SAT. Then there is a manifold M _Q with Heegaard genus g(M _Q ) ≥ | Q | + 2, with equality holding if and only if Q has a satisfying assignment.

The proof of Proposition 3.1 is based on constructing M _Q as a direct translation of the formula Q (a schematic of M _Q for the aforementioned Q is shown in Fig. 1), formed by taking a collection of Heegaard genus two “block” manifolds, one block for each term (var(iable), rep(licate), not, and, or) in Q, and gluing them together along torus boundary components via high distance maps. Each gluing surface then represents a sub-statement of Q. The high-distance gluings guarantee that any minimal genus Heegaard surface for M _Q is an amalgamation of Heegaard surfaces of the blocks (we provide a proof of this fact in the appendix of this paper), and this allows us to compute the Heegaard genus of M _Q .

Fig. 1

The construction of M _Q , where Q = ((a ∨ c) ∧ (¬ a ∨ b)) ∧ (b ∨ c)

Every Heegaard surface induces a bipartition, a partition into two sets, of its manifold’s boundary components. The blocks are constructed so that each block emulates its logical operator via the way its minimal genus Heegaard surfaces bipartition its boundary components. The or block is flexible, in that every non-trivial bipartition is possible, whereas all other block types have a fixed bipartition of boundary components determined by the minimal genus Heegaard surfaces. When Q is satisfiable, there is a minimal genus Heegaard surface for each block so that the complementary pieces can be bicolored in a particular way (see Definition 2.7) so that the Heegaard surfaces for the blocks can be amalgamated to a genus | Q | + 2 Heegaard surface for M _Q . The converse uses the same setup. We show that the genus of M _Q is at least | Q | + 2, and that when equality is achieved it is possible to read off a satisfying assignment for Q from a bicoloring induced by Heegaard surfaces for the block manifolds.

There are many manifolds that fit the above description of M _Q . The second step, from which Theorem 1.2 follows, is that we can construct a triangulation for one efficiently.

Proposition 4.1

A triangulated M _Q can be produced in quadratic time (and tetrahedra) in | Q | .

The essential ingredient for our main result is our ability to choose block manifolds whose minimal genus Heegaard surfaces bipartition their boundary components in a way that emulates the required logical operators. It is then worth asking: given a set of bipartitions, is there a 3-manifold whose minimal genus Heegaard surfaces induce precisely that set? In fact, this is an easy corollary of the techniques we use here.

Corollary 3.8

Let $\mathbb{P}$ be a non-empty set of bipartitions of 1, 2, …, n. Then there is a 3-manifold X and a numbering of its boundary components, 1, 2, …, n, so that the set of bipartitions of ∂X induced by minimal genus Heegaard splittings of X is precisely $\mathbb{P}$ .

This paper is organized as follows: Sect. 2 contains the required background on Heegaard splittings, surfaces, and amalgamation. Section 3 gives a recipe for producing M _Q and proves Proposition 3.1 and Corollary 3.8. Section 4 shows how to triangulate M _Q and proves Proposition 4.1. Section 5 lists some related open questions. The appendix proves Proposition 1, which explains how high distance gluings ensure that minimal genus Heegaard surfaces are amalgamations.

2 Heegaard Splittings and Amalgamations

Definition 2.1

Consider a 3-ball B, and attach 1-handles to ∂B. The resulting 3-manifold is a handlebody. Alternatively, let F be a closed, not necessarily connected, orientable surface such that each component of F has genus greater than zero. Take the product F × [0, 1] and attach 1-handles along F ×{ 1}. Assuming it is connected, the resulting 3-manifold V is a compression body, and we denote ∂ ₋ V = F ×{ 0} and ∂ ₊ V = ∂V − ∂ ₋ V. (We will consider a handlebody as a compression body with ∂ ₋ V = ∅.)

Let M denote a compact, connected, orientable 3-manifold.

Definition 2.2

A Heegaard splitting for M is a decomposition M = V ∪ W where V and W are compression bodies such that ∂ ₊ V = ∂ ₊ W = V ∩ W. The surface H = ∂ ₊ V = ∂ ₊ W in M is called a Heegaard surface, and when needed we may include this surface in the notation for the Heegaard splitting as V ∪ _H W. The genus of V ∪ _H W is the genus of H, denoted g(H).

Remark 2.3

Note that the compression bodies V and W bipartition the boundary of M into ∂ _V M = ∂M ∩ V = ∂ ₋ V and ∂ _W M = ∂M ∩ W = ∂ ₋ W. In particular, a Heegaard splitting for M always induces a bipartition {∂ _V M | ∂ _W M} of the boundary components of M, and thus it is proper to say that V ∪ W is a Heegaard splitting of M with respect to the bipartition {∂ _V M | ∂ _W M}.

Given M, one can find Heegaard splittings of M in several ways. For example, if M is triangulated with t tetrahedra, then one can obtain a Heegaard splitting of M of genus t + 1, taking the boundary of a regular neighborhood of the 1-skeleton as the Heegaard surface. Alternatively, if M can be decomposed as a union of submanifolds $M =\bigcup M_{i}$, so that M is obtained by gluing the M _i together along their boundary components (including possible self-gluings), one can potentially amalgamate Heegaard splittings of the M _i to form a Heegaard splitting of M:

Example 2.4

Let M ₁ and M ₂ be 3-manifolds such that $\partial M_{1}\cong \partial M_{2}\cong F$, and let V ₁ ∪ W ₁ be a Heegaard splitting of M ₁ with respect to the bipartition {∅ | ∂M ₁} and V ₂ ∪ W ₂ a Heegaard splitting of M ₂ with respect to the bipartition {∂M ₂ | ∅}. Note that both W ₁ and V ₂ are compression bodies of the form F × [0, 1] ∪{1-handles}. Form the 3-manifold M by gluing M ₁ to M ₂ along their boundaries, and, abusing notation slightly, let F be the image of the boundary components in M. Collapse the product structures in W ₁ and V ₂ so that in each, F × [0, 1] is mapped to F ×{ 0} = F, and so that the 1-handles of each of W ₁ and V ₂ are attached disjointly on F. We then obtain a new Heegaard splitting V ∪ W of M, where V = V ₁ ∪{1-handles in V ₂}, and W = {1-handles in W ₁} ∪ W ₂. The splitting V ∪ W is called the amalgamation of V ₁ ∪ W ₁ and V ₂ ∪ W ₂ along F. See Fig. 2.

Fig. 2

A schematic for the amalgamation given in Example 2.4. The light and dark regions represent compression bodies, with W ₁ and V ₂ expressed as F × [0, 1] ∪ (1-handles). The dotted lines represent Heegaard surfaces

Constructing an amalgamation of $M =\bigcup M_{i}$ from component Heegaard splittings of M _i , however, is not always possible.

Example 2.5

Suppose M is formed by taking M ₁ = T ² × [0, 1] and gluing the two components of ∂M ₁ together. Let F be the image of ∂M ₁ (an embedded torus) in M.

It is well known that M ₁ admits two irreducible Heegaard surfaces up to isotopy [32]: a “Type 1” surface that is a level torus $T^{2} \times \{\frac{1} {2}\}$ and induces the non-trivial bipartition of boundary components {T ² ×{ 0} | T ² ×{ 1}}, and a “Type 2” surface that is a genus two Heegaard surface obtained by tubing together two disjoint copies, say $T^{2} \times \{\frac{1} {4}\}$ and $T^{2} \times \{\frac{3} {4}\}$, of the level surface. Note that this latter surface induces the trivial bipartition of boundary components {T ² ×{ 0}, T ² ×{ 1} | ∅}.

One cannot form an amalgamated splitting for M by taking a Type 2 Heegaard splitting of M ₁ and amalgamating it to itself (See Fig. 3a). This is because in attempting to apply the construction of Example 2.4, we do not end up with two resulting compression bodies once we collapse the product structure of F × [0, 1] (i.e. the resulting “Heegaard surface” is not separating).

Fig. 3

(a) A Type 2 Heegaard splitting of T ² × [0, 1] cannot be amalgamated to itself; (b) two Type 1 Heegaard splittings of T ² × [0, 1] cannot be amalgamated together (Note that $\mathbb{G}$ here is not a DAG)

Example 2.6

Let M ₁ and M ₂ each be copies of T ² × [0, 1], and form M = M ₁ ∪ M ₂ by gluing ∂M ₁ to ∂M ₂ component-wise. Let F = ∂M ₁ = ∂M ₂, so that F consists of two disjoint tori embedded in M. Then, one cannot form an amalgamated Heegaard splitting of M from Type 1 Heegaard splittings of M ₁ and M ₂ (See Fig. 3b). The issue here is that the Heegaard splitting of M _i , i = 1, 2, does not partition the components of ∂M _i into a single compression body, and thus one cannot simultaneously collapse the product structure F × [0, 1] along each component of F as in Example 2.4 to form an amalgamation.

Assume that $M =\bigcup M_{i}$ where the M _i meet along boundary components. Rather than thinking of the M _i in a linear order, it is more natural to consider the following construction. Let $\mathbb{G}$ be the dual graph of $\bigcup M_{i}$, so that each submanifold M _i is assigned a vertex x, and two vertices corresponding to M _i and M _j are connected by an edge for each component of ∂M _i ∩ ∂M _j . (Note that i may equal j, in the case of self-gluings.) Relabelling the submanifolds M _i as M _x , one for each vertex x of $\mathbb{G}$, we can consider $M =\bigcup _{x\in \mathbb{G}}M_{x}$. The following definition provides the conditions under which Heegaard splittings of the M _x can form an amalgamated Heegaard splitting of M.

Definition 2.7

A generalized Heegaard splitting of $M =\bigcup _{x\in \mathbb{G}}M_{x}$ is a choice, for each M _x , of a Heegaard splitting M _x = V _x ∪ W _x , so that:

• (1) The compression bodies are bicolored “black” and “white” (or “V” and “W”). That is $V _{x} \cap V _{x^{{\prime}}} =\emptyset,W_{x} \cap W_{x^{{\prime}}} =\emptyset$, for all x ≠ x ^′.

• (2) Given this bicoloring, the graph $\mathbb{G}$ becomes a directed acyclic graph (DAG) after assigning edges of $\mathbb{G}$ to point toward “white”: as each edge e of $\mathbb{G}$ is dual to a surface in M that has a black compression body V _x on one side and a white compression body $W_{x^{{\prime}}}$ on the other, assign an orientation to e that points from x to x ^′ (“black” to “white”). We require that the resulting directed graph has no directed cycles.

Theorem 2.8

If $\bigcup _{x\in \mathbb{G}}\left (V _{x} \cup W_{x}\right )$ is a generalized Heegaard splitting of $M =\bigcup _{x\in \mathbb{G}}M_{x}$ , then the Heegaard splittings V _x ∪ W _x can be amalgamated to form a Heegaard splitting of M.

Proof

We construct the desired Heegaard splitting in stages. Assume that the graph $\mathbb{G}$ is directed as per Definition 2.7. As $\mathbb{G}$ contains no directed cycles, the graph has a vertex which is a sink (all edges meeting it point “in”). Remove this vertex and all edges meeting it from the graph. In the remaining (potentially disconnected) graph, find another sink, and repeat the process. Continue until all such sinks have been removed. As $\mathbb{G}$ is a DAG, this means we are left only with a collection of vertices (the sources of the original graph).

Now add back the last removed sink x ₀, along with the edges e ₁, …, e _m that point in toward it. Let x ₁, …, x _n be the set of vertices that bound the edges e ₁, …, e _m along with x ₀. Since x ₀ is a sink, the bicoloring of the compression bodies of $\bigcup V _{x_{i}} \cup W_{x_{i}}$ in the generalized Heegaard splitting implies $M_{x_{0}}$ meets each $M_{x_{i}}$ only in $W_{x_{0}}$ and $V _{x_{i}}$, i = 1, …, n, respectively. In particular, the components $F_{e_{1}},\ldots,F_{e_{m}}$ of $\partial M_{x_{0}}$ corresponding to the edges e ₁, …, e _m are all contained in $W_{x_{0}}$ and $\bigcup V _{x_{i}}$. Thus, we may carry out the procedure of Example 2.4 and collapse the product structures $F_{e_{j}} \times [0,1]$ to $F_{e_{j}}$ simultaneously for all j in the compression bodies $W_{x_{0}}$, $V _{x_{1}},\ldots,V _{x_{n}}$ and obtain a new Heegaard splitting V ^′∪ W ^′ of $M^{{\prime}} = M_{x_{0}} \cup \ldots \cup M_{x_{n}}$. Note that this new Heegaard splitting preserves the original bicoloring given by $\bigcup V _{x} \cup W_{x}$ for boundary components of M ^′: if F ^′ is a component of ∂M ^′, then F ^′ ⊂ ∂V ^′ if and only if $F^{{\prime}}\subset \partial V _{x_{i}}$ for some x _i . (Boundary components of M ^′ stay “black” or “white.”)

Add back in the next sink x ₀ ^′. If $M_{x_{0}^{{\prime}}}$ does not meet M ^′, then we simply repeat the above process for the subset of $\mathbb{G}$ that consists of edges and bounding vertices that meet x ₀ ^′. If $M_{x_{0}^{{\prime}}}$ meets M ^′, then we consider M ^′ as a whole with the Heegaard splitting V ^′∪ W ^′ obtained above. Since V ^′∪ W ^′ preserves the bicoloring of boundary components of M ^′ given by the original generalized Heegaard splitting, we can repeat the above process to obtain a new Heegaard splitting of $M_{x_{0}^{{\prime}}}\cup M^{{\prime}}\cup \{ M_{y}\ \vert \ y\ \mbox{ is a new vertex directed towards }x_{0}^{{\prime}}\}$.

Building in this way, we can continue to obtain new Heegaard splittings of larger collections of submanifolds of M, until we complete the graph $\mathbb{G}$ and produce a Heegaard splitting V ∪ W of M. □

As before, the Heegaard splitting V ∪ W obtained in the above proof is called the amalgamation of the Heegaard splittings of the M _x along the surfaces F, where F is the collection of components of the ∂M _x that are dual to edges in $\mathbb{G}$ (i.e. $F = \left (\bigcup _{x\in \mathbb{G}}\partial M_{x}\right )\setminus \partial M$). Note that V ∪ W is obtained by sequential applications of the technique in Example 2.4 to amalgamations of Heegaard splittings of “sink” submanifolds to their adjacent submanifolds. The critical feature of a generalized Heegaard splitting that allows one to construct V ∪ W is that each component Heegaard splitting bipartitions the boundary components of the M _x suitably so that we can bicolor the set of compression bodies (this allows us to end up with two compression bodies in the amalgamated Heegaard splitting, avoiding the problem of Example 2.5), and can use the bicoloring to direct the edges of $\mathbb{G}$ so that we can amalgamate in sequence “outward” from sinks at each stage (thereby avoiding the problem of Example 2.6 – recall Fig. 3).

Theorem 2.9

Suppose $\bigcup _{x\in \mathbb{G}}\left (V _{x} \cup _{H_{x}}W_{x}\right )$ is a generalized Heegaard splitting of $M =\bigcup _{x\in \mathbb{G}}M_{x}$ . For every edge e of $\mathbb{G}$ , let F _e denote the component of $\bigcup \partial M_{x}$ dual to e in M. Let V ∪ _H W be the amalgamation of $\bigcup _{x\in \mathbb{G}}\left (V _{x} \cup _{H_{x}}W_{x}\right )$ . Then

$$\displaystyle{g(H) = \sum _{x\in \mathbb{G}}g(H_{x}) -\sum _{e\in \mathbb{G}}g(F_{e}) + 1 -\chi (\mathbb{G}).}$$

Proof

Proceed with the same setup and notation as in the proof of Theorem 2.8. In particular, for the first step in constructing an amalgamation of M, consider Heegaard splittings $V _{x_{i}} \cup _{H_{x_{ i}}}W_{x_{i}}$ of $M_{x_{i}}$, i = 0, …, n, respectively, and their corresponding vertices x ₀, …, x _n and connecting edges e ₁, …, e _m in $\mathbb{G}$. Let $F_{e_{1}},\ldots,F_{e_{m}}$ denote the corresponding surfaces in M dual to e ₁, …, e _m . Let $M^{{\prime}} =\bigcup _{ i=0}^{n}M_{x_{i}}$.

By construction, the genus of the amalgamated Heegaard splitting is obtained by adding the genus of $H_{x_{0}}$ to the handle numbers of $V _{x_{i}}$, i = 1, …, n. If V is a compression body, then the handle number of V is the number of 1-handles added to ∂ ₋ V × [0, 1] along ∂ ₋ V ×{ 1} to obtain V (see Fig. 4). There are two types of potential such 1-handles: a minimal set that connects components of ∂ ₋ V × [0, 1] (essentially fulfilling the role of “connected sum” of components of ∂ ₋ V ×{ 1}), and those that increase the genus of ∂ ₊ V. Thus, the handle number of V equals

$$\displaystyle{\#_{handle}(V ) = g(\partial _{+}V ) -\sum _{F\in \partial _{-}V }g(F) + \vert \partial _{-}V \vert - 1.}$$

Fig. 4

A schematic of a compression body V with# _handle (V ) = 5 (Note that ∂ ₊ V is denoted by dotted lines)

Let $V ^{{\prime}}\cup _{H^{{\prime}}}W^{{\prime}}$ be the amalgamation of $\bigcup _{i=0}^{n}\left (V _{x_{i}} \cup _{H_{x_{ i}}}W_{x_{i}}\right )$. Using the handle number, the genus of the Heegaard surface H ^′ is

$$\displaystyle{g(H^{{\prime}}) = g(H_{ x_{0}}) +\sum _{ i=1}^{n}\#_{ handle}(V _{x_{i}}).}$$

Plugging in the equations for the handle numbers for the $V _{x_{i}}$ produces

$$\displaystyle\begin{array}{rcl} & g(H^{{\prime}}) = g(H_{x_{0}}) +\sum _{ i=1}^{n}g(H_{x_{i}}) -\sum _{j=1}^{m}g(F_{e_{j}}) + \left \vert \bigcup _{j=1}^{m}F_{e_{j}}\right \vert - n& {}\\ & =\sum _{ i=0}^{n}g(H_{x_{i}}) -\sum _{j=1}^{m}g(F_{e_{j}}) + m - n. & {}\\ \end{array}$$

Let $\mathbb{G}^{{\prime}}$ denote the graph connecting x ₀ to x ₁, …, x _n . Since m is the number of edges in $\mathbb{G}^{{\prime}}$ and n is the number of vertices minus one, we conclude $m - n = 1 -\chi (\mathbb{G}^{{\prime}})$. Hence

$$\displaystyle{g(H^{{\prime}}) =\sum _{ i=0}^{n}g(H_{ x_{i}}) -\sum _{j=1}^{m}g(F_{ e_{j}}) + 1 -\chi (\mathbb{G}^{{\prime}}).}$$

For any new submanifold that is included in the amalgamation at a subsequent stage, the above relationship is preserved. That is, suppose that $M^{{\prime}} = V ^{{\prime}}\cup _{H^{{\prime}}}W^{{\prime}}$ has already been obtained as above by amalgamating component Heegaard splittings, and suppose $M_{y} = V _{y} \cup _{H_{y}}W_{y}$ is a submanifold and Heegaard splitting being newly amalgamated to $V ^{{\prime}}\cup _{H^{{\prime}}}W^{{\prime}}$ along surfaces $F_{e_{1}^{{\prime}}},\ldots,F_{e_{m^{{\prime}}}^{{\prime}}}$. Let $\mathbb{G}^{{\prime}}$ and $\mathbb{G}_{y}^{{\prime}}$ be the dual graphs for M ^′ and M ^′∪ M _y , respectively. Repeating the above argument implies that the genus of the resulting amalgamation of M ^′∪ M _y increases by

$$\displaystyle{g(H_{y}) -\sum _{k=1}^{m^{{\prime}} }g(F_{e_{k}^{{\prime}}}) + m^{{\prime}}- 1.}$$

Note that m ^′ is the number of edges of $\mathbb{G}_{y}^{{\prime}}\setminus \mathbb{G}^{{\prime}}$, and so $m^{{\prime}}- 1 = -\chi (\mathbb{G}_{y}^{{\prime}}\setminus \mathbb{G}^{{\prime}})$. In particular, this means that $m - n + m^{{\prime}}- 1 = 1 -\chi (\mathbb{G}^{{\prime}}) -\chi (\mathbb{G}_{y}^{{\prime}}\setminus \mathbb{G}^{{\prime}}) = 1 -\chi (\mathbb{G}_{y}^{{\prime}}).$ Thus, the resulting genus of the amalgamation of M ^′∪ M _y is

$$\displaystyle{\sum _{x\in \mathbb{G}_{y}^{{\prime}}}g(H_{x}) -\sum _{e\in \mathbb{G}_{y}^{{\prime}}}g(F_{e}) + 1 -\chi (\mathbb{G}_{y}^{{\prime}}).}$$

Amalgamating thusly along all remaining submanifolds $M_{y^{{\prime}}}$, $y^{{\prime}}\in \mathbb{G}$, produces the desired result. □

It is important to note that one can find examples of (minimal genus) Heegaard splittings of 3-manifolds that are not amalgamations. For example, by gluing the bridge surface of a tunnel number n − 1, n-bridge knot complement to vertical annuli in a Seifert fibered space over a disk with n exceptional fibers, one can obtain a Heegaard surface of the resulting 3-manifold of genus n, whereas the minimal genus amalgamation along the gluing surface has genus 2n. (See [36].) Note that this Heegaard surface results from a very specific gluing map between the boundary components of the two submanifolds. In general, gluing maps between boundary components can be chosen to be “sufficiently complicated” to ensure that all minimal genus Heegaard splittings are amalgamations along the gluing surfaces. (See the appendix.) Exploiting this property in the next sections allows us to ensure that the minimal genus Heegaard splittings of our constructed 3-manifolds M _Q are amalgamations, to which we can thus apply the results of this section.

3 Constructing M _Q

In this section we give a recipe for producing M _Q from Q and prove the following result.

Proposition 3.1

Let Q be an instance of CNF-SAT. Then there is a manifold M _Q with Heegaard genus g(M _Q ) ≥ | Q | + 2, with equality holding if and only if Q has a satisfying assignment.

Recall that | Q |  is the length of Q without counting parentheses.

3.1 Constructing M _Q

The sentence Q will guide our construction of M _Q . To begin, rewrite Q by inserting parentheses, if necessary, to make it clear how each logical connective joins exactly two terms (i.e. Q is made fully parenthesized). The manifold M _Q is then constructed out of building blocks according to instructions provided by this modified version of Q. Each building block will have Heegaard genus 2 and some number of torus boundary components. Each such boundary component will be labelled with a subsentence of Q, and also be designated as either an input or an output to that block. We will depict such blocks so that the input boundary component is on top, and the outputs are on the bottom. See Fig. 5. Each block is chosen based on a desired bipartitioning of its boundary components by genus 2 Heegaard splittings as follows.

Fig. 5

Schematics indicating block types and their labelings. Input surfaces are depicted at the top of each block, and outputs at the bottom. Minimal genus Heegaard surfaces are depicted with bold lines (With the three possible such splittings of the or block indicated with bold dashed lines)

• var(iable) – For each distinct variable in Q let the block manifold M be a trefoil knot exterior (Fig. 8). Then M has one torus boundary component, ∂M = T, and any genus 2 Heegaard splitting induces the only boundary bipartition possible (up to ordering), {T | ∅}. We label the boundary component T with the corresponding variable, and consider it an output of the block.

• rep(licate) – To create multiple copies of a given variable, we use a block manifold M that is the exterior of the twisted torus link in Fig. 9. Then M has three torus boundary components, ∂M = T ₀ ∪ T ₁ ∪ T ₂ where any genus two Heegaard splitting induces the boundary bipartition {T ₀, T ₁ | T ₂} (Lemma 4.9). All three components will be labelled with the variable that is being duplicated. We will say the boundary component T ₂ is preferred, and will be the input. The other two boundary components are outputs.

• not – For each occurrence of “¬a” in Q, the block manifold M will be a high distance filling on the twisted torus link as described in Lemma 4.10. Then ∂M = T ₀ ∪ T ₁ and any genus two Heegaard splitting induces the bipartition {T ₀, T ₁ | ∅}. Label one boundary component a, and consider it an input. The other boundary component is labelled ¬ a and is considered an output. Glue the input surface to the output of a rep block corresponding to a.

Once we have created one labeled output surface for each instance of each variable in Q, and each instance of its negation, we start gluing them to other kinds of blocks determined by the logical structure of Q, as follows:

• and – For each conjunction A ∧ B in Q, we let M be the exterior of the twisted torus link already used for rep. Then ∂M = T ₀ ∪ T ₁ ∪ T ₂, and all genus two Heegaard splittings all induce the bipartition {T ₀, T ₁ | T ₂} (Lemma 4.9). Label the preferred boundary component T ₂ with the expression A ∧ B, and consider it an output. The other two boundary components are inputs, and are labelled with the expressions A and B respectively.

• or – For each disjunction A ∨ B in Q we let M be the exterior of the three component chain indicated in Fig. 8. It is homeomorphic to {pair of pants} × S ¹, has three boundary components ∂M = T ₀ ∪ T ₁ ∪ T ₂, and each of the three boundary bipartitions of the form {T _i , T _j | T _k } is realized by some genus two Heegaard splitting (Lemma 4.8). Choose one boundary component to label as A ∨ B, and consider it an output. The remaining boundary components are inputs, and are labelled with the expressions A and B respectively.

• end – We end by capping the statement off with the same M, the trefoil knot exterior, used for var. The manifold M has one torus boundary component, ∂M = T, and a single boundary bipartition {T | ∅}. It is labelled with the entire expression Q, and is an input.

To glue the blocks, we choose “sufficiently complicated” maps so that every Heegaard splitting of M _Q of genus less than or equal to | Q | + 2 is an amalgamation of splittings of the blocks. (See the appendix.)

As an example, Fig. 1 gives the construction of the manifold M _Q from the expression

$$\displaystyle{Q = ((a \vee c) \wedge (\neg a \vee b)) \wedge (b \vee c).}$$

3.2 Proof of Proposition3.1

Lemma 3.2

The Heegaard genus of M _Q is at least | Q | + 2, and in the case of equality, any such minimal genus splitting is an amalgamation of minimal genus splittings of the building blocks.

Proof

Let S be a minimal genus Heegaard splitting of M _Q . If the genus of S is strictly greater than | Q | + 2 then the result follows. By way of contradiction, we assume the genus of S is at most | Q | + 2. By construction, S is then an amalgamation of Heegaard splittings of the building blocks. We now use Theorem 2.9 to compute the genus of S:

$$\displaystyle{g(S) = \sum _{x\in \mathbb{G}}g(H_{x}) -\sum _{e\in \mathbb{G}}g(F_{e}) + 1 -\chi (\mathbb{G}).}$$

Here $\mathbb{G}$ is the graph dual to the block structure. Let v be the number of vertices, one for each block, and e the number of edges, one for each gluing torus. Note that the number of variable occurrences in Q is the number of var and rep blocks. The operators in Q each have a corresponding not, or, or and block, and there is a final end block for the total statement Q. In particular, v = | Q | + 1. Since each block has genus 2, we have g(H _x ) ≥ 2 for each x, with equality holding only for those blocks with minimal splittings, and g(F _e ) = 1 for each e. Thus,

$$\displaystyle{g(S) \geq 2v - e + 1 - (-e + v) = v + 1 = \vert Q\vert + 2.}$$

□

Lemma 3.3

If the Heegaard genus of M _Q is equal to | Q | + 2 then there is a satisfying assignment of Q.

Proof

Suppose S is a minimal genus Heegaard surface of M _Q . If the genus of S is | Q | + 2, then by the previous lemma S is an amalgamation of minimal genus Heegaard surfaces {S _i } in the building blocks.

Because S is an amalgamation, the surfaces {S _i }, together with the gluing surfaces, separate the manifold M _Q into compression bodies that can be colored “black” and “white” so that no two compression bodies with the same color are adjacent. Without loss of generality, we assume the compression body of the end block which contains its sole input surface is colored white.

We will now assign truth values to the gluing surfaces between blocks, according to this bicoloring. Let F be such a gluing surface. Then F is the input surface for some block. If the compression body in that block containing F is white, then we will say that F is true. Otherwise, we say it is false. Equivalently, we can say that F is true if it is the output of a block, and the compression body in that block that contains F is black. Thus, if the Heegaard surface in some block separates an input surface A of that block from an output surface, B, then A and B will have the same truth value. It follows immediately that the input and output surfaces of all rep blocks have the same truth value. Similarly, the truth value of the input of a not block labelled a will have the opposite truth value as the output labelled ¬ a. Finally, note that the surface at the input of the end block (which we have labelled with the statement Q) is by choice assigned the truth value true.

In the next several claims, we show that our assignment of truth values respects the logical structure of the subsentences of Q that appear at the labels of (most of) the gluing surfaces.

Claim 3.4

All surfaces at the inputs and outputs of the and blocks are true.

Proof

The minimal genus Heegaard surface of an and block separates the output surface from both inputs. Thus, the output and input surfaces all have the same truth value. The proof is complete by noting that since Q is in conjunctive normal form, the output of every and block is glued to the input of the end block (a true surface), or the input of another and block. □

We say an or -tree is a component of the union of the or blocks in M _Q .

Claim 3.5

The output of every or-tree is true, and at least one of the input surfaces of every or -tree is true.

Proof

Let F ₀ denote the output surface of an or-tree. Since Q is in conjunctive normal form, F ₀ is glued to the input of an and block. By the previous claim, F ₀ must be true. By construction, the Heegaard surface of the or block that contains F ₀ separates it from at least one of the input surfaces F ₁ of that block. Thus, F ₁ will also be true. Working up the tree, we now consider the or block in the tree whose output is the surface F ₁. By identical reasoning, one of its input surfaces F ₂ must be true as well. Continuing in this way we eventually reach an input surface F _i of the entire or-tree and conclude that it must be true. □

Note that some of the truth values of the sentences that label gluing surfaces interior to an or-tree may not be correct, but the previous claim shows this does not disturb the logical structure of the or-tree, taken as a whole.

To complete the lemma, note that we have assigned a truth value to the output surface of every var block. These surfaces correspond to the variables used in the sentence Q. We have shown above that our assignment of truth values to the input and output surfaces of rep, not, and and blocks, as well as or trees, respects the logical structure of the sentences that label them. Thus, we have produced an assignment of truth values for the variables that make the statement Q true. □

Lemma 3.6

If there is a satisfying assignment of Q, then the Heegaard genus of M _Q is equal to | Q | + 2.

Proof

If there is a satisfying assignment of Q, then that assignment gives a truth value to each expression at the gluing surfaces. In this way, each boundary component of each building block gets assigned a truth value. We color the sides of each such surface black/white so that if F is a true surface at the output of a block, then the side of F facing into that block is black. Similarly, if F is a true surface at the input of a block, then the side facing in is colored white. Conversely, the side of a false surface at the output of a block is colored white, and the side of a false surface at an input is black.

Claim 3.7

There is a minimal genus splitting of each block that separates all white surfaces on the inside of the block from all black surfaces facing in.

Proof

Consider first the end block. Since there is only one boundary component, any Heegaard splitting (and in particular the minimal genus one) has the desired separation property.

Next we consider the and blocks. Since Q is in conjunctive normal form, the output of each such block is either attached to the end block, or another and block. Hence, if there is a satisfying assignment for Q then the labels at every input and output surface of an and block are true logical sentences. It follows that the side of the input surfaces that face into such a block are white, and the side of the output surface facing into the block is black. Such a block has the output as a preferred boundary component, meaning that a minimal genus splitting separates the output surface from both input surfaces. Hence, the minimal genus splitting has the desired separation property.

An or block has no preferred boundary component. Thus, there is a minimal genus splitting for each non-trivial bipartitioning of the boundary components. It follows that the only way the separation property can fail is if the side of every boundary surface facing in to the block is the same color. If they are all white, then this corresponds to both inputs being true, and the output being false. If they are all black, then both inputs are false, and the output is true. Neither situation obeys the properties of the logical “or” operation, so we will not see these sets of truth values for the labels of the surfaces at the boundary of an or block.

By construction, a rep block has the same logical value at each input and output. If they are all true, then the side of the input surface that faces into the block is white, and the side of the outputs that faces in is black. The input surface of this block is a preferred boundary component, so the minimal genus splitting separates black from white as desired. If all surfaces are false, the situation is reversed.

Finally, we consider the not blocks. The sentences at the boundary components of a not block will have opposite truth values. Thus, the side of the input surface facing into the block will have the same color as the side of the output surface facing in. Both surfaces are on the same side of a minimal genus splitting of a not block. □

Assume we have now chosen splittings of each block in accordance with the conclusion of Claim 3.7. Then the building blocks are separated into compression bodies by these splittings, and these compression bodies inherit the color black or white, according to the colors of their negative boundaries. Furthermore, because opposite sides of any single gluing surface are different colors, it follows that neighboring compression-bodies in M _Q are colored differently.

According to Theorem 2.8, to show that we can amalgamate our choice of splittings of the building blocks, it remains to show that the directed graph $\mathbb{G}$ that is dual to the gluing surfaces has no directed cycles. (Recall that each edge of this graph is oriented so that it passes from a black compression body into a white one.)

We have constructed M _Q vertically so that the output surface(s) of any given block is below its input surface(s). Any directed cycle must have a local maximum, x. Let e ₁ and e ₂ be the edges of the cycle that meet x, where e ₁ is oriented toward x, and e ₂ is oriented away. As x is a local maximum, both e ₁ and e ₂ correspond to output surfaces of the building block corresponding to x. It follows that this building block is a rep block, as this is the only type of block that has two output surfaces. However, according to our coloring scheme, both output surfaces of a rep block are on the boundary of the same compression body. If this compression body is black, then both e ₁ and e ₂ are oriented away from x. If the compression body is white, then both are oriented toward x. This contradiction establishes that there are no directed cycles in $\mathbb{G}$.

By Theorem 2.8 we can now amalgamate the chosen splittings of our building blocks, creating a splitting of M _Q . By the computation given in the proof of Lemma 3.2, the genus of this splitting is | Q | + 2. □

Finally, note that if one were to remove the var blocks from M _Q , we would obtain a manifold with a boundary component corresponding to each variable, and, for each satisfying assignment, a minimal genus Heegaard splitting that induces a {true | false} bipartition of the corresponding boundary components. That is the basis for the following corollary.

Corollary 3.8

Let $\mathbb{P}$ be a non-empty set of bipartitions of 1, 2, …, n. Then there is a 3-manifold X and a numbering of its boundary components, 1, 2, …, n, so that the set of bipartitions of ∂X induced by minimal genus Heegaard splittings of X is precisely $\mathbb{P}$ .

Proof

Suppose that P is a bipartition of 1, . . , n. That is, P = {P ₊ | P ₋} so that P ₊ ∪ P ₋ = 1, . . , n and P ₊ ∩ P ₋ = ∅. Let v _i , i = 1, . . , n be variables and let the clause q(P) be a conjunction of each variable or its negation, depending on which side of the bipartition P its index belongs to:

$$\displaystyle{q(P) =\bigwedge \{ v_{i}\vert i \in P_{+}\}\bigwedge \{\neg v_{i}\vert i \in P_{-}\}.}$$

Of course, q(P) accepts exactly one satisfying assignment, and that corresponds (via the correspondence i ∈ P ₊ ⇔ v _i = true) to the bipartition P. Now let $\mathbb{P}$ be a set of bipartitions of 1, …, n and let $\mathbb{P}^{C}$ be its complement, i.e. the set of bipartitions not in $\mathbb{P}$. Let

$$\displaystyle{Q(\mathbb{P}^{C}) =\bigvee \{ q(P)\vert P \in \mathbb{P}^{C}\}}$$

Now, let $Q = Q(\mathbb{P}) =\neg Q(\mathbb{P}^{C})$ which, after applying De Morgan’s laws, is an instance of CNF-SAT. Let M _Q be built according to the procedure above. Now it is easy to check that satisfying assignments are in 1-1 correspondence with bipartitions $P \in \mathbb{P}$, again by using the correspondence i ∈ P ₊ ⇔ v _i = true.

Let M _Q be constructed as before. Note that since Q is satisfiable, M _Q has Heegaard genus | Q | + 2. Let M _Q ^′ be the manifold obtained by removing each var block. Because each var block removed is a leaf in $\mathbb{G}$, the graph dual to the block structure, the proofs of Lemmas 3.3 and 3.6 apply to M _Q ^′ as well as to M _Q . In particular, a minimal genus splitting of M _Q ^′ determines a satisfying truth assignment to the v _i ’s, and vice-versa. Note that each v _i labels a boundary component of M _Q ^′, and each minimal genus splitting separates the true variables from the false variables, so bipartitions induced by minimal genus splittings are in 1-1 correspondence with satisfying assignments which in turn are in 1-1 correspondence with bipartitions $P \in \mathbb{P}$ (via i ∈ P ₊ ⇔ v _i = true). □

4 Triangulating M _Q

In this section, we describe how to triangulate the manifold M _Q so that the number of tetrahedra used is at most quadratic in | Q |, the length of the statement Q. Our goal is the following:

Proposition 4.1

A triangulated M _Q can be produced in quadratic time (and tetrahedra) in | Q | .

We proceed in several steps. First, in Sects. 4.1 and 4.2 we give a method to perform high distance triangulated gluings via layered triangulations. For the most part, these are not new results. Our statements about distances in the Farey graph in Sect. 4.1 are certainly well known, and layered triangulations (Sect. 4.2) are described by Jaco and Rubinstein in [12]. We include these sections, instead of just citing earlier work, because they are both accessible to the non-expert and also make explicit the relationship between the distance of the gluing and the number of layers.

Next, in Sect. 4.3, we give a topological description of block manifolds whose boundary components are appropriately bipartitioned by minimal genus Heegaard splittings. We consolidate some well known results and substantially leverage the work of Morimoto, Sakuma, and Yokota on Heegaard splittings of twisted torus knots [27], and the work of Moriah, Rieck, Rubinstein and Sedgwick that characterizes how and when a Dehn filling creates new Heegaard splittings [22, 25, 28–30].

We conclude, in Sect. 4.4, with a proof of Proposition 4.1 that describes how the blocks can be triangulated and then glued together.

4.1 Slopes and the Farey Graph

A slope is the isotopy class of an essential simple closed curve on a torus. Fix a pair of basis elements for the homology, $\mathbb{Z} \times \mathbb{Z}$, of the torus. Then any slope can be written as a pair (a, b), and because it is realized by a simple (connected) curve, we have gcd(a, b) = 1. The usual convention is thus to represent the slope by the extended rational $\frac{a} {b} \in \mathbb{Q} \cup \{\infty \}$, where $\infty = \frac{1} {0}$.

We say that a pair of slopes have distance one if there are a pair of curves representing the slopes that intersect transversely in a single point. It is well known that a pair of slopes have distance one if and only if their extended rationals (with respect to any basis), $\frac{a} {b}$ and $\frac{c} {d}$, satisfy | ad − bc | = 1.

Definition 4.2

Let T be a torus. The Farey graph for T is the graph whose vertex set is the set of slopes and whose edges join any pair of vertices whose underlying slopes have distance one. Of course, after choosing a basis for homology, we are able to label each vertex of the graph with an extended rational $\frac{a} {b} \in \mathbb{Q} \cup \{\infty \}$. Each edge then joins a pair of extended rationals, $\frac{a} {b}$ and $\frac{c} {d}$, which satisfies | ad − bc | = 1.

Definition 4.3

If α and β are slopes in a torus T, then the Farey distance between them $d_{\mathbb{F}}(\alpha,\beta )$ is their distance in the Farey graph. If a ⊂ T and b ⊂ T are closed essential curves, then we define their distance, $d_{\mathbb{F}}(a,b) = d_{\mathbb{F}}(\alpha,\beta )$, to be the distance between α and β, isotopy classes of single components of a and b, respectively.

Form a 2-complex, the curve complex of the torus T, by attaching to the Farey graph a triangular face for every triple of slopes that pairwise intersect once. Fixing a basis for T, every edge is specified by a pair $\left (\frac{a} {b}, \frac{c} {d}\right )$ satisfying | ad − bc | = 1. It is not hard to see that in the curve complex, there are precisely two triangles, $\left (\frac{a} {b}, \frac{c} {d}, \frac{a+c} {b+d}\right )$ and $\left (\frac{a} {b}, \frac{c} {d}, \frac{a-c} {b-d}\right )$ attached to the edge $\left (\frac{a} {b}, \frac{c} {d}\right )$. This is described by the well known Farey tessellation of the Poincaré disk model of $\mathbb{H}^{2}$, see Fig. 6.

Fig. 6

The Farey tessellation of the Poincaré disk

Moreover, each triangular face identifies a triangulation of the torus T up to isotopy: The slopes $\frac{a} {b}$ and $\frac{c} {d}$ can be realized by a pair of curves in the torus meeting in a single point. Together, they cut the torus into a rectangle. This rectangle has exactly two choices for a diagonal curve, with slopes $\frac{a+c} {b+d}$ and $\frac{a-c} {b-d}$ when connected through the intersection point. Choose one, say $\frac{a+c} {b+d}$. Then the triple of curves $\left (\frac{a} {b}, \frac{c} {d}, \frac{a+c} {b+d}\right )$ intersect in a single common point. Treating that point as a vertex, we have formed a (non-simplicial) triangulation of the torus T with one vertex, three edges and two faces. We call this a one-vertex triangulation of the torus. Note that the two triangulations $\left (\frac{a} {b}, \frac{c} {d}, \frac{a+c} {b+d}\right )$ and $\left (\frac{a} {b}, \frac{c} {d}, \frac{a-c} {b-d}\right )$ meeting the edge $\left (\frac{a} {b}, \frac{c} {d}\right )$ are related by a diagonal flip, that exchanges the diagonal $\frac{a+c} {b+d}$ for the diagonal $\frac{a-c} {b-d}$, or vice-versa.

4.2 Layering

Later we will assume that our manifold X has been endowed with a triangulation that restricts to a one vertex triangulation of each of its torus boundary components [11].

Let e be an edge in the triangulation of the boundary torus T ⊂ ∂X. Then e can be regarded as the diagonal of a rectangle R bounded by the other two edges. Picture a new tetrahedron, $\Delta$, as being a slightly thickened horizontal rectangle. Its bottom is a rectangle $R_{\Delta }$ with diagonal $e_{\Delta }$ and its top is a rectangle $R_{\Delta }^{{\prime}}$ with diagonal $e_{\Delta }^{{\prime}}$. See Fig. 7. One can form a new triangulated manifold $X^{{\prime}} = X \cup _{R=R_{\Delta }}\Delta$, by gluing R to $R_{\Delta }$ so that the diagonals e and $e_{\Delta }$ are identified. This process is called layering at e (see also [13]). It is not hard to see that the manifold X ^′ is homeomorphic to X (as it retracts onto X) but that the boundary triangulation has changed. In particular, while e is no longer in the boundary torus, the boundary of R is still in the boundary torus, but its diagonal is now opposite and realized by $e_{\Delta }^{{\prime}}$. Thus, layering at e performs a diagonal flip on e in the boundary triangulation. The two triangulations are represented in the Farey tessellation by a pair of triangles that share a common edge.

Fig. 7

Layering a tetrahedron on the boundary swaps a diagonal

Lemma 4.4

Let T ⊂ ∂X have a one-vertex triangulation with edge slopes $\left (\frac{0} {1}, \frac{1} {0}, \frac{1} {1}\right )$ . Then, by layering on k tetrahedra, we can obtain a new triangulation of X with edge slopes $\left (\tfrac{F_{k-1}} {F_{k-2}}, \tfrac{F_{k}} {F_{k-1}}, \tfrac{F_{k+1}} {F_{k}} \right )$ , where F _k is the kth Fibonacci number.

Proof

Consider the sequence $\frac{0} {1}, \frac{1} {0}, \frac{1} {1}, \frac{2} {1}, \frac{3} {2}, \frac{5} {3},\ldots, \tfrac{F_{k-1}} {F_{k-2}}, \tfrac{F_{k}} {F_{k-1}}, \tfrac{F_{k+1}} {F_{k}}$. Note that each successive triple of terms determines a triangulation, and that each successive pair of triples share two slopes. Hence, the latter boundary triangulation can be obtained by layering on the edge of the former that they do not share. It takes k steps, hence k layers, to move from the first triple to the last. □

Furthermore, continued layering in this fashion increases the distance between the latest edge slopes and the original edge slopes:

Lemma 4.5

Let F _k be the kth Fibonacci number. Then,

$$\displaystyle{d_{\mathbb{F}}\left (\tfrac{F_{k+1}} {F_{k}},\infty \right ) = \lfloor k/2\rfloor + 1}$$

Proof

We will give an inductive proof. It is easy to verify that the statement holds for k = 0, 1, 2, where $\tfrac{F_{k+1}} {F_{k}} = \tfrac{1} {1}, \tfrac{2} {1}, \tfrac{3} {2}$, respectively, and the distances to $\infty = \tfrac{1} {0}$ are 1, 1, 2, respectively. Let k be the least k for which the conclusion of the lemma does not hold. In the Poincaré disk, consider the triangle $\left (\tfrac{F_{k-1}} {F_{k-2}}, \tfrac{F_{k}} {F_{k-1}}, \tfrac{F_{k+1}} {F_{k}} \right )$ which is bounded by edges of the Farey Graph (see Fig. 6). This triangle separates the disk into 3 components.

First, we claim that the points $\tfrac{F_{k+1}} {F_{k}}$ and $\infty = \frac{1} {0}$ lie on opposite sides of the edge $\left ( \tfrac{F_{k}} {F_{k-1}}, \tfrac{F_{k-1}} {F_{k-2}} \right )$. To see this, note that the point $\tfrac{F_{k-2}} {F_{k-3}}$ is the other corner of the second triangle that meets the edge $\left ( \tfrac{F_{k}} {F_{k-1}}, \tfrac{F_{k-1}} {F_{k-2}} \right )$. The inductive hypothesis implies $d_{\mathbb{F}}\left (\tfrac{F_{k-2}} {F_{k-3}},\infty \right ) <d_{\mathbb{F}}\left ( \tfrac{F_{k}} {F_{k-1}},\infty \right )$, so the second triangle must lie on the same side of the edge $\left ( \tfrac{F_{k}} {F_{k-1}}, \tfrac{F_{k-1}} {F_{k-2}} \right )$ as ∞, hence the point $\tfrac{F_{k+1}} {F_{k}}$, lies on the other side.

Now, take a minimal path in the Farey Graph joining ∞ to $\tfrac{F_{k-1}} {F_{k-2}}$. By adjoining the edge $\left (\tfrac{F_{k-1}} {F_{k-2}}, \tfrac{F_{k+1}} {F_{k}} \right )$ to that path, we obtain a path from ∞ to $\tfrac{F_{k+1}} {F_{k}}$. It follows that $d_{\mathbb{F}}\left (\tfrac{F_{k+1}} {F_{k}},\infty \right ) \leq d_{\mathbb{F}}\left (\tfrac{F_{k-1}} {F_{k-2}},\infty \right ) + 1$.

Now, take a minimal path from ∞ to $\tfrac{F_{k+1}} {F_{k}}$. Because ∞ and $\tfrac{F_{k}} {F_{k-1}}$ lie on opposite sides of the edge $\left (\tfrac{F_{k-1}} {F_{k-2}}, \tfrac{F_{k}} {F_{k-1}} \right )$, this minimal path must pass through either the point $\tfrac{F_{k-1}} {F_{k-2}}$ or the point $\tfrac{F_{k}} {F_{k-1}}$. It follows that

$$\displaystyle\begin{array}{rcl} d_{\mathbb{F}}\left (\tfrac{F_{k+1}} {F_{k}},\infty \right )& \geq & \min \left \{d_{\mathbb{F}}\left (\tfrac{F_{k-1}} {F_{k-2}},\infty \right ) + 1,d_{\mathbb{F}}\left ( \tfrac{F_{k}} {F_{k-1}},\infty \right ) + 1\right \} {}\\ & =& d_{\mathbb{F}}\left (\tfrac{F_{k-1}} {F_{k-2}},\infty \right ) + 1. {}\\ \end{array}$$

Thus, $d_{\mathbb{F}}\left (\tfrac{F_{k+1}} {F_{k}},\infty \right ) = d_{\mathbb{F}}\left (\tfrac{F_{k-1}} {F_{k-2}},\infty \right ) + 1$ and the desired result follows. □

Lemma 4.6

Let X be a (possibly disconnected) 3-manifold given via a triangulation that has a single vertex in each of two torus boundary components, T ₀ and T ₁ . If α ₀ ⊂ T ₀ and α ₁ ⊂ T ₁ are slopes and $D \in \mathbb{N}$ , then there is a triangulated manifold X ^′ obtained from X by gluing T ₀ to T ₁ so that

• $d_{\mathbb{F}}(\alpha _{0},\alpha _{1})> D$ , where distance is measured in the common image of T ₀ and T ₁ in X ^′ , and

• t(X ^′) = t(X) + 2D, where t(⋅ ) is number of tetrahedra.

Proof

Fix an orientation on X and assume that the T _i , i = 0, 1, have the induced boundary orientation. For each i = 0, 1, we may choose a basis, (0, ∞), for the homology of the boundary torus T _i so that the edges of the one-vertex triangulation have slopes (0, ∞, 1), the basis (0, ∞) induces the boundary orientation, and α _i has non-positive slope, α _i ≤ 0.

Applying Lemma 4.4, layer 2D tetrahedra on the boundary component T ₀ so that the resulting triangulation has edges with slopes $\left (\tfrac{F_{2D-1}} {F_{2D-2}}, \tfrac{F_{2D}} {F_{2D-1}}, \tfrac{F_{2D+1}} {F_{2D}} \right )$.

Now, let X ^′ be the manifold obtained by gluing the boundary triangulations together via an orientation reversing map that identifies the edge with slope $\tfrac{F_{2D+1}} {F_{2D}}$ in T ₀ with the edge with slope 0 in T ₁. This identifies the pair of edges with slopes $\left (\tfrac{F_{2D-1}} {F_{2D-2}}, \tfrac{F_{2D}} {F_{2D-1}} \right )$ in T ₀, with the pair of edges with slopes (1, ∞) in T ₁, or its reverse. Note that the edge $\left (\tfrac{F_{2D-1}} {F_{2D-2}}, \tfrac{F_{2D}} {F_{2D-1}} \right )$ in the Farey graph for T ₀ separates ∞ and the image of α ₁.

Now compute the distance in the original basis for T ₀ using Lemma 4.5. We have distance $d_{\mathbb{F}}\left (\alpha _{0},\alpha _{1}\right )> d_{\mathbb{F}}\left (\infty, \tfrac{F_{2D-1}} {F_{2D-2}} \right ) = \lfloor \frac{2D-2} {2} \rfloor + 1 = D$, as claimed. □

4.3 Blocks from Links

In this section we construct the required block manifolds. In each case, we prescribe a set of bipartitions of boundary components and then construct a manifold whose minimal genus Heegaard surfaces induce precisely that set of bipartitions of boundary components. All of our examples are Heegaard genus two. Three of the four are realized as the exterior of a knot or link in S ³, that is, each manifold is homeomorphic to X(L) = S ³ − N(L) where L is a knot or link in S ³ and N(⋅ ) denotes an open regular neighborhood. The boundary of each manifold is a union of tori, and we often abuse notation by referring to components of the link, rather than to their corresponding boundary components. The fourth block manifold is obtained by Dehn filling on a torus boundary component of the third block manifold. Many of the results in this section are not new, and are collected for the sake of specificity.

Fig. 8

Trefoil knot and three link chain

For var blocks and the end block we need a genus two manifold with a single incompressible torus boundary component. The exterior of any tunnel number one knot will do, we choose a simple one:

Lemma 4.7 (var, end)

Let K ⊂ S ³ be the trefoil knot (see Fig.  8 ) and X(K) = S ³ − N(K) be its exterior. Then X(K) has Heegaard genus two.

Proof

It is well known that K is tunnel number one (genus two), see e.g. [16]. □

For or blocks, we want a manifold whose minimal genus Heegaard surfaces realize every non-trivial bipartition of its three boundary components. The simplest such manifold seems to be the exterior of the three component chain, whose irreducible, and even non-irreducible, Heegaard splittings are quite well understood [24, 35]. Note that it is impossible for a genus two Heegaard surface to trivially bipartition the boundary components, {T ₀, T ₁, T ₂ | ∅}, as a genus two compression body V cannot have three torus boundary components in ∂ ₋ V.

Lemma 4.8 (or)

Let C ⊂ S ³ be the three component chain (see Fig.  8 ), and X(C) = S ³ − N(C) its exterior. Then,

• (1) X(C) has Heegaard genus two,

• (2) every non-trivial bipartition {T _i , T _j | T _k } of the three boundary components of ∂X(C) is induced by a genus two Heegaard surface for X(C).

Proof

Again, these facts are well known: it is easy to see that for each pair of link components, there is a handle and a short arc connecting them that induces a genus two Heegaard splitting that separates the pair from the other link component. □

Fig. 9

Link with three components: T(7, 17, 6) and two unknots U ₀ and U ₁

For and and rep blocks, we want a manifold whose minimal genus Heegaard surfaces all prefer the same bipartition of its three boundary components. This is a bit more challenging. Fortunately, Morimoto, Sakuma and Yokota showed that certain twisted torus knots are not 1-bridge with respect to an unknotted torus in S ³, providing the basis for the following.

Lemma 4.9 (and, rep)

Let L ⊂ S ³ be the link indicated in Fig.  9 . It is the union of the twisted torus knot T(7, 17, 6) along with two unknotted components U ₀ and U ₁ . Let X(L) be its exterior. Then,

• (1) X(L) has Heegaard genus two,

• (2) any genus two Heegaard splitting of X(L) induces the same bipartition of boundary components, that is {U ₀, U ₁ | T(7, 17, 6)},

• (3) X(L) does not contain a Möbius band with its boundary contained on the knotted boundary component.

Note that conclusion (3) is not needed for the and or rep blocks themselves. Rather, it is technical condition used for the construction of the not block via Lemma 4.10, which follows.

Proof

(1) It is well known [27] and easy to see that a short arc joining the pair of twisted strands is a tunnel system for T(7, 17, 6). The strands can be untwisted by sliding them over the tunnel, after which the tunnel appears to be the “middle tunnel” [26] for the torus knot T(7, 17). Moreover, this gives a genus two splitting of the entire link as the indicated unknots U ₀ and U ₁ are cores for the complementary handlebody. Note that this genus two splitting induces the bipartition {T(7, 17, 6) | U ₀, U ₁} of the boundary components. This is also a minimal genus splitting as no exterior of a link with 3 components has genus one.

(2) Suppose that a genus two Heegaard splitting induces a bipartition that isolates one of the two unknotted components, {U _i | U _j , T(7, 17, 6)}, for some i ≠ j. In particular, this implies that the link T(7, 17, 6) ∪ U _j is tunnel number one. Lemma 4.13 of [26] states that any knot whose union with some unknot is a tunnel number one link must be (1, 1). That is, it has a 1-bridge presentation with respect to an unknotted torus. However this is a contradiction, as Morimoto, Sakuma and Yokota [27] demonstrated that the knot T(7, 17, 6) is not (1, 1). It follows that any genus two Heegaard splitting of X(L) induces the bipartition {U ₀, U ₁ | T(7, 17, 6)}.

(3) Note that the exterior of the link U ₀ ∪ U ₁ is a product, T ² × [−1, 1]. Draw the (7, 17) torus knot as a curve on the level surface T ² ×{ 0} in this product. Choose two strands of the torus knot and give them 6 half twists to obtain the twisted torus knot T(7, 17, 6). Its union with the pair of unknots is our twisted torus link L.

Now, note that the (2, 5) curve drawn on the same level torus meets the (7, 17) curve in a single point. Then the product (2, 5) × [−1, 1] is a properly embedded annulus in the product that meets the torus knot once, and the unknots in slopes $\frac{2} {5}$ and $\frac{5} {2}$, respectively. Moreover, the twisting needed to construct T(7, 17, 6) can be performed in the complement of this annulus. Drill out the twisted torus knot. The annulus is punctured once (with slope $\infty = \frac{1} {0}$ on the knot) and becomes an essential pair of pants P in the link exterior.

Let B ⊂ X(L) be a properly embedded Möbius band with its boundary in the knotted component and that meets P in the minimal number of components. Because both surfaces are essential, the intersection consists of a collection of arcs that are essential in both surfaces.

In fact, there is only a single arc of intersection: if there were two or more, then there would be a pair of arcs that are parallel and adjacent on P and that are also parallel on B. Then the union B ^′ = R _P ∪ R _B , where R _P and R _B are the rectangles the arcs bound in P and R, respectively, is a Möbius band (see for example [28]) that can be isotoped to meet P in a single arc.

However, it is also impossible for P ∩ B to consist of a single arc: this implies that the Möbius band has slope $\frac{n} {2}$ for some n as it meets the meridian $\frac{1} {0}$ twice. But, any $\frac{n} {2}$ curve also bounds a Möbius band in the solid torus that is attached to perform the meridional (S ³) filling on the knotted component. The union of the B and the Möbius band in the solid torus is a Klein bottle embedded in S ³, a contradiction. □

Finally, for not blocks we want a manifold for which no minimal genus Heegaard surface splits its two boundary components. Note that X(L) is almost what we want; no minimal Heegaard surface splits the two unknotted boundary components. Nonetheless, there is an inconvenient third boundary component (the knotted one). Can we get rid of it?

There are many results that demonstrate that after a “sufficiently large” Dehn filling, the filled manifold inherits the qualities of the unfilled manifold. Fortunately, that is also true for Heegaard structure [22, 25, 28–30] and that is precisely what we use here:

Lemma 4.10 (not)

Let L ⊂ S ³ be the link indicated in Fig.  9 , and let X(L; γ) be the manifold obtained by Dehn filling the knotted component along the slope γ. If $d_{\mathbb{F}}(\gamma,\infty )> 10$ , where $d_{\mathbb{F}}$ is the distance in the Farey graph, then

• (1) X(L; γ) has Heegaard genus two,

• (2) every genus two Heegaard splitting of X(L; γ) induces the trivial boundary bipartition {U ₀, U ₁ | ∅}.

Proof

Heegaard surfaces survive Dehn fillings. That is, after filling any slope γ, a Heegaard surface for X(L) is also a Heegaard surface for X(L; γ). Thus the genus of X(L; γ) is at most 2.

We now show that under the hypothesis $d_{\mathbb{F}}(\gamma,\infty )> 10$, every genus two Heegaard splitting of X(L; γ) is isotopic (in X(L; γ)) to a Heegaard splitting of X(L). It will follow that the genus of X(L; γ) is exactly two, and any genus two splitting induces the desired bipartition of boundary components.

We will say that a filled manifold X(L; α) has a new Heegaard surface if there is a Heegaard surface $\Sigma \subset X(L;\alpha )$ for the filled manifold that is not isotopic in X(L; α) to a Heegaard surface for X(L). Rieck and Sedgwick [30] have shown that there are two possibilities for a new Heegaard surface $\Sigma$, depending on whether the core of the attached solid torus is isotopic into $\Sigma$ in the filled manifold. In either case, we can find a useful derived surface $\Sigma ^{{\prime}}\subset X(L)$ by isotoping $\Sigma$ in X(L; α) and then drilling out the core: if the attached core is not isotopic into $\Sigma$, then $\Sigma$ is isotopic to a “thick level” in some thin presentation of the core, which is a knot in X(L; α). After drilling out the core, we obtain a properly embedded surface $\Sigma \subset X(L)$ that meets the knotted boundary component in curves of slope α. If the core is isotopic into $\Sigma$, then drilling out the core and possibly compressing, we obtain a properly embedded essential surface $\Sigma ^{{\prime}}\subset X(L)$. Its genus is at most that of $\Sigma$ and its boundary curves meet the knotted boundary component in a slope α ^′, where $d_{\mathbb{F}}(\alpha ^{{\prime}},\alpha ) = 1$.

If two different filled manifolds X(L; α) and X(L; β) have new Heegaard surfaces, then the pair of bounded surfaces derived above, each either essential or “thick,” can be isotoped to intersect essentially [8, 28]. Moreover, the previous lemma shows that there is no Möbius band in X(L) with its boundary in the knotted component. In that case Rieck showed that the number of intersections between the slopes α and β is bounded by a quadratic function, 36g ₁ g ₂ + 36g ₁ + 18g ₂ + 18, where g ₁ and g ₂, g ₁ ≥ g ₂, are the genera of the derived surfaces ([28] Theorem 5.2). (Theorem 5.2 is stated with a stronger hypothesis, that X(L) is a-cylindrical, but the proof clearly states that either the bound holds or there is a Möbius band meeting the boundary component that was filled.)

Now, we know that the manifold X(L, ∞) is the product T ² × [−1, 1] and thus has a new Heegaard surface of genus 1. (As the knotted component is not a torus knot, in this case the derived surface is a thick level with genus 1 and slope ∞.)

Suppose then that X(L, γ) has a new Heegaard surface of genus at most 2. Then the slopes of the derived surfaces intersect at most 180 times (applying the above quadratic function with g ₁ = 2 ≥ g ₂ = 1) and thus have distance in the Farey graph $d_{\mathbb{F}}\leq \log _{2}180 + 1 <9$. As the derived surface in X(L, γ) has distance 0 or 1 from γ, we have $d_{\mathbb{F}}(\gamma,\infty ) <10$, a contradiction.

It follows that X(L, γ) has no new Heegaard surfaces with genus at most 2. Then the genus of X(L, γ) is 2. Moreover, every genus two Heegaard surface of X(L, γ) is isotopic in X(L, γ) to a Heegaard surface for X(L), and in particular induces the boundary bipartition {U ₀, U ₁ | ∅}. This completes the proof. □

Construct the not blocks by using Lemmas 4.6 and 4.10 to glue the triangulated twisted torus link exterior to a one-tetrahedron solid torus (see for example, [13]) so that μ, the curve bounding a meridional disk of the solid torus, and ∞ the meridian of the twisted torus link, satisfy $d_{\mathbb{F}}(\mu,\infty )> 11$.

4.4 Proof of Proposition 4.1

Proof

The manifold M _Q is obtained by gluing a collection of blocks along pairs of torus boundary components via high distance maps. There is exactly one block for each term (var, and, or, not) in Q, plus the end block, for a total of | Q | + 1 blocks.

As a preprocessing step, we triangulate each of the block types so that each torus boundary component has a one-vertex triangulation. For each of the three link exteriors, use the method Weeks describes in [38] and implements in his SnapPea program, to convert the link diagrams given by Figs. 8 and 9 to ideal triangulations of the link exteriors. Then construct a (non-ideal) triangulation by subdividing and deleting tetrahedra meeting the ideal vertex. Use Jaco and Rubinstein’s method to convert this triangulation to a 0-efficient triangulation [11], which has the desired property that it restricts to a one-vertex triangulation of each torus boundary component. For each torus boundary component of each block, use normal surface theory to identify, among essential surfaces meeting the boundary component, a surface maximizing Euler characteristic.

Let T be the maximal number of tetrahedra used by one of the four triangulated blocks types. Since there are | Q | + 1 blocks, we thus require at most T( | Q | + 1) tetrahedra before gluing.

There is a computable constant K, depending only on the homeomorphism types of the blocks, so that if any set of blocks are glued with maps of distance at least Kg (relative to the boundaries), then any Heegaard surface whose genus is at most g is an amalgamation of splittings of the blocks. (The proof of this is given in the appendix; distance is measured between the surfaces chosen above.) As we want to guarantee that any splitting of genus at most | Q | + 2 is an amalgamation, it is thus sufficient to glue each pair of blocks with a map of distance K( | Q | + 2), which by Lemma 4.6 requires 2K( | Q | + 2) tetrahedra per gluing. Since each of the | Q | + 1 blocks has at most 3 boundary components, there are at most $\frac{3} {2}(\vert Q\vert + 1)$ pairs of boundary components to glue. We conclude that we need at most $\frac{3} {2}(\vert Q\vert + 1)2K(\vert Q\vert + 2)$ tetrahedra to glue the blocks.

The total number of tetrahedra required to construct M _Q is then the sum of those for the blocks and those for gluings,

$$\displaystyle{t(M_{Q}) \leq T(\vert Q\vert + 1) + 3K(\vert Q\vert + 1)(\vert Q\vert + 2)}$$

which is clearly quadratically bounded in | Q |. □

5 Open Questions

We now discuss some questions that remain. The most obvious is:

Question 5.1

Is Heegaard Genus ≤ g in NP?

Next, since the 3-sphere is, by definition, the 3-manifold with genus 0, 3-Sphere Recognition is precisely Heegaard Genus ≤ 0, i.e., a special case of our general problem with fixed parameter g = 0. Schleimer showed that 3-Sphere Recognition is in NP [34]. And, using Kuperberg’s work [17], Zentner showed that 3-Sphere Recognition is also in co-NP if we assume that the Generalized Riemann Hypothesis is true [39]. Thus, without disproving a major conjecture, we do not expect the special case Heegaard Genus ≤ 0 to be NP-hard. Since Heegaard genus is such an important invariant, it is worth asking about the complexity of the problem for other small fixed values of g, in particular g ≤ 2:

Question 5.2

What is the computational complexity of deciding Heegaard Genus ≤ 1 and Heegaard Genus ≤ 2?

Finally, note that our construction produces non-hyperbolic manifolds because the identified torus boundary components are incompressible after gluing. It seems probable that hyperbolic examples can be constructed by gluing together hyperbolic block manifolds that have higher genus boundary components. But, the resulting manifolds would most definitely be Haken (have embedded incompressible surfaces). Do embedded essential surfaces explain NP-hardness or,

Question 5.3

Is Heegaard Genus ≤ g NP-hard when restricted to the class of non-Haken manifolds?

Appendix: Sufficiently Complicated Amalgamations

In this section we provide a proof of the following proposition, based on several well-known results.

Proposition 1

There is a computable constant K, depending only on the homeomorphism types of the blocks, so that if any set of blocks are glued with maps of distance at least Kg (in the sense of Theorem  2 below), then any Heegaard surface whose genus is at most g is an amalgamation of splittings of the blocks.

Proof

Suppose H is a minimal genus Heegaard splitting of M _Q . It follows from the results of [33] that there is a DAG $\Gamma$ such that H is an amalgamation of some generalized Heegaard splitting $\bigcup _{x\in \Gamma }M_{x}$ of M _Q , such that for each $x \in \Gamma$, V _x ∩ W _x is strongly irreducible in M _x , and for each x ≠ y, V _x ∩ W _y is a (possibly empty) incompressible surface in M. In the parlance of [2], both kinds of surfaces are topologically minimal in M. Let $\mathbb{H}$ denote the union of all such topologically minimal surfaces.

For each boundary component F of each block used in the original construction of M _Q (see Sect. 3), choose a maximal Euler characteristic, properly embedded, incompressible, boundary incompressible surface in that block that is incident to F. Let $\mathbb{S}$ be the collection of these chosen surfaces. (Note that the surfaces in $\mathbb{S}$ need not be disjoint in each block).

Let M ₋ and M ₊ denote blocks used in the construction of M _Q , such that M ₊ ∩ M ₋ ≠ ∅. Let F be a component of M ₊ ∩ M ₋. Then F can be identified with boundary components F ₋ ⊂ ∂M ₋ and F ₊ ⊂ ∂M ₊. Let ϕ: F ₋ → F ₊ denote the gluing map used to attach M ₋ to M ₊ along F in the construction of M _Q . Let M _ϕ denote the manifold obtained from M ₋ and M ₊ by gluing F ₋ to F ₊ via the map ϕ. Note that M _ϕ may be different from M ₋∪ M ₊, as the latter manifold may be obtained from M ₋ and M ₊ by gluing along multiple surfaces. However, if $\mathbb{F}$ denotes the collection of surfaces at the interfaces between all blocks in M _Q , then M _ϕ can be identified with a component of the complement of $\mathbb{F}\setminus F$.

By [4], we can isotope each surface in $\mathbb{H}$ so that it meets the complementary pieces of $\mathbb{F}\setminus F$ in a collection of surfaces that are topologically minimal (in particular, either incompressible or strongly irreducible). After such an isotopy, let H ^′ denote a component of the intersection of such a surface with M _ϕ .

The first author, building on work of Tao Li [19], proved the following theorem, restated here with notation consistent with that of the present paper:

Theorem 2 (cf. [3], Theorem 5.4.)

Let S ₋ and S ₊ denote the surfaces in $\mathbb{S}$ chosen to meet F ₋ and F ₊ in M ₋ and M ₊ . Let K = 24(1 − 3χ(S ₋) − 3χ(S ₊)). If

$$\displaystyle{d(\phi (S_{-} \cap F_{-}),S_{+} \cap F_{+}) \geq K \cdot \mathit{\mbox{ genus}}(H)}$$

then H ^′ can be isotoped to be disjoint from F in M _ϕ . ¹

Note that H ^′ is a component of $\mathbb{H} \cap M_{\phi }$. Applying this Theorem to every such component (noting that genus(H ^′) ≤ genus (H)), we conclude $\mathbb{H}$ can be isotoped to be disjoint from F in M _Q . Each surface in the resulting collection is now topologically minimal in M _Q − F. Repeating this argument for every surface in $\mathbb{F}$ shows that every surface in $\mathbb{H}$ can be isotoped entirely into some block. It then follows from standard arguments that each surface of $\mathbb{F}$ can be identified with a component of ∂M _x , for some $x \in \Gamma$. Thus, for each block B in M _Q , there is a collection of vertices $\mathbb{V}$ of $\Gamma$ such that $B =\bigcup _{x\in \mathbb{V}}M_{x}$. Amalgamating this generalized Heegaard splitting of B then produces a Heegaard splitting of B. Our original Heegaard surface H is then an amalgamation of these Heegaard surfaces of the blocks. □