Catálogo de publicaciones - libros

Complementing recent progress on classical complexity and polynomial-time approximability of feedback set problems in (bipartite) tournaments, we extend and partially improve fixed-parameter tractability results for these problems. We show that in tournaments is amenable to the novel iterative compression technique. Moreover, we provide data reductions and problem kernels for and in tournaments, and a depth-bounded search tree for in bipartite tournaments based on a new forbidden subgraph characterization.

We are going to analyze simple search tree algorithms for . Although the algorithms are simple, their analysis is technically rather involved. However, this approach allows us to even improve on elsewhere published algorithm running time estimates for the more restricted case of (unweighted) .

In the problem, a graph has to be changed to a disjoint union of cliques by at most edge insertions or deletions. Several reasons suggest a generalized problem where the target graph can have some overlapping cliques. We show that the problem remains fixed-parameter tractable (FPT) in the combination of both parameters: and a second parameter describing somehow the complexity of overlap structure. For this result we need a structural property of twins in graphs enabling a certain elimination scheme that finally leads to a small enough subgraph we can branch on. We also give a nontrivial algorithm for problem minimizing the number of disjoint clusters, based on a concise enumeration of all solutions to the original problem. This generic scheme may become interesting also for other multicriteria FPT problems.

A linear arrangement (LA) is an assignment of distinct integers to the vertices of a graph. The cost of an LA is the sum of lengths of the edges of the graph, where the length of an edge is defined as the absolute value of the difference of the integers assigned to its ends. For many application one hopes to find an LA with small cost. However, it is a classical NP-complete problem to decide whether a given graph admits an LA of cost bounded by a given integer. Since every edge of contributes at least one to the cost of any LA, the problem becomes trivially fixed-parameter tractable (FPT) if parameterized by the upper bound of the cost. Fernau asked whether the problem remains FPT if parameterized by the upper bound of the cost minus the number of edges of the given graph; thus whether the problem is FPT “parameterized above guaranteed value.” We answer this question positively by deriving an algorithm which decides in time ( + + 5.88) whether a given graph with edges and vertices admits an LA of cost at most + (the algorithm computes such an LA if it exists). Our algorithm is based on a procedure which generates a problem kernel of linear size in linear time for a connected graph . We also prove that more general parameterized LA problems stated by Serna and Thilikos are not FPT, unless P = NP.

This paper follows the methodology introduced by Agrawal and Biswas in [AB92], based on a notion of universality for the relations associated with NP-complete problems. The purpose was to study NP-complete problems by examining the effects of reductions on the solution sets of the associated witnessing relations. This provided a useful criterion for NP-completeness while suggesting structural similarities between natural NP-complete problems. We extend these ideas to the class #P. The notion we find also yields a practical criterion for #P-completeness, as illustrated by a varied set of examples, and strengthens the argument for structural homogeneity of natural complete problems.

In this paper, we define three Sperner problems on specific surfaces and prove that they are complete respectively for the classes PPAD, PPADS and PPA. This is the first time that locally 2-dimensional Sperner problems are proved to be complete for any of the polynomial parity argument classes.