We introduce a variant of the graph coloring problem, which we denote as Budgeted Coloring Problem (BCP). Given a graph G, an integer c and an ordered list of integers {b(1), b(2),..., b(c)}, BCP asks whether there ex...
详细信息
ISBN:
(纸本)9783030967307;9783030967314
We introduce a variant of the graph coloring problem, which we denote as Budgeted Coloring Problem (BCP). Given a graph G, an integer c and an ordered list of integers {b(1), b(2),..., b(c)}, BCP asks whether there exists a proper coloring of G where the i-th color is used to color at most b(i) many vertices. This problem generalizes two well-studied graph coloring problems, BOUNDED COLORING PROBLEM (BoCP) and EQUITABLE COLORING PROBLEM (ECP), and as in the case of other coloring problems, BCP is NP-hard even for constant values of c. So we study BCP under the paradigm of parameterized complexity, particularly with respect to (structural) parameters that specify how far (the deletion distance) the input graph is from a tractable graph class. - We show that BCP is FPT (fixed-parameter tractable) parameterized by the vertex cover size. This generalizes a similar result for ECP and immediately extends to the BoCP, which was earlier not known. - We show that BCP is polynomial time solvable for cluster graphs generalizing a similar result for ECP. However, we show that BCP is FPT, but unlikely to have polynomial kernel, when parameterized by the deletion distance to clique, contrasting the linear kernel for ECP for the same parameter. - While the BoCP is known to be polynomial time solvable on split graphs, we show that BCP is NP-hard on split graphs. We also show that BCP is NP-hard on co-cluster graphs, contrasting the polynomial time algorithm for ECP and BoCP. Finally we present an O*(2(|V(G)|)) algorithm for the BCP, generalizing the known algorithm with a similar bound for the standard chromatic number.
We give a new general approach for designing exactexponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to dete...
详细信息
We give a new general approach for designing exactexponential-time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is Weighted d-SAT. Here, the input is a CNF-formula with clauses of size at most d, and an integer W. The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on "monotone local search," where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem, we are also given as input a subset X of the universe and an integer k. The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c(k)n(O(1)) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O((2 - 1/c)(n)). In many cases, the extension problem can be reduced to simply finding a solution of size at most k. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including d-HITTING SET, FEEDBACK VERTEX SET, NODE UNIQE LABEL COVER, and WEIGHTED d-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exactexponential-time algorithms. We also show how to derandomize our algorithms at the cost of a subexponential multiplic
暂无评论