The \textsc{Red-Blue Separation} problem on graphs

DOI10.1016/J.TCS.2023.114061MaRDI QIDQ6168089zbMATH OpenOpenAlexFDO

Authors S. Dev, Sanjana Dey, Florent Foucaud, Ralf Klasing, Tuomo Lehtilä

Publication date 8 August 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.08283

zbMATH Keywords

dominating setsidentifying codesseparating sets

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We introduce the Red-Blue Separation problem on graphs, where we are given a graph $G=(V,E)$ whose vertices are colored either red or blue, and we want to select a (small) subset $SsubseteqV$, called red-blue separating set, such that for every red-blue pair of vertices, there is a vertex $sinS$ whose closed neighborhood contains exactly one of the two vertices of the pair. We study the computational complexity of Red-Blue Separation, in which one asks whether a given red-blue colored graph has a red-blue separating set of size at most a given integer. We prove that the problem is NP-complete even for restricted graph classes. We also show that it is always approximable in polynomial time within a factor of $2lnn$, where $n$ is the input graph's order. In contrast, for triangle-free graphs and for graphs of bounded maximum degree, we show that Red-Blue Separation is solvable in polynomial time when the size of the smaller color class is bounded by a constant. However, on general graphs, we show that the problem is $W[2]$-hard even when parameterized by the solution size plus the size of the smaller color class. We also consider the problem Max Red-Blue Separation where the coloring is not part of the input. Here, given an input graph $G$, we want to determine the smallest integer $k$ such that, for every possible red-blue coloring of $G$, there is a red-blue separating set of size at most $k$. We derive tight bounds on the cardinality of an optimal solution of Max Red-Blue Separation, showing that it can range from logarithmic in the graph order, up to the order minus one. We also give bounds with respect to related parameters. For trees however we prove an upper bound of two-thirds the order. We then show that Max Red-Blue Separation is NP-hard, even for graphs of bounded maximum degree, but can be approximated in polynomial time within a factor of $O(l{n}^{2}n)$.

Cites work

• scientific article; zbMATH DE number 3161569 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• A simplified NP-complete satisfiability problem
• An induced subgraph characterization of domination perfect graphs
• Analytical approach to parallel repetition
• Approximation algorithms for the test cover problem
• Discriminating codes in bipartite graphs: Bounds, extremal cardinalities, complexity
• Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs
• Extremal graphs for the identifying code problem
• Hardness results and approximation algorithms for identifying codes and locating-dominating codes in graphs
• Identification of points using disks
• Identifying codes in hereditary classes of graphs and VC-dimension
• Induced subsets
• Locating and total dominating sets in trees
• On a new class of codes for identifying vertices in graphs
• On separating points by lines
• On separating systems
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the parameterized complexity of red-blue points separation
• Parameterizations of test cover with bounded test sizes
• Parameterized graph separation problems
• Revisiting and improving upper bounds for identifying codes
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• The Complexity of Multiterminal Cuts
• The \textsc{red-blue separation} problem on graphs

Cited in

(3)

• On approximability of optimization problems related to red/blue-split graphs
• Optimal local identifying and local locating-dominating codes
• On the Red/Blue Spanning Tree Problem

This page was built for publication: The \textsc{Red-Blue Separation} problem on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6168089)