We provide a new theory, alternative to bidimensionality, of sub-exponential parameterized algorithms on planar graphs, which is based on the notion of compactness. Roughly speaking, a parameterized problem is (r, q)-...
详细信息
ISBN:
(纸本)9783642237195
We provide a new theory, alternative to bidimensionality, of sub-exponential parameterized algorithms on planar graphs, which is based on the notion of compactness. Roughly speaking, a parameterized problem is (r, q)-compact when all the faces and vertices of its YES-instances are "r-radially dominated" by some vertex set whose size is at most q times the parameter. We prove that if a parameterized problem can be solved in c(branchwidth(G)) n(O(1)) steps and is (r, q)-compact, then it can be solved by a c(*** q.k) n(O(1)) step algorithm (where k is the parameter). Our framework is general enough to unify the analysis of almost all known sub-exponential parameterized algorithms on planar graphs and improves or matches their running times. Our results are based on an improved combinatorial bound on the branchwidth of planar graphs that bypasses the grid-minor exclusion theorem. That way, our approach encompasses new problems where bidimensionality theory do not directly provide sub-exponential parameterized algorithms.
In this paper, we prove that the general CNF satisfiability problem can be solved in O*(1.0646(L)) time, where L is the length of the input CNF-formula (i.e., the total number of literals in the formula), which improv...
详细信息
ISBN:
(纸本)9783030802233;9783030802226
In this paper, we prove that the general CNF satisfiability problem can be solved in O*(1.0646(L)) time, where L is the length of the input CNF-formula (i.e., the total number of literals in the formula), which improves the current bound O* (1. 0652(L)) given by Chen and Liu 12 years ago. Our algorithm is a standard branch-and-search algorithm analyzed by using the measure-and-conquer method. We avoid the bottle-neck in Chen and Liu's algorithm by simplifying the branching operation for 4-degree variables and carefully analyzing the branching operation for 5-degree variables. To simplify case-analyses, we also introduce a general framework for analysis, which may be able to be used in other problems.
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.
In rational decision-making models, transitivity of preferences is an important principle. In a transitive preference, one who prefers x to y and y to z must prefer x to z. Many preference relations, including total o...
详细信息
In rational decision-making models, transitivity of preferences is an important principle. In a transitive preference, one who prefers x to y and y to z must prefer x to z. Many preference relations, including total order, weak order, partial order, and semiorder, are transitive. As a preference which is transitive yet not all pairs of elements are comparable, partial orders have been studied extensively. In graph theory, a comparability graph is an undirected graph which connects all comparable elements in a partial order. A transitive orientation is an assignment of direction to every edge so that the resulting directed graph is transitive. A graph is transitive if there is such an assignment. Comparability graphs are a class of graphs where clique, coloring, and many other optimization problems are solved by polynomial algorithms. It also has close connections with other classes of graphs, such as interval graphs, permutation graphs, and perfect graphs. In this dissertation, we define new measures for transitivity to generalize comparability graphs. We introduce the concept of double threshold digraphs together with a parameter $\lambda$ which we define as our degree of transitivity. We also define another measure of transitivity, $\beta$, as the longest directed path such that there is no edge from the first vertex to the last vertex. We present approximation algorithms and parameterized algorithms for optimization problems and demonstrate that they are efficient for "almost-transitive" preferences.
The Subgraph Isomorphism problem asks, given a host graph G on n vertices and a pattern graph P on k vertices, whether G contains a subgraph isomorphic to P. The restriction of this problem to planar graphs has often ...
详细信息
ISBN:
(纸本)9783939897354
The Subgraph Isomorphism problem asks, given a host graph G on n vertices and a pattern graph P on k vertices, whether G contains a subgraph isomorphic to P. The restriction of this problem to planar graphs has often been considered. After a sequence of improvements, the current best algorithm for planar graphs is a linear time algorithm by Dorn (STACS '10), with complexity 2(O(k)) . O(n). We generalize this result, by giving an algorithm of the same complexity for graphs that can be embedded in surfaces of bounded genus. In addition, we simplify the algorithm and analysis. The key to these improvements is the introduction of surface split decompositions for bounded genus graphs, which generalize sphere cut decompositions for planar graphs. We extend the algorithm for the problem of counting and generating all subgraphs isomorphic to P, even for the case where P is disconnected. This answers an open question by Eppstein (JGAA'99).
Generalised hypertree width (ghw) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing ghw of a hypergraph is notoriously hard. The deci...
详细信息
ISBN:
(纸本)9783959773119
Generalised hypertree width (ghw) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing ghw of a hypergraph is notoriously hard. The decision version of the problem, checking whether ghw(H) <= k, is PARANP-hard when parameterised by k. Furthermore, approximation of ghw is at least as hard as approximation of SET-COVER, which is known to not admit any FPT approximation algorithms. Research in the computation of ghw so far has focused on identifying structural restrictions to hypergraphs such as bounds on the size of edge intersections that permit XP algorithms for ghw. Yet, even under these restrictions that problem has so far evaded any kind of FPT algorithm. In this paper we make the first step towards FPT algorithms for ghw by showing that the parameter can be approximated in FPT time for graphs of bounded edge intersection size. In concrete terms we show that there exists an FPT algorithm, parameterised by k and d, that for input hypergraph H with maximal cardinality of edge intersections d and integer k either outputs a tree decomposition with ghw(H) <= 4k(k d+1)(2k 1), or rejects, in which case it is guaranteed that ghw(H) > k. Thus, in the special case of hypergraphs of bounded edge intersection, we obtain an FPT O(k(3)) -approximation algorithm for ghw.
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.
In the paper, we define a new parameter for tournaments called degreewidth which can be seen as a measure of how far is the tournament from being acyclic. The degreewidth of a tournament T denoted by Delta(T) is the m...
详细信息
ISBN:
(数字)9783031433801
ISBN:
(纸本)9783031433795;9783031433801
In the paper, we define a new parameter for tournaments called degreewidth which can be seen as a measure of how far is the tournament from being acyclic. The degreewidth of a tournament T denoted by Delta(T) is the minimum value k for which we can find an ordering < v(1),..., v(n)> of the vertices of T such that every vertex is incident to at most k backward arcs (i.e. an arc (v(i), v(j)) such that j < i). Thus, a tournament is acyclic if and only if its degreewidth is zero. Additionally, the class of sparse tournaments defined by Bessy et al. [ESA 2017] is exactly the class of tournaments with degreewidth one. We study computational complexity of finding degreewidth. We show it is NP-hard and complement this result with a 3-approximation algorithm. We provide a O(n(3))-time algorithm to decide if a tournament is sparse, where n is its number of vertices. Finally, we study classical graph problems Dominating Set and Feedback Vertex Set parameterized by degreewidth. We show the former is fixed-parameter tractable whereas the latter is NP-hard even on sparse tournaments. Additionally, we show polynomial time algorithm for Feedback Arc Set on sparse tournaments.
Since metabolites cannot be predicted from the genome sequence, high-throughput de novo identification of small molecules is highly sought. Mass spectrometry (MS) in combination with a fragmentation technique is commo...
详细信息
ISBN:
(纸本)9783642200359
Since metabolites cannot be predicted from the genome sequence, high-throughput de novo identification of small molecules is highly sought. Mass spectrometry (MS) in combination with a fragmentation technique is commonly used for this task. Unfortunately, automated analysis of such data is in its infancy. Recently, fragmentation trees have been proposed as an analysis tool for such data. Additional fragmentation steps (MSn) reveal more information about the molecule. We propose to use MSn data for the computation of fragmentation trees, and present the COLORFUL SUBTREE CLOSURE problem to formalize this task: There, we search for a colorful subtree inside a vertex-colored graph, such that the weight of the transitive closure of the subtree is maximal. We give several negative results regarding the tractability and approximability of this and related problems. We then present an exact dynamic programming algorithm, which is parameterized by the number of colors in the graph and is swift in practice. Evaluation of our method on a dataset of 45 reference compounds showed that the quality of constructed fragmentation trees is improved by using MSn instead of MS2 measurements.
暂无评论