argumentation frameworks have received a lot of interest in recent years. Most computational problems in this area are intractable but several tradable fragments have been identified. In particular, Dunne showed that ...
详细信息
argumentation frameworks have received a lot of interest in recent years. Most computational problems in this area are intractable but several tradable fragments have been identified. In particular, Dunne showed that many problems can be solved in linear time for argumentation frameworks of bounded tree-width. However, these tractability results, which were obtained via Courcelle's Theorem, do not directly lead to efficient algorithms. The goal of this paper is to turn the theoretical tractability results into efficient algorithms and to explore the potential of directed notions of tree-width for defining larger tractable fragments. As a by-product, we will sharpen some known complexity results. (C) 2012 Elsevier B.V. All rights reserved.
In the classic MINIMUM BISECTION problem we are given as input an undirected graph G and an integer k. The task is to determine whether there is a partition of V(G) into two parts A and B such that parallel to A verti...
详细信息
In the classic MINIMUM BISECTION problem we are given as input an undirected graph G and an integer k. The task is to determine whether there is a partition of V(G) into two parts A and B such that parallel to A vertical bar-vertical bar B parallel to <= 1 and there are at most k edges with one endpoint in A and the other in B. In this paper we give an algorithm for MINIMUM BISECTION with running time 2(O)(k(3))n(3) log(3) n. This is the first fixedparameter tractable algorithm for MINIMUM BISECTION parameterized by k. At the core of our algorithm lies a new decomposition theorem that states that every graph G can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any separator of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek a bisection of minimum weight among solutions that contain at most k edges.
A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heu...
详细信息
A widely used class of algorithms for computing tree decompositions of graphs are heuristics that compute an elimination order, i.e., a permutation of the vertex set. In this paper, we propose to turbocharge these heuristics. For a target treewidth k, suppose the heuristic has already computed a partial elimination order of width at most k, but extending it by one more vertex exceeds the target width k. At this moment of regret, we solve a subproblem which is to recompute the lastc positions of the partial elimination order such that it can be extended without exceeding width k. We show that this subproblem is fixed-parameter tractable when parameterized by k and c, but it is para-NP-hard and W[1]-hard when parameterized by only k or c, respectively. Our experimental evaluation of the FPT algorithm shows that we can trade a reasonable increase of the running time for the quality of the solution.
We introduce the NP-hard graph-based data clustering problem s-Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-pl...
详细信息
We introduce the NP-hard graph-based data clustering problem s-Plex Cluster Vertex Deletion, where the task is to delete at most k vertices from a graph so that the connected components of the resulting graph are s-plexes. In an s-plex, every vertex has an edge to all but at most s-1 other vertices;cliques are 1-plexes. We propose a new method based on "approximation and tidying" for kernelizing vertex deletion problems whose goal graphs can be characterized by forbidden induced subgraphs. The method exploits polynomial-time approximation results and thus provides a useful link between approximation and kernelization. Employing "approximation and tidying", we develop data reduction rules that, in O(ksn (2)) time, transform an s-Plex Cluster Vertex Deletion instance with n vertices into an equivalent instance with O(k (2) s (3)) vertices, yielding a problem kernel. To this end, we also show how to exploit structural properties of the specific problem in order to significantly improve the running time of the proposed kernelization method.
In this paper, we deal with restoring missing information in molecule databases: Many data formats only store the atoms' configuration but omit bond multiplicities. As this information is essential for various app...
详细信息
In this paper, we deal with restoring missing information in molecule databases: Many data formats only store the atoms' configuration but omit bond multiplicities. As this information is essential for various applications in chemistry, we consider the problem of recovering bond type information using a scoring function for the possible valences of each atom the BOND ORDER ASSIGNMENT problem. We show that the BOND ORDER ASSIGNMENT is NP-hard, and its maximization version is MAX SNP-hard. We then give two exact fixed-parameter algorithms for the problem, where bond orders are computed via dynamic programming on a tree decomposition of the molecule graph. We evaluate our algorithm on a set of real molecule graphs and find that it works fast in practice. (C) 2011 Elsevier B.V. All rights reserved.
Low-rank binary matrix approximation is a generic problem where one seeks a good approximation of a binary matrix by another binary matrix with some specific properties. A good approximation means that the difference ...
详细信息
Low-rank binary matrix approximation is a generic problem where one seeks a good approximation of a binary matrix by another binary matrix with some specific properties. A good approximation means that the difference between the two matrices in some matrix norm is small. The properties of the approximation binary matrix could be: a small number of different columns, a small binary rank or a small Boolean rank. Unfortunately, most variants of these problems are NP-hard. Due to this, we initiate the systematic algorithmic study of low-rank binary matrix approximation from the perspective of parameterized complexity. We show in which cases and under what conditions the problem is fixed-parameter tractable, admits a polynomial kernel and can be solved in parameterized subexponential time.
We do Computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps bo...
详细信息
We do Computational studies concerning the enumeration of isolated cliques in graphs. Isolation, as recently introduced, measures the degree of connectedness of the cliques to the rest of the graph. Isolation helps both in getting faster algorithms for the enumeration of maximal general cliques and in filtering out cliques with special semantics. We compare three isolation concepts and their combination with two enumeration modi for maximal cliques ("isolated maximal" vs "maximal isolated"). All studied concepts exhibit the fixed-parameter tractability of the enumeration task with respect to the parameter "degree of isolation". We provide a first systematic experimental study of the corresponding enumeration algorithms, using synthetic graphs (in the G(n,m,p) model), financial networks, and a music artist similarity network, proposing the enumeration of isolated cliques as a useful instrument in analyzing financial and social networks. (C) 2009 Elsevier B.V. All rights reserved.
The diameter of a graph is the maximum distance between any pair of vertices in the graph. The DIAMETER-t AUGMENTATION problem takes as input a graph G = (V. E) and a positive integer k and asks whether there exists a...
详细信息
The diameter of a graph is the maximum distance between any pair of vertices in the graph. The DIAMETER-t AUGMENTATION problem takes as input a graph G = (V. E) and a positive integer k and asks whether there exists a set E-2 of at most k new edges so that the graph G(2) = (V, E boolean OR E-2) has diameter t. This problem is NP-hard (Schoone et al. 1987) [10], even in the t = 2 case (Li et al. 1992) [7]. We give a parameterized reduction from DOMINATING SET to DIAMETER-t AUGMENTATION to prove that DIAMETER-t AUGMENTATION is W[2]-hard for every t. (C) 2013 Elsevier B.V. All rights reserved.
The Kneser graph K(n, k) is defined for integers n and k with n \geq 2k as the graph whose vertices are all the k -subsets of [n] = {1 , 2 , ... , n\} where two such sets are adjacent if they are disjoint. The Schrijv...
详细信息
The Kneser graph K(n, k) is defined for integers n and k with n \geq 2k as the graph whose vertices are all the k -subsets of [n] = {1 , 2 , ... , n\} where two such sets are adjacent if they are disjoint. The Schrijver graph S(n, k) is defined as the subgraph of K(n, k) induced by the collection of all k -subsets of [n] that do not include two consecutive elements modulo n. It is known that the chromatic number of both K(n, k) and S(n, k) is n - 2k + 2. In the computational KNESER and SCHRIJVER problems, we are given access to a coloring with n - 2k + 1 colors of the vertices of K(n, k) and S(n, k), respectively, and the goal is to find a monochromatic edge. We prove that the problems admit randomized algorithms with running time nO (1) \cdot kO(k) , hence they are fixedparameter tractable with respect to the parameter k. The analysis involves structural results on intersecting families and on induced subgraphs of Kneser and Schrijver graphs. We also study the AGREEABLE -SET problem of assigning a small subset of a set of m items to a group of \ell agents, so that all agents value the subset at least as much as its complement. As an application of our algorithm for the KNESER problem, we obtain a randomized polynomial -time algorithm for the AGREEABLE -SET problem for instances with \ell \geq m - O ( lo \mathrm{g}m l o\mathrm{g}lo \mathrm{g}m ). We further show that the AGREEABLE -SET problem is at least as hard as a variant of the KNESER problem with extended access to the input coloring.
Given a graph G = (V, E), A subset of V, and integers k and l, the (A, l)-PATH PACKING problem asks to find k vertex-disjoint paths of length exactly l that have endpoints in A and internal points in V\A. We study the...
详细信息
Given a graph G = (V, E), A subset of V, and integers k and l, the (A, l)-PATH PACKING problem asks to find k vertex-disjoint paths of length exactly l that have endpoints in A and internal points in V\A. We study the parameterized complexity of this problem with parameters vertical bar A vertical bar, l, k, treewidth, pathwidth, and their combinations. We present sharp complexity contrasts with respect to these parameters. Among other results, we show that the problem is polynomial-time solvable when l <= 3, while it is NP-complete for constant l >= 4. We also show that the problem is W[1]-hard parameterized by pathwidth + vertical bar A vertical bar, while it is fixed-parameter tractable parameterized by treewidth + l. Additionally, we study a variant called SHORT A- PATH PACKING that asks to find k vertex-disjoint paths of length at most l. We show that all our positive results on the exact-length version can be translated to this version and show the hardness of the cases where vertical bar A vertical bar or l is a constant.
暂无评论