What is the complexity of chordalization?

Question

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

Answer 1

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 2

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.