Fixed-Treewidth-Efficient Algorithms for Edge-Deletion to Interval Graph Classes^††thanks: This manuscript corrects some errors in [24].

Intersection graphs are represented by geometric objects aligned in certain ways so that each object corresponds to a vertex and two objects intersect if and only if the corresponding vertices are adjacent. Intersection graphs are well-studied in the area of graph algorithms since there are many important applications and we can solve many NP-hard problems in general graphs in polynomial time on such graph classes. Interval graphs are intersection graphs which are represented by intervals on a line. Clique, Independent Set, and Coloring on interval graphs can be solved in linear time and interval graphs have many applications in bioinformatics, scheduling, and so on. See [14, 3, 26] for more details of interval graphs and other intersection graphs.

Graph modification problems on a graph class $\mathcal{C}$ are to find a graph in $\mathcal{C}$ by modifying a given graph in certain ways. $\mathcal{C}$-Vertex-Deletion, $\mathcal{C}$-Edge-Deletion, and $\mathcal{C}$-Completion are to find a graph in $\mathcal{C}$ by deleting vertices, deleting edges, and adding edges, respectively, with the minimum cost. These problems can be seen as generalizations of many NP-hard problems. Clique is equivalent to Complete-Vertex-Deletion: we find a complete graph by deleting the smallest number of vertices. Modification problems on intersection graph classes also have many applications. For example, Interval-Vertex/Edge-Deletion problems have applications to DNA (physical) mapping [13, 12, 27]. Lewis and Yannakakis showed that $\mathcal{C}$-Vertex-Deletion is NP-complete for any nontrivial hereditary graph class [17]. A graph class $\mathcal{C}$ is hereditary if for any graph in $\mathcal{C}$, every induced subgraph of the graph is also in $\mathcal{C}$. Since the class of intersection graphs are hereditary, $\mathcal{C}$-Vertex Deletion is NP-complete for any nontrivial intersection graph class $\mathcal{C}$. The problems $\mathcal{C}$-Edge-Deletion are also NP-hard when $\mathcal{C}$ is the class of perfect, chordal, split, circular arc, chain [23], interval, proper interval [13], trivially perfect (a.k.a. nested interval) [25], threshold [20], permutation, weakly chordal, or circle graphs [4]. See the lists in [19, 4].

Parameterized complexity is well-studied in the area of computer science. A problem with a parameter $k$ is fixed parameter tractable, FPT for short, if there is an algorithm running in $f(k)n^{c}$ time where $n$ is the size of input, $f$ is a computable function and $c$ is a constant. Such an algorithm is called an FPT algorithm. The treewidth $\mathit{tw}(G)$ of a graph $G$ represents treelikeness and is one of the most important parameters in parameterized complexity concerning graph algorithms. For many NP-hard problems in general, there are tons of FPT algorithms with parameter $\mathit{tw}(G)$ by dynamic programming on tree decompositions. Finding the treewidth of an input graph is NP-hard and it is known that Chordal-Completion with minimizing the size of the smallest maximum clique is equivalent to the problem. There is an FPT algorithm for computing the treewidth of a graph by Bodlaender [2] which runs in $O(f(\mathit{tw}(G))(n+m))$ time where $n$ and $m$ are the numbers of vertices and edges of a given graph: i.e., the running time is linear in the size of input. Courcelle showed that every problem that can be expressed in monadic second order logic (MSO₂) has a linear time algorithm on graphs of bounded treewidth [9]. Some intersection graph classes, for example interval graphs, proper interval graphs, chordal graphs, and permutation graphs, can be represented by MSO₂ [8] and thus there are FPT algorithms for Edge-Deletion problems on such graph classes. However, the algorithms obtained by Courcelle’s theorem have a very large hidden constant factor even when the treewidth is very small, since the running time is the exponential tower of the coding size of the MSO₂ expression.

Concerning parameterized complexity of $\mathcal{C}$-Vertex-Deletion, Hof et al. proposed an FPT algorithm for Proper-Interval-Vertex-Deletion [28], and Marx proposed an FPT algorithm for Chordal-Vertex-Deletion [21]. Heggernes et al. showed Perfect-Vertex-Deletion and Weakly-Chordal-Vertex-Deletion are W[2]-hard [15]. Cai showed that $C$-Vertex/Edge-Deletion are FPT when $\mathcal{C}$ is characterized by a finite set of forbidden induced subgraphs [5].

For modification problems on interval graphs, Villanger et al. presented an FPT algorithm for Interval-Completion [29], and Cao and Marx presented an FPT algorithm for Interval-Vertex-Deletion [7]. Cao improved these algorithms and developed an FPT algorithm for Edge-Deletion [6].

It is known that Threshold-Edge-Deletion, Chain-Edge-Deletion and Trivially-Perfect-Edge-Deletion are FPT, since threshold graphs, chain graphs and trivially perfect graphs are characterized by a finite set of forbidden induced subgraphs [5]. Nastos and Gao presented faster algorithms for the problems [22], and Liu et al. improved their algorithms to $O(2.57^{k}(n+m))$ and $O(2.42^{k}(n+m))$ using modular decomposition trees [18], where $k$ is the number of deleted edges. There are algorithms to find a polynomial kernel for Chain-Edge-Deletion and Trivially Perfect-Edge-Deletion [1, 11].

For a set $X$, its cardinality is denoted by $|X|$. A partition of $X$ is a tuple $(X_{1},\dots,X_{k})$ of subsets of $X$ such that $X=X_{1}\cup\dots\cup X_{k}$ and $X_{i}\cap X_{j}=\emptyset$ if $1\leq i<j\leq k$, where we allow some of the subsets to be empty. For entities $x,y,z\in X$, we let $x[y/z]=y$ if $x=z$, and $x[y/z]=x$ otherwise. For a subset $Y\subseteq X$, define $Y[y/z]=\{\,x[y/z]\mid x\in Y\,\}$.

For a linear order $\pi$ over a finite set $X$, the maximum and the minimum elements of $X$ w.r.t. $\pi$ are denoted by $\max_{\pi}X$ and $\min_{\pi}X$, respectively. We denote the successor of $x\in X$ w.r.t. $\pi$ by $\mathsf{suc}_{\pi}(x)=\min_{\pi}\{\,y\in X\mid x<_{\pi}y\,\}$. Note that $\mathsf{suc}_{\pi}(\max_{\pi}X)$ is undefined. Similarly $\mathsf{pred}_{\pi}(x)=\max_{\pi}\{\,y\in X\mid y<_{\pi}x\,\}$ denotes the predecessor of $x$.

A simple graph $G=(V,E)$ is a pair of vertex and edge sets, where each element of $E$ is a subset of $V$ consisting of exactly two elements.

A tree-decomposition of $G=(V,E)$ is a tree $T$ such that¹¹1We use the terms “vertices” for an input graph and “nodes” for a tree-decomposition.

• •

  to each node of $T$ a subset of $V$ is assigned,

• •

  if the assigned sets of two nodes of $T$ contain a vertex $u\in V$, then so does every node on the path between the two nodes,

• •

  for each $\{u,v\}\in E$, there is a node of $T$ whose assigned set includes both $u$ and $v$.

The width of a tree-decomposition is the maximum cardinality of the assigned sets minus one and the treewidth of a graph is the smallest width of its tree-decompositions. A tree-decomposition is said to be nice if it is rooted, the root is assigned the empty set, and its nodes are grouped into the following four:

• •

  leaf nodes, which have no children and are assigned the empty set,

• •

  introduce nodes, each of which has just one child, where the set assigned to the node adds one vertex to the child’s set,

• •

  forget nodes, each of which has just one child, where the set assigned to the node removes one vertex from the child’s set,

• •

  join nodes, each of which has just two children, where the same vertex set is assigned to the node and its children.

It is known that every tree-decomposition has a nice tree-decomposition of the same width whose size is $O(k|V|)$, where $k$ is the treewidth of the tree-decomposition [16, 10]. Hereafter, under a fixed graph $G$ and a fixed nice tree-decomposition $T$, we let $X_{s}$ denote the subset of $V$ assigned to a node $s$ of a tree-decomposition and $X_{\leq s}$ denote the union of all the subsets assigned to the node $s$ and its descendant nodes. We call vertices in $X_{s}$ and in $X_{\leq s}-X_{s}$ active and forgotten, respectively. Moreover, we define $E_{s}=\{\,\{u,v\}\in E\mid u,v\in X_{s}\,\}$ and $E_{\leq s}=\{\,\{u,v\}\in E\mid u,v\in X_{\leq s}\,\}$. Given a tree decomposition of treewidth $k$, we can compute a nice tree-decomposition with treewidth $k$ and $O(kn)$ nodes in $O(k^{2}(n+m))$ time [10].

A tree-decomposition is called a path-decomposition if the tree is a path. The pathwidth of a graph is the smallest width of its path-decompositions. Every path-decomposition has a nice path-decomposition of the same pathwidth, which consists of leaf, introduce, forget, but not join nodes.

The problem we tackle in this paper is given as follows.

In the succeeding sections, for different classes $\mathcal{C}$ of intersection graphs, we present algorithms for $\mathcal{C}$-Edge-Deletion that run in linear time in the input graph size when the treewidth is bounded. We assume that the algorithm takes a nice tree-decomposition $T$ of $G$ in addition as input [2, 16]. Our algorithms are dynamic programming algorithms that recursively compute solutions (and some auxiliary information) for the subproblems on $(X_{\leq s},E_{\leq s})$ for each node $s$ in the given tree-decomposition from leaves to the root.

An interval representation $\pi$ over a set $X$ is a linear order over the set $\mathit{LR}_{X}=\mathit{L}_{X}\cup\mathit{R}_{X}\cup\{\bot,\top\}$ with $\mathit{L}_{X}=\{\,l_{x}\mid x\in X\,\}$ and $\mathit{R}_{X}=\{\,r_{x}\mid x\in X\,\}$ such that $\bot<_{\pi}l_{x}<_{\pi}r_{x}<_{\pi}\top$ for all $x\in X$. An interval is a pair $(p,q)\in\mathit{LR}_{X}\times\mathit{LR}_{X}$. We say that two intervals $(p_{1},q_{1})$ and $(p_{2},q_{2})$ intersect, denoted by $(p_{1},q_{1})\mathrel{\text{$/$\hbox to0.0pt{\hss$\backslash$}}}_{\pi}(p_{2},q_{2})$ if $p_{1}<_{\pi}q_{2}$ and $p_{2}<_{\pi}q_{1}$. Otherwise, we write $(p_{1},q_{1})\mathrel{/\!/\!}_{\pi}(p_{2},q_{2})$.

The interval graph $G_{\pi}$ of an interval representation $\pi$ on $V$ is $(V,\mathcal{E}_{\pi})$ where

Figure 2 (a) and (b) show an example of an interval representation and the defined interval graph, respectively.

This section presents an FPT algorithm for the interval edge deletion problem w.r.t. the treewidth. Let $G=(V,E)$ be an input graph and $s$ a node of a nice tree-decomposition $T$ of $G$. On each node $s$ of $T$, for each interval representation $\rho$ over $X_{\leq s}$ that gives an interval subgraph of $(X_{\leq s},E_{\leq s})$, we would like to remember some pieces of information about $\rho$, which we call the “abstraction” of $\rho$. The abstraction is the triple $(\pi,I,c)$, where the linear order $\pi$ over $\mathit{LR}_{X_{s}}$ is the restriction of $\rho$ to $X_{s}$, forgotten vertices are represented in $I$ by anchoring the ends of intervals formed by forgotten vertices to active vertices, and $c$ counts the number of edges of $E-E_{\rho}$ such that at least one of their ends is forgotten. For each forgotten vertex $w\in X_{\leq s}-X_{s}$, let the intersection closure of $w$ (w.r.t. $\rho$ and $s$) be the smallest set $[w]_{\rho}^{s}\subseteq\mathit{LR}_{X_{\leq s}-X_{s}}$ such that

• •

  $l_{w},r_{w}\in[w]_{\rho}^{s}$ and

• •

  if $l_{u},r_{u}\in[w]_{\rho}^{s}$, $v\in X_{\leq s}-X_{s}$ and $(l_{u},r_{u})\mathrel{\text{$/$\hbox to0.0pt{\hss$\backslash$}}}_{\rho}(l_{v},r_{v})$, then $l_{v},r_{v}\in[w]_{\rho}^{s}$.

For an interval representation $\rho$ over $X_{\leq s}$ such that $G_{\rho}$ is a subgraph of $(X_{\leq s},E_{\leq s})$, we define the abstraction $\mathscr{A}(\rho,s)$ of $\rho$ for $s$ to be the triple $(\pi,I,c)$ such that²²2Actually presence of intervals $(\bot,\bot)$ and $(\mathsf{pred}_{\pi}(\top),\mathsf{pred}_{\pi}(\top))$ in $I$ does not matter.

• •

  $\pi$ is the restriction of $\rho$ to $\mathit{LR}_{X_{s}}$,

• •

  $I=\{\,(p,q)\in\mathit{LR}_{X_{s}}\times\mathit{LR}_{X_{s}}\mid\text{there is $w\in X_{\leq s}-X_{s}$ such that}$
                        $p<_{\rho}\min_{\rho}[w]_{\rho}^{s}<_{\rho}\mathsf{suc}_{\pi}(p)$ and $q<_{\rho}\max_{\rho}[w]_{\rho}^{s}<_{\rho}\mathsf{suc}_{\pi}(q)$ },

• •

  $c=|E_{\leq s}-\mathcal{E}_{\rho}-E_{s}|$
  $c$${}=|\{\,\{u,v\}\in E_{\leq s}\mid u\notin{X_{s}}$ and $(l_{u},r_{u})\mathrel{/\!/\!}_{\rho}(l_{v},r_{v})\,\}|$.

We call elements of $I$ forbidden intervals because introducing a new vertex interval intersecting a forbidden interval means making the new vertex and a forgotten vertex adjacent, which is forbidden. Figure 2 (c) shows an example of $I$. Since forbidden intervals are formed by intersection closures, no distinct forbidden intervals may intersect. If $s$ is the root of a nice tree-decomposition, the abstraction will be $\mathscr{A}(\rho,s)=(o,\{(\bot,\bot)\},c_{\rho})$ where $o$ is the trivial order on $\{\bot,\top\}$ such that $\bot<_{o}\top$ and $c_{\rho}=|E-E_{\rho}|$. That is, the smallest $c_{\rho}$ for an interval subgraph $G_{\rho}$ is the solution to our problem.

However, we do not have to compute $\mathscr{A}(\rho,s)$ of all the possible interval representations $\rho$ over $X_{\leq s}$ on each node $s$. We say that $(\pi,I,c)$ dominates $(\pi^{\prime},I^{\prime},c^{\prime})$ if and only if $\pi=\pi^{\prime}$, $I\sqsubseteq_{\pi}I^{\prime}$ and $c\leq c^{\prime}$, where we write $I\sqsubseteq_{\pi}I^{\prime}$ if every forbidden interval of $I$ is inside some forbidden interval of $I^{\prime}$: i.e., for every $(p,q)\in I$, there is $(p^{\prime},q^{\prime})\in I^{\prime}$ such that $p^{\prime}\leq_{\pi}p$ and $q\leq_{\pi}q^{\prime}$. In this case, every possible way of introducing new intervals to $\rho^{\prime}$ is also possible for $\rho$ by cheaper or equivalent cost. Therefore, it is enough to remember $\mathscr{A}(\rho,s)$ discarding $\mathscr{A}(\rho^{\prime},s)$. For a set of abstractions, the process of removing ones which are dominated by others is called reduction. We call a set of abstractions reduced if it has no pair of distinct elements such that one dominates the other.

Our algorithm calculates a reduced set $\mathscr{I}_{s}$ of abstractions of interval representations of interval subgraphs of $({X}_{\leq s},{E}_{\leq s})$ for each node $s$ of $T$ which satisfies the following invariant.

Since $\mathscr{I}_{s}$ is reduced, if $X_{s}=\emptyset$, we have $\mathscr{I}_{s}=\{(o,I,c)\}$ for some $I\subseteq\{(\bot,\bot)\}$ and $c\in\mathbb{N}$, where $o$ is the trivial order such that $\bot<_{o}\top$. Particularly for the root node $s$, the number $c$ is the least number such that one can obtain an interval subgraph by removing $c$ edges from $G$. That is, $c$ is the solution to our problem. If $s$ is a leaf, $\mathscr{I}_{s}=\{(o,\emptyset,0)\}$ by definition. It remains to show how to calculate $\mathscr{I}_{s}$ from the child(ren) of $s$, while preserving the invariant (Condition 1).

A permutation representation over a set $X$ is a pair $\pi=(\pi_{1},\pi_{2})$ of linear orders on $X^{+}=X\cup\{\top,\bot\}$ such that $\bot<_{\pi_{i}}x<_{\pi_{i}}\top$ for all $x\in X$ and $i\in\{1,2\}$. For two points $u$ and $v$ in $X^{+}$, we write $u\mathrel{/\!/\!}_{\pi}v$ if $\pi_{1}$ and $\pi_{2}$ agree on the order of $u$ and $v$: that is, either $u\leq_{\pi_{1}}v$ and $u\leq_{\pi_{2}}v$ or $v<_{\pi_{1}}u$ and $v<_{\pi_{2}}u$. Otherwise, we write $u\mathrel{\text{$/$\hbox to0.0pt{\hss$\backslash$}}}_{\pi}v$ and say that $u$ and $v$ intersect in $\pi$. The permutation graph $G_{\pi}$ of a permutation representation $\pi$ on $V$ is $(V,\mathcal{E}_{\pi})$ where

Figure 7 (a) shows an example of a permutation representation $\rho$ and (b) shows the induced permutation graph $G_{\rho}$. For each vertex $u$ of $V$, we put a point on each of the two parallel lines respecting the linear orders $\pi_{1}$ and $\pi_{2}$ and draw a line, called the $u$-line, between the points. Then we make an edge between $u$ and $v$ if and only if the $u$-line and the $v$-line intersect. This section gives an FPT algorithm for the edge deletion problem for permutation graphs.