Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy

摘要

We present new results on the parameterized complexities of k-Vertex Clique Partition and k-SEPARATING Vertices in multiple-interval graphs and their complements, and present a very simple alternative proof of the W[1]-hardness of k-IRREDUNDANT Set in general graphs.