Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLinear-Time Recognition of Probe Interval Graphs
152
0
0.0
(
0
)
Added by
Ross M. McConnell
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The interval graph for a set of intervals on a line consists of one vertex for each interval, and an edge for each intersecting pair of intervals. A probe interval graph is a variant that is motivated by an application to genomics, where the intervals are partitioned into two sets: probes and non-probes. The graph has an edge between two vertices if they intersect and at least one of them is a probe. We give a linear-time algorithm for determining whether a given graph and partition of vertices into probes and non-probes is a probe interval graph. If it is, we give a layout of intervals that proves this. We can also determine whether the layout of the intervals is uniquely constrained within the same time bound. As part of the algorithm, we solve the consecutive-ones probe matrix problem in linear time, develop algorithms for operating on PQ trees, and give results that relate PQ trees for different submatrices of a consecutive-ones matrix.
rate research
Read More
A graph $G = (V,E)$ is a double-threshold graph if there exist a vertex-weight function $w colon V to mathbb{R}$ and two real numbers $mathtt{lb}, mathtt{ub} in mathbb{R}$ such that $uv in E$ if and only if $mathtt{lb} le mathtt{w}(u) + mathtt{w}(v) le mathtt{ub}$. In the literature, those graphs are studied as the pairwise compatibility graphs that have stars as their underlying trees. We give a new characterization of double-threshold graphs, which gives connections to bipartite permutation graphs. Using the new characterization, we present a linear-time algorithm for recognizing double-threshold graphs. Prior to our work, the fastest known algorithm by Xiao and Nagamochi [COCOON 2018] ran in $O(n^6)$ time, where $n$ is the number of vertices.
Interval graphs were used in the study of genomics by the famous molecular biologist Benzer. Later on probe interval graphs were introduced by Zhang as a generalization of interval graphs for the study of cosmid contig mapping of DNA. A tagged probe interval graph (briefly, TPIG) is motivated by similar applications to genomics, where the set of vertices is partitioned into two sets, namely, probes and nonprobes and there is an interval on the real line corresponding to each vertex. The graph has an edge between two probe vertices if their corresponding intervals intersect, has an edge between a probe vertex and a nonprobe vertex if the interval corresponding to a nonprobe vertex contains at least one end point of the interval corresponding to a probe vertex and the set of non-probe vertices is an independent set. This class of graphs have been defined nearly two decades ago, but till today there is no known recognition algorithm for it. In this paper, we consider a natural subclass of TPIG, namely, the class of proper tagged probe interval graphs (in short PTPIG). We present characterization and a linear time recognition algorithm for PTPIG. To obtain this characterization theorem we introduce a new concept called canonical sequence for proper interval graphs, which, we belief, has an independent interest in the study of proper interval graphs. Also to obtain the recognition algorithm for PTPIG, we introduce and solve a variation of consecutive $1$s problem, namely, oriented consecutive $1$s problem and some variations of PQ-tree algorithm. We also discuss the interrelations between the classes of PTPIG and TPIG with probe interval graphs and probe proper interval graphs.
In this paper we obtain several characterizations of the adjacency matrix of a probe interval graph. In course of this study we describe an easy method of obtaining interval representation of an interval bipartite graph from its adjacency matrix. Finally, we note that if we add a loop at every probe vertex of a probe interval graph, then the Ferrers dimension of the corresponding symmetric bipartite graph is at most 3.
We initiate the study of a new parameterization of graph problems. In a multiple interval representation of a graph, each vertex is associated to at least one interval of the real line, with an edge between two vertices if and only if an interval associated to one vertex has a nonempty intersection with an interval associated to the other vertex. A graph on n vertices is a k-gap interval graph if it has a multiple interval representation with at most n+k intervals in total. In order to scale up the nice algorithmic properties of interval graphs (where k=0), we parameterize graph problems by k, and find FPT algorithms for several problems, including Feedback Vertex Set, Dominating Set, Independent Set, Clique, Clique Cover, and Multiple Interval Transversal. The Coloring problem turns out to be W[1]-hard and we design an XP algorithm for the recognition problem.
Let $G = (V,E,w)$ be a weighted undirected graph on $|V| = n$ vertices and $|E| = m$ edges, let $k ge 1$ be any integer, and let $epsilon < 1$ be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness, which culminate a long line of work in this area. (By near-optimal we mean optimal under ErdH{o}s girth conjecture and disregarding the $epsilon$-dependencies.) - There are (deterministic) algorithms for constructing $(2k-1)(1+epsilon)$-spanners for $G$ with a near-optimal sparsity of $O(n^{1/k} log(1/epsilon)/epsilon))$. The first algorithm can be implemented in the pointer-machine model within time $O(malpha(m,n) log(1/epsilon)/epsilon) + SORT(m))$, where $alpha( , )$ is the two-parameter inverse-Ackermann function and $SORT(m)$ is the time needed to sort $m$ integers. The second algorithm can be implemented in the WORD RAM model within time $O(m log(1/epsilon)/epsilon))$. - There is a (deterministic) algorithm for constructing a $(2k-1)(1+epsilon)$-spanner for $G$ that achieves a near-optimal bound of $O(n^{1/k}mathrm{poly}(1/epsilon))$ on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time $O(malpha(m,n) mathrm{poly}(1/epsilon) + SORT(m))$ and in the WORD RAM model within time $O(m alpha(m,n) mathrm{poly}(1/epsilon))$. The previous fastest constructions of $(2k-1)(1+epsilon)$-spanners with near-optimal sparsity incur a runtime of is $O(min{m(n^{1+1/k}) + nlog n,k n^{2+1/k}})$, even regardless of the lightness. Importantly, the greedy spanner for stretch $2k-1$ has sparsity $O(n^{1/k})$ -- with no $epsilon$-dependence whatsoever, but its runtime is $O(m(n^{1+1/k} + nlog n))$. Moreover, the state-of-the-art lightness bound of any $(2k-1)$-spanner is poor, even regardless of the sparsity and runtime.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
