Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems

摘要

In this work, we focus on several completion problems for subclasses of chordal graphs: MINIMUM FILL-IN, INTERVAL COMPLETION, PROPER INTERVAL COMPLETION, TRIVIALLY PERFECT COMPLETION, and THRESHOLD COMPLETION. In these problems, the task is to add at most k edges to a given graph to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related CHAIN COMPLETION PROBLEM: