Algorithms seminar series

30 March

10th Annual Winter School in Algorithms, Graph Theory, and Combinatorics

joint work with Marek Cygan, Marcin Pilipczuk and Jakub Onufry Wojtaszczyk

Abstract The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z1, Z2 , asks whether it is possible to find disjoint sets A1, A2, such that Z1\subseteq A1, Z2\subseteq A2 and A1, A2 induce connected subgraphs. While the naive algorithm runs in O*(2^n) time, solutions with complexity of form O((2−eps)^n) have been found only for special graph classes. In the paper we present an O(1.933^n) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2^n barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel.

Joint work with: Petr Golovach, Marcin Kaminski and Dimitrios Thilikos

Abstract We introduce a new containment relation in graphs: lift contractions. We say that a graph H is a lift contraction of G if H can be obtained from G by a sequence of edge lifts and edge contractions. The edge lift operation is defined as follows. Let e=uv and e'=uw be two different edges incident with the same vertex u in a graph G. The lift of e and e' removes e and e' from G and then adds the edge vw if v and w are nonadjacent. We show that a graph contains every n-vertex graph as a lift contraction, if (1) its treewidth is large enough, or (2) its pathwidth is large enough and it is 2-connected, or (3) its order is large enough and its minimum degree is at least 3.

In this talk I will motivate why this is an interesting problem to look at, for example both broadcast scheduling and web search ranking can be modelled as Generalized Min Sum Set Cover. Further, why it makes sense to look at the Preemptive version of the problem. I will not give proofs in this talk, I will just highlight the main ingredients needed to obtain this 2-approximation for the preemptive problem and later show how to transform this into a non-preemptive solution. At the end, I will possibly say something on generalizing this problem by using submodular cost functions, but only if time permits. 

Problems parameterized by treewidth tractable in single exponential time: a logical approach

Joint work with Christina Boucher and Christine Lo, UCSD

Abstract A major impediment in the development of inexpensive, efficient, full genome sequencing is the large portion of erroneous reads produced by sequencing platforms. Error correction is the computational process that attempts to identify and correct these mistakes. Several classical stringology problems, including the Consensus String problem, are used to model error correction. However, a significant shortcoming of using these formulations is that they do not account for a few of the reads being too erroneous to correct; these outlier strings potentially have great effect on the solution, and should be detected and removed. We formalize the problem of error correction with outlier detection by defining the Consensus String with Outliers problem. Given a set S of n length-L strings, and parameters d and k, the objective in the Consensus String with Outliers problem is to find a subset S^* of S of size n-k and a string s such that \sum_{s_i \in S^*} d(s_i, s) <= d. Here d(x, y) denotes the Hamming distance between the two strings x and y. We prove the following results:

 - The variant of Consensus String with Outliers where the number k of outliers is fixed and the total distance \sum{s_i \in S^*} d(s_i, s) is to be minimized admits a simple PTAS. Our PTAS can easily be modified to also handle the variant of the problem where a hard upper bound d on the total distance is given as input, and the size of S^* is to be maximized. The approximation schemes are in fact so simple that our results are best viewed as a performance guarantee on natural heuristics for the problem when the parameters of the heuristic are chosen appropriately.

- Under the natural assumption that the number of outliers k is small, the PTAS for the distance minimization version of Consensus String with Outliers performs very well. In particular, as long as k <= n/2 the algorithm provides a (1+e) approximate solution in time f(1/e)(nL)^{O(1)} and thus is an EPTAS.

- In order to improve the PTAS for Consensus String with Outliers to an EPTAS, the assumption that k is small is necessary. Specifically, when k is allowed to be arbitrary the Consensus String with Outliers problem does not admit an EPTAS unless FPT=W[1].

- The decision version of {\em Consensus String with Outliers} is fixed parameter tractable when parameterized by d/(n-k). and thus, also when parameterized by just d.

To the best of our knowledge, Consensus String with Outliers is the first problem that admits a PTAS, is fixed parameter tractable when parameterized by the value of the objective function, but which provably does not admit an EPTAS under plausible complexity assumptions. To accommodate for this our hardness of approximation proof needs to combine parameterized reductions and gap preserving reductions in a novel manner.

On Tractable Cases of Target Set Selection

Abstract We study the NP-hard Target Set Selection (TSS) problem occurring in social network analysis. Roughly speaking, given a graph where each vertex is associated with a threshold, in TSS the task is to select a minimum-size "target set" such that all vertices of the graph get activated. Activation is a dynamic process. First, only the vertices in the target set are activated. Then, a vertex becomes activated if the number of its activated neighbors exceeds its threshold, and so on. TSS models the spread of information and influence in networks.

Complementing results on its approximability and extending results for its restriction to trees and bounded treewidth graphs, we classify the influence of the parameters "diameter", "cluster editing number", "vertex cover number", and "feedback edge set number" of the underlying graph on the problem's computational complexity, revealing both tractable and intractable cases. For instance, even for diameter-two split graphs TSS remains W[2]-hard with respect to the parameter "size of the target set". TSS can be efficiently solved on graphs with small feedback edge set number and also turns out to be fixed-parameter tractable when parameterized by the vertex cover number. Both results contrast known parameterized intractability results for the parameter treewidth. While these tractability results are relevant for sparse networks, we also show efficient fixed-parameter algorithms for the parameter cluster edge deletion number, yielding tractability for certain dense networks.

PTAS for Weighted Set Cover on Unit Squares

Algorithmic aspects of modular decomposition

27 March 2003