Université Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016 Paris,
Francevirginia.ardevol-
martinez@dauphine.psl.euhttps://orcid.org/0000-0002-3703-2335 Department of
Computer Science, University of Verona,
Italyromeo.rizzi@univr.ithttps://orcid.org/0000-0002-2387-0952 Université
Paris-Dauphine, PSL University, CNRS, LAMSADE, 75016 Paris,
Franceflorian.sikora@dauphine.frhttps://orcid.org/0000-0003-2670-6258 LIGM,
CNRS, Univ Gustave Eiffel, F77454 Marne-la-Vallée, France
stephane.vialette@univ-eiffel.frhttps://orcid.org/0000-0003-2308-6970 Virginia
Ardévol Martínez, Romeo Rizzi, Florian Sikora, Stéphane Vialette [500]Theory
of computation Problems, reductions and completeness [500]Mathematics of
computing Graph theory

###### Acknowledgements.

Part of this work was conducted when RR was an invited professor at Université
Paris-Dauphine. This work was partially supported by the ANR project
ANR-21-CE48-0022 (“S-EX-AP-PE-AL”). Satoru Iwata and Naonori Kakimura 2 34th
International Symposium on Algorithms and Computation (ISAAC 2023) ISAAC 2023
ISAAC 2023 December 3-6, 2023 Kyoto, Japan 283 50

# Recognizing unit multiple intervals is hard

Virginia Ardévol Martínez  Romeo Rizzi  Florian Sikora  Stéphane Vialette

###### Abstract

Multiple interval graphs are a well-known generalization of interval graphs
introduced in the 1970s to deal with situations arising naturally in
scheduling and allocation. A $d$-interval is the union of $d$ intervals on the
real line, and a graph is a $d$-interval graph if it is the intersection graph
of $d$-intervals. In particular, it is a unit $d$-interval graph if it admits
a $d$-interval representation where every interval has unit length.

Whereas it has been known for a long time that recognizing 2-interval graphs
and other related classes such as 2-track interval graphs is -complete, the
complexity of recognizing unit 2-interval graphs remains open. Here, we settle
this question by proving that the recognition of unit 2-interval graphs is
also -complete. Our proof technique uses a completely different approach from
the other hardness results of recognizing related classes. Furthermore, we
extend the result for unit $d$-interval graphs for any $d\geqslant 2$, which
does not follow directly in graph recognition problems –as an example, it took
almost 20 years to close the gap between $d=2$ and $d>2$ for the recognition
of $d$-track interval graphs. Our result has several implications, including
that recognizing $(x,\dots,x)$ $d$-interval graphs and depth $r$ unit
2-interval graphs is -complete for every $x\geqslant 11$ and every $r\geqslant
4$.

###### keywords:

Interval graphs, unit multiple interval graphs, recognition, NP-hardness

###### category:

##  1 Introduction

_Interval graphs_ are undirected graphs formed from a set of intervals on the
real line, with a vertex for each interval and an edge between vertices whose
intervals intersect. In particular, they are chordal and perfect graphs. Due
to its numerous applications the class of interval graphs is one of the most
well-studied classes of graphs [roberts1978graph, Fishburn1985,
mckee1999topics]. These include DNA mapping [zhang1994algorithm], resource
allocation problems in scheduling theory [bar2001unified] and ecological niche
and food web [10.2307/j.ctvx5wc04].

The practical applications of interval graphs have led to the study of various
generalizations, including multiple interval graphs [mcguigan1977presentation,
DBLP:journals/jgt/TrotterH79, DBLP:journals/siammax/GriggsW80]. A graph is a
$d$-interval graph if each vertex is associated with a $d$-interval (the union
of $d$ disjoint intervals on the real line) instead of a simple interval, and
again, there is an edge between two vertices if and only if the corresponding
$d$-intervals overlap at some point of the real line. This generalization
enables us to model more complex situation arising naturally in scheduling and
allocation problems, such as multi-task scheduling, allocation of multiple
associated linear resources, or transmission of continuous-media data [Bar-
Yehuda2006]. Applications to bioinformatics, namely to model DNA sequence
similarity or RNA secondary structure [Joseph1992, Vialette2004], increased
the interest in this class of graphs.

Inside the class of multiple interval graphs, different restrictions have been
studied. One of the most natural ones is the subclass of unit $d$-interval
graphs, which corresponds to $d$-interval graphs that have an interval
representation where every interval has unit length. Unit multiple intervals
can be applied, for example, to model tasks of the same duration in
scheduling.

Apart from their concrete applications, another reason why interval graphs
have been widely studied in the literature is because many problems that are
-hard in general graphs become polynomial-time solvable when restricted to
interval graphs: colorability, clique, independent set, or Hamiltonian cycle,
to name a few. In particular, recognizing interval graphs is also polynomial,
and more precisely, it can be done in linear time [Booth1976,
corneil2010lbfs]. Furthermore, there exist multiple characterizations of
interval graphs, including a characterization in terms of forbidden induced
subgraphs [lekkeikerker1962representation]. This is also the case for unit
interval graphs [zbMATH03307330], which are exactly graphs that do not contain
any claw, tent, net, or induced cycle of length at least 4. Unit interval
graphs are also characterized as interval graphs that are claw-free
[roberts1978graph].

However, for multiple interval graphs, most problems remain hard, even their
recognition, and they do not have any simple characterization. In particular,
they are neither chordal graphs nor perfect graphs. It is known that Maximum
Clique remains $\NP$-complete in multiple interval graphs, even for unit
2-intervals [DBLP:journals/algorithmica/Francis0O15], and so do other problems
such as Independent Set or Dominating Set [Bar-Yehuda2006, Butman2010]. The
parameterized complexity of some of these problems in multiple interval graphs
has also been studied, see for instance [DBLP:journals/algorithmica/Jiang13,
Fellows2009]. With respect to the recognition of multiple interval graphs, it
was proven to be $\NP$-hard in 1984 [West1984]. More precisely, West and
Shmoys showed that determining whether the interval number of a graph (i.e.,
the smallest integer $d$ such that the graph has a disjoint $d$-interval
representation) is smaller or equal to $d$, for any $d\geqslant 2$, is
$\NP$-complete. Furthermore, they also proved that for any $r\geqslant 3$ and
any $d\geqslant 2$, determining whether a graph has an $r$-depth $d$-interval
representation (i.e., a $d$-interval representation with at most $r$ intervals
sharing a common point) is $\NP$-complete. On the other hand, the complexity
of recognizing depth 2 $d$-interval graphs is still open, although it is known
to be polynomial for depth 2 unit $d$-interval graphs
[DBLP:journals/algorithmica/Jiang13]. The above-mentioned proof of hardness
(for unrestricted depth) was then adapted by Gambette and Vialette for
balanced $2$-intervals [Gambette2007], which are 2-interval graphs that admit
a representation such that every 2-interval is composed of two intervals of
the same length, while intervals of different 2-intervals can have different
lengths. In the same paper, the authors also initiate the study of the
recognition of unit 2-interval graphs and of $(x,x)$ 2-interval graphs (where
the two disjoint open intervals have integer endpoints and have length $x$),
but the complexity of both problems remained unsettled. Note that contrary to
the previous characterization by Roberts of unit interval graphs, unit
2-interval graphs _cannot_ be characterized as $K_{1,5}$-free 2-interval
graphs [alexandre].

Another well-studied generalization of interval graphs are $d$-track interval
graphs, where each vertex is associated to the _union_ of $d$ disjoint
intervals, each in a different parallel line called _track_. Gyárfás and West
proved that their recognition is -hard for $d=2$, and conjectured the same for
$d\geqslant 3$ [gyarfas1995multitrack]. This conjecture was proven way later
in [DBLP:journals/algorithmica/Jiang13] by Jiang, who also showed that
recognition remains hard for unit $d$-track interval graphs for any
$d\geqslant 2$, but left the recognition of unit $d$-interval graphs as an
open question.

Multiple track interval graphs can be seen as the union of interval graphs. In
the same manner, $d$-boxicity graphs can be seen as the _intersection_ of
interval graphs. Boxicity is a graph invariant introduced by Roberts
[roberts1969recent] and it is the minimum dimension in which a graph can be
represented as the intersection graph of boxes. Furthermore, given a graph
$G=(V,E)$, it corresponds to the minimum number of interval graphs on the set
of vertices $V$ such that the intersection of their edge sets is $G$. Their
recognition is $\NP$-complete [cozzens1982higher, yannakakis1982complexity],
even for $d=2$ [KRATOCHVIL1994233].

In this paper, we finally settle the complexity of the recognition of unit
2-interval graphs, answering the open question by Jiang
[DBLP:journals/algorithmica/Jiang13]. To do so, we prove that it is -hard by
reducing from Satisfiability instead of Hamiltonian Path, which has been often
used for proving the hardness of the recognition of variants of interval
graphs. The reductions from Hamiltonian path in triangle-free cubic graphs
used previously to prove the hardness of recognizing $d$-interval graphs,
balanced $d$-interval graphs and $d$-track interval graphs all use a special
vertex which is adjacent to $n$ vertices of a triangle free graph, and
therefore, cannot be directly adapted for unit $2$-interval graphs. We then
extend the hardness result for unit $d$-interval graphs, for any $d\geqslant
2$. Note that, as pointed out in the concluding remarks of
[DBLP:journals/algorithmica/Jiang13], recognition problems are very different
from optimization problems, and the boundary of a graph class is not
necessarily harder than that of a subclass111As an example, the class of
$K_{1,5}$-free graphs, which admits a brute-force $\mathcal{O}(n^{6})$ time
recognition algorithm, contains the class of unit 2-track interval graphs,
which is -hard to recognize [DBLP:journals/algorithmica/Jiang13].. Thus, even
though one would expect the recognition of unit $d$-interval graphs to be hard
for any $d$ if it’s hard for $d=2$, it is not directly implied.

Our result has several consequences, namely that recognizing $(x,\dots,x)$
$d$-interval graphs and depth $r$ unit $d$-interval graphs is -complete for
every $x\geqslant 11$ and every $r\geqslant 4$. Finally, our reduction implies
as well a lower bound under the ETH.

#### Structure of the paper.

The paper is organized as follows. Section 2 briefly introduces the necessary
concepts and definitions. In Section 3, we present the results of the paper.
First, in subsection 3.1, we prove that a generalization of the recognition of
unit 2-intervals, Colored unit 2-interval recognition, is -complete. Then, we
use this result in subsection 3.2 to prove the main theorem of the paper,
which states the -completeness of Unit 2-interval recognition. Finally, we
present several implications of our result in subsection 3.3, namely the
-completeness of recognizing unit $d$-interval graphs for every $d\geqslant
2$, and of recognizing $(x,\dots,x)$ $d$-interval graphs and depth $r$ unit
$d$-interval graphs for every $x\geqslant 11$ and every $r\geqslant 4$. We
conclude with some directions for future work in section 4.

##  2 Definitions

An _interval_ is a set of real numbers of the form
$[a,b]:=\\{x\in\mathbb{R}\mid a\leqslant x\leqslant b\\}$.222In the
literature, it is not always specified whether the intervals considered for
the intersection representation of interval graphs are open or closed. As
discussed in [rautenbach2013unit], the reason for this might be that both
definitions lead to the same class of finite graphs [frankl1987open], even for
unit interval graphs. However, note that if we allow the use of both open and
closed intervals within one representation, then the class of unit interval
graphs obtained is not the same as if we only allowed open or closed intervals
within one representation [rautenbach2013unit].

A _$d$ -interval_ is the union of $d$ disjoint intervals. A $d$-interval is
_balanced_ if all its $d$ intervals have the same length, and _unit_ when this
common length is $1$. A family $\mathcal{F}$ of $d$-intervals is _balanced_
(resp., _unit_) if it comprises only balanced (resp., unit) $d$-intervals.
Notice that, for $d\geqslant 2$, different $d$-intervals of a same balanced
family may comprise $1$-intervals with different lengths. A family
$\mathcal{F}$ of $d$-intervals can be used as a representation of the graph
$\Omega\,(\mathcal{F}\,)$ having the $d$-intervals of $\mathcal{F}$ as its
vertex set, and where two $d$-intervals are adjacent if and only if their
intersection is not empty. A graph $G$ is called a (possibly balanced, unit)
_$d$ -interval graph_ when it admits a representation $\mathcal{F}$ consisting
only of (respectively balanced, unit) $d$-intervals. Notice that the
representing family is not unique (in fact, even only by translating all
intervals by a same value, we already obtain an infinite number of them).
Multiple interval graphs generalize the standard notion of interval graphs
(special case for $d=1$). In this paper, we will use the term _unit
1-interval_ (resp. _unit 1-interval graph_) to denote a classical unit
interval (resp. a classical unit interval graph), to avoid confusion with a
unit 2-interval (resp. unit 2-interval graphs).

Note that many references do not specify whether the intervals of a
$d$-interval must be disjoint or not, and some even define them as the union
of $d$ not necessarily disjoint intervals [DBLP:journals/jgt/TrotterH79].
However, this might be related to the fact that, when there are no
restrictions on the length of the intervals, the two definitions lead to the
same class of graphs. This is not true for unit $d$-intervals, so we study the
case where disjointness is required, as in the hardness proof of recognizing
multiple interval graphs [West1984].

A $d$-interval graph is _proper_ when it admits a representing family
$\mathcal{F}$ such that no $1$-interval is properly contained in another one.
The classes of proper and unit $1$-interval graphs are equivalent, and they
correspond exactly to $K_{1,3}$-free interval graphs. The graph $K_{1,3}$ is
the star with 3 leaves, and is also called a _claw_. Equivalently, unit
interval graphs are known to be exactly those graphs that do not contain any
claw, tent, net, or cycle of length at least 4 as an induced subgraph
[zbMATH03307330].

A $d$-interval is a $(x_{1},\dots,x_{d})$ $d$-interval if the $d$ disjoint
intervals are open, have integer endpoints, and have lengths
$x_{1},\dots,x_{d}$, respectively.

The _depth_ of a family of intervals is the maximum number of intervals that
share a common point, and the _representation depth_ of a $d$-interval graph
is the minimum depth of any $d$-interval representation of the graph.

The hierarchy of subclasses of $d$-interval graphs is as follows
[Gambette2007, DBLP:journals/algorithmica/Jiang13]:
$(x,\dots,x)\subset(x+1,\dots,x+1)\subset\textit{unit}\subset\textit{balanced}\subset\textit{unrestricted}$.

The problem Unit 2-interval recognition is defined as follows.

Unit 2-interval recognition
Input: A graph $G=(V,E)$
Task: Decide whether $G$ has a unit 2-interval representation.

Furthermore, we define a more general version of the above problem, which will
be useful to prove the hardness of Unit 2-interval recognition.

Colored unit 2-interval recognition
Input: A graph $G=(V,E)$ and a coloring
$\gamma:V\to\\{\texttt{white},\texttt{black}\\}$.
Task: Decide whether $G$ has a unit 2-interval representation where: • each
white vertex is represented by a unit 2-interval, • each black vertex is
represented by a unit 1-interval. We refer to this representation as a
_colored unit 2-interval representation_.

##  3 Hardness of recognizing unit multiple interval graphs

In this section, we prove the main result of this paper, which is the hardness
of recognizing unit 2-interval graphs, used later on to prove the hardness of
recognizing unit $d$-intervals for every $d\geqslant 2$. The result for $d=2$
is obtained in two steps. We first prove that the more general version Colored
unit 2-interval representation is -complete, and then reduce this problem to
Unit 2-interval recognition, which yields the main result of this paper.

###  3.1 Hardness of Colored Unit 2-Interval Recognition

Before proceeding to the hardness proof of Colored unit 2-interval
recognition, we first introduce the variant of SAT that we will reduce from.
In the following, we use the term “$j$-clause” to refer to a clause that
contains exactly $j$ literals.

######  Lemma axp@fw@ri ([DBLP:journals/algorithmica/FellowsKMP95]).

($\star$) Satisfiability is -complete even when restricted to CNF-formulae
such that:

  1. 1.

Every clause contains either $3$ literals ($3$-clause) or $2$ literals
($2$-clause).

  2. 2.

Each variable appears in exactly one $3$-clause.

  3. 3.

Each $3$-clause is positive monotone, i.e., is comprised of three positive
literals.

  4. 4.

Each variable occurs exactly in three clauses, once negated and twice
positive.

We can now proceed to the proof of hardness of Colored Unit $2$-Interval
Recognition.

######  Theorem 3.1.

Colored Unit $2$-Interval Recognition is -complete, even for graphs of degree
at most 6.

The rest of the subsection is dedicated to the proof of Theorem 3.1. We first
describe the construction used for the reduction and then prove its
correctness.

#### Construction

Let $\Psi$ be an instance of the variant of SAT described in subsection 3.1,
formed by a set of Boolean variables $x_{1},\dots,x_{n}$ and a set of clauses
$C_{1},\dots,C_{m}$. We construct an equivalent instance
$(G_{\Psi},\gamma_{\Psi})$ of Colored unit 2-interval recognition as follows.

For every variable $x_{i}$, we introduce the variable gadget $\hat{V_{i}}$
(truth setting component), which is the vertex-colored graph on three black
vertices $A_{i}$, $B_{i}$, $C_{i}$ and three white vertices $x_{i}^{1}$,
$x_{i}^{2}$ and $x_{i}^{N}$, with all edges between a black vertex and a white
vertex, plus the edges $(x_{i}^{1},x_{i}^{2})$, $(C_{i},A_{i})$ and
$(C_{i},B_{i})$. We anticipate that the white vertices of $\hat{V_{i}}$ will
be adjacent also to vertices outside $\hat{V_{i}}$; in order to underline this
distinction, these three vertices are called _public_ , and the black vertices
are called _private_.

$A_{i}$$B_{i}$$C_{i}$$x_{i}^{1}$$x_{i}^{2}$$x_{i}^{N}$ Figure 1: Variable
gadget $\hat{V_{i}}$ corresponding to a variable $x_{i}$. Black vertices are
displayed with a black background.
$A_{i}$$B_{i}$$C_{i}$$x_{i}^{1}$$x_{i}^{2}$$x_{i}^{N}$$A_{j}$$B_{j}$$C_{j}$$x_{j}^{1}$$x_{j}^{2}$$x_{j}^{N}$$A_{k}$$B_{k}$$C_{k}$$x_{k}^{1}$$x_{k}^{2}$$x_{k}^{N}$
Figure 2: Clause gadget $\hat{C_{\alpha}}$ associated to a 3-clause
$C_{\alpha}=(x_{i}\vee x_{j}\vee x_{k})$. Note that in the final graph, each
vertex $x_{i}^{m},x_{j}^{m},x_{k}^{m}$, for every $m\in\\{1,2,N\\}$, will be
incident to exactly 2 edges linking them to vertices outside their variable
gadget.

Figure 1 illustrates the variable gadget $\hat{V_{i}}$. Notice that the three
white node $x_{i}^{1},x_{i}^{2},x_{i}^{N}$ correspond each to precisely one of
the occurrences of the represented variable $x_{i}$: vertex $x_{i}^{N}$
represents the negated occurrence of $x_{i}$, vertex $x_{i}^{1}$ represents
the positive occurrence in a 3-clause, and vertex $x_{i}^{2}$ represent the
positive occurrence in a 2-clause. Therefore, we refer to them as _literal
vertices_. Furthermore, note that a vertex of $\hat{V_{i}}$ is adjacent to
$A_{i}$ if and only if it is adjacent to $B_{i}$; and being private, these two
nodes will remain false twins also in $G$. We will exploit this symmetry to
simplify the case analysis.

To conclude the construction, we show how to encode each clause $C_{\alpha}$,
for $\alpha=1,\ldots,m$. If $C_{\alpha}$ is a $3$-clause, then it is monotone
positive, i.e., $C_{\alpha}=(x_{i}\vee x_{j}\vee x_{k})$ for some
$i,j,k\in\\{1,\ldots,n\\}$, and all that is needed is to introduce the three
edges $(x_{i}^{1},x_{j}^{1})$, $(x_{j}^{1},x_{k}^{1})$,
$(x_{k}^{1},x_{i}^{1})$. These three edges comprise the clause gadget (see
Figure 2).

If $C_{\alpha}$ is a 2-clause, say $C_{\alpha}=(x_{i}^{r}\vee x_{j}^{s})$ with
$i,j\in\\{1,\ldots,n\\}$ and $r,s\in\\{2,N\\}$, then we introduce a public
black vertex $L_{i,j}^{\alpha}$ with a private black neighbor
$p_{i,j}^{\alpha}$ and we add the four edges $(x_{i}^{r},x_{j}^{s})$,
$(x_{i}^{r},L_{i,j}^{\alpha})$, $(x_{j}^{s},L_{i,j}^{\alpha})$ and
$(L_{i,j}^{\alpha},p_{i,j}^{\alpha})$. These four edges together with the two
vertices added comprise the clause gadget (see Figure 3).

$A_{i}$$B_{i}$$C_{i}$$x_{i}^{1}$$x_{i}^{2}$$x_{i}^{N}$$A_{j}$$B_{j}$$C_{j}$$x_{j}^{1}$$x_{j}^{2}$$x_{j}^{N}$$L_{i,j}^{\alpha}$$p_{i,j}^{\alpha}$
Figure 3: Gadget for a $2$-clause $\hat{C_{\alpha}}$ of the form
$C_{\alpha}=(x_{i}\vee\overline{x}_{j})$.

The description of the reduction is complete. Clearly, $G_{\Psi}$ has at most
$6n+2m$ vertices and at most $12n+4m$ edges. We next introduce a few notions
to ease the proof that $G_{\Psi}$ is a colored unit $2$-interval graph if and
only if $\Psi$ is satisfiable.

######  Definition 3.2.

Given a colored graph $(G,\gamma)$, we say that a pair $(S,f)$ formed by a
graph $S$ and a function $f:V(S)\mapsto V(G)$ is a split of $(G,\gamma)$ if
$f$ satisfies the following conditions:

  * •

$|f^{-1}(v)|=1$ for every $v\in V(G)$ with $\gamma(v)=\texttt{black}$.

  * •

$|f^{-1}(v)|=2$ for every $v\in V(G)$ with $\gamma(v)=\texttt{white}$.

  * •

For every vertex $v$ of $G$, $f^{-1}(v)$ is an independent set in $S$.

  * •

For every edge $(s,t)$ of $S$, $(f(s),f(t))$ is an edge of $G$.

  * •

For every edge $(u,v)$ of $G$, there exist two vertices $s$ and $t$ in
$f^{-1}(\\{u,v\\})$ such that $(s,t)$ is an edge of $S$.

######  Definition 3.3.

We define the family of splits of $G$ that lead to a unit 1-interval graph as
$\mathcal{S}_{\mathcal{U}}(G):=\\{(S,f)\mid(S,f)\text{ is a split of
}$G$\allowbreak\text{ and $S$ is a unit 1-interval graph}\\}$.

The next lemma shows how a split $(S,f)$ of a colored graph $G$ can be used to
certify that $G$ is a colored unit 2-interval graph. This has the advantage of
being a truly combinatorial certificate, whereas the number of interval
families representing a same graph is infinite with the power of the
continuous as soon as at least one exists. Trotter and Harary
[DBLP:journals/jgt/TrotterH79] have already studied vertex splitting in the
context of turning a graph into an interval graph.

######  Lemma 3.4.

($\star$)lemma:equivalence A colored graph $(G,\gamma)$ is a colored unit
2-interval graph if and only if the family $\mathcal{S}_{\mathcal{U}}(G)$ is
not empty.

######  Proof 3.5.

Suppose that $G$ is a colored unit $2$-interval graph with
$V=V_{\texttt{white}}\cup V_{\texttt{black}}$. Then, by assumption, there
exists a collection of unit $2$-intervals
$\mathbf{D}_{\texttt{white}}=\\{(I_{1}(v),I_{2}(v))\mid v\in
V_{\texttt{white}}\\}$ and a collection of unit intervals
$\mathbf{I}_{\texttt{black}}=\\{I_{1}(v)\mid v\in V_{\texttt{black}}\\}$ such
that
$G\simeq\Omega\left(\mathbf{D}_{\texttt{white}}\cup\mathbf{I}_{\texttt{black}}\right)$.
Let $\mathcal{F}$ be the family of 1-intervals formed by the ground set of
$\mathbf{D}_{\texttt{white}}\cup\mathbf{I}_{\texttt{black}}$. Let $S$ be the
1-interval graph defined as the intersection graph of the family
$\mathcal{F}$, i.e., $S\simeq\Omega(\mathcal{F})$. Consider the function
$f:V(S)\mapsto V(G)$ such that:

  * •

For every $I_{1}(v)\in\mathbf{D}_{\texttt{black}}$, $f(I_{1}(v))=v$.

  * •

For every pair $I_{1}(v),I_{2}(v)\in\mathbf{D}_{\texttt{white}}$,
$f(I_{1}(v))=f(I_{2}(v))=v$.

By construction, $f$ satisfies all the conditions in 3.2. Indeed, the first
three conditions follow directly by definition, while the last two conditions
follow because if we have an edge $(I_{j}(u),I_{k}(v))$ in $S$, for some
$j,k\in\\{1,2\\}$, this is equivalent to the 2-intervals associated to
vertices $u$ and $v$ of $G$ intersecting, so there is an edge $(u,v)$ in $G$.
Therefore, $(S,f)$ is a split of $(G,\gamma)$.

Conversely, suppose that there exists a split $(S,f)$ of $(G,\gamma)$ that
satisfies the property of being a unit interval graph. Then, there exists a
collection of unit intervals $\mathbf{I}=\\{I_{1}(s)\mid s\in V(S)\\}$ such
that $S\simeq\Omega\left(\mathbf{I}\right)$. Since $(S,f)$ is a split of
$(G,\gamma)$, we know that there exists a map $f:V(S)\mapsto V(G)$ satisfying
the conditions in 3.2. We construct a colored unit 2-interval representation
of $G$, i.e., a collection of unit 2-intervals
$\mathbf{D}_{\texttt{white}}=\\{(I_{1}(v),I_{2}(v))\mid v\in
V_{\texttt{white}}\\}$ and a collection of unit 1-intervals
$\mathbf{I}_{\texttt{black}}=\\{I_{1}(v)\mid v\in V_{\texttt{black}}\\}$, as
follows:

  * •

For every $v\in V(G)$ with $\gamma(v)=\texttt{black}$, we let
$I_{1}(v)=I_{1}(s)$, where $s=f^{-1}(v)$.

  * •

For every $v\in V(G)$ with $\gamma(v)=\texttt{white}$, we let
$I_{1}(v)=I_{1}(s)$ and $I_{2}(v)=I_{1}(t)$, where $\\{s,t\\}=f^{-1}(v)$.

By construction, this is a colored unit 2-interval representation of $G$, as
the last two conditions of $f$ ensure that we preserve the same edges.

We can now proceed to study the shape of the possible splits
$(S,f)\in\mathcal{S}_{\mathcal{U}}(G_{\Psi})$. Let $(S,f)$ be a split of a
graph $G$. For every vertex $v\in V(G)$, we call each element of the set
$f^{-1}(v)$ a representative of $v$. In particular, if $v$ is a white node, we
denote its two representatives in $V(S)$ by $f^{-1}_{1}(v)$ and
$f^{-1}_{2}(v)$. For simplicity, when we refer to an arbitrary representative
of a vertex or to the unique representative of a black vertex, we abuse
notation and denote it by its label in $V(G)$. Furthermore, given an edge
$(u,v)\in G$, we call the edge $(s,t)\in S$, a representative of $(u,v)$ if
$s\in f^{-1}(u)$ and $t\in f^{-1}(v)$. Furthermore, given a split $(S,f)$ of
the graph $G_{\Psi}$, we denote by $S[\hat{V_{i}}]$ the subgraph of $S$
induced by the vertices of the variable gadget $\hat{V_{i}}$ (i.e., vertices
$A_{i},B_{i},C_{i}$, $f^{-1}_{1}(x_{i}^{N}),f^{-1}_{1}(x_{i}^{1})$,
$f^{-1}_{1}(x_{i}^{2})$, $f^{-1}_{2}(x_{i}^{N}),f^{-1}_{2}(x_{i}^{1})$ and
$f^{-1}_{2}(x_{i}^{2})$). Finally, we say that a representative of a literal
vertex is an _isolated vertex_ if it is not adjacent to any of the private
vertices of its variable gadget (i.e., it is not adjacent to $A_{i},B_{i}$ or
$C_{i}$).

######  Claim 1.

Let $(S,f)$ be an arbitrary graph in $\mathcal{S}_{\mathcal{U}}(G_{\Psi})$.
Then, none of the black vertices of $S[\hat{V_{i}}]$ can be adjacent to both
representatives of a literal vertex. Furthermore, if a black vertex is
adjacent to a representative of $x_{i}^{1}$ and to a representative of
$x_{i}^{2}$, these two representatives must be adjacent to each other.

Suppose that the two representatives of a literal vertex are adjacent to the
same black vertex. If the literal vertex is $x_{i}^{1}$ or $x_{i}^{2}$, the
black vertex would be a center of a $K_{1,3}$ with these two representatives
plus a representative of the vertex $x_{i}^{N}$ as leaves. If the literal
vertex is $x_{i}^{N}$, the black vertex would be a center of a $K_{1,3}$ with
the two representatives of $x_{i}^{N}$ and one of $x_{i}^{1}$ or $x_{i}^{2}$
as leaves. Since the graph $K_{1,3}$ is a forbidden induced subgraph for unit
1-interval graphs, this contradicts the fact that $S$ belongs to
$\mathcal{S}_{\mathcal{U}}(G_{\Psi})$. Finally, if a black vertex is adjacent
to a representative of $x_{i}^{1}$ and to a representative of $x_{i}^{2}$
which are not adjacent, the black vertex would be a center of a $K_{1,3}$ with
these two representatives plus a representative of $x_{i}^{N}$ as leaves.

######  Claim 2.

Let $(S,f)$ be an arbitrary split in $\mathcal{S}_{\mathcal{U}}(G_{\Psi})$.
Then, for every variable $x_{i}$ with $i\in\\{1,\dots,n\\}$, the subgraph
$S[\hat{V_{i}}]$ satisfies at least one of the following two conditions, up to
symmetry:

  1. 1.

The vertex $f^{-1}_{1}(x_{i}^{N})$ is adjacent to $A_{i}$ and the vertex
$f^{-1}_{2}(x_{i}^{N})$ is adjacent to $B_{i}$.

  2. 2.

The vertices $f^{-1}_{1}(x_{i}^{1})$ and $f^{-1}_{1}(x_{i}^{2})$ are adjacent
to each other and to $A_{i}$, and the vertices $f^{-1}_{2}(x_{i}^{1})$ and
$f^{-1}_{2}(x_{i}^{2})$ are adjacent to each other and to $B_{i}$.

By the properties of $f$, for every edge $(u,v)\in G_{\Psi}$, there exist
elements $s,t\in V(S)$ with $f^{-1}(u)=s$ and $f^{-1}(v)=t$ such that $(s,t)$
is an edge in $S$.

Suppose condition 1 does not hold, i.e., one of the representatives of
$x_{i}^{N}$, say $f^{-1}_{1}(x_{i}^{N})$, is adjacent to both $A_{i}$ and
$B_{i}$. We will show that if condition 2 does not hold either, $S$ cannot be
a unit 1-interval graph. Assume that one of the representatives of $x_{i}^{1}$
or $x_{i}^{2}$, say $f^{-1}_{1}(x_{i}^{1})$ (resp. $f^{-1}_{1}(x_{i}^{2})$),
is adjacent to both $A_{i}$ and $B_{i}$. Then, $S$ contains an induced cycle
of length four:
$\left(f^{-1}_{1}(x_{i}^{N}),B_{i},f^{-1}_{1}(x_{i}^{1}),A_{i}\right)$ (resp.
$\left(f^{-1}_{1}(x_{i}^{N}),B_{i},f^{-1}_{1}(x_{i}^{2}),A_{i}\right)$). This
is a forbidden induced subgraph for unit 1-interval graphs, so it contradicts
the hypothesis. Thus, it follows that, up to symmetry, vertices
$f^{-1}_{1}(x_{i}^{1})$ and $f^{-1}_{1}(x_{i}^{2})$ need to be adjacent to
$A_{i}$, and vertices $f^{-1}_{2}(x_{i}^{1})$ and $f^{-1}_{2}(x_{i}^{2})$, to
$B_{i}$. Finally, by 1, $f^{-1}_{1}(x_{i}^{1})$ and $f^{-1}_{1}(x_{i}^{2})$
need to be adjacent to each other, so condition 2 must hold.

Conversely, suppose condition 2 does not hold, i.e., at least one of the
representatives of $x_{i}^{1}$ or $x_{i}^{2}$, say $f^{-1}_{1}(x_{i}^{1})$
w.l.o.g., is adjacent to both $A_{i}$ and $B_{i}$. We will see that condition
1 must hold in order for $S$ to be a unit 1-interval graph. Indeed, if a
single representative of $x_{i}^{N}$, say $f^{-1}_{1}(x_{i}^{N})$, is adjacent
to both $A_{i}$ and $B_{i}$, then $S$ contains an induced cycle of size four:
$\left(f^{-1}_{1}(x_{i}^{N}),B_{i},f^{-1}_{1}(x_{i}^{1}),A_{i}\right)$.
Therefore, one representative of $x_{i}^{N}$ must be adjacent to $A_{i}$ and
the other, to $B_{i}$.

The previous claim implies that there are four possible configuration of
$S[\hat{V_{i}}]$ such that it does not contain any induced cycles of length
greater or equal to 4.

######  Lemma 3.6.

Let $(S,f)$ be a split of $G_{\Psi}$ such that $S[\hat{V_{i}}]$ does not
contain any induced cycles of length greater or equal to 4. Then, $S$
satisfies one of the following conditions:

  1. 1.

The vertex $f^{-1}_{1}(x_{i}^{N})$ is adjacent to $A_{i}$ and the vertex
$f^{-1}_{2}(x_{i}^{N})$ is adjacent to $B_{i}$, while for the rest of the
literal vertices, there exists an element in the image via $f^{-1}$ that is an
isolated vertex.

  2. 2.

The vertices $f^{-1}_{1}(x_{i}^{1})$ and $f^{-1}_{1}(x_{i}^{2})$ are adjacent
to each other and to $A_{i}$, and the vertices $f^{-1}_{2}(x_{i}^{1})$ and
$f^{-1}_{2}(x_{i}^{2})$ are adjacent to each other and to $B_{i}$, while
$f^{-1}(x_{i}^{N})$ contains an isolated vertex.

  3. 3.

The images of $x_{i}^{1}$ and $x_{i}^{2}$ via $f^{-1}$ are as in Case 1 and
$f^{-1}(x_{i}^{N}$) is as in Case 2 (see the graph in Figure 4).

  4. 4.

Either the image of $x_{i}^{1}$ or the image of $x_{i}^{2}$ via $f^{-1}$ is as
in Case 1 (w.l.o.g., assume it is $f^{-1}(x_{i}^{1})$) so that both
representatives of $x_{i}^{1}$ are adjacent to the non-isolated representative
of $x_{i}^{2}$; and $f^{-1}(x_{i}^{N})$ is as in Case 2.

######  Proof 3.7.

We have already shown that one of the conditions of 2 must hold. If condition
1 holds, then we have three possible configurations of $f^{-1}(x_{i}^{1})$ and
$f^{-1}(x_{i}^{2})$: either both literal vertices have a representative that
is isolated (Case 1), only one of them has a representative that is isolated
(Case 4), or none of them has an isolated representative (Case 3). On the
other hand, if condition 2 holds, the we only have two possible configurations
of $f^{-1}(x_{i}^{N})$: one representative of $x_{i}^{N}$ is isolated (Case
2), or none of them is (Case 3). Finally, note that in Case 4, both
representatives of $x_{i}^{1}$ need to be adjacent to the non-isolated
representative of $x_{i}^{2}$ by 1.

The next two claims are devoted to proving that if $(S,f)$ is a split of
$(G_{\Psi},\gamma)$ contained in the family
$\mathcal{S}_{\mathcal{U}}(G_{\Psi})$, then Cases 3 and 4 of 3.6 are not
possible. To do so, observe that by construction, since every variable appears
exactly in three clauses (twice positive and once negated), we know that in
$G_{\Psi}$, the vertices $x_{i}^{N},x_{i}^{1}$ and $x_{i}^{2}$ all have two
incident edges linking them with vertices outside of the variable gadget,
called _external edges_ in the following. The neighbors outside of the
variable gadget are _external vertices_ , and they constitute private
neighbors of the vertices of the variable gadget, as it is not possible for
two different vertices of the variable gadget to be incident to the same
external neighbor. We will see that if $S$ is as in Case 3 or Case 4, then the
vertices of $S[\hat{V_{i}}]$ create an induced net with the external
neighbors. Since nets are a forbidden induced subgraph for (unit) interval
graphs, then $S$ cannot be a unit 1-interval graph.

######  Claim 3.

Let $S$ be an arbitrary graph in $\mathcal{S}_{\mathcal{U}}(G_{\Psi})$. Then,
for every variable $x_{i}$ with $i\in\\{1,\dots,n\\}$, the subgraph
$S[\hat{V_{i}}]$ cannot be as in Case 3 of 3.6.

Suppose that $S[\hat{V_{i}}]$ is as in Case 3 of 3.6, i.e., as in Figure 4
(where $C_{i}$ could be in the neighborhood of the other representatives of
the vertices, but thanks to the symmetry, these cases are equivalent). We
distinguish two cases:

  * •

The two external edges incident to $x_{i}^{1}$ and $x_{i}^{2}$ are incident to
two representatives that are adjacent. Then, either
$f^{-1}_{1}(x_{i}^{N}),A_{i},f^{-1}_{1}(x_{i}^{1}),f^{-1}_{1}(x_{i}^{2})$, a
private neighbor of $f^{-1}_{1}(x_{i}^{1})$ and a private neighbor of
$f^{-1}_{1}(x_{i}^{2})$ form a net; or
$f^{-1}_{2}(x_{i}^{N}),B_{i},f^{-1}_{2}(x_{i}^{1}),f^{-1}_{2}(x_{i}^{2})$, a
private neighbor of $f^{-1}_{2}(x_{i}^{1})$ and a private neighbor of
$f^{-1}_{2}(x_{i}^{2})$ form a net (see the red net in Figure 4).

  * •

Otherwise, at least one of $f^{-1}_{1}(x_{i}^{1})$ or $f^{-1}_{1}(x_{i}^{2})$
will be incident to an external edge. Then,
$C_{i},A_{i},f^{-1}_{1}(x_{i}^{1})$ or $C_{i},A_{i},f^{-1}_{1}(x_{i}^{2})$
will create a net together with $B_{i},f^{-1}_{1}(x_{i}^{N})$, and the
corresponding external neighbor of $f^{-1}_{1}(x_{i}^{1})$ or
$f^{-1}_{1}(x_{i}^{2})$, respectively (see the blue net in Figure 4).

$A_{i}$$B_{i}$$C_{i}$$f^{-1}_{1}(x_{i}^{1})$$x_{l}^{1}$$f^{-1}_{1}(x_{i}^{2})$$f^{-1}_{2}(x_{i}^{1})$$x_{j}^{1}$$f^{-1}_{2}(x_{i}^{2})$$x_{k}^{1}$$f^{-1}_{1}(x_{i}^{N})$$f^{-1}_{2}(x_{i}^{N})$
Figure 4: Configuration of $S[\hat{V_{i}}]$ described in Case 3 of 3.6. In
red, the net created if both $f^{-1}_{2}(x_{i}^{1})$ and
$f^{-1}_{2}(x_{i}^{2})$ have an external neighbor. In blue, the net created if
$f^{-1}_{1}(x_{i}^{1})$ has an external neighbor.

In both cases, we have a forbidden induced subgraph for (unit) interval
graphs, contradicting the hypothesis that $S$ is a unit interval graph.

######  Claim 4.

($\star$)notcase4 Let $(S,f)$ be an arbitrary split in
$\mathcal{S}_{\mathcal{U}}(G_{\Psi})$. Then, for every variable $x_{i}$ with
$i\in\\{1,\dots,n\\}$, the subgraph $S[\hat{V_{i}}]$ cannot be as in Case 4 of
3.6.

Suppose that $S[\hat{V_{i}}]$ is as in Case 4 of 3.6, i.e., as in Figure 5. By
construction, $x_{i}^{2}$ and at least one of $f^{-1}_{1}(x_{i}^{1})$ or
$f^{-1}_{2}(x_{i}^{1})$ have an external neighbor. We distinguish two cases:

  * •

The vertex $f^{-1}_{1}(x_{i}^{1})$ has an external neighbor. Then, vertices
$A_{i},f^{-1}_{1}(x_{i}^{1}),x_{i}^{2},x_{i}^{N}$, and the external neighbors
of $x_{i}^{2}$ and $f^{-1}_{1}(x_{i}^{1})$ form a net (see the red net in
Figure 5).

  * •

The vertex $f^{-1}_{2}(x_{i}^{1})$ has an external neighbor. Then, vertices
$B_{i},f^{-1}_{2}(x_{i}^{1}),x_{i}^{2},x_{i}^{N}$, and the external neighbors
of $x_{i}^{2}$ and $f^{-1}_{2}(x_{i}^{1})$ form a net (see the blue net in
Figure 5).

$A_{i}$$B_{i}$$C_{i}$$f^{-1}_{1}(x_{i}^{1})$$x_{j}^{1}$$x_{k}^{1}$$x_{l}^{1}$$f^{-1}_{2}(x_{i}^{1})$$x_{i}^{2}$$f^{-1}_{1}(x_{i}^{N})$$f^{-1}_{2}(x_{i}^{N})$
Figure 5: Configuration of $S[\hat{V_{i}}]$ described in Case 4 of 3.6. In
red, the net created if $f^{-1}_{1}(x_{i}^{1})$ has an external neighbor, and
in blue, the net created if $f^{-1}_{2}(x_{i}^{1})$ has an external neighbor
(edge $(x_{i}^{2},x_{l}^{1})$ is part of both nets and is depicted in purple).

In both cases, we have a forbidden induced subgraph for (unit) interval
graphs, contradicting the hypothesis that $S$ is a unit interval graph.

The proof of LABEL:notcase4 uses similar arguments to that of 3 and is thus
omitted here. Recall that in Case 1 of 3.6, one of the representatives of
$x_{i}^{1}$ and one of the representatives of $x_{i}^{2}$ are isolated; and in
Case 2 of 3.6, one of the representatives of $x_{i}^{N}$ is isolated.
Therefore, we obtain the following result.

######  Claim 5.

Let $(S,f)$ be an arbitrary split in the family
$\mathcal{S}_{\mathcal{U}}(G_{\Psi})$. Then, for every variable $x_{i}$ with
$i\in\\{1,\dots,n\\}$, the subgraph $S[\hat{V_{i}}]$ satisfies exactly one of
the following two conditions:

  1. 1.

There is a representative of $x_{i}^{1}$ and a representative of $x_{i}^{2}$
that are isolated vertices (they are either two non-adjacent vertices or they
form a $K_{2}$).

  2. 2.

One of the representatives of $x_{i}^{N}$ is an isolated vertex.

Combining 3.6 with Claims 3 and LABEL:notcase4, it follows that
$S[\hat{V_{i}}]$ is either as in Case 1 or as in Case 2 of 3.6, which means
that either one representative of each of $x_{i}^{1}$ and $x_{i}^{2}$ is
isolated, or that one representative of $x_{i}^{N}$ is isolated, respectively.
These options correspond to the interval representations in 6(a) and 6(b),
respectively. The reader can check the previous assertion observing the
figures, and verify that the external edges incident to each of the vertices
$x_{i}^{1},x_{i}^{2}$ and $x_{i}^{N}$ can be added in both representations, as
we always have either a whole free interval (not depicted in the figures) or
one extreme of the interval free for each of the vertices.

$I_{1}(C_{i})$$I_{1}(A_{i})$$I_{1}(B_{i})$$I_{1}(x_{i}^{N})$$I_{2}(x_{i}^{N})$$I_{1}(x_{i}^{1})$$I_{1}(x_{i}^{2})$
(a)

$I_{1}(C_{i})$$I_{1}(A_{i})$$I_{1}(B_{i})$$I_{1}(x_{i}^{1})$$I_{2}(x_{i}^{1})$$I_{1}(x_{i}^{2})$$I_{2}(x_{i}^{2})$$I_{1}(x_{i}^{N})$
(b)

Figure 6: Representation of the variable gadget associated to the true value
(left, 6(a)) or false value (right, 6(b)).

The correctness of the reduction now follows from the two lemmas below.

######  Lemma 3.8.

If $\Psi$ is satisfiable, then the constructed graph $G_{\Psi}=(V,E)$,
$V=V_{\texttt{white}}\cup V_{\texttt{black}}$, admits a colored unit
2-interval representation.

######  Proof 3.9.

Given a satisfying assignment $\phi$ of $\Psi$, we explain how to construct a
colored unit 2-interval representation of $G_{\Psi}$, i.e., a collection of
unit $2$-intervals $\mathbf{D}_{\texttt{white}}=\\{(I_{1}(v),I_{2}(v))\mid
v\in V_{\texttt{white}}\\}$ and a collection of unit 1-intervals
$\mathbf{I}_{\texttt{black}}=\\{I_{1}(v)\mid v\in V_{\texttt{black}}\\}$ such
that
$G\simeq\Omega\left(\mathbf{D}_{\texttt{white}}\cup\mathbf{I}_{\texttt{black}}\right)$.
Note that by LABEL:lemma:equivalence, if $G_{\Psi}$ is a colored unit
2-interval graph, then there exists a split $(S,f)$ in the family
$\mathcal{S}_{\mathcal{U}}(G_{\Psi})$, and we know how to construct a colored
unit 2-interval representation of $G_{\Psi}$ given a unit 1-interval
representation of $S$ by defining the 2-interval associated to a white vertex
$v\in V_{\texttt{white}}$ as the union of the interval associated to
$f^{-1}_{1}(v)$ and the interval associated to $f^{-1}_{2}(v)$; and the
1-interval associated to a black vertex $v\in V_{\texttt{black}}$ as the
interval associated to the single vertex $f^{-1}(v)$.

For each variable $x_{i}$ with $i\in\\{1,\dots,n\\}$, if $\Phi(x_{i})=true$,
we represent the variable gadget $\hat{V_{i}}$ as shown in 6(a), which
corresponds exactly to Case 1 of 5. On the other hand, if $\Phi(x_{i})=false$,
we represent $\hat{V_{i}}$ as in 6(b), which corresponds to Case 2 of 5.
Notice that in both representations, the literals that are true have an
isolated representative, i.e., one of the intervals associated to them is
unused in the representation of $\hat{V_{i}}$ and remains completely free to
display intersections with external neighbors.

After this, it only remains to explain the connections introduced by the
clauses.

######  Claim 6.

Given a 3-clause $(x_{i}\vee x_{j}\vee x_{k})$, there exists a unit interval
representation of the subgraph of $G_{\Psi}$ induced by the vertices of the
variable gadgets $\hat{V_{i}},\hat{V_{j}}$ and $\hat{V_{k}}$.

Each of the variable gadgets can be represented as in 6(a) or 6(b). To
represent the edges associated to the 3-clauses, we first notice that, since
the 3-clauses are positive monotone, true literals correspond to true
variables. As we are assuming that we have a satisfying assignment, we only
have three cases (up to symmetry), which correspond to the three variables
being true; exactly two variables being true; and only one variable being
true. The literals that are true have a whole free interval to display the
intersection, whereas the literals that are false only have the extreme of an
interval (while the other extreme is glued to the rest of the representation
of the gadget, see 6(b)). Let $(x_{i}\vee x_{j}\vee x_{k})$ be a 3-clause,
with $i,j,k\in\\{1,\dots,n\\}$. If the three variables are true, we can easily
represent the clause by making the three free intervals of the variables –
w.l.o.g. $I_{2}(x_{i}^{1}),I_{2}(x_{j}^{1}),I_{2}(x_{k}^{1})$ – intersect at
the same time. On the other hand, if only one variable – say $x_{i}$ – is
false, we can add the two free intervals –$I_{2}(x_{j}^{1}),I_{2}(x_{k}^{1})$
– to the corresponding extreme of the gadget of the false variable, as in
Figure 7. Finally, if two variables are false – say $x_{i},x_{k}$ –, then we
need to merge the two interval representations associated to their gadgets and
add the free interval – $I_{2}(x_{j}^{1})$ – in the middle, as in Figure 8.
Note that the interval representations given in the figures are not unit, but
they are proper, so at the end we will be able to use the algorithm described
in [DBLP:journals/dm/BogartW99] to turn it into a unit one.

$I_{1}(C_{i})$$I_{1}(A_{i})$$I_{1}(B_{i})$$I_{1}(x_{i}^{1})$$I_{2}(x_{i}^{1})$$I_{1}(x_{i}^{2})$$I_{2}(x_{j}^{2})$$I_{2}(x_{k}^{1})$$I_{2}(x_{i}^{2})$$I_{1}(x_{i}^{N})$
Figure 7: Representation of a 3-clause $(x_{i}\vee x_{j}\vee x_{k})$, where
$x_{i}$ is set to false while $x_{j},x_{k}$ are set to true.
$I_{1}(C_{i})$$I_{1}(A_{i})$$I_{1}(B_{i})$$I_{1}(x_{i}^{2})$$I_{2}(x_{i}^{2})$$I_{1}(x_{i}^{1})$$I_{2}(x_{j}^{1})$$I_{2}(x_{i}^{1})$$I_{1}(x_{i}^{N})$$I_{1}(C_{k})$$I_{1}(A_{k})$$I_{1}(B_{k})$$I_{1}(x_{k}^{2})$$I_{2}(x_{k}^{2})$$I_{1}(x_{k}^{1})$$I_{2}(x_{k}^{1})$$I_{1}(x_{k}^{N})$
Figure 8: Representation of a 3-clause $(x_{i}\vee x_{j}\vee x_{k})$, where
$x_{i}$ and $x_{k}$ are set to false and $x_{j}$ is set to true.

After representing all the 3-clauses, we can assume that the representations
of some of the variable gadgets have been merged two by two (we will never
have to merge a gadget more than once since a variable occurs in exactly one
3-clause in $\Psi$) and we can fix them in the real line separated from one
another. The separation between them can be arbitrarily large, and needs to be
at least greater than the space needed to place the remaining intervals. The
variable gadgets that have not been merged can also be fixed in the real line,
while the unused free intervals (corresponding to true literals), the
intervals $I_{1}(L_{i,j}^{\alpha})$, and the intervals
$I_{1}(p_{i,j}^{\alpha})$ remain unplaced.

$I_{1}(C_{i})$$I_{1}(A_{i})$$I_{1}(B_{i})$$I_{1}(x_{i}^{2})$$I_{2}(x_{i}^{2})$$I_{1}(x_{i}^{1})$$I_{2}(x_{m}^{2})$$I_{1}(L_{m,i})$$I_{1}(p_{m,i})$$I_{2}(x_{l}^{2})$$I_{1}(L_{l,k})$$I_{1}(p_{l,k})$$I_{1}(x_{i}^{1})$$I_{2}(x_{j}^{1})$$I_{2}(x_{i}^{1})$$I_{1}(x_{i}^{N})$$I_{1}(C_{k})$$I_{1}(A_{k})$$I_{1}(B_{k})$$I_{1}(x_{k}^{2})$$I_{2}(x_{k}^{2})$$I_{1}(x_{k}^{1})$$I_{2}(x_{k}^{1})$$I_{1}(x_{k}^{N})$
Figure 9: Representation of a longest contiguous block of intervals, where
each color represents the intervals associated to a different variable. A
longest contiguous block occurs when there is a clause $(x_{i}\vee x_{j}\vee
x_{k})$, where $x_{i}$ and $x_{k}$ are set to false and both of them also
appear as positive literals in a 2-clause.

Now, to display the 2-clauses, we distinguish two cases. First, if both
literals are true, then there exists a free interval for each, and we can
represent the clause in a separate part of the real line (there is one
$L_{i,j}^{\alpha}$ and one $p_{i,j}^{\alpha}$ per clause, so these intervals
will never cause a problem). Secondly, if one of the literals is false, then
the free interval associated to the true literal needs to be glued to the
extreme of the representation of the variable gadget of the false one. Note
that there is always one free extreme because the 3-clauses use at most one
extreme per variable gadget (and we can extend $I_{j}(x_{i}^{2})$ to allow the
intersection while keeping the representation proper). Note also that we will
never need more than two extremes to obtain a representation because, since
each variable occurs twice positive and once negated, we can have at most two
false literals (when the variable is set to false).

Since we have constructed a proper interval representation, we can now use the
algorithm described in [DBLP:journals/dm/BogartW99] to turn the representation
into a unit one, as mentioned before.

Let us now prove the converse implication.

######  Lemma 3.10.

If the constructed graph $G_{\Psi}=(V,E)$, $V=V_{\texttt{white}}\cup
V_{\texttt{black}}$, admits a colored unit 2-interval representation, then the
original formula $\Psi$ is satisfiable.

######  Proof 3.11.

Assume that the constructed graph $G_{\Psi}$ admits a colored unit 2-interval
representation where black vertices are represented by unit 1-intervals and
white vertices are represented by unit 2-intervals. As in 5, we study the
splits $(S,f)\in\mathcal{S}_{\mathcal{U}}(G_{\Psi})$.

We have already seen in 5 that there are only two possible configurations for
$S[\hat{V_{i}}]$, up to symmetry. Let us assign a truth value to each of the
configurations. If $S[\hat{V_{i}}]$ satisfies condition 1 of Claim 5, we set
$\Phi(x_{i})=true$. Otherwise, if it satisfies condition 2 of Claim 5, then we
set $\Phi(x_{i})=false$. Recall that this implies that there is a
representative of the vertices representing true literals which remains
isolated from its variable gadget.

The following claims restrict the structure of a representable clause gadget.
Both use similar arguments, so only the first proof is included here. Given a
clause gadget $\hat{C_{\alpha}}$ in $G$, we define the clause gadget
$S[\hat{C_{\alpha}}]$ in $S$ as the set of representatives of the edges and
vertices of $\hat{C_{\alpha}}$.

######  Claim 7.

Let $(S,f)$ be an arbitrary split in $\mathcal{S}_{\mathcal{U}}(G_{\Psi})$.
Then, for every 3-clause, at least one of the representatives of the literal
vertices incident to the clause gadget in $S$ must be an isolated vertex.

Towards a contradiction, we assume that there exists a 3-clause gadget in $S$
such that none of the representatives of the literal vertices adjacent to the
clause gadget are isolated. Let $C_{\alpha}=x_{i}\vee x_{j}\vee x_{k}$, with
$i,j,k\in\\{1,\dots,n\\}$ be a (monotone positive) 3-clause. Each of the
literal vertices has two external neighbors. In $S$, either the two external
neighbors are incident to the same representative of the literal vertices (and
thus only one representative is incident to the clause gadget), or each of
them is incident to a different representative. We distinguish two cases,
depending on whether only one representative of each literal vertex is
incident to the clause gadget, or whether there is at least one literal vertex
such that both of its representatives are incident to the clause gadget:

  * •

If only one representative of each literal vertex is incident to the clause
gadget in $S$, then w.l.o.g., the clause gadget is formed by edges
$\\{(f^{-1}_{1}(x_{i}^{1}),f^{-1}_{1}(x_{j}^{1})),\allowbreak(f^{-1}_{1}(x_{j}^{1}),f^{-1}_{1}(x_{k}^{1})),\allowbreak(f^{-1}_{1}(x_{k}^{1}),f^{-1}_{1}(x_{i}^{1}))\\}$.
By assumption, none of the vertices incident to the clause gadget in $S$ are
isolated, so they are all connected to at least one black vertex of their
variable gadget. Thus, without loss of generality,
$\\{f^{-1}_{1}(x_{i}^{1}),f^{-1}_{1}(x_{j}^{1}),f^{-1}_{1}(x_{k}^{1}),A_{i},A_{j},A_{k}\\}$
form a net (the readers can convince themselves looking at Figure 2). Note
that when we say without loss of generality, we are using the symmetry between
$A_{i}$ and $B_{i}$.

  * •

If there is at least one literal vertex such that both of its representatives
are incident to the clause gadget, then w.l.o.g., the clause gadget in $S$
contains edges
$\\{(f^{-1}_{1}(x_{i}^{1}),f^{-1}_{1}(x_{j}^{1})),\allowbreak(f^{-1}_{1}(x_{k}^{1}),f^{-1}_{2}(x_{i}^{1}))\\}$
(and eventually, edges between representatives of $x_{j}^{1}$ and
$x_{k}^{1}$). Then, since one of the representative of $x_{i}^{2}$ also has a
private neighbor outside of the variable gadget, either the subgraph induced
by $\\{A_{i},f^{-1}_{1}(x_{i}^{1}),f^{-1}_{1}(x_{i}^{2})\\}$ or the subgraph
induced by $\\{B_{i},f^{-1}_{2}(x_{i}^{1}),f^{-1}_{2}(x_{i}^{2})\\}$ (and one
private neighbor of each of the three vertices, where the private neighbor of
$A_{i}$ and $B_{i}$ is $x_{i}^{N}$) is a net. This situation is depicted in
Figure 10.

$A_{i}$$B_{i}$$C_{i}$$f^{-1}_{1}(x_{i}^{1})$$f^{-1}_{1}(x_{i}^{2})$$x_{j}^{1}$$x_{k}^{1}$$f^{-1}_{2}(x_{i}^{1})$$f^{-1}_{2}(x_{i}^{2})$$x_{i}^{N}$
Figure 10: In red, the net created if both representatives of $x_{i}^{1}$ are
incident to the clause gadget in $S$ and $f^{-1}_{1}(x_{i}^{2})$ is incident
to an external edge.

In both cases, the resulting graph $S$ would not be a unit 1-interval graph,
contradicting the hypothesis.

######  Claim 8.

($\star$)representable 2clause Let $(S,f)$ be an arbitrary split in
$\mathcal{S}_{\mathcal{U}}(G_{\Psi})$. Then, for every 2-clause, at least one
of the representatives of the literal vertices incident to the clause gadget
in $S$ must be an isolated vertex.

Towards a contradiction, we assume that there exists a 2-clause gadget in $S$
such that none of the representatives of the literal vertices adjacent to the
clause gadget are isolated. Let $C_{\alpha}=x_{i}^{r}\vee x_{j}^{s}$, with
$i,j\in\\{1,\dots,n\\}$, be a 2-clause, where the indices $r,s\in\\{2,N\\}$
indicate which occurrence of the variable appears in the clause. Again, there
are two options:

  * •

W.l.o.g., the clause gadget in $S$ comprises edges
$\\{(f^{-1}_{1}(x_{i}^{r}),f^{-1}_{1}(x_{j}^{s})),(f^{-1}_{1}(x_{j}^{s}),L_{i,j}^{\alpha}),\allowbreak(L_{i,j}^{\alpha},f^{-1}_{1}(x_{i}^{r}))\\}$.
Then, without loss of generality, we will have a net induced by
$\\{x_{i}^{r},x_{j}^{s},L_{i,j}^{\alpha},A_{i},A_{j},p_{i,j}^{\alpha}\\}$
(since $L_{i,j}^{\alpha}$ is black and $f^{-1}(L_{i,j}^{\alpha})$ consists of
a single element, this unique representative will be incident to the clause
gadget and adjacent to $p_{i,j}^{\alpha}$ at the same time). The readers can
convince themselves looking at figure Figure 3.

  * •

W.l.o.g., the clause gadget in $S$ contains edges
$\\{(f^{-1}_{1}(x_{i}^{r}),f^{-1}_{1}(x_{j}^{s})),(L_{i,j}^{\alpha},f^{-1}_{2}(x_{i}^{r}))\\}$.
Suppose first that $x_{i}^{r}$ is $x_{i}^{2}$. As in the case of 3-clauses,
either the subgraph induced by
$\\{A_{i},f^{-1}_{1}(x_{i}^{1}),f^{-1}_{1}(x_{i}^{2})\\}$ or by
$\\{B_{i},f^{-1}_{2}(x_{i}^{1}),f^{-1}_{2}(x_{i}^{2})\\}$ (and one private
neighbor of each of the three vertices, where the private neighbor of $A_{i}$
and $B_{i}$ is $x_{i}^{N}$) is a net. On the other hand, if $x_{i}^{r}$ is
$x_{i}^{N}$, since this literal only occurs in 2-clauses and the vertex
$L_{i,j}^{\alpha}$ for 2-clauses is black, then it cannot be the case that
$f^{-1}_{1}(x_{i}^{N})$ is adjacent to $x_{j}^{s}$, and
$f^{-1}_{2}(x_{i}^{N})$ is adjacent to $L_{i,j}^{\alpha}$. Indeed, if this
happened, $L_{i,j}^{\alpha}$ would be the center of an induced $K_{1,3}$ with
leaves $p_{i,j}^{\alpha}$, $f^{-1}_{2}(x_{i}^{N})$, and a representative of
$x_{j}^{s}$ (which is not adjacent to $f^{-1}_{2}(x_{i}^{N})$ by assumption).
This would contradict the fact that $S$ is a unit 1-interval graph. The
illustration of the $K_{1,3}$ created can be seen in Figure 3 removing the
edge $(x_{i}^{1},x_{i}^{2})$, and replacing $x_{i}^{1}$ with $x_{i}^{N}$.

In both cases, the resulting graph $S$ would not be a unit 1-interval graph,
contradicting the hypothesis.

The previous claims imply that there is an isolated literal vertex incident to
every 3-clause and to every 2-clause. Since literal vertices that have an
isolated representative correspond to true literals in the assignment fixed
before, it follows that there is a true literal per clause, and thus, all
clauses are satisfied. This finishes the proof of the converse direction.

As the problem is clearly in , the polynomial-time construction together with
Lemmas 3.8 and 3.10 conclude the proof of Theorem 3.1. The bound on the degree
follows because the constructed graph $G$ has maximum degree 6 (the positive
literal vertices have degree 4 in the variable gadget and are incident to 2
external edges).

###  3.2 Hardness of Unit 2-Interval Recognition

We show next that Colored Unit $2$-Interval Recognition is polynomial-time
reducible to Unit 2-Interval Recognition, which yields the main result of the
paper:

######  Theorem 3.12.

Unit 2-Interval Recognition is -complete, even for graphs of degree at most 7.

######  Proof 3.13.

We reduce from Colored Unit $2$-Interval Recognition, which is -hard by
Theorem 3.1. Given any instance $(G,\gamma)$ of Colored Unit $2$-Interval
Recognition, where $G=(V,E)$ is a graph and
$\gamma:V\to\\{\texttt{white},\texttt{black}\\}$ is a vertex-coloring map, we
construct an equivalent instance $G^{\prime}=(V^{\prime},E^{\prime})$ of Unit
2-Interval Recognition. Define $n=|V|$ and $V_{\texttt{c}}=\\{u\mid u\in
V\;\wedge\;\gamma(u)=\texttt{c}\\}$ for
$c\in\\{\texttt{white},\texttt{black}\\}$ (so that
$n=\left|V_{\texttt{white}}\right|+\left|V_{\texttt{black}}\right|$).

We obtain $G^{\prime}=(V^{\prime},E^{\prime})$ from $G$ by replacing every
vertex $v\in V_{\texttt{black}}$ by the gadget $B_{v}$ depicted in Figure 11,
which we also call black vertex gadget. Formally, for every $v\in
V_{\texttt{black}}$, we add the vertices $V_{v}=\\{a_{v}^{i},b_{v}^{i}\mid
0\leqslant i\leqslant 3\\}$ and the edges
$E_{v}=\\{(v,a_{v}^{0}),\allowbreak(a_{v}^{0},a_{v}^{i}),(v,b_{v}^{0}),\allowbreak(b_{v}^{0},b_{v}^{i}),\allowbreak(a_{v}^{0},b_{v}^{0})\mid
1\leqslant i\leqslant 3\\}$. The gadget $B_{v}$ is exactly the graph induced
by the union of $V_{v}$ and vertex $v$. Note that the vertex $v$ of $B_{v}$ is
_public_ , that is, it is adjacent to vertices of $B_{v}$ and to vertices
outside of $B_{v}$, while the rest of the vertices of $B_{v}$ are _private_ ,
i.e., they are only adjacent to vertices of $B_{v}$.

We have thus constructed a graph $G^{\prime}$ with vertex set
$V^{\prime}=V\cup\\{V_{v}\mid v\in V_{\texttt{black}}\\}$ and edge set
$E^{\prime}=E\cup\\{E_{v}\mid v\in V_{\texttt{black}}\\}$. Note that
$G^{\prime}$ contains $G$ as an induced subgraph, as $G^{\prime}[V]=G$.
Combining this with the replacement of every vertex in $V_{\texttt{black}}$ by
a gadget with 9 vertices and 9 edges, it follows that
$|V^{\prime}|=\left|V_{\texttt{white}}\right|+9\,\left|V_{\texttt{black}}\right|$
and $|E^{\prime}|=|E|+9\,\left|V_{\texttt{black}}\right|$.

$v$$a_{v}^{0}$$b_{v}^{0}$$a_{v}^{1}$$b_{v}^{1}$$a_{v}^{2}$$b_{v}^{2}$$a_{v}^{3}$$b_{v}^{3}$
Figure 11: Gadget $B_{v}$ used to replace every black vertex $v$ of $G$ in the
construction of $G^{\prime}$. Vertex $v$ is a _public_ vertex, as it is
adjacent to vertices of the gadget ($a_{v}^{0}$ and $b_{v}^{0}$) and vertices
outside the gadget (namely, its neighbors in the original graph $G$), whereas
the rest of the vertices are _private_ , as their only neighbors are vertices
from the gadget (the ones shown in the figure).

The purpose of the black vertex gadget $B_{v}$ used to replace every $v\in
V_{\texttt{black}}$ in the construction of $G^{\prime}$ is to restrict the
unit 2-interval representations of $G^{\prime}$. Indeed, we will see that it
forces one of the intervals associated to $v$ to be used exclusively to
represent the gadget, while the other interval is used exclusively to
represent the rest of the neighborhood of $v$ (which is exactly its
neighborhood in the original graph $G$). Figure 12 shows a unit 2-interval
representation $\mathbf{R}=\\{(I_{1}(x),I_{2}(x))\mid x\in
V_{v}\cup\\{v\\}\\}$ of $B_{v}$ such that $I_{1}(v)$ does not have any points
in common with the rest of the intervals of $\mathbf{R}$ (i.e., only
$I_{2}(v)$ is used to represent the gadget). Furthermore, in the given
representation, $I_{2}(v)$ cannot intersect any interval associated to a
vertex outside of the gadget, as there is no point of $I_{2}(v)$ that does not
intersect either $I_{1}(a_{v}^{0})$ or $I_{1}(b_{v}^{0})$, and both
$a_{v}^{0}$ and $b_{v}^{0}$ are private vertices for $v$. The next claim
proves that any unit 2-interval representation of $B_{v}$ is as in Figure 12,
up to symmetry.

$I_{1}(a_{v}^{1})$$I_{1}(a_{v}^{0})$$I_{2}(v)$$I_{1}(b_{v}^{0})$$I_{1}(b_{v}^{1})$$I_{1}(a_{v}^{2})$$I_{2}(a_{v}^{0})$$I_{1}(a_{v}^{3})$$I_{1}(b_{v}^{2})$$I_{2}(b_{v}^{0})$$I_{1}(b_{v}^{3})$
Figure 12: A unit 2-interval representation of $B_{v}$ (Figure 11), i.e.,
$\mathbf{D}_{B_{v}}$ for an arbitrary $v\in V_{\texttt{black}}$. Note that
only one interval of $v$ is used ($I_{2}(v)$), while the other one remains
free to display the rest of the neighborhood of $v$ (and is not represented
here).

######  Claim 9.

Let $\\{(I_{1}(x),I_{2}(x))\mid x\in V_{v}\cup\\{v\\}\\}$ be a unit 2-interval
representation of $B_{v}$. Then, there exist some indices $i,j,k\in\\{1,2\\}$
such that the representation of $I_{i}(v),I_{j}(a_{v}^{0}),I_{k}(b_{v}^{0})$
is contiguous (i.e., the union of the three intervals is an interval) and
$I_{i}(v)$ is properly contained in the union $I_{j}(a_{v}^{0})\cup
I_{k}(b_{v}^{0})$.

In the following, we denote an interval associated to a vertex by the name of
the vertex if it refers to an arbitrary interval from the corresponding
2-interval (i.e., we will write $v$ to denote $I_{1}(v)$ or $I_{2}(v)$ when
the choice of interval is irrelevant).

Since $a_{v}^{0}$ and $b_{v}^{0}$ are both centers of an induced $K_{1,4}$,
one of the intervals associated to $a_{v}^{0}$, say $I_{1}(a_{v}^{0})$, needs
to intersect $v$, $b_{v}^{0}$ and one of the $a_{v}^{i}$ for some
$i\in\\{1,2,3\\}$, say $a_{v}^{1}$ without loss of generality (because of the
symmetry). Furthermore, the intervals of $v$ and $b_{v}^{0}$ that intersect
$I_{1}(a_{v}^{0})$ also need to intersect each other, as otherwise
$I_{1}(a_{v}^{0})$ would intersect three disjoint intervals, contradicting the
fact that the representation is unit. On the other hand, $I_{2}(a_{v}^{0})$
has to intersect the two remaining $a_{v}^{i}$, that is, $a_{v}^{2}$ and
$a_{v}^{3}$. Similarly, one of the intervals associated to $b_{v}^{0}$, say
$I_{1}(b_{v}^{0})$, needs to intersect $v$ and $a_{v}^{0}$ (which also
intersect each other), and one of the $b_{v}^{i}$ for some $i\in\\{1,2,3\\}$,
whereas $I_{2}(b_{v}^{0})$ intersects the two remaining $b_{v}^{i}$. Again,
without loss of generality, we can assume that $I(b_{v}^{0})$ intersects
$b_{v}^{1}$ while $I_{2}(b_{v}^{0})$ intersects $b_{v}^{2}$ and $b_{v}^{3}$.

Thus, we have that $I_{1}(a_{v}^{0})$ intersects $v$ and $I_{1}(b_{v}^{0})$
(which also intersect each other), and $a_{v}^{1}$; while $I(b_{v}^{0})$
intersects $v$ and $I_{1}(a_{v}^{0})$ (which also intersect each other), and
$b_{v}^{1}$. This implies that the representation of $a_{v}^{1}$,
$I_{1}(a_{v}^{0})$, $b_{v}^{1}$, $I_{1}(b_{v}^{0})$ has to be contiguous.
Finally, since vertex $v$ is not adjacent to either $a_{v}^{1}$ nor
$b_{v}^{1}$, the only possibility to represent the edges $(v,a_{v}^{0})$ and
$(v,b_{v}^{0})$ is by placing an interval associated to $v$, say $I_{2}(v)$,
properly contained in the union $I_{1}(a_{v}^{0})\cup I_{1}(b_{v}^{0})$, as in
Figure 12.

The next two claims now prove the correctness of the reduction.

######  Claim 10.

If $G$ is a colored unit $2$-interval graph, then $G^{\prime}$ is a unit
$2$-interval graph.

Suppose that $G$ is a colored unit $2$-interval graph. Then, by assumption,
there exists a collection of unit $2$-intervals
$\mathbf{D}_{\texttt{white}}=\\{(I_{1}(v),I_{2}(v))\mid v\in
V_{\texttt{white}}\\}$ and a collection of unit intervals
$\mathbf{I}_{\texttt{black}}=\\{I_{1}(v)\mid v\in V_{\texttt{black}}\\}$ such
that
$G\simeq\Omega\left(\mathbf{D}_{\texttt{white}}\cup\mathbf{I}_{\texttt{black}}\right)$.

From
$\mathbf{D}=\left(\mathbf{D}_{\texttt{white}}\cup\mathbf{I}_{\texttt{black}}\right)$,
we show how to construct a unit $2$-interval representation
$\mathbf{D}^{\prime}$ of $G^{\prime}$. Recall that $(V_{\texttt{white}}\cup
V_{\texttt{black}})=V\subset V^{\prime}$. Similarly, we will construct
$\mathbf{D}^{\prime}$ such that $\mathbf{D}\subset\mathbf{D}^{\prime}$. In
fact, we will have that $\mathbf{D}^{\prime}=\mathbf{D}\cup\left(\bigcup_{v\in
V_{\texttt{black}}}\mathbf{D}_{B_{v}}\right)$, where for every $v\in
V_{\texttt{black}}$, $\mathbf{D}_{B_{v}}$ is the interval representation of
the gadget $B_{v}$. More precisely, we construct $\mathbf{D}^{\prime}$ as
follows:

  * •

For every $v\in V_{\texttt{white}}$, we add to $\mathbf{D}^{\prime}$ the
$2$-interval $(I_{1}(v),I_{2}(v))$ from $\mathbf{D}$.

  * •

For every $v\in V_{\texttt{black}}$, we add to $\mathbf{D}^{\prime}$ the
interval $I_{1}(v)$ from $\mathbf{D}$ together with $\mathbf{D}_{B_{v}}$,
i.e., the interval $I_{2}(v)$ plus the $2$-intervals
$(I_{1}(a_{v}^{k}),I_{2}(a_{v}^{k}))$ and
$(I_{1}(b_{v}^{k}),I_{2}(b_{v}^{k}))$ for $0\leqslant k\leqslant 3$ as defined
in Figure 12.

By construction, $\mathbf{D}^{\prime}$ is a collection of unit $2$-intervals.
It is now a simple matter to verify that
$G^{\prime}\simeq\Omega(\mathbf{D}^{\prime})$.

######  Claim 11.

($\star$)colorconverse If $G^{\prime}$ is a unit $2$-interval graph, then $G$
is a colored unit $2$-interval graph.

Suppose that $G^{\prime}$ is a unit $2$-interval graph. Then, by assumption,
there exists a collection of unit $2$-intervals
$\mathbf{D^{\prime}}=\\{(I_{1}(v),I_{2}(v))\mid v\in V^{\prime}\\}$ such that
$G^{\prime}\simeq\Omega(\mathbf{D^{\prime}})$. From $\mathbf{D^{\prime}}$, we
show how to construct a set $\mathbf{D}$ of $\left|V_{\texttt{white}}\right|$
unit $2$-intervals and $\left|V_{\texttt{black}}\right|$ unit intervals.

Recall that $V\subset V^{\prime}$. Similarly, we will take $\mathbf{D}$ to be
a subset of $\mathbf{D}^{\prime}$. Let $v\in V\subseteq V^{\prime}$ be a
vertex of $G^{\prime}$. We distinguish two cases depending on the color of $v$
in $G$:

  * •

$\gamma(v)=\texttt{white}$. We add to $\mathbf{D}$ the unit $2$-interval
$(I_{1}(v),I_{2}(v))$ of $\mathbf{D}^{\prime}$.

  * •

$\gamma(v)=\texttt{black}$. In $\mathbf{D^{\prime}}$, we have a pair of
intervals $(I_{1}(v),I_{2}(v))$. By 9, w.l.o.g, $I_{2}(v)$ is used to display
the gadget for black vertices, and cannot be used to represent any other
edges. This means that all the remaining neighbors of $v$, which are exactly
its neighbors in $G$, are displayed by $I_{1}(v)$. Thus, we add to
$\mathbf{D}$ the unit interval $I_{1}(v)$ from $\mathbf{D}^{\prime}$.

As the problem is clearly in , combining the fact that the construction of
$G^{\prime}$ can be carried out in polynomial time with Claims 10 and
LABEL:colorconverse, we obtain that Unit 2-Interval Recognition is -complete.
The bound on the degree given in the statement of the theorem follows by
construction, from adding the black vertex gadgets (Figure 11) to the graph
constructed in the proof of Theorem 3.1 (Figure 2). Indeed, this results in a
graph of maximum degree 7, as $C_{i}$ is adjacent to 5 vertices in the
variable gadget and to 2 vertices from the black vertex gadget.

###  3.3 Consequences and generalizations

We now generalize the result for unit $d$-interval graphs, with $d\geqslant
2$, which is not directly implied in graph recognition problems, and for some
specific cases of unit $d$-intervals.

######  Corollary 3.14.

($\star$)d-interval Recognizing unit $d$-interval graphs is -complete for
every $d\geqslant 2$.

######  Proof 3.15.

We reduce recognition of unit $(d-1)$-interval graphs to recognition of unit
$d$-interval graphs, hence the result holds by Theorem 3.12.

The idea is similar to the proof of Theorem 3.12. Given a graph $G=(V,E)$, we
construct in polynomial-time a graph $G^{\prime}$ by adding to each vertex a
gadget similar to the one in Figure 11. Indeed, for every vertex $v$ in $G$,
we create a triangle with vertices $v,a_{v}^{0}$ and $b_{v}^{0}$, but now
$a_{v}^{0}$ and $b_{v}^{0}$ are adjacent to $2d-1$ independent vertices
instead of just 3 (which is the case in Figure 11). Formally, for every $v\in
V$, we add the vertices

$V_{v}=\\{a_{v}^{i},b_{v}^{i}\mid 0\leqslant i\leqslant 2d-1\\}$

and the edges

$E_{v}=\\{(v,a_{v}^{0}),(a_{v}^{0},a_{v}^{i}),(v,b_{v}^{0}),(b_{v}^{0},b_{v}^{i}),(a_{v}^{0},b_{v}^{0})\mid
1\leqslant i\leqslant 2d-1\\}$

We now prove that $G$ has a unit $(d-1)$-interval representation if and only
if it has a unit $d$-interval representation. First, given a unit
$(d-1)$-interval representation, we can build a unit $d$-interval
representation as in Figure 12. However, in this case, instead of having two
intervals $I_{1}(v),I_{2}(v)$ associated to every vertex $v$, we have $d$
intervals, say $I_{1}(v),\dots,I_{d}(v)$. W.l.o.g., the intervals
$I_{1}(v),\dots,I_{d-1}(v)$ are the $d-1$ intervals of the unit
$(d-1)$-interval representation of $G$, while $I_{d}(v)$ plays the role of
$I_{2}(v)$ in Figure 12. Similarly, $I_{1}(a_{v}^{0})$ plays the role of
$I_{1}(a_{v}^{0})$ in Figure 12, while every $I_{j}(a_{v}^{0})$, with
$1<j\leqslant d$ is represented as $I_{2}(a_{v}^{0})$ in Figure 12, each
intersecting two different $a_{v}^{i}$, with $1<i\leqslant 2d-1$. The same
holds for $b_{v}^{0}$.

For the converse implication, if we have a unit $d$-interval representation of
$G^{\prime}$, then, using the same argument as in the proof of 9, we see that
for every vertex $v$, we need to use a complete interval of $v$ to represent
the gadget added in the construction of $G^{\prime}$. Therefore, the remaining
edges (which correspond exactly to the edges of $G$), need to be displayed
using only $d-1$ intervals associated to $v$. This implies that $G$ has a unit
$(d-1)$-interval representation.

######  Corollary 3.16.

($\star$)corollaryxx Recognizing $(x,\dots,x)$ $d$-interval graphs is
-complete for every $x\geqslant 11$ and every $d\geqslant 2$.

######  Proof 3.17.

The result follows because the graph constructed in the reduction is a
$(11,11)$ 2-interval graph, and every $(11,11)$ 2-interval graph is also a
unit 2-interval graph (so the same reduction can be applied). To see this, the
reader can verify the $(11,11)$ 2-interval representation of the largest
contiguous block in Figure 13, and check that the black vertex gadget used in
the proof of Theorem 3.12 is also a $(11,11)$ 2-interval graph.

$I_{1}(C_{i})$$I_{1}(A_{i})$$I_{1}(B_{i})$$I_{1}(x_{i}^{1})$$I_{2}(x_{i}^{1})$$I_{1}(x_{i}^{2})$$I_{1}(x_{m}^{1})$$I_{1}(L_{m,i})$$I_{1}(p_{m,i})$$I_{2}(x_{l}^{2})$$I_{1}(L_{l,k})$$I_{1}(p_{l,k})$$I_{2}(x_{i}^{2})$$I_{2}(x_{j}^{2})$$I_{1}(x_{i}^{N})$$I_{1}(C_{k})$$I_{1}(A_{k})$$I_{1}(B_{k})$$I_{1}(x_{k}^{1})$$I_{2}(x_{k}^{1})$$I_{1}(x_{k}^{2})$$I_{2}(x_{k}^{2})$$I_{1}(x_{k}^{N})$$0$
$5$ $10$ $15$ $20$ $25$ $30$ $35$ $40$ $45$ $50$ $55$ $60$ $65$ $70$ $75$ $80$
$85$ $90$ $95$ $100$ $105$ $110$ $115$ $120$

Figure 13: An $(11,11)$ 2-interval representation of a longest contiguous
block of the graph constructed in the main reduction.

To generalize for $d>2$, it suffices to check that the gadgets added in the
reduction of LABEL:d-interval are $(11,\dots,11)$ $d$-interval. Finally, as
any $(x,\dots,x)$ $d$-interval graph can be turned into a $(x+1,\dots,x+1)$
$d$-interval graph (by partitioning the $dn$ intervals into the minimum number
of maximal cliques and stretching the intersection of the intervals in each
clique by one unit, as described in [DBLP:journals/algorithmica/Jiang13]), the
graph constructed in the main reduction is an $(x,\dots,x)$ $d$-interval graph
for every $x\geqslant 11$. However, the graph constructed is not a
$(x,\dots,x)$ $d$-interval graph for any $x<11$ (this has been checked with
the help of an ILP solver).

######  Corollary 3.18.

($\star$)cordepth Recognizing depth $r$ unit $d$-interval graphs is -complete
for every $r\geqslant 4$ and every $d\geqslant 2$.

######  Proof 3.19.

The result follows because the depth of the representation constructed in the
hardness proof of Theorem 3.1 is 4 (this can be verified by looking at Figure
9), and the depth of the representation of the black vertex gadget added in
the proof of Theorem 3.12 is 3 (as can be seen in Figure 12). Furthermore, the
gadgets added to prove the result for $d>2$ have a representation of depth at
most 3. The corollary generalizes for any depth $r>4$, as for any $r>4$, it is
true that there exists a satisfying assignment if and only if the constructed
graph $G^{\prime}$ has a unit 2-interval representation of depth at most $r$.

The following corollary is based on the Exponential Time Hypothesis (ETH).
More details on this notion that we are only touching here can be found in
[DBLP:books/sp/CyganFKLMPPS15, Chapter 14].

######  Corollary 3.20.

($\star$)corETH Unless the ETH fails, Unit $d$-interval recognition does not
admit an algorithm with running time $2^{o(|V|+|E|)}$.

######  Proof 3.21.

We have provided a polynomial-time reduction from 3-SAT to Unit 2-interval
recognition such that given an instance of 3-SAT of $n$ variables and $m$
clauses, it outputs an equivalent instance of Unit 2-interval recognition
whose size is bounded by $O(n+m)$. Indeed, given an instance of 3-SAT of $n$
variables and $m$ clauses, we first build in subsection 3.1 an equivalent
instance of a special case of SAT with at most $3m$ variables and $7m$
clauses, and then an instance of Colored unit 2-interval recognition with at
most $18m$ vertices and $232m$ edges. Finally, to construct an equivalent
instance of Unit 2-interval recognition, we also add a linear number of
vertices and edges (at most $9|V|$ and $9|E|$, respectively). Therefore, if
Unit 2-interval recognition admitted an algorithm with running time
$2^{o(|V|+|E|)}$, composing the reduction with such an algorithm would yield
an algorithm for 3-SAT running in time $2^{o(n+m)}$, which would contradict
the ETH. To generalize the result for $d>2$, notice that the number of
vertices and edges that we add in the proof of LABEL:d-interval is also
linear.

##  4 Concluding remarks

We have proven that recognizing unit $d$-interval graphs is -complete for any
$d\geqslant 2$. Furthermore, our reduction implies that recognizing
$(x,\dots,x)$ $d$-interval graphs for any $x\geqslant 11$, and depth $r$ unit
$d$-interval graphs for any $r\geqslant 4$, is also hard. These results
represent a significant step towards settling the landscape of the complexity
of the recognition of the different subclasses of $d$-interval graphs.

However, some questions still remain open. Since we have shown that
recognizing depth 4 unit $d$-interval graphs is -complete and it is known that
the recognition of depth 2 unit $d$-interval graphs is polynomial-time
solvable [DBLP:journals/algorithmica/Jiang13], it still remains to delineate
the exact boundary, i.e., study the case of depth 3 unit $d$-interval graphs.
On the other hand, the complexity of recognizing $(x,\dots,x)$ $d$-interval
graphs for $x<11$ is also unknown. Finally, we have obtained a lower bound for
the running time of an algorithm for recognizing unit 2-intervals. Since the
brute-force algorithm, running in $\mathcal{O}(2^{n^{2}})$, is far from
achieving it, it would be interesting to reduce this gap.

## References

  * [1] Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber.  A unified approach to approximating resource allocation and scheduling.  J. ACM, 48(5):1069–1090, 2001.  doi:10.1145/502102.502107.
  * [2] Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, and Irina Shapira.  Scheduling Split Intervals.  SIAM J. Comput., 36(1):1–15, 2006.  doi:10.1137/S0097539703437843.
  * [3] Kenneth P. Bogart and Douglas B. West.  A short proof that ’proper = unit’.  Discret. Math., 201(1-3):21–23, 1999.  doi:10.1016/S0012-365X(98)00310-0.
  * [4] Kellogg S. Booth and George S. Lueker.  Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ-Tree Algorithms.  J. Comput. Syst. Sci., 13(3):335–379, 1976.  doi:10.1016/S0022-0000(76)80045-1.
  * [5] Ayelet Butman, Danny Hermelin, Moshe Lewenstein, and Dror Rawitz.  Optimization problems in multiple-interval graphs.  ACM Trans. Algorithms, 6(2), 2010.  doi:10.1145/1721837.1721856.
  * [6] Joel E. Cohen.  Food Webs and Niche Space, volume 11 of Monographs in Population Biology.  Princeton University Press, 1978.
  * [7] Derek G. Corneil, Stephan Olariu, and Lorna Stewart.  The LBFS structure and recognition of interval graphs.  SIAM J. Discret. Math., 23(4):1905–1953, 2010.  doi:10.1137/S0895480100373455.
  * [8] Margaret B. Cozzens.  Higher and Multi-Dimensional Analogues of Interval Graphs.  PhD thesis, Rutgers University, 1982.
  * [9] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Parameterized Algorithms.  Springer, 2015.  doi:10.1007/978-3-319-21275-3.
  * [10] Michael R. Fellows, Danny Hermelin, Frances A. Rosamond, and Stéphane Vialette.  On the Parameterized Complexity of Multiple-Interval Graph Problems.  Theor. Comput. Sci., 410(1):53–61, 2009.  doi:10.1016/j.tcs.2008.09.065.
  * [11] Michael R. Fellows, Jan Kratochvíl, Matthias Middendorf, and Frank Pfeiffer.  The complexity of induced minors and related problems.  Algorithmica, 13(3):266–282, 1995.  doi:10.1007/BF01190507.
  * [12] Peter C. Fishburn.  Interval Orders and Interval Graphs: A Study of Partially Ordered Sets.  Wiley, 1985.
  * [13] Mathew C. Francis, Daniel Gonçalves, and Pascal Ochem.  The maximum clique problem in multiple interval graphs.  Algorithmica, 71(4):812–836, 2015.  doi:10.1007/s00453-013-9828-6.
  * [14] Peter Frankl and Hiroshi Maehara.  Open-interval graphs versus closed-interval graphs.  Discret. Math., 63(1):97–100, 1987.  doi:10.1016/0012-365X(87)90156-7.
  * [15] Philippe Gambette and Stéphane Vialette.  On restrictions of balanced 2-interval graphs.  In Andreas Brandstädt, Dieter Kratsch, and Haiko Müller, editors, Graph-Theoretic Concepts in Computer Science, 33rd International Workshop, WG 2007, Dornburg, Germany, June 21-23, 2007. Revised Papers, volume 4769 of LNCS, pages 55–65. Springer, 2007.  doi:10.1007/978-3-540-74839-7\\_6.
  * [16] Jerrold R. Griggs and Douglas B. West.  Extremal values of the interval number of a graph.  SIAM J. Algebraic Discret. Methods, 1(1):1–7, 1980.  doi:10.1137/0601001.
  * [17] András Gyárfás and Douglas West.  Multitrack interval graphs.  Congressus Numerantium, pages 109–116, 1995.
  * [18] Minghui Jiang.  Recognizing d-interval graphs and d-track interval graphs.  Algorithmica, 66(3):541–563, 2013.  doi:10.1007/s00453-012-9651-5.
  * [19] Deborah Joseph, Joao Meidanis, and Prasoon Tiwari.  Determining DNA sequence similarity using maximum independent set algorithms for interval graphs.  In Otto Nurmi and Esko Ukkonen, editors, Algorithm Theory - SWAT ’92, Third Scandinavian Workshop on Algorithm Theory, Helsinki, Finland, July 8-10, 1992, Proceedings, volume 621 of LNCS, pages 326–337. Springer, 1992.  doi:10.1007/3-540-55706-7\\_29.
  * [20] Jan Kratochvíl.  A special planar satisfiability problem and a consequence of its NP-completeness.  Discret. Appl. Math., 52(3):233–252, 1994.  doi:10.1016/0166-218X(94)90143-0.
  * [21] Cornelis Gerrit Lekkerkerker and Johan Ch. Boland.  Representation of a finite graph by a set of intervals on the real line.  Fundamenta Mathematicae, 51:45–64, 1962.
  * [22] Robert McGuigan.  Presentation at NSF-CBMS Conference at Colby College, 1977.
  * [23] Terry A McKee and Fred R McMorris.  Topics in intersection graph theory.  SIAM, 1999.
  * [24] Dieter Rautenbach and Jayme L Szwarcfiter.  Unit interval graphs of open and closed intervals.  J. Graph Theory, 72(4):418–429, 2013.  doi:10.1002/jgt.21650.
  * [25] Fred S. Roberts.  Indifference graphs.  In F. Harary, editor, Proof Techniques in Graph Theory, pages 139–146. Academic Press, NY, 1969.
  * [26] Fred S. Roberts.  On the boxicity and cubicity of a graph.  In W. T. Tutte, editor, Recent Progress in Combinatorics, pages 301–310. Academic Press, NY, 1969.
  * [27] Fred S. Roberts.  Graph theory and its applications to problems of society.  SIAM, 1978.
  * [28] Alexandre Simon.  Algorithmic study of 2-interval graphs.  Master’s thesis, Delft University of Technology, 2021.
  * [29] William T. Trotter and Frank Harary.  On double and multiple interval graphs.  J. Graph Theory, 3(3):205–211, 1979.  doi:10.1002/jgt.3190030302.
  * [30] Stéphane Vialette.  On the computational complexity of $2$-interval pattern matching problems.  Theor. Comput. Sci., 312(2-3):223–249, 2004.  doi:10.1016/j.tcs.2003.08.010.
  * [31] Douglas B. West and David B. Shmoys.  Recognizing graphs with fixed interval number is NP-complete.  Disrecte Appl. Math., 8:295–305, 1984.  doi:10.1016/0166-218X(84)90127-6.
  * [32] Mihalis Yannakakis.  The complexity of the partial order dimension problem.  SIAM Journal on Algebraic Discrete Methods, 3(3):351–358, 1982\.
  * [33] Peisen Zhang, Eric A Schon, Stuart G Fischer, Eftihia Cayanis, Janie Weiss, Susan Kistler, and Philip E Bourne.  An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA.  Comput. Appl. Biosci., 10(3):309–317, 1994.  doi:10.1093/bioinformatics/10.3.309.