Graphon convergence of random cographs Stufler, Benedikt
Random structures & algorithms,
October 2021, 2021-10-00, 20211001, Volume:
59, Issue:
3
Journal Article
Peer reviewed
Open access
We study the behavior of random labeled and unlabeled cographs with n vertices as n tends to infinity. We show that both models admit a novel random graphon W1/2 as distributional limit. Our main ...tool is an enhanced skeleton decomposition of the random Pólya An tree with n leaves and no internal vertices having only one child. As a byproduct, we obtain limits describing the asymptotic shape of this model of random trees.
Full text
Available for:
FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
We consider the problems of finding optimal identifying codes, (open) locating–dominating sets and resolving sets of an interval or a permutation graph. In these problems, one asks to find a subset ...of vertices, normally called a solution set, using which all vertices of the graph are distinguished. The identification can be done by considering the neighborhood within the solution set, or by employing the distances to the solution vertices. Normally the goal is to minimize the size of the solution set then. Here we study the case of interval graphs, unit interval graphs, (bipartite) permutation graphs and cographs. For these classes of graphs we give tight lower bounds for the size of such solution sets depending on the order of the input graph. While such lower bounds for the general class of graphs are in logarithmic order, the improved bounds in these special classes are of the order of either quadratic root or linear in terms of number of vertices. Moreover, the results for cographs lead to linear-time algorithms to solve the considered problems on inputs that are cographs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let G and H be equivalent cographs with reductions
and
and suppose the vertices of
and
are labelled by the twin numbers
of the k twin classes they represent. In this paper, we prove that G and H have ...at least
Laplacian eigenvalues in common, where
is the indices of the twin classes whose types are identical in G and H. This confirms the conjecture proposed by Abrishami A combinatorial analysis of the eigenvalues of the Laplacian matrices of cographs Master's thesis. Johns Hopkins University; 2019. Available from:
http://jscholarship.library.jhu.edu/bitstream/handle/1774.2/61684/ABRISHAMI-THESIS-2019.pdf
. We also show that no two nonisomorphic equivalent cographs are cospectral with relation to the Laplacian matrix.
Full text
Available for:
BFBNIB, GIS, IJS, KISLJ, NUK, PNG, UL, UM, UPUK
The modular decomposition of a graph G is a natural construction to capture key features of G in terms of a labeled tree (T, t) whose vertices are labeled as series(1), parallel(0) or prime. However, ...full information of G is provided by its modular decomposition tree (T, t) only, if G does not contain prime modules. In this case, (T, t) explains G, i.e., {x, y} is an element of E(G) if and only if the lowest common ancestor lca(T)(x, y) of x and y has label 1. This information, however, gets lost whenever (T, t) contains vertices with label prime. In this contribution, we aim at replacing prime vertices in (T, t) by simple 0/1-labeled cycles, which leads to the concept of rooted labeled level-1 networks (N, t).
We characterize graphs that can be explained by such level-1 networks (N, t), which generalizes the concept of graphs that can be explained by labeled trees, that is, cographs. We provide three novel graph classes: polar-cats are a proper subclass of pseudo-cographs which forms a proper subclass of prime polar-cats. In particular, every cograph is a pseudo-cograph and prime polar-cats are precisely those graphs that can be explained by a labeled level-1 network. The class of prime polar-cats is defined in terms of the modular decomposition of graphs and the property that all prime modules induce polar-cats. We provide a plethora of structural results and characterizations for graphs of these new classes.
In particular, Polar-cats are precisely those graphs that can be explained by an elementary level-1 network (N, t), i.e., (N, t) contains exactly one cycle C that is rooted at the root rho(N) of N and where rho(N) has exactly two children while every vertex distinct from rho(N) has a unique child that is not located in C. Pseudo-cographs are less restrictive and those graphs that can be explained by particular level-1 networks (N, t) that contain at most one cycle. These findings, eventually, help us to characterize the class of all graphs that can be explained by labeled level-1 networks, namely prime polar-cats. Moreover, we show under which conditions there is a unique least-resolved labeled level-1 network that explains a given graph. In addition, we provide linear-time algorithms to recognize all these types of graphs and to construct level-1 networks to explain them.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A cograph is a graph without induced paths of length 4. A graph G is (2, 1) if its vertex set can be partitioned into at most 2 independent sets and 1 clique. Cographs-(k,ℓ) have already a ...characterization by forbidden subgraphs, but no structural characterization is known, except for cographs-(1, 1), i.e threshold graphs. In this paper, we present a structural characterization and a decomposition theorem for cographs-(2, 1) and, consequently, for cographs-(1, 2), leading to linear time recognition algorithms for both classes.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK
This paper is interested in independent sets (or equivalently, cliques) in uniform random cographs. We also study their permutation analogs, namely, increasing subsequences in uniform random ...separable permutations. First, we prove that, with high probability as $n$ gets large, the largest independent set in a uniform random cograph with $n$ vertices has size $o(n)$. This answers a question of Kang, McDiarmid, Reed and Scott. Using the connection between graphs and permutations via inversion graphs, we also give a similar result for the longest increasing subsequence in separable permutations. These results are proved using the self-similarity of the Brownian limits of random cographs and random separable permutations, and actually apply more generally to all families of graphs and permutations with the same limit. Second, and unexpectedly given the above results, we show that for $\beta >0$ sufficiently small, the expected number of independent sets of size $\beta n$ in a uniform random cograph with $n$ vertices grows exponentially fast with $n$. We also prove a permutation analog of this result. This time the proofs rely on singularity analysis of the associated bivariate generating functions.
Cyclability in graph classes Crespelle, Christophe; Golovach, Petr A.
Discrete Applied Mathematics,
05/2022, Volume:
313
Journal Article
Peer reviewed
Open access
A subset T⊆V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every set of vertices of size ...at most k is cyclable. The Terminal Cyclability problem asks, given a graph G and a set T of vertices, whether T is cyclable, and the k-Cyclability problem asks, given a graph G and a positive integer k, whether G is k-cyclable. These problems are generalizations of the classical Hamiltonian Cycle problem. We initiate the study of these problems for graph classes that admit polynomial algorithms for Hamiltonian Cycle. We show that Terminal Cyclability can be solved in linear time for interval graphs, bipartite permutation graphs and cographs. Moreover, we construct certifying algorithms that either produce a solution, that is a cycle, or output a graph separator that certifies a no-answer. We use these results to show that k-Cyclability can be solved in polynomial time when restricted to the aforementioned graph classes.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The MaxSTC problem is an assignment of the edges with two types of labels, namely, strong and weak, that maximizes the number of strong edges such that any two vertices that have a common neighbor ...with a strong edge are adjacent. The Cluster Deletion problem seeks for the minimum number of edge removals of a given graph such that the remaining graph is a disjoint union of cliques. Both problems are known to be NP-hard and an optimal solution for the Cluster Deletion problem provides a feasible solution for the MaxSTC problem, however not necessarily an optimal one. In this work we conduct the first systematic study that reveals graph families for which the optimal solutions for MaxSTC and Cluster Deletion coincide. We first show that MaxSTC coincides with Cluster Deletion on cographs and, thus, MaxSTC is solvable in polynomial time on cographs. As a side result, we give an interesting computational characterization of the maximum independent set on the cartesian product of two cographs. Furthermore, we address the influence of the low degree bounds to the complexity of the MaxSTC problem. We show that this problem is polynomial-time solvable on graphs of maximum degree three, whereas MaxSTC becomes NP-complete on graphs of maximum degree four. The proof of the latter result implies that there is no subexponential-time algorithm for MaxSTC unless the Exponential-Time Hypothesis fails.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Reciprocal best match graphs (RBMGs) are vertex colored graphs whose vertices represent genes and the colors the species where the genes reside. Edges identify pairs of genes that are most closely ...related with respect to an underlying evolutionary tree. In practical applications this tree is unknown and the edges of the RBMGs are inferred by quantifying sequence similarity. Due to noise in the data, these empirically determined graphs in general violate the condition of being a “biologically feasible” RBMG. Therefore, it is of practical interest in computational biology to correct the initial estimate. Here we consider deletion (remove at most k edges) and editing (add or delete at most k edges) problems. We show that the decision version of the deletion and editing problem to obtain RBMGs from vertex colored graphs is NP-hard. Using known results for the so-called bicluster editing, we show that the RBMG editing problem for 2-colored graphs is fixed-parameter tractable.
A restricted class of RBMGs appears in the context of orthology detection. These are cographs with a specific type of vertex coloring known as hierarchical coloring. We show that the decision problem of modifying a vertex-colored graph (either by edge-deletion or editing) into an RBMG with cograph structure or, equivalently, to an hierarchically colored cograph is NP-complete.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We consider uniform random cographs (either labeled or unlabeled) of large size. Our first main result is the convergence toward a Brownian limiting object in the space of graphons. We then show that ...the degree of a uniform random vertex in a uniform cograph is of order n, and converges after normalization to the Lebesgue measure on 0,1. We finally analyze the vertex connectivity (i.e., the minimal number of vertices whose removal disconnects the graph) of random connected cographs, and show that this statistics converges in distribution without renormalization. Unlike for the graphon limit and for the degree of a random vertex, the limiting distribution of the vertex connectivity is different in the labeled and unlabeled settings. Our proofs rely on the classical encoding of cographs via cotrees. We then use mainly combinatorial arguments, including the symbolic method and singularity analysis.
Full text
Available for:
FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
PDF
