Samer Marko, Stefan Szeider · Frontiers in artificial intelligence and applications · 2009
Parameterized complexity is a new theoretical framework that considers, in addition to the overall input size, the effects on computational complexity of a secondary measurement, the parameter. This two-dimensional viewpoint allows a fine-grained complexity analysis that takes structural properties of problem instances into account. The central notion is “fixed-parameter tractability” which refers to solvability in polynomial time for each fixed value of the parameter such that the order of the polynomial time bound is independent of the parameter. This chapter presents main concepts and recent results on the parameterized complexity of the satisfiability problem and it outlines fundamental algorithmic ideas that arise in this context. Among the parameters considered are the size of backdoor sets with respect to various tractable base classes and the treewidth of graph representations of satisfiability instances.
Cited by 51
Erik D. Demaine, MohammadTaghi Hajiaghayi, Dániel Marx · 2013
We study an extensive class of movement minimization problems which arise from many practical scenarios but so far have little theoretical study. In general, these problems involve planning the coordinated motion of a collection of agents (representing robots, people, map labels, network messages, etc.) to achieve a global property in the network while minimizing the maximum or average movement (expended energy). The only previous theoretical results about this class of problems are about approximation, and mainly negative: many movement problems of interest have polynomial inapproximability. Given that the number of mobile agents is typically much smaller than the complexity of the environment, we turn to fixed-parameter tractability. We characterize the boundary between tractable and intractable movement problems in a very general setup: it turns out the complexity of the problem fundamentally depends on the treewidth of the minimal configurations. Thus the complexity of a particular problem can be determined by answering a purely combinatorial question. Using our general tools, we determine the complexity of several concrete problems and fortunately show that many movement problems of interest can be solved efficiently.
Cited by 0
Marko Samer, Stefan Szeider · Frontiers in artificial intelligence and applications · 2021
Parameterized complexity is a new theoretical framework that considers, in addition to the overall input size, the effects on computational complexity of a secondary measurement, the parameter. This two-dimensional viewpoint allows a fine-grained complexity analysis that takes structural properties of problem instances into account. The central notion is “fixed-parameter tractability” which refers to solvability in polynomial time for each fixed value of the parameter such that the order of the polynomial time bound is independent of the parameter. This chapter presents main concepts and recent results on the parameterized complexity of the satisfiability problem and it outlines fundamental algorithmic ideas that arise in this context. Among the parameters considered are the size of backdoor sets with respect to various tractable base classes and the treewidth of graph representations of satisfiability instances.
Cited by 5
2016
We study an extensive class of movement minimization problems which arise from many practical scenarios but so far have little theoretical study. In general, these problems involve planning the coordi-nated motion of a collection of agents (representing robots, people, map labels, network messages, etc.) to achieve a global property in the network while minimizing the maximum or average movement (expended energy). The only previous theoretical results about this class of problems are about approximation, and mainly negative: many movement problems of interest have polynomial inapproximability. Given that the number of mobile agents is typically much smaller than the complexity of the environment, we turn to fixed-parameter tractability. We characterize the boundary between tractable and intractable movement problems in a very general setup: it turns out the complexity of the problem fundamentally depends on the treewidth of the minimal configurations. Thus the complexity of a particular problem can be determined by answering a purely combinatorial question. Using our general tools, we determine the complexity of several concrete problems and fortunately show that many movement problems of interest can be solved efficiently. 1
Cited by 0
Michael A. Langston · Lecture notes in computer science · 2012
Cited by 22
Fedor V. Fomin, Michał Pilipczuk · 2013
We give a fixed-parameter tractable (FPT) approximation algorithm computing the pathwidth of a tournament, and more generally, of a semi-complete digraph. Based on this result, we prove the following. The Topological Containment problem is FPT on semi-complete digraphs. More precisely, given a semi-complete n-vertex digraph T and a digraph H, one can check in time f(|H|)n3 log n, where f is some elementary function, whether T contains a subdivision of H as a subgraph. The previous known algorithm for this problem was due to Fradkin and Seymour and was of running time nm(|H|), where m is a quadruple-exponential function. The Rooted Immersion problem is FPT on semi-complete digraphs. The complexity of this problem was left open by Fradkin and Seymour. Our algorithm solves it in time g(|H|)n4 log n, for some elementary function g. Vertex deletion distance to every immersion-closed class of semi-complete digraphs is fixed-parameter tractable. More precisely, for every immersion-closed class П of semi-complete digraphs, there exists an algorithm with running time h(k)n3 log n that checks, whether one can remove at most k vertices from a semi-complete n-vertex digraph to obtain a digraph from class Π. Here, h is some function depending on the class Π.
Cited by 9
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen et al. · Society for Industrial and Applied Mathematics eBooks · 2025
In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph. Ghaffari, Karger, and Panigrahi [SODA 2017] showed that Hedge Cut can be solved in quasipolynomial-time, raising the hope for a polynomial time algorithm. Jaffke, Lima, Masarik, Pilipczuk, and Souza [SODA 2023] complemented this result by showing that assuming the Exponential Time Hypothesis (ETH), no polynomial-time algorithm exists. In this paper, we show that Hedge Cut is fixed-parameter tractable parameterized by the solution size ℓ by providing an algorithm with running time , which can be upper bounded by Cℓ · (n + m)O (1) for any constant c > 1. This running time captures at the same time the fact that the problem is quasipolynomial-time solvable, and that it is fixed-parameter tractable parameterized by ℓ. We further generalize this algorithm to an algorithm with running time for Hedge k-CUT.
Cited by 1
Rod Downey, Jörg Flum, Martin Grohe et al. · Annals of Pure and Applied Logic · 2007
Cited by 3
Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk et al. · arXiv (Cornell University) · 2011
In the Correlation Clustering, also known as Cluster Editing, we are given an undirected n-vertex graph G and a positive integer k. The task is to decide if G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, i.e. by adding/deleting at most k edges. We give a subexponential algorithm that, in time 2^O(sqrt(pk)) + n^O(1) decides whether G can be transformed into a cluster graph with p cliques by changing at most k adjacencies. We complement our algorithmic findings by the following tight lower bounds on the asymptotic behaviour of our algorithm. We show that, unless ETH fails, for any constant 0 < s <= 1, there is p = Theta(k^s) such that there is no algorithm deciding in time 2^o(sqrt(pk)) n^O(1) whether G can be transformed into a cluster graph with p cliques by changing at most k adjacencies.
Cited by 12Open access
Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2006
Summary of the Dagstuhl Seminar held 24. July - 29. July 2005.
Cited by 0Open access
Rajesh Chitnis · 2014
Most interesting optimization problems on graphs are NP-hard, implying that (un-less P = NP) there is no polynomial time algorithm that solves all the instances of an NP-hard problem exactly. However, classical complexity measures the running time as a function of only the overall input size. The paradigm of parameterized complexity was introduced by Downey and Fellows to allow for a more refined multivariate analy-sis of the running time. In parameterized complexity, each problem comes along with a secondary measure k which is called the parameter. The goal of parameterized com-plexity is to design efficient algorithms for NP-hard problems when the parameter k is small, even if the input size is large. Formally, we say that a parameterized problem is fixed-parameter tractable (FPT) if instances of size n and parameter k can be solved in f (k) · nO(1) time, where f is a computable function which does not depend on n. A pa-rameterized problem belongs to the class XP if instances of size n and parameter k can be solved in f (k) ·nO(g(k)) time, where f and g are both computable functions. In this thesis we focus on the parameterized complexity of transversal and connec-tivity problems on directed graphs. This research direction has been hitherto relatively
Cited by 0
Kevin Buchin, Maike Buchin, Jaroslaw Byrka et al. · 2013
A binary tanglegram is a pair 〈S, T〉 of binary trees whose leaf sets are in one-to-one correspondence; matching leaves are connected by inter-tree edges. For applications, for example in phylogenetics, it is essential that both trees are drawn with no edge crossing and that the inter-tree edges have as few crossings as possible. It is known that finding a drawing with the minimum number of crossings is NP-hard and that the problem is fixed-parameter tractable with respect to that number. We show that the problem is hard even if both trees are complete binary trees. For this case we give an O(n³)-time 2-approximation and a new and simple fixedparameter algorithm. We prove that under the Unique Games Conjecture there is no constant-factor approximation for general binary trees. We show that the maximization version of the problem for general binary trees can be reduced to a version of MaxCut for which the algorithm of Goemans and Williamson yields a 0.878-approximation.
Cited by 0
Lirong Xia · 2014
We prove that for any integer generalized scoring rules (GSRs), winner determination and computing a wide range of strategic behavior are fixed-parameter tractable (FPT) w.r.t. the number of alternatives.
Cited by 0
Vincent Cohen-Addad, Jason Li · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
We study the complexity of the classic capacitated k-median and k-means problems parameterized by the number of centers, k. These problems are notoriously difficult since the best known approximation bound for high dimensional Euclidean space and general metric space is Theta(log k) and it remains a major open problem whether a constant factor exists. \nWe show that there exists a (3+epsilon)-approximation algorithm for the capacitated k-median and a (9+epsilon)-approximation algorithm for the capacitated k-means problem in general metric spaces whose running times are f(epsilon,k) n^{O(1)}. For Euclidean inputs of arbitrary dimension, we give a (1+epsilon)-approximation algorithm for both problems with a similar running time. This is a significant improvement over the (7+epsilon)-approximation of Adamczyk et al. for k-median in general metric spaces and the (69+epsilon)-approximation of Xu et al. for Euclidean k-means.
Cited by 12Open access
Rodney G. Downey, Martin Grohe, Gerhard J. Woeginger · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2006
From 24.07.05 to 29.07.05, the Dagstuhl Seminar 05301 ``Exact Algorithms and Fixed-Parameter Tractability'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. This is a collection of abstracts of the presentations given during the seminar.
Cited by 0Open access
Eiben, Eduard · reposiTUm (TU Wien) · 2020
The design of efficient algorithms for various problems is a fundamental part of computer science. One significant obstacle in this area is the fact that many interesting problems from areas such as Algorithmic Graph Theory, Artificial Intelligence, or Optimization are known to be NP-hard on general instances. However, in the majority of applications the instances of interest are the result or output of some other processes, and as such inherently contain some form of structure. This structure can often be exploited to efficiently find exact solutions for many NP-hard problems. To capture the structure of the input instance, we use the framework of parameterized complexity. In parameterized algorithms, the running time is analyzed in finer detail than in classical complexity theory: instead of expressing the running time as a function of the input size only, dependence on a parameter k is taken into account. We use the parameter k to describe how “structured” the input instance is. Algorithms with running time f(k)nc, where n is the input size and c is a constant independent of both n and k, are called fixed-parameter algorithms or FPT algorithms. Typically the goal in parameterized algorithms is to design FPT algorithms while minimizing both the f(k) factor and the constant c in the bound on the running time. We study a range of different problems under the paradigm of parameterized complexity. More precisely, our research focuses on two approaches to analyze the structure of instances and their combination. The first approach focuses on the notion of decomposition. The idea is to decompose the given input into simpler parts and use this decomposition to solve the problem more efficiently. The second approach is based on the established notion of a modulator to a tractable class of instances, which applies to problem instances that may be placed in a tractable class by a small number of local changes. We design several algorithms that exploit some of the already established parameters. However, our main focus is on designing and exploiting new kinds of structure. We highlight here one of the results in particular. We develop a family of parameters that combine the two approaches outlined above to capture forms of structure not accessible to a single approach, and we show that these parameters give rise to efficient algorithms for a plethora of NP-hard problems.
Cited by 0Open access
Panos Giannopoulos, Christian Knauer, Günter Rote et al. · Computational Geometry · 2011
Cited by 13Open access
Sylvain Guillemot, Vincent Berry · IEEE/ACM Transactions on Computational Biology and Bioinformatics · 2010
Given a set L of labels and a collection of rooted trees whose leaves are bijectively labeled by some elements of L, the Maximum Agreement Supertree (Smast) problem is given as follows: find a tree T on a largest label set L^{\prime} \subseteq L that homeomorphically contains every input tree restricted to L^{\prime}. The problem has phylogenetic applications to infer supertrees and perform tree congruence analyses. In this paper, we focus on the parameterized complexity of this NP-hard problem, considering different combinations of parameters as well as particular cases. We show that Smast on k rooted binary trees on a label set of size n can be solved in O((8n)^{k}) time, which is an improvement with respect to the previously known O(n^{3k^{2}}) time algorithm. In this case, we also give an O((2k)^{p}kn^{2}) time algorithm, where p is an upper bound on the number of leaves of L missing in a Smast solution. This shows that Smast can be solved efficiently when the input trees are mostly congruent. Then, for the particular case where any triple of leaves is contained in at least one input tree, we give O(4^{p}n^{3}) and O(3.12^{p} + n^{4}) time algorithms, obtaining the first fixed-parameter tractable algorithms on a single parameter for this problem. We also obtain intractability results for several combinations of parameters, thus indicating that it is unlikely that fixed-parameter tractable algorithms can be found in these particular cases.
Cited by 6
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen et al. · ACM Transactions on Algorithms · 2024
We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored \(n\) -vertex undirected graph, vertices \(s\) and \(t\) , and an integer \(k\) , finds an \((s,t)\) -path containing at least \(k\) different colors in time \(2^{k}n^{\mathcal{O}(1)}\) . This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman on finding a path through \(k\) specified vertices. It also implies the first \(2^{k}n^{\mathcal{O}(1)}\) time algorithm for finding an \((s,t)\) -path of length at least \(k\) . Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an \(n\) -vertex undirected graph \(G\) , a matroid \(M\) whose elements correspond to the vertices of \(G\) and which is represented over a finite field of order \(q\) , a positive integer weight function on the vertices of \(G\) , two sets of vertices \(S,T\subseteq V(G)\) , and integers \(p,k,w\) , and the task is to find \(p\) vertex-disjoint paths from \(S\) to \(T\) so that the union of the vertices of these paths contains an independent set of \(M\) of cardinality \(k\) and weight \(w\) , while minimizing the sum of the lengths of the paths. We give a \(2^{p+\mathcal{O}(k^{2}\log(q+k))}n^{\mathcal{O}(1)}w\) time randomized algorithm for this problem.
Cited by 1
Kobayashi, Yusuke, Lin, Bingkai · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2025
In the Pinwheel Packing problem, we are given a set of recurring tasks, each associated with a positive integer a_i for task i. The objective is to select one task to perform each day such that every task i is performed at least once within every a_i consecutive days. The exact computational complexity of this problem, where ∑ 1/a_i = 1, has remained an open question for more than 30 years; in particular, it is still unknown whether the problem is NP-hard. The first contribution of this paper is to show that Pinwheel Packing cannot be solved in polynomial time under a standard complexity assumption, improving upon the hardness result shown by Jacobs and Longo. Additionally, we present fixed-parameter algorithms for variants of Pinwheel Packing, parameterized by the number of tasks.
Cited by 0Open access