5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Florent Foucaud Jun 19 '12 at 13:24
9
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.