5 results
Now showing1 - 5 of 5
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Linear kernels and linear-time algorithms for finding large cutsThe maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: – We show that an algorithm by Crowston et al. (Algorithmica 72(3):734–757, 2015) for (Signed) Max- Cut Above Edwards−ErdÖs Bound can be implemented so as to run in linear time 8k ·O(m); this significantly improves the previous analysis with run time 8k · O(n4). – We give an asymptotically optimal kernel for (Signed) Max- Cut Above Edwards−ErdÖs Bound with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. (Theor Comput Sci 513:53–64, 2013). – We improve all known kernels for parameterizations above strongly λ-extendible properties (a generalization of the Max- Cut results) by Crowston et al. (Proceedings of FSTTCS 2013, Leibniz international proceedings in informatics,Guwahati, 2013) from O(k3) vertices to O(k) vertices.Publicationtype: Journal Article229 247 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Big data algorithms beyond machine learningThe availability of big data sets in research, industry and society in general has opened up many possibilities of how to use this data. In many applications, however, it is not the data itself that is of interest but rather we want to answer some question about it. These answers may sometimes be phrased as solutions to an optimization problem. We survey some algorithmic methods that optimize over large-scale data sets, beyond the realm of machine learning.Publicationtype: Journal ArticleScopus© Citations 6 153 178 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Polynomial kernels for deletion to classes of acyclic digraphsWe consider the problem to find a set X of vertices (or arcs) with |X|≤k in a given digraph G such that D=G−X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET (or DIRECTED FEEDBACK ARC SET); the existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider the vertex deletion problem with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of the above three restrictions we can obtain a kernel with kO(1) vertices on general digraphs. We also show that the arc deletion problem with the first two restrictions (out-forest and out-tree) can be solved in polynomial time; this contrasts the status of the vertex deletion problem of these restrictions, which is NP-hard even for acyclic digraphs. The arc and vertex deletion problem with the third restriction (pumpkin), however, can be solved in polynomial time for acyclic digraphs, but becomes NP-hard for general digraphs. We believe that the idea of restricting D could yield new insights towards resolving the status of DIRECTED FEEDBACK VERTEX SET.Publicationtype: Journal Article176 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: with files , Linear kernels and linear-time algorithms for finding large cuts(Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing, 2016-12-01); The maximum cut problem in graphs and its generalizations are fundamental combinatorial problems. Several of these cut problems were recently shown to be fixed-parameter tractable and admit polynomial kernels when parameterized above the tight lower bound measured by the size and order of the graph. In this paper we continue this line of research and considerably improve several of those results: We show that an algorithm by Crowston et al. [ICALP 2012] for (Signed) Max-Cut Above Edwards-Erdös Bound can be implemented in such a way that it runs in linear time 8k · O(m); this significantly improves the previous analysis with run time 8k · O(n4). We give an asymptotically optimal kernel for (Signed) Max-Cut Above Edwards-Erdös Bound with O(k) vertices, improving a kernel with O(k3) vertices by Crowston et al. [COCOON 2013]. We improve all known kernels for strongly λ-extendable properties parameterized above tight lower bound by Crowston et al. [FSTTCS 2013] from O(k3) vertices to O(k) vertices. As a consequence, Max Acyclic Subdigraph parameterized above Poljak-Turzík bound admits a kernel with O(k) vertices and can be solved in time 2O(k) · nO(1); this answers an open question by Crowston et al. [FSTTCS 2012]. All presented kernels can be computed in time O(km).Publicationtype: Conference Paper184 183 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Parameterized complexity dichotomy for Steiner Multicut(2016-09-01); ; ; We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T={T1,...,Tt}, Ti V(G), of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set Ti at least one pair of terminals is in different connected components of G-S. We provide a dichotomy of the parameterized complexity of Steiner Multicut. For any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable, W[1]-hard, or (para-)NP-complete. Our characterization includes a dichotomy for Steiner Multicut on trees as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).Publicationtype: Journal Article174