Maximum Cut on Interval Graphs of Interval Count Two is NP-complete

For a given input graph $G=\bigl{(}V(G),E(G)\bigr{)}$, the Maximum Cut problem finds a partition of $V(G)$ in two sets such that the number of edges between them is maximal.

Maximum Cut is a fundamental and well-known NP-complete problem [3]. The weighted version of the problem is one of Karp’s original 21 NP-complete problems [4]. There are many results describing the complexity of Maximum Cut, where the input of the problem is restricted on some particular classes of graphs. The problem remains NP-complete for many graph classes, such like cubic graphs [5], split graphs [6], co-bipartite graphs [6], unit disk graphs [7], total graphs [8], and interval graphs [1]. On the positive side, polynomial time algorithms are known for planar graphs [9], line graphs [8], graphs not contractible to $K_{5}$ [10] and graphs with bounded treewidth [6].

There are two papers that have mainly motivated our research. First, a recent proof of NP-completeness of Maximum Cut on interval graphs provided by Adhikary et al. in [1]. Second, a more recent result of de Figueiredo et al. in [2], where they extend the result of the first paper by proving that Maximum Cut is NP-complete on graphs of interval count four. Using the technique of the above work, de Figueiredo et al. prove the NP-completeness of Maximum Cut on permutation graphs as well, which too was open for a long time [11]. The bounding of the number of interval lengths brings us closer to the final goal: to characterize Maximum Cut for unit interval graphs as they are exactly interval graphs of interval count one. There were attempts to provide a polynomial-time algorithm for unit interval graphs [12, 13], but they both were later shown to be incorrect [14, 15]. In this paper, we extend the result of de Figueiredo et al. [2] by proving Theorem 1 which brings us as close as possible to Maximum Cut on unit interval graphs.

For $a,b$ in $\mathbb{R}$, an interval between $a$ and $b$, denoted $[a,b]$, is the set of all $x\in\mathbb{R}$ such that $a\leq x\leq b$. The left and right endpoints of $I=[a,b]$ are denoted by $\ell(I):=a$ and $r(I):=b$. The length $\textrm{len}({I})$ of an interval $I$ equals $r(I)-\ell(I)$. A set of intervals $\mathcal{I}$ is called an interval model of a graph $G$ if there is a one-to-one mapping $f\colon V(G)\to\mathcal{I}$ such that, for any pair $u,v$ of vertices of $G$, $uv$ is in $E(G)$ if and only if the intervals $f(u)$ and $f(v)$ have a non-empty intersection. A graph is called interval if it has an interval model. A graph $G$ has interval count $\ell$ if there exists a set $C\subset\mathbb{R}$ of size $\ell$ and an interval model $\mathcal{I}$ of $G$ such that, for all $I$ in $\mathcal{I}$, we have $\textrm{len}({I})\in C$.

A cut $(R,B)$ of a graph $G$ is a partition of its vertices in two classes: $V(G)=R\sqcup B$. For a cut $(R,B)$, a cut edge is an edge that is incident to a vertex in $A$ and to a vertex in $B$. The cut value is the number of cut edges of the graph. For a subset of vertices $S$ of a graph, the cut value contributed by $S$ is the number of cut edges that have at least one of their ends in $S$. Recall that the Maximum Cut problem asks for a cut of the maximal value. Notice that, for interval graphs, Maximum Cut is equivalent to the problem of finding a coloring of an interval model in two colors, say $R$ (Red) and $B$ (Blue), where the number of differently colored pairs with non-empty intersection is maximal. If an interval $I$ has a color $c\in\{R,B\}$, then we use the notation $\chi(I)=c$. If $\mathcal{B}$ is a set of intervals that all have the same color $c\in\{R,B\}$, then we use the notation $\chi(\mathcal{B})=c$.

We use intervals of two different lengths: short and long. We assume that, if an interval $I$ is short, then $\textrm{len}({I})=1$, otherwise, $\textrm{len}({I})=\alpha$ for some $\alpha>1$ that will be made precise later.

A block $\mathcal{B}$ is a set of short intervals such that, for any two intervals $I,I^{\prime}\in\mathcal{B}$, we have $\ell(I)=\ell(I^{\prime})$ and $r(I)=r(I^{\prime})$. For a block $\mathcal{B}$, denote $\ell(\mathcal{B}):=\ell(I)$ and $r(\mathcal{B}):=r(I)$ for an interval $I\in\mathcal{B}$. The size $|\mathcal{B}|$ of a block $\mathcal{B}$ is the number of intervals in it. For example, a block of size $n$ is an interval model of the complete graph $K_{n}$ on $n$ vertices.

A union of blocks $\mathcal{B}_{1}\cup\mathcal{B}_{2}\cup\mathcal{B}_{3}$ is a 3-block if

• •

  $r(\mathcal{B}_{1})<\ell(\mathcal{B}_{3})$ and $r(\mathcal{B}_{1})\geq\ell(\mathcal{B}_{2})$ and $r(\mathcal{B}_{2})\geq\ell(\mathcal{B}_{3})$ and

• •

  $|\mathcal{B}_{1}|=|\mathcal{B}_{3}|$ and $|\mathcal{B}_{2}|=2|\mathcal{B}_{1}|$.

In this article, 3-blocks are displayed as three rectangles, see Figure 1. An interval $I$ terminates at a block $\mathcal{B}$ if $\ell(\mathcal{B})\leq r(I)\leq r(\mathcal{B})$ and starts from $\mathcal{B}$ if $\ell(\mathcal{B})\leq\ell(I)\leq r(\mathcal{B})$. For a long interval $L$, we say that it covers $\mathcal{B}$ if $\ell(L)<\ell(\mathcal{B})<r(\mathcal{B})<r(L)$. For example, on Figure 1, $L_{1}$ terminates at $\mathcal{B}_{1}$, $L_{2}$ covers all the blocks, $L_{3}$ starts from $\mathcal{B}_{3}$, $L_{4}$ covers $\mathcal{B}_{1}$ and terminates at $\mathcal{B}_{2}$, and $L_{5}$ starts from $\mathcal{B}_{2}$ and covers $\mathcal{B}_{3}$.

Consider any family of blocks of intervals of the same length $\mathcal{B}_{1},\ldots,\mathcal{B}_{s}$ such that, for $i$ in $[s-1]$, we have $r(\mathcal{B}_{i})=\ell(\mathcal{B}_{i+1})$. A coloring is a mapping $\chi\colon\mathcal{B}_{1}\cup\dots\cup\mathcal{B}_{s}\to\{R,B\}$. A coloring $\chi$ is alternating if, for $i\in[s-1]$, we have $\chi(\mathcal{B}_{i})\not=\chi(\mathcal{B}_{i+1})$. A coloring $\chi$ is almost alternating except for $(\mathcal{B}_{i},\delta)$ if it becomes alternating after removal of at most $\delta$ intervals from the block $\mathcal{B}_{i}$.

We first revisit the reduction of Adhikary et al. in [1]. They reduced Maximum Cut on cubic graphs to Maximum Cut on interval graphs. Recall that a graph $G$ is cubic if the degree of every vertex $v\in V(G)$ is equal to 3. In their paper, each vertex and edge of the original cubic graph was represented by a set of intervals, called vertex and edge gadgets respectively. The interval model consisted of first all the vertex gadgets, and then all the edge gadgets arranged from left to right. If an edge was incident to a vertex, then the corresponding vertex and edge gadgets were “linked” by a pair of very long intervals starting from the vertex gadgets and terminating at the edge gadget. They were called link intervals. The number of intervals in any gadget was much greater than the total number of link intervals in the graph. It was shown that, in any Maximum Cut partition of this interval graph, each vertex gadget or edge gadget could have only two possible partitions. For a vertex gadget, these two partitions were made to correspond to its membership in one of the partition sets for a maximum cut of the original cubic graph. If two adjacent vertices of the cubic graph belonged to different sets, then the corresponding edge gadget would make more cut edges with link intervals than if these vertex gadgets were in the same set. Thus, a cut of maximum size of the given cubic graph always corresponded to a cut of maximum size of the constructed interval graph and vice versa. As Maximum Cut on cubic graphs is NP-complete, this reduction implies that it is also NP-complete on interval graphs.

In the reduction above, the gadgets contained intervals of two different lengths. However, the length of each link interval depended on the relative positions of its vertex and edge gadgets. So the total number of different lengths of link intervals was linearly dependent on the size of the cubic graph. So, this interval graph seemed to be far away from unit interval graphs, for which the problem was still open. De Figueiredo et al. in [2] made a very important advancement in this regard. They showed that Maximum Cut was NP-complete even when the total number of lengths used for the intervals was only 4, i.e., when the interval count of the graph was 4. In their paper, the vertex and edge gadgets were basically the same as that of Adhikary et al. in [1]. However, an extra gadget, resembling the vertex and edge gadgets, was used as a “join gadget” between link intervals. Instead of having a link interval running through the entire length between its corresponding vertex and edge gadgets, they used a chain of link intervals joined to each other with the use of join gadgets.

A link chain is a sequence of link intervals with a join gadget between every two consecutive link intervals, where one link interval terminates at the gadget and the other one starts from it. The link intervals of all other link chains that intersect this join gadget, cover it. The join gadgets ensure that, in a maximum cut partition, the link intervals of every link chain are colored with Red and Blue alternately. Thus, link intervals of arbitrary lengths in the original reduction can be replaced by link intervals of a single size. However, one problem remained. Between consecutive vertex or edge gadgets, the link chains had their join gadgets in a fixed order. For example, consider vertex gadgets $\mathcal{V}_{i-1}$, $\mathcal{V}_{i}$ and $\mathcal{V}_{i+1}$, and link chains $\mathcal{L}_{j-1}$, $\mathcal{L}_{j}$ and $\mathcal{L}_{j+1}$ (fig. 2). If in the gap between $\mathcal{V}_{i-1}$ and $\mathcal{V}_{i}$, the join gadget of $\mathcal{L}_{i-1}$ occurred first, followed by a join gadget each of $\mathcal{L}_{j}$ and $\mathcal{L}_{j+1}$ respectively, then they would occur in the same order in the gap between $\mathcal{V}_{i}$ and $\mathcal{V}_{i+1}$. This would pose a problem if the structure of the graph required $\mathcal{L}_{j-1}$ and $\mathcal{L}_{j+1}$ to have a partial intersection with the same edge gadget. In such a case, a second type of link interval with a different length would be used to end link chain $\mathcal{L}_{j+1}$ early and enable it to partially intersect the same edge gadget along with $\mathcal{L}_{j-1}$. Thus, their reduction needed intervals of two lengths for the vertex, edge and join gadgets, and another two lengths as the link intervals, totaling to an interval count of four.

We reduce the interval count down to 2 due to our modifications of gadgets and link chains. Instead of using separate lengths of short and long intervals in previous works, the gadgets are now mainly constructed from 3-blocks. The link chains do not use long intervals of two separate lengths anymore. The issue of non-consecutive link chains partially intersecting the same edge gadget is resolved by using a switch gadget that switches the relative positions of join gadgets of link chains.

The Maximum Cut problem is NP-complete on cubic graphs [5]. In this article, we provide a polynomial time reduction from Maximum Cut on cubic graphs to Maximum Cut on interval graphs of interval count two. For every cubic graph $G$ (of size $n$), we construct a graph $H$ of interval count 2 such that any Maximum Cut partition of $H$ corresponds to some Maximum Cut partition of $G$ and vice versa. Its top level composition is displayed on Figure 3. On the left, there are vertex gadgets $\mathcal{V}_{1},\dots,\mathcal{V}_{n}$. For each vertex gadget there are three link chains constructed by alternating long intervals and join gadgets. For every edge $g_{i}g_{j}$ of $E(G)$ there is an edge gadget $\mathcal{E}_{ij}$ such that two link chains $\mathcal{L}^{i}_{ij},\mathcal{L}_{ij}^{j}$ starting from $\mathcal{V}_{i}$ and $\mathcal{V}_{j}$ respectively both terminate at $\mathcal{E}_{ij}$.

Before $\mathcal{L}^{i}_{ij},\mathcal{L}_{ij}^{j}$ reach the edge gadget, we must ensure that there is no other link chain between them. The reason is that, in our construction, neither $\mathcal{E}_{ij}$ can intersect another gadget nor a long interval not from $\mathcal{L}^{i}_{ij}\cup\mathcal{L}_{ij}^{j}$ can start from or terminate at $\mathcal{E}_{ij}$. Suppose, for example, that $v_{1}v_{3}\in E(G)$. If we straightforwardly connect link chains $\mathcal{L}^{1}_{13},\mathcal{L}_{13}^{3}$ to $\mathcal{E}_{13}$, then, as $\mathcal{V}_{2}$ is positioned “between” $\mathcal{V}_{1}$ and $\mathcal{V}_{3}$, this edge gadget will intersect join gadgets of link chains that start from $\mathcal{V}_{2}$. To solve this issue, we repetitively apply the switching procedure that switches two consecutive link chains and, therefore, reduces the number of join gadgets between the ones of $\mathcal{L}^{i}_{ij},\mathcal{L}_{ij}^{j}$. After these two chains terminate at $\mathcal{E}_{ij}$, we proceed similarly for every other edge of $E(G)$.

Before we formally describe the reduction graph $H$ of interval count two, we present all the gadgets that are used in its construction. Assuming that the size $|V(G)|$ of the cubic graph $G$ is $n$, we introduce two parameters that denote the gadget sizes. Let $x$ be in $\Omega(n^{7})$ and let $k$ be in $\Omega(n^{6})$. Next to the definition of each gadget, we add a figure, where this gadget is displayed. On each of the figures, this gadget is colored in Red and Blue. After we construct the whole graph $H$ of interval count two, we will argue that, for every Maximum Cut partition of $H$, the coloring of each of its gadgets is similar to one displayed on the corresponding figure.

Let $G$ be a cubic graph of size $n$. Let the long interval length be $\alpha:=53n-3$ while the short interval length is 1. All the intervals of $H$ belong to $[0,+\infty)$. This ray is split into zones and buffers in the following order:

Each zone (or buffer) is a disjoint union of fragments of the same length, where the distance between two neighbor fragments of the same zone is the same and depends on the long interval length $\alpha$.

• •

  Here, $\textrm{Zone}(1),\ldots,\textrm{Zone}(n)$ are the zones that correspond to vertices of $G$. For a vertex $g_{i}\in V(G)$, $\textrm{Zone}(i)$ is the following disjoint union of fragments of the same size:

  $$\textrm{Zone}(i)=\bigcup_{j\in\mathbb{Z}}\bigl{[}53i+j(\alpha+3),53i+j(\alpha+3)+32\bigr{]}.$$

  This zone usually contains the vertex and the join gadgets corresponding to $g_{i}\in V(G)$. The size of its fragments is 32. The distance $\alpha+3$ between the left endpoints of two neighbor fragments is called the phase.

• •

  Buffer zones. For two vertices $g_{i},g_{i+1}\in V(G)$ (and also $g_{n-1},g_{0}$), we introduce a buffer zone between $\textrm{Zone}(i),\textrm{Zone}(i+1)$. It is denoted by $\textrm{Buffer}(i,i+1)$ ($\textrm{Buffer}(n-1,0)$ is denoted similarly) and is defined as follows:

  $$\textrm{Buffer}(i,i+1)=\bigcup_{j\in\mathbb{Z}}\bigl{[}53i+j(\alpha+3)+32,53(i+1)+j(\alpha+3)\bigr{]}.$$

  We need buffer zones in order to do the switching. Every fragment of a buffer zone has size 21.

We need to write $\alpha+3$ instead of $\alpha$ because a long interval must start from the rightmost block of some 3-block and must terminate at the leftmost block of another 3-block. So, the length of long intervals must be lesser than the length of the phase by 3.

For $i\in\{1,\ldots,n\}$, add a vertex gadget $\mathcal{V}_{i}$ into the leftmost fragment of $\textrm{Zone}(i)$. For each $\mathcal{V}_{i}$ there are 3 long intervals starting from it; they terminate at a join gadget that has 3 new long intervals starting from it, and so on. This produces 3 link chains of long intervals. Each such chain eventually terminates at a corresponding edge gadget.

For every edge $g_{i}g_{j}\in E(G)$, where $i<j$, we choose a link chain starting from $\mathcal{V}_{i}$ and repeatedly apply the switch procedure (introduced formally in the next paragraph) to this chain until it is in $\textrm{Zone}(j)$. Once it happens, this chain of $\mathcal{V}_{i}$ and one of the chains of $\mathcal{V}_{j}$ terminate at the same edge gadget $\mathcal{E}_{ij}$. No long interval starts from $\mathcal{E}_{ij}$. Then we choose another edge of $G$ and repeat this operation until all edges of $G$ are treated. If a chain does not participate in some switch procedure, then, during this procedure, the long intervals of this chain are joined by join gadgets that look the same as vertex gadgets. The composition of $H$ is displayed on Figure 3 on fig. 3.