# What is the complexity of chordalization?

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, $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? }

• 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 Jun 19 '12 at 13:24

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.
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.