We consider structural parameterizations of several variants of DOMINATING SET in the parameter ecology program. We give improved FPT algorithms and lower bounds under well-known conjectures for DOMINATING SET and its...
详细信息
We consider structural parameterizations of several variants of DOMINATING SET in the parameter ecology program. We give improved FPT algorithms and lower bounds under well-known conjectures for DOMINATING SET and its variants in graphs that are k vertices away from a cluster graph or a split graph. These are graphs in which there is a set of k vertices (called the modulator) whose deletion results in a cluster graph or a split graph. We also call k as the deletion distance (to the appropriate class of graphs). For example, we show that when parameterized by the deletion distance k to cluster graphs: DOMINATING SET, INDEPENDENT DOMINATING SET, DOMINATING CLIQUE, EFFICIENT DOMINATING SET and TOTAL DOMINATING SET can be solved in 3knO(1)-time. Additionally, when parameterized by the deletion distance k to split graphs, we prove that EFFICIENT DOMINATING SET can be solved in 3k/2nO(1)-time breaking the 2k barrier. (c) 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Title: parameterized complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisors e-mail address: honza@*** Abstract: This thesis deals wit...
详细信息
Title: parameterized complexity Author: Ondřej Suchý Department: Department of Applied Mathematics Advisor: Prof. RNDr. Jan Kratochvíl, CSc. Advisors e-mail address: honza@*** Abstract: This thesis deals with the parameterized complexity of NP-hard graph problems. We explore the complexity of the problems in various scenarios, with respect to miscellaneous parameters and their combina- tions. Our aim is rather to classify in this multivariate manner whether the particular parameters make the problem fixed-parameter tractable or intractable than to present the algorithm achieving the best running time. In the questions we study typically the first-choice parameter is unsuccessful, in which case we propose to use less standard ones. The first family of problems investigated provides a common general- ization of many well known and studied domination and independence problems. Here we suggest using the dual parameterization and show that, in contrast to the standard solution-size, it can confine the in- evitable combinatorial explosion. Further studied problems are ana- logues of the Steiner problem in directed graphs. Here the parameter- ization by the number of terminals to be connected seems to be previ- ously unexplored in the directed setting. Unfortunately, the problems are shown to be...
We study single-machine scheduling problems where processing each job requires both processing time and rechargeable energy. Subject to a predefined energy capacity, energy can be recharged after each job during a fix...
详细信息
We study single-machine scheduling problems where processing each job requires both processing time and rechargeable energy. Subject to a predefined energy capacity, energy can be recharged after each job during a fixed recharging period. Our focus is on two due date-related scheduling criteria: minimizing the number of late jobs and maximizing the weighted number of jobs completed exactly at their due dates. This study aims to analyze the parameterized tractability of the two problems and develop fixed-parameter algorithms. with respect to three natural parameters the number of different due dates, the number of different processing times, and the number of different energy consumptions. Following the proofs of NP-hardness across several contexts, we demonstrate that both problems remain intractable when parameterized by and . To complement our results, we show that both problems become fixed-parameter tractable (FPT) when parameterized by u, and, and are solvable in polynomial time when both, Ve and, vp are constant.
We study the Shortest Path problem subject to positive binary disjunctive constraints. In positive disjunctive constraints, there are certain pairs of edges such that at least one edge from every pair must be part of ...
详细信息
We compare the fixed parameter complexity of various variants of coloring problems (including LIST COLORING, PRECOLORING EXTENSION, EQUITABLE COLORING, L(p, 1)-LABELING and CHANNEL ASSIGNMENT) when parameterized by tr...
详细信息
We compare the fixed parameter complexity of various variants of coloring problems (including LIST COLORING, PRECOLORING EXTENSION, EQUITABLE COLORING, L(p, 1)-LABELING and CHANNEL ASSIGNMENT) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems. (C) 2010 Elsevier B.V. All rights reserved.
Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border M...
详细信息
Microarrays are research tools used in gene discovery as well as disease and cancer diagnostics. Two prominent but challenging problems related to microarrays are the Border Minimization Problem (BMP) and the Border Minimization Problem with given placement (P-BMP). The common task of these two problems is to create so-called probe sequences (essentially a string) in a microarray. Here, the goal of the former problem is to determine an assignment of each probe sequence to a unique cell of the array and afterwards to construct the sequences at their respective cells while minimizing the border length of the probes. In contrast, for the latter problem the assignment of the probes to the cells is already given. In this paper we investigate the parameterized complexity of the natural exhaustive variants of BMP and P-BMP, termed BMPe and P-BMPe respectively, under several natural parameters. We show that BMPe and P-BMPe are in FPT under the following two combinations of parameters: (1) the size of the alphabet (c), the maximum length of a sequence (string) in the input () and the number of rows of the microarray (r);and, (2) the size of the alphabet and the size of the border length (o). Furthermore, P-BMPe is in FPT when parameterized by c and . We complement our tractability results with a number of corresponding hardness results.
We study the parameterized complexity of computing nontrivial automorphisms of weight k for a given hypergraph X = (V, E), with k as fixed parameter, where the weight of a permutation pi is an element of S-n is the nu...
详细信息
We study the parameterized complexity of computing nontrivial automorphisms of weight k for a given hypergraph X = (V, E), with k as fixed parameter, where the weight of a permutation pi is an element of S-n is the number of points moved by pi. Building on the earlier work of Schweitzer (in: Proceedings of 19th ESA, Springer, Berlin, 2011. https://***/10.1007/978-3-642-23719-5_32), we show the following results: (1) Computing nontrivial automorphisms of weight at most k for d-hypergraphs (that is, with edge-size bounded by d) remains fixed parameter tractable, with d treated as a second fixed parameter. Likewise, finding isomorphisms of weight k between d-hypergraphs X and Y (both defined on vertex set [n]) remains fixed parameter tractable. (2) For dealing with the exact weight k version of the problem, we introduce a more general algorithmic problem PERMCODE: given a permutation group G by a generating set and a fixed parameter k, is there is a nontrivial element of G with support at most (or exactly) k? We give a method for shrinking large orbits of the given group G to obtain subgroups while maintaining existence of weight at most k elements in it. An application of this yields an FPT algorithm for finding exact weight k nontrivial automorphisms in d-hypergraphs, d as second fixed parameter. (3) For hypergraphs with edges of unbounded size, we show that the problem is in FPTGI. (4) Computing d-hypergraph isomorphisms of weight exactly k is fixed parameter tractable. This requires a more complicated orbit shrinking technique.
SET COVER is one of the well-known classical NP-hard problems. We study the conflict-free version of the SET COVER problem. Here we have a universe U, a family F of subsets of U and a graph G(F) on the vertex set F an...
详细信息
SET COVER is one of the well-known classical NP-hard problems. We study the conflict-free version of the SET COVER problem. Here we have a universe U, a family F of subsets of U and a graph G(F) on the vertex set F and we look for a subfamily F' subset of F of minimum size that covers U and also forms an independent set in G(F). We study conflict-free SET COVER in parameterized complexity by restricting the focus to the variants where SET COVER is fixed parameter tractable (FPT). We give upper bounds and lower bounds for the running time of conflict-free version of SET COVER with and without duplicate sets along with restrictions to the graph classes of G(F). For example, when pairs of sets in F intersect in at most one element, for a solution of size k, we give an f (k)vertical bar F vertical bar(o(k)) lower bound for any computable function f assuming ETH even if G(F) is bipartite, but an O*(3(k2)) FPT algorithm (O* notation ignores polynomial factors of input) when G(F) is chordal.
In this paper, we study the parameterized complexity of DOMINATING SET problem in chordal graphs and near chordal graphs. We show the problem is W[2]hard and cannot be solved in time n(o(k)) in chordal and s-chordal (...
详细信息
In this paper, we study the parameterized complexity of DOMINATING SET problem in chordal graphs and near chordal graphs. We show the problem is W[2]hard and cannot be solved in time n(o(k)) in chordal and s-chordal (s > 3) graphs unless W[1] = FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal and near chordal graphs. Our results prove that unless NP = P, the minimum dominating set in a chordal or s-chordal (s > 3) graph cannot be approximated within a ratio of c/3 ln n in polynomial time, where n is the number of vertices in the graph and 0 < c < 1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar results for the INDEPENDENT DOMINATING SET problem and the CONNECTED DOMINATING SET problem in chordal or near chordal graphs.
We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the dist...
详细信息
We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance between any two vertices in H is at most t times the distance between these vertices in G, that is, H keeps the distances in G up to the distortion (or stretch) factor t. An additive t-spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter t, that is, the distances in H and G differ by at most t. The task of Directed Multiplicative Spanner is, given a directed graph G with m arcs and positive integers t and k, decide whether G has amultiplicative t-spanner with at most m-k arcs. Similarly, Directed Additive Spanner asks whether G has an additive t-spanner with at most m-k arcs. We show that (i) Directed Multiplicative Spanner admits a polynomial kernel of size O(k(4)t(5)) and can be solved in randomized (4t)(k) . n(O(1)) time, (ii) the weighted variant of DIRECTED MULTIPLICATIVE SPANNER can be solved in k(2k) . n(O(1)) time on directed acyclic graphs, (iii) Directed Additive Spanner is W[1]-hard when parameterized by k for every fixed t >= 1 evenwhen the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is FPT when parameterized by t and k.
暂无评论