Catálogo de publicaciones - libros

Up to now, most work in the area of parameterized complexity has focussed on exact algorithms for decision problems. The goal of this paper is to apply parameterized ideas to approximation. We begin exploration of parameterized approximation problems , where the problem in question is a parameterized decision problem, and the required approximation factor is treated as a second parameter for the problem.

A subset of vertices D  ⊆  V of a graph G = ( V , E ) is a dominating clique if D is a dominating set and a clique of G . The existence problem ‘Given a graph G , is there a dominating clique in G ?’ is NP-complete, and thus both the Minimum and the Maximum Dominating Clique problem are NP-hard. We present an O (1.3390^ n ) time algorithm that for an input graph on n vertices either computes a minimum dominating clique or reports that the graph has no dominating clique. The algorithm uses the Branch & Reduce paradigm and its time analysis is based on the Measure & Conquer approach. We also establish a lower bound of Ω(1.2599^ n ) for the worst case running time of our algorithm.

We analyze edge dominating set from a parameterized perspective. More specifically, we prove that this problem is in ${\mathcal{FPT}}$ for general (weighted) graphs. The corresponding algorithms rely on enumeration techniques. In particular, we show how the use of compact representations may speed up the decision algorithm.

We investigate the parameterized complexity of Maximum Independent Set and Dominating Set restricted to certain geometric graphs. We show that Dominating Set is W[1]-hard for the intersection graphs of unit squares, unit disks, and line segments. For Maximum Independent Set , we show that the problem is W[1]-complete for unit segments, but fixed-parameter tractable if the segments are axis-parallel.

We present a fixed parameter tractable algorithm for the Independent Set problem in 2-dir graphs and also its generalization to d -dir graphs. A graph belongs to the class of d -dir graphs if it is an intersection graph of segments in at most d directions in the plane. Moreover our algorithms are robust in the sense that they do not need the actual representation of the input graph and they answer correctly even if they are given a graph from outside the promised class.

Deciding whether two n -point sets A , B ∈ℝ^ d are congruent is a fundamental problem in geometric pattern matching. When the dimension d is unbounded, the problem is equivalent to graph isomorphism and is conjectured to be in FPT. When | A |= m <| B |= n , the problem becomes that of deciding whether A is congruent to a subset of B and is known to be NP-complete. We show that point subset congruence, with d as a parameter, is W[1]-hard, and that it cannot be solved in O ( mn ^ o ( d ))-time, unless SNP⊂DTIME(2^ o ( n )). This shows that, unless FPT=W[1], the problem of finding an isometry of A that minimizes its directed Hausdorff distance, or its Earth Mover’s Distance, to B , is not in FPT.

We present an $\mathcal{O} (1.7548^n)$ algorithm finding a minimum feedback vertex set in a graph on n vertices.

Resolving a noted open problem, we show that the Undirected Feedback Vertex Set problem, parameterized by the size of the solution set of vertices, is in the parameterized complexity class Poly ( k ), that is, polynomial-time pre-processing is sufficient to reduce an initial problem instance ( G , k ) to a decision-equivalent simplified instance ( G ′, k ′) where k ′ ≤ k , and the number of vertices of G ′ is bounded by a polynomial function of k . Our main result shows an O ( k ^11) kernelization bound.

We provide first-time fixed-parameter tractability results for the NP-complete problems Maximum Full-Degree Spanning Tree and Minimum-Vertex Feedback Edge Set . These problems are dual to each other: In Maximum Full-Degree Spanning Tree , the task is to find a spanning tree for a given graph that maximizes the number of vertices that preserve their degree. For Minimum-Vertex Feedback Edge Set the task is to minimize the number of vertices that end up with a reduced degree. Parameterized by the solution size, we exhibit that Minimum-Vertex Feedback Edge Set is fixed-parameter tractable and has a problem kernel with the number of vertices linearly depending on the parameter k . Our main contribution for Maximum Full-Degree Spanning Tree , which is W[1]-hard, is a linear-size problem kernel when restricted to planar graphs. Moreover, we present subexponential-time algorithms in the case of planar graphs.

In the field of computational optimization, it is often the case that we are given an instance of an NP problem and asked to enumerate the first few ”best” solutions to the instance. Motivated by this, we propose in this paper a new framework to measure the effective enumerability of NP optimization problems. More specifically, given an instance of an NP problem, we consider the parameterized problem of enumerating a given number of best solutions to the instance, and study its average complexity in terms of the number of solutions. Our framework is different from the previously-proposed ones. For example, although it is known that counting the number of k -paths in a graph is # W [1]-complete, we present a fixed-parameter enumeration algorithm for the problem. We show that most algorithmic techniques for fixed-parameter tractable problems, such as search trees, color coding, and bounded treewidth, can be used for parameterized enumerations. In addition, we design elegant and new enumeration techniques and show how to generate small-size structures and enumerate solutions efficiently.