5 research outputs found
The Weighted k-Center Problem in Trees for Fixed k
No full textWe present a linear time algorithm for the weighted k-center problem on trees for fixed k. This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O(n log n) by Wang et al. [Haitao Wang and Jingru Zhang, 2018]. Whether an O(n) time algorithm exists for arbitrary k is still open
The weighted k-center problem in trees for fixed k
No full textWe present a linear time algorithm for the weighted k-center problem on trees for fixed k. This partially settles the long-standing question about the lower bound on the time complexity of the problem. The current time complexity of the best-known algorithm for the problem with k as part of the input is O(nlogn) by Wang et al. (2018) [20]. Whether an O(n) time algorithm exists for arbitrary k is still open
The Red-Blue Separation Problem on Graphs
No full textInternational audienceWe introduce the Red-Blue Separation problem on graphs, where we are given a graph whose vertices are colored either red or blue, and we want to select a (small) subset , called red blue separating set , such that for every red-blue pair of vertices, there is a vertex 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 , where 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 , we want to determine the smallest integer such that, for every possible red-blue-coloring of , there is a red-blue separating set of size at most . 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
