1 Introduction

Chordal graphs are arguably the oldest and most important perfect graph class [2, 3, 12]. A graph is chordal if very cycle of length larger than three has a chord. Chordal graphs have many nice structural properties, which earn them wide applications. Balas and Yu [1] proposed a heuristic algorithm for the maximum clique problem by first finding a maximum spanning chordal subgraph (see also [25]). This is equivalent to the chordal edge deletion problem, which asks for the existence of a set of at most edges whose deletion makes a graph chordal. Dearing et al. [8] observed that a maximum spanning chordal subgraph can also be used to approximate maximum independent sets and sparse matrix completion. This observation turns out to be archetypal: many NP-hard problems (coloring, maximum clique, etc.) are known to be solvable in polynomial time when restricted to chordal graphs, and hence admit a similar heuristic algorithm. Some applications of chordal graphs might not seem to be related to graphs at first sight. During the study of Gaussian elimination on sparse positive definite matrices, Rose [23, 24] formulated the chordal completion problem, which asks for the existence of a set of at most edges whose addition makes a graph chordal, and showed that it is equivalent to minimum fill-in.

Cai [5] extended this observation to the exact setting. He studied the coloring problems on graphs close to certain graph classes. In particular, he asked the following question: given an -vertex graph that can be obtained from a chordal graph by adding edges (or vertices), can we find a minimum coloring for in time? The edge version was resolved by Marx [18] affirmatively. His algorithm needs as part of the input the additional edges; to find them is equivalent to solving the chordal edge deletion problem. Likewise, to decide whether a graph can be obtained from a chordal graph by additional vertices is equivalent to solving the chordal vertex deletion problem. One may observe that though with slightly different purpose, the inspirations behind [1, 8, 25] and [5] are exactly the same.

All three aforementioned modification problems, unfortunately but understandably, are NP-hard [14, 16, 21, 26]. Therefore, early work of Kaplan et al. [13] and Cai [4] focused on their parameterized complexity, and proved that chordal completion is fixed-parameter tractable (FPT). Recall that a graph problem, with a nonnegative parameter , is FPT if there is an algorithm solving it in time , where is a computable function depending only on  and is the number of vertices in the input graph [10]. Marx [19] showed that the complementary deletion problems, both edge and vertex versions, are also FPT. Here we consider the generalized chordal editing problem that combines all three operations: the task is to decide whether a graph can be made chordal by deleting at most vertices, deleting at most edges, and adding at most edges. On the formulation we have two quick remarks. First, it does not make sense to add new vertices, as chordal graphs are hereditary (i.e., any induced subgraph of a chordal graph is chordal). Second, the budgets for different operations are not transferable, as otherwise it degenerates to chordal vertex deletion. Our main result establishes the fixed-parameter tractability of chordal editing parameterized by .

Theorem 1.1

(Main result) There is a -time algorithm for deciding, given an -vertex graph , whether there are a set of at most vertices, a set of at most edges, and a set of at most non-edges, such that the deletion of and and the addition of make chordal.

As a corollary, our algorithm implies the fixed-parameter tractability of chordal edge editing, which allows both edge operations but not vertex deletions (we can try every combination of and where does not exceed the given bound), resolving an open problem asked by Mancini [17]. Moreover, we get a new FPT algorithm for the special case chordal deletion, and it is far simpler and faster than the algorithm of Marx [19].

Motivation In the last two decades, graph modification problems have received intensive attention, and promoted themselves as an independent line of research in both parameterized computation and algorithmic graph theory. For graphs representing experimental data, the edge additions and deletions are commonly used to model false negatives and false positives respectively, while vertex deletions can be viewed as the detection of outliers. In this setting, it is unnatural to consider any single type of errors, while the chordal editing problem formulated above is able to encompass both positive and negative errors, as well as outliers. Further, since it is generally acknowledged that the study of chordal graphs motivated the theory of perfect graphs [2, 12], the importance of chordal graphs merits such a study from the aspect of structural graph theory.

Related work Chordal graphs contain no holes (i.e., induced cycles of at least four vertices) as induced subgraphs. Observing that a large hole cannot be fixed by the addition of a small number of edges, it is easy to devise a bounded search tree algorithm for the chordal completion problem [4, 13]. No such simple argument works for the deletion versions: the removal of a single vertex/edge suffices to break a hole of an arbitrary length. The way Marx [19] showed that the deletion problems are FPT is to (1) prove that if the graph contains a large clique, then we can identify an irrelevant vertex whose deletion does not change the problem; and (2) observe that if the graph has no large cliques, then it has bounded treewidth, so the problem can be solved by standard techniques, such as the application of Courcelle’s Theorem. In contrast, our algorithm uses simple reductions and structural properties, which reveal a better understanding of the deletion problems, and easily extend to the more general chordal editing problem.

Of all the vertex deletion problems, we would like to single out those to forests (also known as feedback vertex set), interval graphs, and unit interval graphs for a special comparison. Their commonality with chordal vertex deletion lies in the fact that these graph classes are proper subsets of chordal graphs, or equivalently, their forbidden subgraphs contain all holes as a proper subset. For these problems, we can dispose of those small forbidden subgraphs first and their nonexistence simplifies the graph structure and significantly decreases the possible configurations on which we conduct branching (all known algorithms use bounded search trees). As a result, each of them admits a -time algorithms for some small constant . However, long holes, which do not bother us at all in these three problems, turn out to be the main difficulty of the current paper. This partially explains why a -time algorithm for chordal vertex deletion is so elusive.

Our techniques As a standard opening step, we use the iterative compression method introduced by Reed et al. [22] and concentrate on the compression problem. Given a solution () to a graph , we can easily find a set of at most vertices such that is chordal. A clique tree decomposition of will be extensively employed in the compression step,Footnote 1 where short holes can be broken by simple branching, and the main technical idea appears in the way we break long holes. We show that a hole of the minimum length can be decomposed into a bounded number of segments, where the internal vertices of each segment, as well as the part of the graph “close” to them behave in a well-structured and simple way with respect to their interaction with . To break , we have to break some of the segments, and the properties of the segments allow us to show that we need to consider only a bounded number of canonical separators breaking them. Therefore, we can branch on choosing one of these canonical separators and break the hole using it, resulting in an FPT algorithm.

Notation All graphs discussed in this paper shall always be undirected and simple. The vertex set and edge set of a graph are denoted by respectively. We use the customary notation to mean , and by we mean that is adjacent to at least one vertex in . Two vertex sets and are completely connected if for every pair of and . A hole has the same number of vertices and edges, denoted by . We use as a shorthand for , regardless of whether or not; moreover, for a hole . A vertex is simplicial if induces a clique. A set of vertices is an separator if and belong to different components in the subgraph ; it is minimal if no proper subset of is an separator. Note that the definition of separators requires them to be disjoint from . Minimal separators and induced paths are connected by the following fact.

Proposition 1.2

A vertex is an internal vertex of an induced path if and only if it is in some minimal separator.

Let be a tree whose vertices, called bags, correspond to the maximal cliques of a connected graph . With the customary abuse of notation, the same symbol is used for a bag in and its corresponding maximal clique of . We say that is a clique tree of if for every , all bags containing induce a subtree of , denoted by . It is known that a connected graph is chordal if and only if it has a clique tree, which has at most bags [9]. Between any pair of adjacent bags and of a clique tree \(\mathcal{T}\), the intersection is a minimal separator for any pair of vertices and . In our setting, this separator is necessarily nonempty. A vertex is simplicial if and only if it belongs to exactly one maximal clique; thus, any non-simplicial vertex appears in some minimal separator(s) [15]. By definition, a pair of vertices of is adjacent if and only if and intersect. Otherwise, there exists a unique path connecting and in , where and are the only bags that contain and respectively; the intersection of any pair of consecutive bags in this path is a (not necessarily minimal) separator.

A notational remark is worth here. For technical reasons, we have restricted clique trees in this paper to be defined only on connected chordal graphs, or components in a general chordal graph. However, in literature it is more common that clique trees are defined without the condition on connectedness. Indeed, given a set of clique trees for all components of a disconnected chordal graph, one may add arbitrary edges to connect them into a single tree, where some adjacent bags may share no common vertices. We remark also that clique trees of chordal graphs are not unique, and our algorithm does not rely on a particular one.

2 Outline of the Algorithm

A subset of vertices is called a hole cover of a graph if its deletion makes chordal. Let , and let and be a set of edges and a set of non-edges of respectively. We say that () is an chordal editing set of if the deletion of from and the addition of to create a chordal graph. Its size is defined to be the 3-tuple (), and we say that it is smaller than () if all of and and hold true and at least one inequality is strict. Note that since chordal graphs are hereditary, it does not make sense to add new vertices. The main problem studied in the paper is formally defined as follows.

figure a

We use to denote the total numbers of operations. One might be tempted to define the editing problem by imposing a combined quota on the total number of operations instead of three separate parameters. However, this formulation is computationally equivalent to chordal vertex deletion in a trivial sense, as vertex deletions are clearly preferable to both edge operations.

We use the technique iterative compression, i.e., we define and solve a compression version of the problem first and argue that this implies the fixed-parameter tractability of the original problem. In the compression problem a hole cover of a bounded size is given in the input. Note that the definition below has a slightly technical (but standard) additional condition: we are not allowed to delete any vertex from .

figure b

The hole cover is called the modulator of this instance, which makes the problem somewhat easier: as is chordal, we have useful structural information about the graph. The main part of this paper will be focused on an algorithm for chordal editing compression. More specifically, we will endeavor to prove the following theorem.

Theorem 2.1

Chordal editing compression can be solved in time .

Roughly speaking, our algorithm for chordal editing compression either repetitively calls the following steps or reduces the instance when it identifies a vertex that has to be in .

  1. 1.

    find a shortest hole ;

  2. 2.

    if is shorter than , then guess a way to fix it;

  3. 3.

    otherwise, decompose into segments, and guess a segment and break it.

Let us briefly explain here steps 1 and 2, while leaving the main technical part, step 3, for later sections. A shortest hole can be detected in time as follows: we guess three consecutive vertices of , and then search for the shortest path in . In order to destroy , we need to perform at least one of the possible vertex deletions (vertices in are avoided here), edge deletions, or edge insertions that affect . Therefore, if the length of is no more than , then we can fix it easily by branching into directions. Hence we may assume in step 3. Such a hole cannot be fixed with edge additions only; thus at least one deletion has to occur on this hole. As we shall see in Sect. 3, the hole can be divided into a bounded number of “segments” (paths), of which at least one needs to be “broken.” In our case, breaking a segment means more than deleting one vertex or edge from it, and it needs a strange mixed form of separation: we have to separate two vertices by removing both edges and vertices. We study this notion of mixed separation on chordal graphs in Sect. 4. Finally, we show in Sect. 5 that there is a bounded number of canonical ways of breaking a segment and we may branch on choosing one segment and one of the canonical ways of breaking it. This completes the proof of Theorem 2.1, which enables us to prove the main theorem.

Fig. 1
figure 1

Algorithm for chordal editing

Full size image

Proof of Theorem 1.1

Let be an arbitrary ordering of , and let be the subgraph induced by the first vertices. Note that . The algorithm described in Fig. 1 iteratively finds a chordal editing set of from to ; the solution for is used in solving . The main work is done in the for-loop, which maintains as an invariant that () is a chordal editing set of size at most () of for the current . The set found in step 1 contains no more than vertices, and then step 2 generates at most instances of chordal editing compression, where is the modulator . Each instance has parameter at most (), and thus can be solved in time. There are iterations, and the running time of the algorithm is thus . \(\square \)

3 Segments

We consider the chordal editing compression problem. Let be the shortest hole we have found, which is assumed to be longer than . We denote by the set of common neighbors of , and define and . We can assume that induces a clique: if two vertices in are nonadjacent, then they form a 4-hole together with any two nonadjacent vertices of . The following observation follows from the fact that is the shortest hole of .

Proposition 3.1

A vertex not in is adjacent to at most three vertices of and these vertices have to be consecutive in .

Let . For each component in the chordal subgraph , we fix a clique tree. Note that partitions , and is disjoint from . Since and is chordal, the hole intersects both and . Every component of is an induced path of , and there are at most such paths. We divide each of these paths into parts; observing , this leads to a decomposition of into parts. For this purpose, it suffices to consider paths longer than . Let denote such a path in , then for and the other neighbors of and in (different from and respectively) are in .

It is worth noting that the definition of depends upon the hole . We shall now define two more vertex sets and , which depend upon, apart from , the sub-path we are considering, and the clique tree \(\mathcal{T}\) for the component of containing .

We take the unique path of bags that connects the disjoint subtrees and in \(\mathcal{T}\), where and are the only bags of that contain and respectively. The condition implies that . The removal of and from will separate into a set of subtrees, one of which contains all with ; let denote this nonempty subtree. The set is defined to be the union of all bags in and . Since these bags induce a subtree, and our definition of clique tree requires a nonempty intersection between two adjacent bags, is a subset of and induces a connected subgraph.

We then focus on bags in and their union. (One may have judiciously observed that these vertices induce an interval subgraph.) For every with , we denote by (resp., ) the smallest (resp., largest) index such that and . Recall that and appear only in and respectively, hence and . On the other hand, every internal vertex of appears in more than one bag of . Since is an induced path, for each with , we have

$$\begin{aligned} {\mathtt {first}(i)} \le {\mathtt {last}(i-1)} < {\mathtt {first}(i + 1)} \le {\mathtt {last}(i)}. \end{aligned}$$
(1)

For any pair of nonadjacent vertices in , (i.e., ,) all minimal separators in are contained in . The set is defined to be the union of vertices in all induced paths in ; according to Proposition 1.2, , and thus . Note that and are completely connected: given a pair of nonadjacent vertices and , we can find a hole of that consists of and part of a path through in .

Proposition 3.2

The vertex sets and are completely adjacent.

The set is easily understood, and we now consider . Given a pair of nonadjacent vertices , we say that lies to the left (resp., right) of if every bag of containing has smaller (resp., greater) index than every bag of containing . If an induced path of consists of three or more vertices, then its ends are nonadjacent and have a left-right relation. This relation can be extended to all pairs of consecutive (and adjacent) vertices in this path, the one with smaller distance to the left end of the path is said to the left of the other.

Lemma 3.3

Let be a component of the subgraph induced by . If is nonadjacent to and , then induces a clique and there exists such that and .

Proof

Since is nonadjacent to and , it is disjoint from and . As a result, , and then . Recall that all vertices of appear in , and thus every clique of is a subset of some bag in ; it suffices to show that induces a clique. Suppose for contradiction that there is a pair of nonadjacent vertices ; without loss of generality, let lie to the left of . We can find an induced path through no vertices to the right of , and an induced path through no vertices to the left of . Let be the first vertex in (counting from ) that is adjacent to , and the last vertex in (counting from ) that is adjacent to . We can find an induced path with all internal vertices from . Note that either is or lies to the left of in and either is or lies to the right of , which imply . Thus is an induced path through , which is impossible. This completes the proof. \(\square \)

Such a component is called a branch of , and we say that is near to some internal vertex of if there is an with satisfying the condition of Lemma 3.3. In other words, is near to if and only if ; here note that since is connected, . Applying Proposition 3.1 on any vertex in , we conclude that a branch is near to at most three vertices of . If there exists some hole passing through , then has to be adjacent to : by Proposition 3.2 and Lemma 3.3, is a clique, and thus a hole cannot both enter and leave via . The converse is not necessarily true: some branch that is adjacent to might still be disjoint from all holes, e.g., can be a clique even if it intersects . This observation inspires us to generalize the definition of simplicial vertices to sets of vertices.

Definition 1

A set of vertices is called simplicial in a graph if induces a chordal subgraph of and induces a clique of .

It is easy to verify that a simplicial set of vertices is disjoint from all holes. This may suggest that simplicial sets are irrelevant to chordal editing problem and we may never want to add/delete edges incident to a vertex in a simplicial set . However, this is not true: as Fig. 2 shows, if a solution removes some edges of , then the solution may also need to add/delete edges incident to . As characterized by the following lemma, this is the only reason for touching in the solution. In other words, a simplicial set will only concern us after has been changed; after all, may not be simplicial any more. We say that a chordal editing set () edits a set of vertices if either contains a vertex of or contains an edge incident to . We use a classic result of Dirac [9] stating that the graph obtained by identifying two cliques of the same size from two chordal graphs is also chordal.

Fig. 2
figure 2

Possible modifications to simplicial vertices (③ means a clique of 3 vertices). a A minimal solution (two deletions) that deletes a (dashed) edge incident to a simplicial vertex . b A minimal solution ( deletions and additions) that adds (dotted) edges incident to a simplicial vertex

Full size image

Lemma 3.4

A minimal chordal editing set edits a simplicial set only if it removes at least one edge induced by .

Proof

Let () be a minimal editing set of such that does not contain any edge induced by . We restrict the editing set to the subgraph , i.e., we consider the set (), and let be the graph obtained by applying it to . Clearly is chordal, where induces a clique. Also chordal is the subgraph of induced by . Both of them contain the clique . Since can be obtained from them by identifying , it is also chordal. Then by the minimality of (), it must be the same as (), and this proves this lemma. \(\square \)

Now we are ready to define segments of the path , which are delimited by some special vertices called junctions. Note that a branch is always simplicial in (by the definition of and Lemma 3.3), but it is not necessarily simplicial in .

Definition 2

(Segment) A vertex is called a junction (of  ) if

(1) :

some bag that contains is adjacent to ;

(2) :

some branch near to is adjacent to ;

(3) :

some branch near to is not simplicial in ; or

(4) :

is not completely connected to .

A sub-path of , denoted by , is a segment if and are the only junctions in it.

Because is adjacent to , both and are junctions of type (1); so are . We point out that the four types are not exclusive, and one junction might be in more than one type. For a junction of type (1) or (2), we say that the vertex in used in its definition witnesses it. Let us briefly explain the intuition behind the definition of junctions and segments.

Remark 3.5

For a junction of type (1) or (2), there is a path from to that is “local to ” in some sense. For a junction of type (3) or (4), there might be a hole “local to ” (in the sense that it passes through only and vertices near to ), and its disposal might interfere with that of . On the other hand, since there are no junctions inside a segment , if another hole intersects it, then has to “go through the whole segment.” Or precisely, necessarily enters and exits the segment via and , respectively.

The definition of junctions and segments extends to all paths of . Once is given, we can find in polynomial time the sets and , and construct clique trees for each component of ; for each path of , we can find in polynomial time and , and identify all its junctions. Since both ends of are type (1) junctions (adjacent to ), every vertex in is contained in some segment, and in each path of , the number of segments is the number of junctions minus one. We are now ready for the main result of this section that gives a cubic bound on the number of segments of . It should be noted that the constants—both the exponent and the coefficient—in the following statement are not tight, and the current values simplify the argument significantly. Recall that, by Proposition 3.1, a vertex not in sees at most three vertices in , and they have to be consecutive.

Theorem 3.6

If contains more than segments, then we can either find a vertex that has to be in , or return “NO.”

Proof

Since there are at most paths in , at least one of them contains more than segments. Let be such a path, then has more than junctions. Let us first attend to junctions of type (1) in . \(\square \)

Claim 1

Each witnesses at most junctions of type (1) in .

Proof

Suppose, for contradiction, that or more vertices in appear in bags adjacent to ; let be this set of vertices. Assume first that is consecutive. At most 3 of them are adjacent to , and they are either consecutive in or at the two ends of (Proposition 3.1). Thus, we can always pick 6 consecutive vertices from that are nonadjacent to ; let them be . By definition, there are two vertices such that and . Using Proposition 3.1 it is easy to verify that and . Therefore, we can find an induced path with all internal vertices from . The length of this path is at least , and hence ( is chordal) and the path together with makes a hole of length at most , contradicting the assumption that is a shortest hole.

Assume now that is not consecutive in , then we can pick a pair of nonadjacent vertices from such that for every . Note that neither of and can be adjacent to , as otherwise or will also be a junction of type (1). There are two vertices such that and . Neither of and can be adjacent to for (they are not junctions of type (1)); noting that , from Proposition 3.1 and the fact that is chordal we can conclude that , and . Therefore, is a hole. By assumption that , we have . Thus, we obtain a hole strictly shorter than , a contradiction. \(\lrcorner \)

Claim 2

If some vertex witnesses junctions of types (1) and (2) in , then we can return “NO.”

Proof

Let be this set of junctions of type (1) or (2) witnessed by . We order these vertices according to their indices in and group each consecutive five from the beginning. We omit groups that contain junctions of type (1) witnessed by , and in each remaining group, we pair the second and last vertices in it. According to Claim 1, we end with at least pairs, which we denote by (), , ().

For each pair (), where , we construct a hole as follows. By definition, there is a branch (resp., ) whose neighborhood in is a proper subset of (resp., ). By the selection of the pair and (two vertices of have been skipped in between), they are nonadjacent, and . According to Proposition 3.1, and have no common neighbors in . Therefore, and , which are nonempty subsets of and respectively, are disjoint. The neighborhoods of and on the hole are possibly empty, and this fact is irrelevant for the argument to follow. Since induces a connected subgraph and is adjacent to both and , we can find an induced path with all internal vertices from . Likewise, we can obtain an induced path \(P_{r_j}\) with all internal vertices from \(C_{r_j-1}\cup N_{V_0}[v_{{r_j}}]\). These two paths \(P_{\ell _j}\) and \(P_{r_j}\), together with \(v_{\ell _j +1}\ldots v_{r_j-1}\), make the hole \(H_{j}\): we have \({\ell _j +1}<{r_j-1}\); for each \({\ell _j +1}\le s\le {r_j-1},\,v_s\not \sim w\) (as there cannot be a junction of type (1) in between); and for each \({\ell _j +1}< s< {r_j-1},\,v_s\not \sim C_{\ell _j}, C_{r_j}\). This hole goes through w. This way we can construct \(k+1\) holes, and it can be easily verified that they intersect only in w. Since we are not allowed to delete w in the disjoint compression version of the problem, we cannot fix all these holes by at most k operations. Thus we can return “NO.” \(\lrcorner \)

If Claim 2 applies, then we are already done; otherwise, there are at most junctions of the first two types in . We proceed to consider the set of junctions that are only of type (3) or (4) but not of the first two types. The size of is at least (noting )

$$\begin{aligned} (14 k^2 + 88 k + 83) - (5k+74)\cdot |M| \ge 9 k^2 + 9 k + 9 = 9\left( k(k+1) + 1\right) . \end{aligned}$$

We order according to their indices in , and let denote the index of the th vertex of in . For each , we use the ()th vertex of to construct a hole . Then we argue that this collection of holes either allows us to identify a vertex that has to be in the solution, or conclude infeasibility.

The first case is when is of type (4): there is a pair of nonadjacent vertices and ; according to Proposition 3.2, . In this case we can assume that is adjacent to neither nor ; otherwise or is a 4-hole, which contradicts the fact that is the shortest. In other words, only appears in bags between and . By the definition of , there is an induced path via in . This path necessarily passes through both and . We find the last neighbor of on and the first neighbor of on ; they must lie to the different sides of . We can thus construct an induced path through in . Note that and are adjacent to and respectively; by Proposition 3.1, this path does not visit or . Starting from , we traverse to the left until the first vertex that is adjacent to ; the existence of such a vertex is ensured by the fact that . Similarly, we find the first neighbor of in to the right of . Then the sub-path of between and , together with , gives the hole . By construction, no vertex of is adjacent to or .

In the other case, is of type (3): some branch near to is not simplicial in . By definition, either the subgraph induced by is not a clique, or the subgraph induced by is not chordal.

  • The subgraph induced by is not a clique. Since does not satisfy the conditions of type (1) and (2), , i.e., . On the other hand, according to Lemma 3.3, induces a clique. Therefore, there must be a pair of nonadjacent vertices and , which is necessarily in . As is near to , it must hold that . However, then is also of type (4), and it has already been discussed.

  • Suppose now that induces a clique and there is a hole in . Since is not of type (2), . Since is chordal, must intersect ; let be a vertex in . If is disjoint from , then no vertex in can be adjacent to or . Otherwise, it contains some vertex ; noting that induces a clique, . Moreover, is in the neighborhood of and therefore and are disjoint for : the existence of a vertex adjacent to both and would contradict Proposition 3.1 (noting that the distance of and is greater than 2 on the hole ).

In summary, we have a set of at least distinct holes such that (1) each hole in contains at most one vertex of , and (2) the intersection of any pair of them is in and it has size at most two (as is a clique). If there is a contained in at least holes of ; we argue that we have to put into . Here note that it might be the case that these holes contain also a common vertex , and then the edge is also common to them. Suppose that we delete but not . After the deletion of , each of these holes becomes a path. Internal vertices of these paths are in or in branches near to for some , and thus internal vertices of different paths cannot be adjacent. Therefore, any two of these paths will together make a hole longer than , not fixable by edge additions only. Therefore, at least of these paths have to be broken, but we have only modifications left, so we still need to delete . Otherwise, no vertex in is contained in more than holes of . We can find distinct holes that intersect only in . Some subset of may share the same edge with , but a similar argument as above ensures us that at least edges need to be deleted from . Therefore, we can return “NO.” This concludes the proof.\(\square \)

4 Mixed Separators in Chordal Graphs

Given a pair of nonadjacent vertices of a graph, we say that a pair of vertex set and edge set is a mixed separator if the deletion of and leaves and in two different components; its size is defined to be (\(|V_S|, |E_S|\)). Again, by definition, needs to be disjoint from . A mixed separator is inclusion-wise minimal if there exists no other mixed separator (\(V'_S, E'_S\)) such that and and at least one containment is proper. If (\(V_S, E_S\)) is an inclusion-wise minimal mixed separator in graph , then each component of is an induced subgraph of . Therefore, we have the following simple property of inclusion-wise minimal mixed separators in chordal graphs.

Proposition 4.1

In a chordal graph, all components obtained by deleting an inclusion-wise minimal separator are chordal.

Consider an inclusion-wise minimal separator () in a connected chordal graph . The degenerate case where is well understood: itself makes an separator and can be easily found. Hence we may assume . Let and be the vertices in the components of that contain and respectively. We fix a clique tree of , and consider the subtree induced by bags intersecting , and the subtree induced by bags intersecting . By minimality, all edges of are between and , hence in , which is again a subtree of , and every bag in it intersects both and . The following conclusions follow from the minimality of ().

  1. (1)

    All vertices in all bags of are either in or belong to ; in the second case, every such vertex is incident to at least one edge of .

  2. (2)

    Every vertex in is adjacent to both and , thereby appearing in some bag of .

We remark that the remaining vertices of a bag not in the subtree may belong to a different component of than and .

Each bag in the subtree contains at most vertices: the number of edges between any nontrivial partition of is at least , which has to be at most . Likewise, the total number of vertices in all bags of this subtree is at most : each vertex in these bags that are not in is incident to at least one edge in , and one edge is incident to two vertices. This inspires the following algorithm.

Lemma 4.2

Let and be a pair of nonadjacent vertices in a connected chordal graph . For any pair (a, b) of nonnegative integers, we can find a mixed separator of size at most (a, b) or assert its nonexistence in time .

Proof

We find first a minimum vertex separator ; if its size is at most , then (\(S,\emptyset \)) will be the mixed separator. Henceforth we may assume that in any mixed separator satisfying . By previous discussion, to find such a mixed separator, it suffices to find the subtree and a tri-partition of all vertices in all bags of this subtree, where and are the components of containing and respectively.

To begin with, we guess a bag of size at most vertices, and generate in time all tri-partitions of . If a mixed separator of size at most (a, b) exists, then in some branch we will guess a bag in along with its tri-partition whose three parts are in , and respectively. We grow the bag to the subtree by considering its neighboring bags one by one. For such a bag , we consider , of which all vertices have already been decided. If they are all in , then their deletion separates the rest of (as well as all vertices in the subtree containing in ) from both and , and thus they will not further concern us. A similar situation is when a subset of or , then the rest of will be in or accordingly: all paths connecting them to the other side go through . Otherwise, intersects both and , and then must be in . Let the number of vertices that have been decided to be in , and let be the number of edges between vertices that have been decided in and . If contains more than vertices, then we terminate this branch; otherwise we guess a tri-partition for it and proceed to the next bag.

Extending this way, in the whole process all bags that have been partitioned form a subtree. Either all partitions have been terminated and we can conclude that there is no mixed separator of size at most (a, b), or we obtain a mixed separator when it cannot be further extended, i.e., for every bag adjacent to some bag of this subtree, are fully contained in either or . The execution of this algorithm can be viewed as traversing a bounded search tree, and to bound the number of its leaves, we use as the measure. There are at most bags in , which is the number of child nodes of the root node in the search tree. For each new bag with undecided vertices, we have at most tri-partitions to consider. For each of these tri-partitions, we have a sub-instance, where the measure decreases by at least . Noting that , the total number of leaves is at most , and the running time of the algorithm is . This completes the proof.

\(\square \)

The definition of mixed separator can be easily generalized to two disjoint vertex sets each inducing a connected subgraph—we may simply contract each set into a single vertex (after which the graph remains chordal) and then look for a mixed separator for these two new vertices. Another interpretation of Lemma 4.2 is the following.

Corollary 4.3

Let be a chordal graph, and let and be a pair of disjoint and nonadjacent sets of vertices in such that both and are connected. For any nonnegative integer , in time we can find the minimum number such that and there is a mixed separator of size (a, b) or assert that there is no mixed separator of size (\(a,k_2\)).

We remark that the problem of finding a mixed separator of certain size is fixed-parameter tractable even in general graphs: the treewidth reduction technique of Marx et al. [20] can be used after a simple reduction (subdivide each edge, color the new vertices red and the original vertices black, and find a separator with at most black vertices and at most red vertices). However, the algorithm of Lemma 4.2 for the special case of chordal graphs is simpler and much more efficient. On the other hand, we are not aware of any proof of its NP-hardness on chordal graphs, and its complexity is still open.

5 Proof of Theorem 2.1

We are now ready to put everything together and finish the algorithm for chordal editing compression. We say that a chordal editing set is minimum if there exists no chordal editing set with a smaller size.

Proof of Theorem 2.1

We start from finding a shortest hole . If , then we try one of the vertex deletions, edge deletions, and edge insertions that affect . Clearly, at least one of these operations is necessary, and each of them makes a new instance that has strictly smaller parameters. Hence we may assume . With fixed, we have (common neighbors of ) and (i.e., ) defined; we further build clique trees for all components in and find all segments of . If there are more than segments, then by Theorem 3.6, we have either found a vertex that must be in in any valid solution, leading to a new instance with smaller parameters, or been ready to return “NO.” Henceforth, we may assume that contains segments, which also means that it has junctions.

Let us fix a hypothetical (\(V^*_-, E^*_-, E^*_+\)) minimum chordal editing set of of size no more than (\(k_1, k_2, k_3\)). There are three options for breaking by this set. In the first case, contains some junction, or contains some edge of that is incident to . In this case, we can branch on including one of these vertices or edges into the solution; there are of them. Otherwise, we need to delete an internal vertex or an edge from some segment. Let . In the second case, we delete either (1) a vertex that is at distance at most (on the hole ) from a junction; or (2) an edge whose both endvertices are at distance at most (on the hole ) from a junction. In particular, this case must apply when we are breaking a segment of length at most . If one of the two aforementioned cases is correct, then we can identify one vertex or edge of the solution by branching. In total, there are branches we need to try.

Henceforth, we assume that none of these two cases holds. The vertex or edge we need to delete from must then belong to some segment with ; in particular, it is in the sub-path , where and . This is the third case and our main concern. Recall that any segment belongs to some maximal path of , on which and are well defined, and is a clique tree for the component of the chordal subgraph that contains . For any pair of indices with , we use to denote the union of the set of bags in the nonempty subtree of that contains , plus the two vertices and . Let be the subgraph induced by .

Claim 3

There must be some segment with such that vertices and are disconnected in .

Proof

We prove by contradiction. Suppose that for every segment with , vertices and remain connected in . We can find an induced path in , which has to visit every bag with . Appending to this path and , (which are assumed to be not impacted by the deletion of and ,) we get a path in . From we can extract an induced path of . It is also a path of . By the definition of , the path must be disjoint from . The distance between and in must be ; otherwise we have a hole shorter than (whether some internal vertex of is adjacent to or not), which is impossible. Therefore, the length of is larger than .

We have assumed that any segment of length at most remains intact in . Therefore, we have now for each segment of an induced path in . Concatenating all these paths, as well as edges of incident to , we get a closed walk , which is disjoint from . To show that is a hole, it suffices to verify that any vertex is nonadjacent to other vertices of different from its two neighbors in . By construction, belongs to some path given above, which is either in , or in some branch near to ; since none of is a junction of type (1) or (2), it follows that is not adjacent to , and thus . Suppose that besides its two neighbors in , the vertex is adjacent to another vertex in , then cannot be in and cannot be in . In other words, is in a branch near to some vertex that is at least far away from , which is impossible as is chordal. Hence, must be a hole of of length larger than . It cannot be made chordal by the addition of the at most edges of , and this contradiction proves the claim. \(\lrcorner \)

In other words, there is a segment such that (\(V^*_-, E^*_-\)) contains some inclusion-wise minimal mixed separator in . The resulting graph obtained by deleting this mixed separator from is characterized by the following claim.

Claim 4

Let , where (\(V_S, E_S\)) is an inclusion-wise minimal mixed separator in . For any with , the component of containing is simplicial in .

Proof

We argue first that is the same as the component of containing . Let be the component; note that it fully contains the path . Since is a subgraph of , it follows that . Note that no path in can be shorter than (otherwise there is a hole shorter than ). As a result, cannot contain a neighbor of : since is connected, a path will imply that . Therefore, has no neighbor in . On the other hand, a vertex in is either in or a branch near to , and hence cannot be adjacent to . Suppose for contradiction that , then we can find a neighbor of in or , but we have seen that it is not possible. Hence, , and since and (\(V_S, E_S\)) have been deleted, it can be further inferred . Then . Since and is not a junction of type (4), must be a clique. Since (\(V_S, E_S\)) is inclusion-wise minimal, no edge in is induced by . In particular, induces the same subgraph in and , which is a clique. It remains to show that induces a chordal subgraph of .

The subgraph induced by is chordal, and since every vertex in it is adjacent to some vertex in , which is not a junction of type (4), they are completely adjacent to . All other vertices in (not in ) are in some branch near to . Since these vertices are not junctions of type (3), these branches are all simplicial in . Let be such a branch; according to Lemma 3.3, is a clique, and are in and hence is a clique. Therefore, induces a chordal subgraph in . \(\lrcorner \)

A symmetric claim holds for the other side of the segment . That is, for any with , the component of that contains is simplicial in . Let (\(V^*_S, E^*_S\)), where and , be an inclusion-wise minimal mixed separator in . We now consider the subgraph obtained from by deleting (\(V^*_S, E^*_S\)), i.e., . Note that () is a minimum chordal editing set of .

Claim 5

For any mixed separator () of size at most () in , substituting () for () in () gives another minimum editing set to .

Proof

We first argue the existence of some vertex with such that contains no edge induced by . For each with , since and every vertex in them is adjacent to at most vertices of (Proposition 3.1), bags and are disjoint. In particular, an edge cannot be induced by both and . Suppose that contains an edge induced by for each with , then we must have , which is impossible. Likewise, we have some vertex with such that contains no edge induced by . By Claim 4, it follows that every vertex of is in a simplicial set of . Since (\(V^*_- {\setminus } V^*_S, E^*_- {\setminus } E^*_S, E^*_+\)) is a minimum chordal editing set to , we have by Lemma 3.4 that () does not edit any vertex of .

Suppose that there is a hole in the graph obtained by applying () to . By construction, contains a vertex of . However, by Claim 4, every vertex of is in some simplicial set of and, as (\(V^*_- {\setminus } V^*_S, E^*_- {\setminus } E^*_S, E^*_+\)) does not edit , every such vertex is in a simplical set after applying () to . Thus no vertex of is on a hole, a contradiction. \(\lrcorner \)

For any segment , we can use Corollary 4.3 to find all possible sizes of a minimum mixed separator. There are at most of them. By Claim 5, one of them can be used to compose the desired chordal editing set. In each iteration, we branch into instances to break a hole, and in each branch decreases by at least . The running time is thus . This completes the proof.\(\square \)

6 Concluding Remarks

We would like to draw attention to the similarity between chordal vertex deletion and the classic feedback vertex set problem, which asks for the deletion of at most vertices to destroy all cycles in a graph, i.e., to make the graph a forest. The ostensible relation is that the forbidden induced subgraphs of forests are precisely all holes and triangles. But triangles can be easily disposed of and their nonexistence significantly simplifies the graph structure. On the other hand, each component of a chordal graph can be represented as a clique tree, which gives another and probably better way to correlate these two problems.

Recall that vertices with degree less than two are irrelevant for feedback vertex set, while degree two vertices can also be preprocessed, and thus it suffices to consider graphs with minimum degree three. Earlier algorithms for feedback vertex set are based on some variations of the upper bounds of Erdős and Pósa [11] on the length of shortest cycles in such a graph. For chordal vertex deletion, our algorithm can be also interpreted in this way. First of all, a simplicial vertex participates in no holes, and thus can be removed safely.

Reduction 1

Remove all simplicial vertices.

Note that a simplicial vertex corresponds to a leaf in the clique tree, Reduction 1 can be viewed as a generalization of the disposal of degree-1 vertices for feedback vertex set. For feedback vertex set, we “smoothen” a degree-2 vertex by removing it and adding a new edge to connect its two neighbors. This operation shortens all cycles through this vertex and result in an equivalent instance. To have a similar reduction rule, we need an explicit clique tree,Footnote 2 so we consider the compression problem, which, given a hole cover , asks for another hole cover disjoint from . The following reduction rule will only be used after Reduction 1 is not applicable, then no vertex inside a segment can have a branch. Let denote the separator in the clique tree.

Reduction 2

Let be a segment and let have the minimum cardinality among . If there exists such that is disjoint from and there exists , then remove and insert edges to make a clique.

After both reductions are exhaustively applied, we can use an argument similar as Theorem 3.6 to show that either the length of a shortest hole is or there is no solution. Simply deleting vertices of degrees one or two already suffices to yield a linear-vertex kernel for the disjoint feedback vertex set problem, the compression variant of feedback vertex set [7]. However, for our problem it does not seem to be the case, and to furnish a polynomial kernel for even the compression variant of the chordal vertex deletion problem, we might need more than Reductions 1 and 2. We leave the existence of polynomial kernels for chordal vertex deletion and its compression variant as an open problem.

We have presented the first FPT algorithm for the general modification problem to a graph class that has an infinite number of obstructions. Following this work, the first author [6] showed that the unit interval editing problem is FPT as well. It is natural to ask for its parameterized complexity on other related graph classes, especially for those classes on which every single-operation version is already known to be FPT. The most interesting candidates would be the interval graphs.