A Linear Kernel for Planar Red-Blue Dominating Set

In the Red-Blue Dominating Set problem, we are given a bipartite graph \(G = (V_B \cup V_R,E)\) and an integer \(k\), and asked whether \(G\) has a subset \(D \subseteq V_B\) of at most \(k\) "blue" vertices such that each "red" vertex from \(V_R\) is adjacent to a vertex in \(D\...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-04
Main Authors: Garnero, Valentin, Sau, Ignasi, Thilikos, Dimitrios M
Format: Article
Language:English
Subjects:
Apexes
Graph theory
Kernels
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In the Red-Blue Dominating Set problem, we are given a bipartite graph \(G = (V_B \cup V_R,E)\) and an integer \(k\), and asked whether \(G\) has a subset \(D \subseteq V_B\) of at most \(k\) "blue" vertices such that each "red" vertex from \(V_R\) is adjacent to a vertex in \(D\). We provide the first explicit linear kernel for this problem on planar graphs, of size at most \(43k\).
ISSN:2331-8422