Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLinear-Time Recognition of Double-Threshold Graphs
77
0
0.0
(
0
)
Added by
Yota Otachi
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved trees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.
For every constant $d geq 3$ and $epsilon > 0$, we give a deterministic $mathrm{poly}(n)$-time algorithm that outputs a $d$-regular graph on $Theta(n)$ vertices that is $epsilon$-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by $2sqrt{d-1} + epsilon$ (excluding the single trivial eigenvalue of~$d$).
The partial representation extension problem generalizes the recognition problem for classes of graphs defined in terms of vertex representations. We exhibit circular-arc graphs as the first example of a graph class where the recognition is polynomially solvable while the representation extension problem is NP-complete. In this setting, several arcs are predrawn and we ask whether this partial representation can be completed. We complement this hardness argument with tractability results of the representation extension problem on various subclasses of circular-arc graphs, most notably on all variants of Helly circular-arc graphs. In particular, we give linear-time algorithms for extending normal proper Helly and proper Helly representations. For normal Helly circular-arc representations we give an $O(n^3)$-time algorithm. Surprisingly, for Helly representations, the complexity hinges on the seemingly irrelevant detail of whether the predrawn arcs have distinct or non-distinct endpoints: In the former case the previous algorithm can be extended, whereas the latter case turns out to be NP-complete. We also prove that representation extension problem of unit circular-arc graphs is NP-complete.
We study the computational complexity of two well-known graph transversal problems, namely Subset Feedback Vertex Set and Subset Odd Cycle Transversal, by restricting the input to $H$-free graphs, that is, to graphs that do not contain some fixed graph~$H$ as an induced subgraph. By combining known and new results, we determine the computational complexity of both problems on $H$-free graphs for every graph $H$ except when $H=sP_1+P_4$ for some $sgeq 1$. As part of our approach, we introduce the Subset Vertex Cover problem and prove that it is polynomial-time solvable for $(sP_1+P_4)$-free graphs for every $sgeq 1$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
