| 1. |
|
|
| 2. |
- Dannenberg, Katharina, et al.
(författare)
-
The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets
- 2019
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X. ; 257, s. 101-114
-
Tidskriftsartikel (refereegranskat)abstract
- The NP-hard maximum rooted resolved triplets consistency problem (MRTC) takes as input a set [Formula presented] of leaf labels and a set [Formula presented] of resolved triplets over [Formula presented] and asks for a rooted phylogenetic tree that is consistent with the maximum number of elements in [Formula presented]. This article studies the approximability of a generalization of the problem called the maximum rooted triplets consistency problem (MTC) where in addition to resolved triplets, the input may contain fan triplets, forbidden resolved triplets, and forbidden fan triplets. To begin with, we observe that MTC admits a [Formula presented]-approximation in polynomial time. Next, we generalize Wu's exact exponential-time algorithm for MRTC (Wu, 2004) to MTC. Forcing the algorithm to always output a rooted [Formula presented]-ary phylogenetic tree for any specified [Formula presented] subsequently leads to an exponential-time approximation scheme (ETAS) for MTC. We then present a polynomial-time approximation scheme (PTAS) for complete instances of MTC (meaning that for every [Formula presented] with [Formula presented], [Formula presented] contains at least one rooted triplet involving the leaf labels in [Formula presented]), based on the techniques introduced by Jiang et al. (2001) for a related problem. We also study the computational complexity of MTC restricted to fan triplets and forbidden fan triplets. Finally, extensions to weighted instances are considered.
|
|
| 3. |
- Dessmark, Anders, et al.
(författare)
-
On the approximability of maximum and minimum edge clique partition problems
- 2007
-
Ingår i: International Journal of Foundations of Computer Science. - 0129-0541. ; 18:2, s. 217-226
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the following clustering problems: given an undirected graph, partition its vertices into disjoint clusters such that each cluster forms a clique and the number of edges within the clusters is maximized (Max-ECP), or the number of edges between clusters is minimized (Min-ECP). These problems arise naturally in the DNA clone classification. We investigate the hardness of finding such partitions and provide approximation algorithms. Further, we show that greedy strategies yield constant factor approximations for graph classes for which maximum cliques can be found efficiently.
|
|
| 4. |
- Dessmark, Anders, et al.
(författare)
-
On the approximability of maximum and minimum edge clique partition problems
- 2006
-
Ingår i: Conferences in Research and Practice in Information Technology Series. - 1920682333 ; 168, s. 101-105
-
Konferensbidrag (refereegranskat)abstract
- We consider the following clustering problems: given a general undirected graph, partition its vertices into disjoint clusters such that each cluster forms a clique and the number of edges within the clusters is maximized (Max-ECP), or the number of edges between clusters is minimized (Min-ECP). These problems arise naturally in the DNA clone classification. We investigate the hardness of finding such partitions and provide approximation algorithms. Further, we show that greedy strategies yield constant factor approxi mations for graph classes for which maximum cliques can be found efficiently.
|
|
| 5. |
- Dessmark, Anders, et al.
(författare)
-
Polynomial-time algorithms for the ordered maximum agreement subtree problem
- 2007
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 3109, s. 220-229
-
Tidskriftsartikel (refereegranskat)abstract
- For a set of rooted, unordered, distinctly leaf-labeled trees, the NP-hard maximum agreement subtree problem (MAST) asks for a tree contained (up to isomorphism or homeomorphism) in all of the input trees with as many labeled leaves as possible. We study the ordered variants of MAST where the trees are uniformly or non-uniformly ordered. We provide the first known polynomial-time algorithms for the uniformly and non-uniformly ordered homeomorphic variants as well as the uniformly and non-uniformly ordered isomorphic variants of MAST. Our algorithms run in time O(kn(3)), O (n(3) min{kn, n + log(k-1) n}), O(kn(3)), and O(n(3) min{kn, n + log(k-1) n)), respectively, where n is the number of leaf labels and k is the number of input trees.
|
|
| 6. |
- Dessmark, Anders, et al.
(författare)
-
Subexponential-time framework for optimal embeddings of graphs in integer lattices
- 2004
-
Ingår i: Algorithm Theory - SWAT 2004/Lecture Notes in Computer Science. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. - 9783540223399 ; 3111, s. 248-259
-
Konferensbidrag (refereegranskat)abstract
- We present a general framework for computing various optimal embeddings of undirected and directed connected graphs in two and multi-dimensional integer lattices in time sub-exponential either in the minimum number n of lattice points used by such optimal embeddings or in the budget upper bound b on the number of lattice points that may be used in an embedding. The sub-exponential upper bounds in the two dimensional case and d-dimensional case are respectively of the form 2(O(rootln log n)), 2(Orootlb log b)) and 2(n)(O(dl1/d) ((d-1)/d)(log n)),2(O(dl l/d(d-1)/d) (log b),) where l stands for the degree of the allowed overlap. For the problem of minimum total edge length planar or multi-dimensional embedding or layout of a graph and the problem of an optimal protein folding in the so called HP model we obtain the upper bounds in terms of n. Note that in case of protein folding n is also the size of the input. The list of problems for which we can derive the upper bounds in terms of b includes among other things: 1. a minimum area planar embedding or layout of a graph, 2. a minimum bend planar or three dimensional embedding or layout, 3. a minimum maximum edge length planar or three dimensional embedding or layout.
|
|
| 7. |
- Floderus, Peter, et al.
(författare)
-
Detecting and Counting Small Pattern Graphs
- 2015
-
Ingår i: SIAM Journal on Discrete Mathematics. - : Society for Industrial & Applied Mathematics (SIAM). - 0895-4801 .- 1095-7146. ; 29:3, s. 1322-1339
-
Tidskriftsartikel (refereegranskat)abstract
- We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.
|
|
| 8. |
- Floderus, Peter, et al.
(författare)
-
Detecting and Counting Small Pattern Graphs
- 2013
-
Ingår i: Algorithms and Computation. - Berlin, Heidelberg : Springer Berlin Heidelberg. - 1611-3349 .- 0302-9743. ; 8283, s. 547-557
-
Konferensbidrag (refereegranskat)abstract
- We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for non-identity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size s and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slower combinatorial algorithm.
|
|
| 9. |
- Floderus, Peter, et al.
(författare)
-
Induced subgraph isomorphism: Are some patterns substantially easier than others?
- 2015
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 605, s. 119-128
-
Tidskriftsartikel (refereegranskat)abstract
- The complexity of the subgraph isomorphism problem where the pattern graph is of fixed size is well known to depend on the topology of the pattern graph. Here, we present two results which, in contrast, provide evidence that no topology of an induced subgraph of fixed size can be substantially easier to detect or count than an independent set of related size. We show that any fixed pattern graph having a maximum independent set of size k that is disjoint from other maximum independent sets is not easier to detect as an induced subgraph than an independent set of size k. It follows in particular that an induced path on 2k-1 vertices is not easier to detect than an independent set on k vertices, and that an induced cycle on 2k vertices is not easier to detect than an independent set on k vertices. In view of linear time upper bounds on the detection of induced path of length two and three, our lower bound is tight. Similar corollaries hold for the detection of induced complete bipartite graphs and an induced paw and its generalizations. We show also that for an arbitrary pattern graph H on k vertices with no isolated vertices, there is a simple subdivision of H, resulting from splitting each edge into a path of length four and attaching a distinct path of length three at each vertex of degree one, that is not easier to detect or count than an independent set on k vertices, respectively. Next, we show that the so-called diamond and its generalizations on k vertices are not easier to detect as induced subgraphs than an independent set on three vertices or an independent set on k vertices, respectively. For C-4, we give a weaker evidence of its hardness in terms of an independent set on three vertices. Finally, we derive several results relating the complexity of the edge-colored variant of induced subgraph isomorphism to that of the standard variant. (C) 2015 Elsevier B.V. All rights reserved.
|
|
| 10. |
- Kowaluk, Miroslaw, et al.
(författare)
-
Counting and Detecting Small Subgraphs via Equations
- 2013
-
Ingår i: SIAM Journal on Discrete Mathematics. - : Society for Industrial & Applied Mathematics (SIAM). - 0895-4801 .- 1095-7146. ; 27:2, s. 892-909
-
Tidskriftsartikel (refereegranskat)abstract
- We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let H be a fixed graph with k vertices and an independent set of size s. 1. Detecting if an n-vertex graph contains a (not necessarily induced) subgraph isomorphic to H can be done in time O(n(omega(inverte right perpendicular(k-s)/2inverted letf perpendicular,1,1 right perpendicular(k- s)/2inverted letf perpendicular))), where omega(p, q, r) is the exponent of fast arithmetic matrix multiplication of an n(p) x n(q) matrix by an n(q) x n(r) matrix. 2. When s = 2, counting the number of (not necessarily induced) subgraphs isomorphic to H can be done in the same time, i.e., in time O(n(omega(inverted right perpendicular(k-2)/2inverted left perpendicular,1, inverted right perpendicular(k-2)/2inverted left perpendicular))). It follows in particular that we can count the number of subgraphs isomorphic to any H on four vertices that is not K-4 in time O(n(omega)), where omega = omega(1, 1, 1) is known to be smaller than 2.373. Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K-5 in time O(n(omega(2,1,1))), where omega(2, 1, 1) is known to be smaller than 3.257. Finally, we derive input-sensitive variants of our time upper bounds. They are partially expressed in terms of the number m of edges of the input graph and do not rely on fast matrix multiplication.
|
|
