We study the calculation of the largest pairwise intersections in a given set family. We give combinatorial and algorithmic results both for the worst case and for set families where the frequencies of elements follow...
详细信息
We study the calculation of the largest pairwise intersections in a given set family. We give combinatorial and algorithmic results both for the worst case and for set families where the frequencies of elements follow a power law, as words in texts typically do. The results can be used in faster preprocessing routines in a simple approach to multi-document summarization. (C) 2015 Elsevier B.V. All rights reserved.
Given an undirected and connected graph G = (V, E) and two vertices s, t is an element of V, a vertex subset S that separates s and t is called an s-t separator, and an s-t separator is called minimal if no proper sub...
详细信息
Given an undirected and connected graph G = (V, E) and two vertices s, t is an element of V, a vertex subset S that separates s and t is called an s-t separator, and an s-t separator is called minimal if no proper subset of S separates s and t. Moreover, we say that a set S is a minimal separator of G if S is a minimal s-t separator for some s and t. In this paper, we consider finding a minimal (s-t) separator with maximum weight on a vertex-weighted graph. We first prove that these problems are NP-hard. On the other hand, we give an O*(tw(O(tw)))-time deterministic algorithm based on tree decompositions where o* is the order notation omitting the polynomial factor of n. Moreover, we improve the algorithm by using the Rank-Based approach and the running time is O*(38 . 2(omega))tw. Finally, we give an O*(9(tw) . W-2)-time randomized algorithm to determine whether there exists a minimal (s-t) separator where W is its weight and tw is the treewidth of G. (C) 2019 Elsevier B.V. All rights reserved.
We study the parameterized complexity of domination problems on sparse graphs and beyond. The nowhere dense classes of graphs have been proposed as the main model for sparseness that can be utilized algorithmically. T...
详细信息
We study the parameterized complexity of domination problems on sparse graphs and beyond. The nowhere dense classes of graphs have been proposed as the main model for sparseness that can be utilized algorithmically. The class of d-degenerate graphs is not nowhere dense, yet domination remains fixed-parameter tractable. Both nowhere dense classes of graphs and d-degenerate graph classes are biclique-free classes, meaning there is an integer t such that no graph in the class contains K-t,K-t as a subgraph. In this paper we show that various domination problems are fixed-parameter tractable on biclique-free classes of graphs. Our algorithms are simple and rely on results from extremal graph theory that bound the number of edges in a t-biclique free graph. In particular, the problems k-DOMINATING SET, CONNECTED k-DOMINATING SET, INDEPENDENT k-DOMINATING SET and MINIMUM WEIGHT k-DOMINATING SET are shown to be FPT, when parameterized by t + k, on graphs not containing K-t,K-t as a subgraph. With the exception of CONNECTED k-DOMINATING SET all described algorithms are linear in the size of the input graph. (C) 2018 Elsevier B.V. All rights reserved.
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, whe...
详细信息
In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, where p is a constant between 0 and 1. We show that a maximum independent set in a random graph that contains n vertices can be computed in expected computation time 2(O(log22 n)). In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in n vertices can be approximated within a ratio of 2n/2(root log2 n) in expected polynomial time.
Let C be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph G is an element of C with n vertices, finds a simple cycle of size k in G (if exists) in 2(O(k))n time. The algorit...
详细信息
Let C be a proper minor-closed family of graphs. We present a randomized algorithm that given a graph G is an element of C with n vertices, finds a simple cycle of size k in G (if exists) in 2(O(k))n time. The algorithm applies to both directed and undirected graphs. In previous linear time algorithms for this problem, the runtime dependence on k is super-exponential. The algorithm can be derandomized yielding a 2(O(k))n log n time algorithm. (C) 2020 Elsevier B.V. All rights reserved.
In DIRECTED FEEDBACK ARC SET (DFAS) we search for a set of at most k arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if DFAS admits a kernel...
详细信息
In DIRECTED FEEDBACK ARC SET (DFAS) we search for a set of at most k arcs which intersect every cycle in the input digraph. It is a well-known open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size. We consider C-ARC DELETION SET (C-ADS), a variant of DFAS where we want to remove at most k arcs from the input digraph in order to turn it into a digraph of a class C. In this work, we choose C to be the class of funnels. FUNNEL-ADS is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to k. So far no polynomial kernels for this problem were known. Our main result is a kernel for FUNNEL-ADS with O(k(6)) many vertices and O(k(7)) many arcs, computable in O(nm) time, where n is the number of vertices and m the number of arcs in the input digraph.
A link stream is a sequence of pairs of the form (t, {u, v}), where t is an element of N represents a time instant and u v. Given an integer gamma, the gamma-edge between vertices u and v, starting at time t, is the s...
详细信息
A link stream is a sequence of pairs of the form (t, {u, v}), where t is an element of N represents a time instant and u v. Given an integer gamma, the gamma-edge between vertices u and v, starting at time t, is the set of temporally consecutive edges defined by {(t'. {u. v}) I t' is an element of[t, t + gamma - 1]}. We introduce the notion of temporal matching of a link stream to be an independent gamma-edge set belonging to the link stream. We show that the problem of computing a temporal matching of maximum size is NP-hard as soon as gamma > 1. We depict a kernelization algorithmparameterized by the solution size for the problem. As a byproduct we also give a 2-approximation algorithm. Both our 2-approximation and kernelization algorithms are implemented and confronted to link streams collected from real world graph data. We observe that finding temporal matchings is a sensitive question when mining our data from such a perspective as: managing peer-working when any pair of peers X and Y are to collaborate over a period of one month, at an average rate of at least two email exchanges every week. We furthermore design a link stream generating process by mimicking the behavior of a random moving group of particles under natural simulation, and confront our algorithms to these generated instances of link streams. All the implementations are open source. (C) 2019 Elsevier B.V. All rights reserved.
A vector with at most k nonzeros is called k-sparse. We show that enumerating the support vectors of k-sparse solutions to a system Ax = b of r-sparse linear equations (i.e., where the rows of A are r-sparse) is fixed...
详细信息
A vector with at most k nonzeros is called k-sparse. We show that enumerating the support vectors of k-sparse solutions to a system Ax = b of r-sparse linear equations (i.e., where the rows of A are r-sparse) is fixed-parameter tractable (FPT) in the combined parameter r, k. We give different branching algorithms based on the close relationship to the hitting set problem in fixed-rank hypergraphs. For r = 2 the problem is simple. For 0, 1-matrices A we can also compute an O(rk(r)) kernel. For systems of linear inequalities we get an FPT result in the combined parameter d, k, where d is the total number of minimal solutions. This is achieved by interpreting the problem as a case of group testing in the complex model. The problems stem from the reconstruction of chemical mixtures by observable reaction products. (C) 2012 Elsevier B.V. All rights reserved.
Given a matroid M = (E, I), and a family S of p-subsets of E, a subfamily (S) over cap subset of S represents S if for any X is an element of S and Y subset of E \ X satisfying X boolean OR Y is an element of I, there...
详细信息
Given a matroid M = (E, I), and a family S of p-subsets of E, a subfamily (S) over cap subset of S represents S if for any X is an element of S and Y subset of E \ X satisfying X boolean OR Y is an element of I, there is a set (X) over cap is an element of (S) over cap disjoint from Y, where (X) over cap boolean OR Y is an element of I. We show that a powerful technique for computing representative families, introduced by Fomin et al, (2014)15], leads to a unified approach for substantially improving the running times of parameterized algorithms for some classic problems. This includes k-PARTIAL COVER, k-INTERNAL OUT-BRANCHING, and LONG DIRECTED CYCLE, among others. Our approach exploits an interesting tradeoff between running time and the representative family size. (C) 2015 Elsevier Inc. All rights reserved.
parameterized algorithms and kernelization algorithms are presented for the weighted P-2-Packing problem, which is a generalization of the famous Graph Matching problem. The parameterized algorithms are based on the f...
详细信息
parameterized algorithms and kernelization algorithms are presented for the weighted P-2-Packing problem, which is a generalization of the famous Graph Matching problem. The parameterized algorithms are based on the following new techniques and observations: (1) new study on structure relationship between graph matchings in general graphs and P-2-packings in bipartite graphs;(2) an effective graph bi-partitioning algorithm;and (3) a polynomial-time algorithm for a constrained weighted P-2-Packing problem in bipartite graphs. The kernelization algorithms are based on the following new techniques: (1) the application of graph matching in kernelization;(2) a crown reduction structure for weighted problems. These techniques lead to randomized and deterministic parameterized algorithms that significantly improve the previous best upper bounds for the problem for both weighted and unweighted versions. For the kernelization algorithm, by using a weighted version of crown reduction, a kernel of size O(k(2)) is presented, where k is the given parameter of the problem. (C) 2013 Elsevier B.V. All rights reserved.
暂无评论