The d-bounded-degree vertex deletion problem, to delete at most k vertices in a given graph to make the maximum degree of the remaining graph at most d, finds applications in computational biology, social network anal...
详细信息
ISBN:
(纸本)9783319426341;9783319426334
The d-bounded-degree vertex deletion problem, to delete at most k vertices in a given graph to make the maximum degree of the remaining graph at most d, finds applications in computational biology, social network analysis and some others. It can be regarded as a special case of the (d + 2)-hitting set problem and generates the famous vertex cover problem. The d-bounded-degree vertex deletion problem is NP-hard for each fixed d >= 0. In terms of parameterized complexity, the problem parameterized by k is W[2]-hard for unbounded d and fixed-parameter tractable for each fixed d >= 0. Previously, (randomized) parameterized algorithms for this problem with running time bound O*((d + 1)(k)) are only known for d <= 2. In this paper, we give a uniform parameterized algorithm deterministically solving this problem in O*((d + 1)(k)) time for each d >= 3. Note that it is an open problem whether the d ' -hitting set problem can be solved in O*((d ' - 1)(k)) time for d ' >= 3. Our result answers this challenging open problem affirmatively for a special case. Furthermore, our algorithm also gets a running time bound of O*(3.0645(k)) for the case that d = 2, improving the previous deterministic bound of O*(3.24(k)).
A matchingM in a graph G is an acyclic matching if the subgraph of G induced by the endpoints of the edges of M is a forest. Given a graph G and a positive integer l, Acyclic Matching asks whether G has an acyclic mat...
详细信息
ISBN:
(数字)9783031433801
ISBN:
(纸本)9783031433795;9783031433801
A matchingM in a graph G is an acyclic matching if the subgraph of G induced by the endpoints of the edges of M is a forest. Given a graph G and a positive integer l, Acyclic Matching asks whether G has an acyclic matching of size (i.e., the number of edges) at least l. In this paper, we first prove that assuming W[1] not subset of FPT, there does not exist any FPT-approximation algorithm for Acyclic Matching that approximates it within a constant factor when parameterized by l. Our reduction is general in the sense that it also asserts FPT-inapproximability for Induced Matching and Uniquely Restricted Matching. We also consider three below-guarantee parameters for Acyclic Matching, viz. n/2 - l, MM(G)- l, and IS(G)- l, where n is the number of vertices in G, MM(G) is the matching number of G, and IS(G) is the independence number of G. We note that the result concerning the below-guarantee parameter n/2 - l is the most technical part of our paper. Also, we show that Acyclic Matching does not exhibit a polynomial kernel with respect to vertex cover number (or vertex deletion distance to clique) plus the size of the matching unless NP subset of coNP/poly.
This paper presents a parameterized shared-memory scheme for parameterized metaheuristics. The use of a parameterized metaheuristic facilitates experimentation with different metaheuristics and hybridation/combination...
详细信息
This paper presents a parameterized shared-memory scheme for parameterized metaheuristics. The use of a parameterized metaheuristic facilitates experimentation with different metaheuristics and hybridation/combinations to adapt them to the particular problem we are working with. Due to the large number of experiments necessary for the metaheuristic selection and tuning, parallelism should be used to reduce the execution time. To obtain parallel versions of the metaheuristics and to adapt them to the characteristics of the parallel system, a unified parameterized shared-memory scheme is developed. Given a particular computational system and fixed parameters for the sequential metaheuristic, the appropriate selection of parameters in the unified parallel scheme eases the development of parallel efficient metaheuristics.
We study the INDEPENDENT FEEDBACK VERTEX SET problem - a variant of the classic FEEDBACK VERTEX SET problem where, given a graph G and an integer k, the problem is to decide whether there exists a vertex set S. V (G) ...
详细信息
We study the INDEPENDENT FEEDBACK VERTEX SET problem - a variant of the classic FEEDBACK VERTEX SET problem where, given a graph G and an integer k, the problem is to decide whether there exists a vertex set S. V (G) such that G \ S is a forest and S is an independent set of size at most k. We present an O* ((1+.2)k)time FPT algorithm for this problem, where phi < 1.619 is the golden ratio, improving the previous fastest O* (4.1481k)-time algorithm given by Agrawal et al. (2016). The exponential factor in our time complexity bound matches the fastest deterministic FPT algorithm for the classic FEEDBACK VERTEX SET problem. On the technical side, the main novelty is a refined measure of an input instance in a branching process, that allows for a simpler and more concise description and analysis of the algorithm.
The tree inclusion problem is, given two node-labeled trees P and T (the "pattern tree" and the "target tree"), to locate every minimal subtree in T (if any) that can be obtained by applying a sequ...
详细信息
The tree inclusion problem is, given two node-labeled trees P and T (the "pattern tree" and the "target tree"), to locate every minimal subtree in T (if any) that can be obtained by applying a sequence of node insertion operations to P. Although the ordered tree inclusion problem is solvable in polynomial time, the unordered tree inclusion problem is NP-hard. The currently fastest algorithm for the latter is a classic algorithm by Kilpelainen and Mannila from 1995 that runs in O (d2(2d)mn) time, where m and n are the sizes of the pattern and target trees, respectively, and d is the degree of the pattern tree. Here, we develop a new algorithm that runs in O (d2(d)mn(2)) time, improving the exponential factor from 2(2d) to 2(d) by considering a particular type of ancestor-descendant relationships that is suitable for dynamic programming. We also study restricted variants of the unordered tree inclusion problem. (C) 2021 Elsevier B.V. All rights reserved.
We survey the parameterized complexity of problems that arise in artificial intelligence, database theory and automated reasoning. In particular, we consider various parameterizations of the constraint satisfaction pr...
详细信息
We survey the parameterized complexity of problems that arise in artificial intelligence, database theory and automated reasoning. In particular, we consider various parameterizations of the constraint satisfaction problem, the evaluation problem of Boolean conjunctive database queries and the propositional satisfiability problem. Furthermore, we survey parameterized algorithms for problems arising in the context of the stable model semantics of logic programs, for a number of other problems of non-monotonic reasoning, and for the computation of cores in data exchange.
The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show...
详细信息
The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that, for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic programming algorithm for hypergraphs. The algorithm might be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected.
In this paper we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives a parameterized algorithm of running time O((5.7...
详细信息
In this paper we illustrate how nondeterminism can be used conveniently and effectively in designing efficient deterministic algorithms. In particular, our method gives a parameterized algorithm of running time O((5.7 k)(k) n) for the 3-D matching problem, which significantly improves the previous algorithm by Downey et al. The algorithm can be generalized to yield an improved algorithm for the r-D matching problem for any positive integer r. The method can also be employed in designing deterministic algorithms for other optimization problems as well.
We show that the CNF satisfiability problem can be solved in 0*(1.2226(m)) time, where m is the number of clauses in the formula, improving the known upper bounds 0*(1.234(m)) given by Yamamoto 15 years ago and 0*(1.2...
详细信息
We show that the CNF satisfiability problem can be solved in 0*(1.2226(m)) time, where m is the number of clauses in the formula, improving the known upper bounds 0*(1.234(m)) given by Yamamoto 15 years ago and 0*(1.239(m)) given by Hirsch 22 years ago. By using an amortized technique and careful case analysis, we successfully avoid the bottlenecks in previous algorithms and get the improvement. (C) 2021 Elsevier B.V. All rights reserved.
In the minimum fill-in problem, one wishes to nd a set of edges of smallest size, whose addition to a given graph will make it chordal. The problem has important applications in numerical algebra and has been studied ...
详细信息
In the minimum fill-in problem, one wishes to nd a set of edges of smallest size, whose addition to a given graph will make it chordal. The problem has important applications in numerical algebra and has been studied intensively since the 1970s. We give the rst polynomial approximation algorithm for the problem. Our algorithm constructs a triangulation whose size is at most eight times the optimum size squared. The algorithm builds on the recent parameterized algorithm of Kaplan, Shamir, and Tarjan for the same problem. For bounded degree graphs we give a polynomial approximation algorithm with a polylogarithmic approximation ratio. We also improve the parameterized algorithm.
暂无评论