The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each...
详细信息
The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem (Bar-Noy et al. STOC 2001) and also a QPTAS (Hohn et al. ICALP 2018). In this paper we study fixed-parameteralgorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slighly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of f (k) center dot n(O epsilon)(1) that outputs a solution with at most (1 + tasks or asserts that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times. We show that the other two algorithms extend also to the weighted case of the problem, at the expense of losing a factor of 1 + in the cost of the selected tasks.
Recent research has revealed new applications of network control science within bio-medicine, pharmacology, and medical therapeutics. These new insights and new applications generated in turn a rediscovery of some old...
详细信息
ISBN:
(纸本)9783319919386;9783319919379
Recent research has revealed new applications of network control science within bio-medicine, pharmacology, and medical therapeutics. These new insights and new applications generated in turn a rediscovery of some old, unresolved algorithmic questions, this time with a much stronger motivation for their tackling. One of these questions regards the so-called Structural Target Control optimization problem, known in previous literature also as Structural Output Controllability problem. Given a directed network (graph) and a target subset of nodes, the task is to select a small (or the smallest) set of nodes from which the target can be independently controlled, i.e., it can be driven from any given initial configuration to any desired final one, through a finite sequence of input values. In recent work, this problem has been shown to be NP-hard, and several heuristic algorithms were introduced and analyzed, both on randomly generated networks, and on bio-medical ones. In this paper, we show that the Structural Target Controllability problem is fixedparameter tractable when parameterized by the number of target nodes. We also prove that the problem is hard to approximate at a factor better than O(log n).
The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each...
详细信息
ISBN:
(纸本)9783959771405
The Unsplittable Flow Cover problem (UFP-cover) models the well-studied general caching problem and various natural resource allocation settings. We are given a path with a demand on each edge and a set of tasks, each task being defined by a subpath and a size. The goal is to select a subset of the tasks of minimum cardinality such that on each edge e the total size of the selected tasks using e is at least the demand of e. There is a polynomial time 4-approximation for the problem [Bar-Noy et al., STOC 2000] and also a QPTAS [Hahn et al., ICALP 2014]. In this paper we study fixed-parameteralgorithms for the problem. We show that it is W[1]-hard but it becomes FPT if we can slightly violate the edge demands (resource augmentation) and also if there are at most k different task sizes. Then we present a parameterized approximation scheme (PAS), i.e., an algorithm with a running time of f((k)).n(O epsilon(1)) that outputs a solution with at most (1 + epsilon)k tasks or assert that there is no solution with at most k tasks. In this algorithm we use a new trick that intuitively allows us to pretend that we can select tasks from OPT multiple times.
We consider connectivity-augmentation problems in a setting where each potential new edge has a non-negative cost associated with it, and the task is to achieve a certain connectivity target with at most p new edges o...
详细信息
We consider connectivity-augmentation problems in a setting where each potential new edge has a non-negative cost associated with it, and the task is to achieve a certain connectivity target with at most p new edges of minimum total cost. The main result is that the minimum cost augmentation of edge-connectivity from k - 1 to k with at most p new edges is fixed-parameter tractable parameterized by p and admits a polynomial kernel. We also prove the fixed-parameter tractability of increasing edge connectivity from 0 to 2 and increasing node connectivity from 1 to 2.
We study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. We focus on the PLANAR MAXIMUM NONSEPARATING INDEPENDENT SET problem, where given a planar graph and an integer k one h...
详细信息
We study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. We focus on the PLANAR MAXIMUM NONSEPARATING INDEPENDENT SET problem, where given a planar graph and an integer k one has to find an independent set of size k whose removal leaves the graph connected. Our main result is a kernel of size at most 9k vertices for this problem. A direct consequence of this result is that PLANAR CONNECTED VERTEX COVER has no kernel with at most (9/8 - epsilon)k vertices, for any epsilon > 0, assuming P not equal NP. As a by-product we show extremal graph theory results which might be of independent interest. We prove that graphs that contain no separator consisting of only degree two vertices contain (a) a spanning tree with at least n/4 leaves and (b) a nonseparating independent set of size at least n/9 (also, equivalently, a connected vertex cover of size at most 8/9n). The result (a) is a generalization of a theorem of Kleitman and West [12] who showed the same bound for graphs of minimum degree three. Finally, we show that every n-vertex outerplanar graph contains an independent set I and a collection of vertex-disjoint cycles C such that 9 vertical bar I vertical bar >= 4n - 3 vertical bar C vertical bar. (C) 2013 Elsevier B.V. All rights reserved.
In this paper, we obtain linear time algorithms to determine the acyclic chromatic number, the star chromatic number, the non repetitive chromatic number and the clique chromatic number of P-4-tidy graphs and (q, q - ...
详细信息
In this paper, we obtain linear time algorithms to determine the acyclic chromatic number, the star chromatic number, the non repetitive chromatic number and the clique chromatic number of P-4-tidy graphs and (q, q - 4)-graphs, for every fixed q, which are the graphs such that every set with at most q vertices induces at most q - 4 distinct P-4's. These classes include cographs and P-4-sparse graphs. We also obtain a linear time algorithm to compute the harmonious chromatic number of connected P-4-tidy graphs and connected (q, q - 4)-graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixedparameter tractable on the parameter q(G), which is the minimum q such that G is a (q, q - 4)-graph. We also prove that every connected (q, q - 4)-graph with at least q vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive, generalizing the main result of Lyons (2011).
Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard ...
详细信息
Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the MAXIMUM INDEPENDENT SET problem, a parameterized and a counting version of d-HITTING SET and the MAXIMUM INDUCED CLUSTER SUBGRAPH problem. (C) 2009 Elsevier B.V. All rights reserved.
In the paper, we study three related problems, the closest strung problem, the farthest string problem and the distinguishing string selection problem. These problems have applications in motif detection, binding site...
详细信息
ISBN:
(纸本)9783642022692
In the paper, we study three related problems, the closest strung problem, the farthest string problem and the distinguishing string selection problem. These problems have applications in motif detection, binding sites locating, genetic drug target identification, genetic probes design, universal PCR primer design, etc. They have been extensively studied in recent years. The problems are defined as follows: THE CLOSEST STRING PROBLEM: given a group of strings B = {s(1), s(2),..., s(n)}, each of length L, and an integer d, the problem is to compute a center string s of length L such that the Hamming distance d(s,s(i)) <= d for all s(y) is an element of B. THE FARTHEST STRING PROBLEM: given a group of strings G = {g(1), g(2),..., g(n2)};with all strings of the same length L, and an integer d(b), the FARTHEST STRING problem is to compute a center string s of length L such that the Hamming distance d(s, g(j)) >= L - d(b) for all g(j) is an element of G. THE DISTINGUISHING STRING SELECTION PROBLEM: given two groups of strings B (bad genes) and G (good genes), B = {s(1), s(2),..., s(n1)} and G = {g(n1+1), g(n1+2),...., g(n2)}, with all strings of the same length L, and two integers d(b) and d(g) with d(g) >= L - d(b), the Distinguishing String Selection problem is to compute a center string s of length L such that the Hamming distance d(s, s(i)) <= d(b), for all S-i is an element of B and the Hamming distance d(s,g(j)) >= d(g) for all g(j) is an element of G. Our results: We design an O(Ln + nd(|Sigma - 1|)(d)2(3.25d)) time fixedparameter algorithm for the closest string problem which improves upon the best known O(Ln + nd2(4d) x (|Sigma| - 1)(d)) algorithm in [14], where |Sigma| is the size of the alphabet. We also design fixed parameter algorithms for both the farthest string problem and the distinguishing string selection problem. Both algorithms run in time O(Ln + nd2(3.25db)) when the input strings are binary strings over Sigma = {0, 1}.
The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete if H has more than two vertices in some connected component. In the framework of parameterized complexity, we analyze a ...
详细信息
The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete if H has more than two vertices in some connected component. In the framework of parameterized complexity, we analyze a particular family of instances of this problem, namely the packing of stars. We give a quadratic kernel for packing k copies of H = K-1,K-s,,. When we consider the special case of s = 2, i.e. H being a star with two leaves, we give a linear kernel and an algorithm running in time sigma(2(5.30)vertical bar(k)k(2.5) + n(3)). (c) 2005 Elsevier B.V. All rights reserved.
The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete if H has more than two vertices in some connected component. In the framework of parameterized complexity, we analyze a ...
详细信息
ISBN:
(纸本)9783540230717
The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete if H has more than two vertices in some connected component. In the framework of parameterized complexity, we analyze a particular family of instances of this problem, namely the packing of stars. We give a quadratic kernel for packing k copies of H = K-1,K-s,,. When we consider the special case of s = 2, i.e. H being a star with two leaves, we give a linear kernel and an algorithm running in time sigma(2(5.30)vertical bar(k)k(2.5) + n(3)). (c) 2005 Elsevier B.V. All rights reserved.
暂无评论