The DIRECTED FEEDBACK VERTEX SET (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp's 21 NP-complete problems. Resolving the parameter...
详细信息
The DIRECTED FEEDBACK VERTEX SET (DFVS) problem takes as input a directed graph G and seeks a smallest vertex set S that hits all cycles in G. This is one of Karp's 21 NP-complete problems. Resolving the parameterized complexity status of DFVS was a long-standing open problem until Chen et al. (2008) showed its fixed-parameter tractability via a 4kk!nO(1)-time algorithm, where k = |S|. Here we show fixed-parameter tractability of two generalizations of DFVS:center dot Find a smallest vertex set S such that every strong component of G - S has size at most s: we give an algorithm solving this problem in time 4k(ks + k + s)! middot nO(1). This generalizes an algorithm by Xiao (2017) for the undirected version of the *** dot Find a smallest vertex set S such that every non-trivial strong component of G - S is 1-out-regular: we give an algorithm solving this problem in time 2O(k3) middot nO(1). We also solve the corresponding arc versions of these problems by fixed-parameter algorithms. (c) 2022 Published by Elsevier B.V.
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the ...
详细信息
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra's algorithm has two drawbacks: First, the run time of the resulting algorithms is often double-exponential in the parameter, and second, an ILP formulation in small dimension cannot easily express problems involving many different costs. Inspired by the work of Hemmecke et al. (Math Program 137(12, Ser. A):325-341, 2013), we develop a single-exponential algorithm for so-called combinatorial n-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to many relevant problems problems like Closest String, Swap Bribery, Weighted Set Multicover, and several others, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra's algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs, existence of an augmenting step implies existence of a "local" augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.
fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter a...
详细信息
fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f(k)n(1+o(1)) time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of.(k)n(o(1));such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that FEEDBACK VERTEX SET and k-PATH admit dynamic algorithms with f (k) log(O(1)) n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, DIRECTED FEEDBACK VERTEX SET and DIRECTED k-PATH do not admit dynamic algorithms with n(o(1)) update and query times even for constant solution sizes k <= 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, DIRECTED FEEDBACK VERTEX SET cannot be solved with update time that is purely a function of k.
We consider the classic problem of NETWORK RELIABILITY. A network is given together with a source vertex, one or more target vertices, and probabilities assigned to each of the edges. Each edge of the network is opera...
详细信息
We consider the classic problem of NETWORK RELIABILITY. A network is given together with a source vertex, one or more target vertices, and probabilities assigned to each of the edges. Each edge of the network is operable with its associated probability and the problem is to determine the probability of having at least one source-to-target path that is entirely composed of operable edges. This problem is known to be NP-hard. We provide a novel scalable algorithm to solve the NETWORK RELIABILITY problem when the treewidth of the underlying network is small. We also show our algorithm's applicability for real-world transit networks that have small treewidth, including the metro networks of major cities, such as London and Tokyo. Our algorithm leverages tree decompositions to shrink the original graph into much smaller graphs, for which reliability can be efficiently and exactly computed using a brute force method. To the best of our knowledge, this is the first exact algorithm for NETWORK RELIABILITY that can scale to handle real-world instances of the problem.
We study the parameterized and classical complexity of two problems that are concerned with induced paths on three vertices, called P(3)s, in undirected graphs G = ( V, E). In Strong Triadic Closure we aim to label th...
详细信息
We study the parameterized and classical complexity of two problems that are concerned with induced paths on three vertices, called P(3)s, in undirected graphs G = ( V, E). In Strong Triadic Closure we aim to label the edges in E as strong and weak such that at most k edges are weak and G contains no induced P-3 with two strong edges. In Cluster Deletion we aim to destroy all induced P3s by a minimum number of edge deletions. We first show that Strong Triadic Closure admits a 4k-vertex kernel. Then, we study parameterization by l := |E|- k and show that both problems are fixed-parameter tractable and unlikely to admit a polynomial kernel with respect to l. Finally, we give a dichotomy of the classical complexity of both problems on H-free graphs for all H of order at most four.
Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have ...
详细信息
Stable matching problems with lower quotas are fundamental in academic hiring and ensuring operability of rural hospitals. Only few tractable (polynomial-time solvable) cases of stable matching with lower quotas have been identified;most such problems are NP-hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440-465, 2016). We therefore consider stable matching problems with lower quotas under a relaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitals we focus on the case when all hospitals have upper quota equal to 1, which generalizes the setting of "arranged marriages" first considered by Knuth (Mariages stables et leurs relations avec d'autres problemes combinatoires, Les Presses de l'Universite de Montreal, Montreal, 1976). We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy: for each choice of parameters we either provide a polynomial-time algorithm, or an NP-hardness proof and fixed-parameter algorithm, or NP-hardness proof and W[1]-hardness proof. As corollary, we negatively answer a question by Hamada et al. (Algorithmica 74(1):440-465, 2016) by showing fixed-parameter intractability parameterized by optimal solution size. We also classify all cases of one-sided constraints where only women may be distinguished.
This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Previously, [Tofi...
详细信息
This paper deals with the problem of enumerating all minimum-cost LCA-reconciliations involving gene duplications and lateral gene transfers (LGTs) for a given species tree S and a given gene tree G. Previously, [Tofigh A, Hallett M, Lagergren J, Simultaneous identification of duplications and lateral gene transfers, IEEE/ACM Trans Comput Biol Bioinf 517-535, 2011.] gave a fixed-parameter algorithm for this problem that runs in O(m + 3(k)n) time, where m is the number of vertices in S, n is the number of vertices in G, and k is the minimum cost of an LCA-reconciliation between S and G. In this paper, by refining their algorithm, we obtain a new one for the same problem that finds and outputs the solutions in a compact form within O(mn(2) + 3(k)) time. In the most interesting case where 3(k) >= mn(2) , our algorithm is O(n) times faster.
Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string t(sol) that is within a Hamming distance of d to each of the given strings. It is known that the proble...
详细信息
Given a set of n strings of length L and a radius d, the closest string problem (CSP for short) asks for a string t(sol) that is within a Hamming distance of d to each of the given strings. It is known that the problem is NP-hard and its optimization version admits a polynomial time approximation scheme (PTAS). A number of parameterized algorithms have been then developed to solve the problem when d is small. Among them, the relatively new ones have not been implemented before and their performance in practice was unknown. In this study, we implement all of them by careful engineering. For those that have been implemented before, our implementation is much faster. For some of those that have not been implemented before, our experimental results show that there exist huge gaps between their theoretical and practical performances. We also design a new parameterized algorithm for the binary case of CSP. The algorithm is deterministic and runs in O (n(2)L + n(2)d. 6.16(d)) time, while the previously best deterministic algorithm runs in O (nL + nd(3). 6.731(d)) time. (C) 2018 Elsevier B.V. All rights reserved.
In this paper, we study covering and domination problems on directed graphs. Although undirected VERTEX COVER and EDGE DOMINATING SET are well-studied classical graph problems, the directed versions have not been stud...
详细信息
In this paper, we study covering and domination problems on directed graphs. Although undirected VERTEX COVER and EDGE DOMINATING SET are well-studied classical graph problems, the directed versions have not been studied much due to the lack of clear definitions. We give natural definitions for DIRECTED r-IN (OUT) VERTEX COVER and DIRECTED (p, q)-EDGE DOMINATING SET as directed generalizations Of VERTEX COVER and EDGE DOMINATING SET. For these problems, we show that (1) DIRECTED r-IN (OUT) VERTEX COVER and DIRECTED (p, q)-EDGE DOMINATING SET are NP-complete on planar directed acyclic graphs except when r = 1 or (p, q) = (0, 0), (2) if r >= 2, DIRECTED r-IN (OUT) VERTEX COVER is W[2]-hard and c In k-inapproximable on directed acyclic graphs, (3) if either p or q is greater than 1, DIRECTED (p, q)-EDGE DOMINATING SET is W[2]-hard and c In k-inapproximable on directed acyclic graphs, (4) all problems can be solved in polynomial time on trees, and (5) DIRECTED (0, 1)-EDGE ((1, 0)-EDGE, (1, 1)-EDGE) DOMINATING SET is fixed-parameter tractable on general graphs. The first result implies that DIRECTED r-DOMINATING SET on directed line graphs is NP-complete even if r = 1. (C) 2019 Elsevier B.V. All rights reserved.
We study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k ...
详细信息
We study a variant of the problem of finding a collection of disjoint s-clubs in a given network. Given a graph, the problem asks whether there exists a collection of at most r disjoint s-clubs that covers at least k vertices of the network. An s-club is a connected graph that has diameter bounded by s, for a positive integer s. We demand that each club is non-trivial, that is it has order at least t >= 2, for some positive integer t. We prove that the problem is APX-hard even when the input graph has bounded degree, s = 2, t = 3 and r = vertical bar V vertical bar. Moreover, we show that the problem is polynomial-time solvable when s >= 4, t = 3 and r = vertical bar V vertical bar, and when s >= 3, t = 2 and r = vertical bar V vertical bar. Finally, for s >= 2, we present a fixed-parameter algorithm for the problem, when parameterized by the number of covered vertices. (C) 2019 Elsevier B.V. All rights reserved.
暂无评论