Many common graph data mining tasks take the form of identifying dense subgraphs (e.g. clustering, clique-finding, etc). In biological applications, the natural model for these dense substructures is often a complete ...
详细信息
ISBN:
(纸本)9781611975673
Many common graph data mining tasks take the form of identifying dense subgraphs (e.g. clustering, clique-finding, etc). In biological applications, the natural model for these dense substructures is often a complete bipartite graph (biclique), and the problem requires enumerating all maximal bicliques (instead of identifying just the largest or densest). The best known algorithm in general graphs is due to Dias et al., and runs in time O(M vertical bar V vertical bar(4)), where M is the number of maximal induced bicliques (MIBs) in the graph. When the graph being searched is itself bipartite, Zhang et al. give a faster algorithm where the time per MIB depends on the number of edges in the graph. In this work, we present a new algorithm for enumerating MIBs in general graphs, whose run time depends on how "close to bipartite" the input is. Specifically, the runtime is parameterized by the size k of an odd cycle transversal (OCT), a vertex set whose deletion results in a bipartite graph. Our algorithm runs in time O(M vertical bar V parallel to E vertical bar k(2)3(k/3)), which is an improvement on Dias et al. whenever k <= 3 log(3) vertical bar V vertical bar. We implement our algorithm alongside a variant of Dias et al.'s in open-source C++ code, and experimentally verify that the OCT-based approach is faster in practice on graphs with a wide variety of sizes, densities, and OCT decompositions.
Cograph Editing is to find for a given graph G = (V, E) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper...
详细信息
Cograph Editing is to find for a given graph G = (V, E) a set of at most k edge additions and deletions that transform G into a cograph. The computational complexity of this problem was open in the past. In this paper, we first show that this problem is NP-hard by a reduction from Exact 3-Cover. Subsequently, we present a parameterized algorithm based on a refined search tree technique with a running time of O(4.612(k) + vertical bar V vertical bar(4.5)), which improves the trivial algorithm of running time O(6(k) + vertical bar V vertical bar(4-5)). (c) 2011 Elsevier B.V. All rights reserved.
We study the STEINER TREE problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of appr...
详细信息
ISBN:
(纸本)9783959770620
We study the STEINER TREE problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parametrization. In particular, on one hand STEINER TREE is known to be APX-hard, and W[2]-hard on the other, if parameterized by the number of non-terminals (Steiner vertices) in the optimum solution. In contrast to this we give an efficient parameterized approximation scheme (EPAS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (PSAKS) for the considered parameter. We further study the parameterized approximability of other variants of STEINER TREE, such as DIRECTED STEINER TREE and STEINER FOREST. For neither of these an EPAS is likely to exist for the studied parameter: for STEINER FOREST an easy observation shows that the problem is APX-hard, even if the input graph contains no Steiner vertices. For DIRECTED STEINER TREE we prove that computing a constant approximation for this parameter is W[1]-hard. Nevertheless, we show that an EPAS exists for UNWEIGHTED DIRECTED STEINER TREE. Also we prove that there is an EPAS and a PSAKS for STEINER FOREST if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter.
A secure set S in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is -complete. ...
详细信息
A secure set S in a graph is defined as a set of vertices such that for any the majority of vertices in the neighborhood of X belongs to S. It is known that deciding whether a set S is secure in a graph is -complete. However, it is still open how this result contributes to the actual complexity of deciding whether for a given graph G and integer k, a non-empty secure set for G of size at most k exists. In this work, we pinpoint the complexity of this problem by showing that it is -complete. Furthermore, the problem has so far not been subject to a parameterized complexity analysis that considers structural parameters. In the present work, we prove that the problem is -hard when parameterized by treewidth. This is surprising since the problem is known to be FPT when parameterized by solution size and "subset problems" that satisfy this property usually tend to be FPT for bounded treewidth as well. Finally, we give an upper bound by showing membership in , and we provide a positive result in the form of an FPT algorithm for checking whether a given set is secure on graphs of bounded treewidth.
In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, w...
详细信息
In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, we propose Fixed Parameter Tractable (FPT) algorithms. For the enumeration task, we construct a Binary Decision Diagram (BDD) to represent all orientations of the two kinds, instead of explicitly enumerating them. We prove that the running time of this construction is bounded by O* (2 pw 2 /4+ o (pw 2 ) ) with respect to the pathwidth pw. We then develop faster FPT algorithms to count acyclic and totally acyclic orientations, running in O* (2 bw 2 /2+o(bw 2 ) ) time, where bw denotes the branch-width of the given graph. These counting algorithms are obtained by applying the observations in our enumerating algorithm to branch decomposition.
In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on...
详细信息
ISBN:
(数字)9783319773131
ISBN:
(纸本)9783319773131;9783319773124
In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (ExT). Our algorithm can even be used to enumerate all generating defaults (ENuMSE) that lead to stable extensions. We show that our algorithm decides EXT in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves ENuMSE with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.
In this paper, we introduce a novel algorithm to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projected variables, where multiple solutions that...
详细信息
ISBN:
(纸本)9783319941448;9783319941431
In this paper, we introduce a novel algorithm to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projected variables, where multiple solutions that are identical when restricted to the projected variables count as only one solution. Our algorithm exploits small treewidth of the primal graph of the input instance. It runs in time O(2(2k+4) n(2)) where k is the treewidth and n is the input size of the instance. In other words, we obtain that the problem PMC is fixed-parameter tractable when parameterized by treewidth. Further, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for PMC, yielding asymptotically tight runtime bounds of our algorithm.
It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to A-cI for constants c, where A is the adjacency matrix of the graph G of order n, can be co...
详细信息
ISBN:
(纸本)9783319774046;9783319774039
It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to A-cI for constants c, where A is the adjacency matrix of the graph G of order n, can be computed in time O(k(2)n). This allows to quickly tell the number of eigenvalues in a given interval.
We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on para...
详细信息
ISBN:
(纸本)9783959770620
We study the parameterized complexity of the Bounded-Degree Vertex Deletion problem (BDD), where the aim is to find a maximum induced subgraph whose maximum degree is below a given degree bound. Our focus lies on parameters that measure the structural properties of the input instance. We first show that the problem is W[1]-hard parameterized by a wide range of fairly restrictive structural parameters such as the feedback vertex set number, pathwidth, treedepth, and even the size of a minimum vertex deletion set into graphs of pathwidth and treedepth at most three. We thereby resolve the main open question stated in Betzler, Bredereck, Niedermeier and Uhlmann (2012) concerning the complexity of BDD parameterized by the feedback vertex set number. On the positive side, we obtain fixed-parameter algorithms for the problem with respect to the decompositional parameter treecut width and a novel problem-specific parameter called the core fracture number.
After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that ...
详细信息
After the number of vertices, Vertex Cover Number is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized problems, including problems that are not directly related to the Vertex Cover Number. Here we consider the TREEWIDTH and PATHWIDTH problems parameterized by k, the size of a minimum vertex cover of the input graph. We show that the PATHWIDTH and TREEWIDTH can be computed in O*(3(k)) time. This complements recent polynomial kernel results for TREEWIDTH and PATHWIDTH parameterized by the Vertex Cover Number. (C) 2014 Elsevier B.V. All rights reserved.
暂无评论