ALCOMFT-TR-01-113

Hans L. Bodlaender
Necessary edges in k-chordalizations of graphs
Utrecht. Work package 4. May 2001.

Abstract: In this note, we look at which edges must always be added to a given graph G=(V,E), when we want to make it a chordal graph with maximum clique size at most k by adding edges. lThis problem has a strong relation to the (algorithmic) theory of the treewidth of graphs. If {x,y} is an edge in every chordal supergraph of G with maximum clique size at most k, we call the pair necessary for treewidth k. Some sufficient, or necessary and sufficient conditions are given for pairs of vertices to be necessary for treewidth k. For a fixed k, the set of all edges that always must be added when making the graph chordal with maximum clique size <= k, can be found in linear time. If k is given as part of the input, then this problem is coNP-hard. A few similar results are given when interval graphs (and hence pathwidth) are used instead of chordal graphs and treewidth.

Postscript file: ALCOMFT-TR-01-113.ps.gz (81 kb).