We study the parameterized complexity of k-PERFECT CODE in graphs without small cycles. We show that k-PERFECT CODE is W[1]-hard in bipartite graphs and thus in graphs with girth 4. On the other hand, we show that k-PERFECT CODE admits a k~2 + k kernel in graphs with girth ≥ 5.
展开▼
