Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MINIMUM CHORDAL GRAPH COMPLETION

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A chordal graph completion, i.e., a superset E' containing E such that $G'=\left(V,E'\right)$ is chordal, that is, for every simple cycle of more than 3 vertices in G', there is some edge in E' that is not involved in the cycle but that joins two vertices in the cycle.
• MEASURE: The size of the completion, i.e., $\vert E' - E\vert$.

  
  

• Good News: Approximable within $O(\vert V\vert)$ [384].
• Comment: Also known as Minimum Fill-in. Approximable within $O(\mbox{\sl opt})$ [384], where $\mbox{\sl opt}$ denotes the minimum number of fill edges needed. Approximable within $O(\sqrt{\Delta} \log^4 \vert V\vert)$ for graphs with bounded degree $\Delta$ [322], and within $O(\Delta^{2.5} \log^4 (\mbox{\sl opt}d))$ [384]. See results on related problems under MINIMUM TREE WIDTH.
• Garey and Johnson: OPEN4