<p>One characterization of chordal graphs is that they have a so-called elimination ordering: You always find a simplicial vertex (i.e., neighbors form a clique) and upon deletion of it you again have a chordal graph. This gives an ordering such that the neighbors with higher number must form a clique.</p>

<p>Now to get a chordal graph, fix any vertex ordering in G and vertex by vertex make the neighborhood a clique and delete the vertex. The set of introduced edges will make $G$ chordal (also called a fill-in). Thus, your first question is efficiently solvable.</p>

<p>Finding the minimum fill-in (minimum number of edges to make a graph chordal) is NP-complete.</p>

<p>For the second one, I'm not so sure. First of all, it should be easy to construct graphs $G$ where no chordalization without new $K_4$ is possible. In fact, if you have a biclique (two independent sets with all possible edges between them) then you have to make one side a clique. Furthermore, the treewidth of $G$ is the minimum clique size minus one over all chordalizations $H$ of $G$. The Treewidth problem is NP-complete. Finding graphs $H$ that have essentially the same cliques as $G$ therefore seems hard. Hence, my guess(!) is that this is NP-hard to find if it exists.</p>

CC BY-SA 3.0
2012-06-19T11:34:10.577Z
2012-06-19T13:21:00.657Z
2012-06-19T13:21:00.657Z
Stefan Kratsch
<p>If the graph doesn't already have any K4, then Q2 is the same as asking for whether the graph has treewidth at most two. This is easy to check in linear time: it's true iff every biconnected component is series-parallel.</p>

CC BY-SA 3.0
2012-06-19T17:23:22.077Z
2012-06-19T17:23:22.077Z
David Eppstein
<p>A graph $G=(V,E)$ is a chordal graph, if it does not contain an induced
cycle of length at least four. We say a graph $H$ is a chordalization of graph
$G$, if $H$ contains $G$ as a subgraph, and $H$ is chordal. </p>

<p>$Q_1$: Find <em>minimum number</em> of edges whose addition to a given graph makes the graph a chordal graph.</p>

<p>According to <a href="http://www.cse.cuhk.edu.hk/~lcai/papers/graph-modify.pdf" rel="nofollow">this</a>, $Q_1$ is NP-hard.</p>

<p>$Q_2$: Find a chordalization that does not introduce new $K_4$? </p>

<p>What is the complexity of $Q_2$? Is $Q_2$ harder than $Q_1$?</p>

<p>{
Remark: After Florent comment, I changed $Q_1$ from the following: </p>

<p>$Q_1$ in first version of my post: What is the complexity of giving an arbitrary chordalization of input graph?
}</p>

CC BY-SA 3.0
2012-06-19T13:24:01.207Z
Since a complete graph is chordal, if you're looking for an arbitrary chordalization, I guess that adding all possible edges will suffice for your first question!
Florent Foucaud
<cc.complexity-theory><graph-theory><graph-algorithms>
What is the complexity of chordalization?
j.s.
# What is the complexity of chordalization?

(Asked by: username_0 on 2012-06-19)

A graph $G=(V,E)$ is a chordal graph, if it does not contain an induced
cycle of length at least four. We say a graph $H$ is a chordalization of graph
$G$, if $H$ contains $G$ as a subgraph, and $H$ is chordal.

$Q\_1$: Find *minimum number* of edges whose addition to a given graph makes the graph a chordal graph.

According to [this](http://www.cse.cuhk.edu.hk/~lcai/papers/graph-modify.pdf), $Q\_1$ is NP-hard.

$Q\_2$: Find a chordalization that does not introduce new $K\_4$?

What is the complexity of $Q\_2$? Is $Q\_2$ harder than $Q\_1$?

{
Remark: After Florent comment, I changed $Q\_1$ from the following:

$Q\_1$ in first version of my post: What is the complexity of giving an arbitrary chordalization of input graph?
}

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Since a complete graph is chordal, if you're looking for an arbitrary chordalization, I guess that adding all possible edges will suffice for your first question!  

---

## 2 answers

### Answer by username_3 on 2012-06-19. Score: 9 | Accepted answer

If the graph doesn't already have any K4, then Q2 is the same as asking for whether the graph has treewidth at most two. This is easy to check in linear time: it's true iff every biconnected component is series-parallel.


---

### Answer by username_2 on 2012-06-19. Score: 4

One characterization of chordal graphs is that they have a so-called elimination ordering: You always find a simplicial vertex (i.e., neighbors form a clique) and upon deletion of it you again have a chordal graph. This gives an ordering such that the neighbors with higher number must form a clique.

Now to get a chordal graph, fix any vertex ordering in G and vertex by vertex make the neighborhood a clique and delete the vertex. The set of introduced edges will make $G$ chordal (also called a fill-in). Thus, your first question is efficiently solvable.

Finding the minimum fill-in (minimum number of edges to make a graph chordal) is NP-complete.

For the second one, I'm not so sure. First of all, it should be easy to construct graphs $G$ where no chordalization without new $K\_4$ is possible. In fact, if you have a biclique (two independent sets with all possible edges between them) then you have to make one side a clique. Furthermore, the treewidth of $G$ is the minimum clique size minus one over all chordalizations $H$ of $G$. The Treewidth problem is NP-complete. Finding graphs $H$ that have essentially the same cliques as $G$ therefore seems hard. Hence, my guess(!) is that this is NP-hard to find if it exists.


---

