There is substantial literature dealing with fixedparameteralgorithms for the dominating set problem on various families of graphs. In this paper, we give a k (O(dk)) n time algorithm for finding a dominating set of...
详细信息
ISBN:
(纸本)9783540735441
There is substantial literature dealing with fixedparameteralgorithms for the dominating set problem on various families of graphs. In this paper, we give a k (O(dk)) n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parametertractable for degenerated graphs. For graphs that do not contain K (h) as a topological minor, we give an improved algorithm for the problem with running time (O(h)) (hk) n. For graphs which are K (h) -minor-free, the running time is further reduced to (O(log h)) (hk/2) n. fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(nlog n) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs.
We investigate a generalization of the classical FEEDBACK VERTEX SET (FVS) problem from the point of view of parameterized algorithms. INDEPENDENT FEEDBACK VERTEX SET (IFVS) is the "independent" variant of t...
详细信息
ISBN:
(纸本)9783642226847
We investigate a generalization of the classical FEEDBACK VERTEX SET (FVS) problem from the point of view of parameterized algorithms. INDEPENDENT FEEDBACK VERTEX SET (IFVS) is the "independent" variant of the FVS problem and is defined as follows: given a graph G and an integer k, decide whether there exists F subset of V (G), vertical bar F vertical bar <= k, such that G[V(G)\F] is a forest and G[F] is an independent set;the parameter is k. Note that the similarly parameterized version of the FVS problem - where there is no restriction on the graph G[F] - has been extensively studied in the literature. The connected variant CFVS - where G[F] is required to be connected - has received some attention as well. The FVS problem easily reduces to the IFVS problem in a manner that preserves the solution size, and so any algorithmic result for IFVS directly carries over to FVS. We show that IFVS can be solved in O(5(k)n(O(1))) time, where n is the number of vertices in the input graph G, and obtain a cubic (O(k(3))) kernel for the problem. Note the contrast with the CFVS problem, which does not admit a polynomial kernel unless CoNP subset of NP/Poly. (c) 2012 Elsevier B.V. All rights reserved.
This paper introduces a novel parameter, called iterated type partition, that can be computed in polynomial time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring...
详细信息
ISBN:
(纸本)9783030489656;9783030489663
This paper introduces a novel parameter, called iterated type partition, that can be computed in polynomial time and nicely places between modular-width and neighborhood diversity. We prove that the Equitable Coloring problem is W[1]-hard when parametrized by the iterated type partition. This result extends to modular-width, answering an open question on the complexity of Equitable Coloring when parametrized by modular-width. On the contrary, we show that the Equitable Coloring problem is FPT when parameterized by neighborhood diversity. Furthermore, we present a scheme for devising FPT algorithmsparameterized by iterated type partition, which enables us to find optimal solutions for several graph problems. While the considered problems are already known to be FPT with respect to modular-width, the novel algorithms are both simpler and more efficient. As an example, in this paper, we give an algorithm for the Dominating Set problem that outputs an optimal set in time O(2(t) + poly(n)), where n and t are the size and the iterated type partition of the input graph, respectively.
The domination number of a graph C = (V, E) is the minimum size of a dominating set U C V. which satisfies that every vertex in V \ U is adjacent to at least one vertex in U. The notion of a problem kernel refers to a...
详细信息
ISBN:
(纸本)9783642112683
The domination number of a graph C = (V, E) is the minimum size of a dominating set U C V. which satisfies that every vertex in V \ U is adjacent to at least one vertex in U. The notion of a problem kernel refers to a polynomial time algorithm that achieves some provable reduction of the input size. Given a graph C whose domination number is k, the objective is to design a polynomial time algorithm that produces a graph C-n whose size depends only on k, and also has domination number equal to k. Note that the graph C' is constructed without knowing the value of k. All the constructions in this paper are of monotone kernels, that is, the kernel G' is a subgraph of the input graph G. Problem kernels can be used to obtain efficient;approximation and exact algorithms for the domination number, and are also useful in practical settings. In this paper, we present the first nontrivial result for the general case of graphs with an excluded minor, as follows. For every fixed h, given a graph G with n vertices that does not contain K-h as a topological minor, our O(n(3.5) + kO((1))) time algorithm constructs a subgraph C' of G, such that if the domination number of C is k, then the domination number of G' is also k and C' has at most k(c) vertices, where c is a constant that depends only on h. This result is improved for graphs that do not contain K-3,K-h as a topological minor, using a simpler algorithm that constructs a subgraph with at most ck vertices, where c is a constant;that depends only on h. Our results imply that there is a problem kernel of polynomial size for graphs with an excluded minor and a linear kernel for graphs that are K-3,K-5-minor-free. The only previous kernel results known for the dominating set problem are the existence of a linear kernel for the planar case as well as for graphs of bounded genus. Using the polynomial kernel construction, we give an O(n(3.5) + 2O(root k)) time algorithm for finding a dominating set of size at most k in an H-minor-fr
We study new generalizations of the classic capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions in which the total production (or transportation) capa...
详细信息
We study new generalizations of the classic capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions in which the total production (or transportation) capacity in each time period is the summation of capacities of a subset of n available modules (machines or vehicles) of different capacities. We refer to this problem as Multi-module Capacitated Lot-Sizing Problem without or with Subcontracting, and denote it by MCLS or MCLS-S, respectively. These are NP-hard problems if n is a part of the input and polynomially solvable for n = 1. In this article we address an open question: Does there exist a polynomial time exact algorithm for solving the MCLS or MCLS-S with fixed n >= 2? We present exact fixed-parametertractable (polyno-mial) algorithms that solve MCLS and MCLS-S in O(T2n+3) time for a given n > 2: It generalizes algo-rithm of Atamtu euro rk and Hochbaum [Management Science 47(8):1081-1100, 2001] for MCLS-S with n = 1. We also present exact algorithms for two-generalizations of the MCLS and MCLS-S: (a) a lot-siz-ing problem with piecewise concave production cost functions (denoted by LS-PC-S) that takes O(T2m+3) time, where m is the number of breakpoints in these functions, and (b) two-echelon MCLS that takes O(T4n+4) time. The former reduces run time of algorithm of Koca et al. [INFORMS J. on Computing 26(4):767-779, 2014] for LS-PC-S by 93.6%, and the latter generalizes algorithm of van Hoesel et al. [Management Science 51(11):1706-1719, 2005] for two-echelon MCLS with n =1. We per-form computational experiments to evaluate the efficiency of our algorithms for MCLS and LS-PC-S and their parallel computing implementation, in comparison to Gurobi 9.1. The results of these experi-ments show that our algorithms are computationally efficient and stable. Our algorithm for MCLS-S addresses another open question related to the existence of a polynomial time algorithm for optimiz-ing a linear function over n
We study new generalizations of the classic capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions in which the total production (or transportation) capa...
详细信息
We study new generalizations of the classic capacitated lot-sizing problem with concave production (or transportation), holding, and subcontracting cost functions in which the total production (or transportation) capacity in each time period is the summation of capacities of a subset ofnavailable modules (machines or vehicles) of different capacities. We refer to this problem asMulti-moduleCapacitatedLot-Sizing Problem without or withSubcontracting, and denote it by MCLS or MCLS-S, respectively. These are NP-hard problems ifnis a part of the input and polynomially solvable forn= 1. In this article we address an open question:Does there exist a polynomial time exact algorithm for solving the MCLS or MCLS-S with fixedn≥2?We present exact fixed-parametertractable (polynomial) algorithms that solve MCLS and MCLS-S inO(T2n+3)time for a givenn≥*** generalizes algorithm of Atamtürk and Hochbaum [Management Science 47(8):1081–1100, 2001] for MCLS-S withn= 1. We also present exact algorithms for two-generalizations of the MCLS and MCLS-S: (a) a lot-sizing problem with piecewise concave production cost functions (denoted by LS-PC-S) that takesO(T2m+3)time, wheremis the number of breakpoints in these functions, and (b) two-echelon MCLS that takesO(T4n+4)time. The former reduces run time of algorithm of Koca et al. [INFORMS J. on Computing 26(4):767–779, 2014] for LS-PC-S by 93.6%, and the latter generalizes algorithm of van Hoesel et al. [Management Science 51(11):1706–1719, 2005] for two-echelon MCLS withn= 1. We perform computational experiments to evaluate the efficiency of our algorithms for MCLS and LS-PC-S and their parallel computing implementation, in comparison to Gurobi 9.1. The results of these experiments show that our algorithms are computationally efficient and stable. Our algorithm for MCLS-S addresses another open question related to the existence of a polynomial time algorithm for optimizing a linear function overn-mixing set (a generalization of the well-kn
暂无评论