Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGraph Isomorphism Restricted by Lists
270
0
0.0
(
0
)
Added by
Peter Zeman
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs $G$ and $H$, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (ListIso) is NP-complete: for each $u in V(G)$, we are given a list ${mathfrak L}(u) subseteq V(H)$ of possible images of $u$. After 35 years, we revive the study of this problem and consider which results for GraphIso translate to ListIso. We prove the following: 1) When GraphIso is GI-complete for a class of graphs, it translates into NP-completeness of ListIso. 2) Combinatorial algorithms for GraphIso translate into algorithms for ListIso: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, bounded genus graphs, and bounded treewidth graphs. 3) Algorithms based on group theory do not translate: ListIso remains NP-complete for cubic colored graphs with sizes of color classes bounded by 8. Also, ListIso allows to classify results for the graph isomorphism problem. Some algorithms are robust and translate to ListIso. A fundamental problem is to construct a combinatorial polynomial-time algorithm for cubic graph isomorphism, avoiding group theory. By the 3rd result, ListIso is NP-hard for them, so no robust algorithm for cubic graph isomorphism exists, unless P = NP.
rate research
Read More
A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic et al. (Uniquely restricted matchings, M. C. Golumbic, T. Hirst and M. Lewenstein, Algorithmica, 31:139--154, 2001). Our algorithm actually solves the more general problem of computing a maximum cardinality strong independent set in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.
A graph where each vertex $v$ has a list $L(v)$ of available colors is $L$-colorable if there is a proper coloring such that the color of $v$ is in $L(v)$ for each $v$. A graph is $k$-choosable if every assignment $L$ of at least $k$ colors to each vertex guarantees an $L$-coloring. Given a list assignment $L$, an $L$-request for a vertex $v$ is a color $cin L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvov{r}ak, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy enough, as opposed to all, of the requested set of precolors. A graph $G$ is $varepsilon$-flexible for list size $k$ if for any $k$-list assignment $L$, and any set $S$ of $L$-requests, there is an $L$-coloring of $G$ satisfying an $varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $varepsilon$-flexible for list size $5$, yet it is proved only for list size $6$ and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masav{r}ik and show that planar graphs without $K_4^-$ are $varepsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $varepsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $varepsilon$-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are $varepsilon$-flexible for list size $5$.
Using three supercomputers, we broke a record set in 2011, in the enumeration of non-isomorphic regular graphs by expanding the sequence of A006820 in Online Encyclopedia of Integer Sequences (OEIS), to achieve the number for 4-regular graphs of order 23 as 429,668,180,677,439, while discovering serval optimal regular graphs with minimum average shortest path lengths (ASPL) that can be used as interconnection networks for parallel computers. The number of 4-regular graphs and the optimal graphs, extremely time-consuming to calculate, result from a method we adapt from GENREG, a classical regular graph generator, to fit for supercomputers strengths of using thousands of processor cores.
Given two graphs $G_1$ and $G_2$ on $n$ vertices each, we define a graph $G$ on vertex set $V_1times V_2$ and the edge set as the union of edges of $G_1times bar{G_2}$, $bar{G_1}times G_2$, ${(v,u),(v,u))(|u,uin V_2}$ for each $vin V_1$, and ${((u,v),(u,v))|u,uin V_1}$ for each $vin V_2$. We consider the completely-positive Lovasz $vartheta$ function, i.e., $cpvartheta$ function for $G$. We show that the function evaluates to $n$ whenever $G_1$ and $G_2$ are isomorphic and to less than $n-1/(4n^4)$ when non-isomorphic. Hence this function provides a test for graph isomorphism. We also provide some geometric insight into the feasible region of the completely positive program.
We are given an integer $d$, a graph $G=(V,E)$, and a uniformly random embedding $f : V rightarrow {0,1}^d$ of the vertices. We are interested in the probability that $G$ can be realized by a scaled Euclidean norm on $mathbb{R}^d$, in the sense that there exists a non-negative scaling $w in mathbb{R}^d$ and a real threshold $theta > 0$ so that [ (u,v) in E qquad text{if and only if} qquad Vert f(u) - f(v) Vert_w^2 < theta,, ] where $| x |_w^2 = sum_i w_i x_i^2$. These constraints are similar to those found in the Euclidean minimum spanning tree (EMST) realization problem. A crucial difference is that the realization map is (partially) determined by the random variable $f$. In this paper, we consider embeddings $f : V rightarrow { x, y}^d$ for arbitrary $x, y in mathbb{R}$. We prove that arbitrary trees can be realized with high probability when $d = Omega(n log n)$. We prove an analogous result for graphs parametrized by the arboricity: specifically, we show that an arbitrary graph $G$ with arboricity $a$ can be realized with high probability when $d = Omega(n a^2 log n)$. Additionally, if $r$ is the minimum effective resistance of the edges, $G$ can be realized with high probability when $d=Omegaleft((n/r^2)log nright)$. Next, we show that it is necessary to have $d geq binom{n}{2}/6$ to realize random graphs, or $d geq n/2$ to realize random spanning trees of the complete graph. This is true even if we permit an arbitrary embedding $f : V rightarrow { x, y}^d$ for any $x, y in mathbb{R}$ or negative weights. Along the way, we prove a probabilistic analog of Radons theorem for convex sets in ${0,1}^d$. Our tree-realization result can complement existing results on statistical inference for gene expression data which involves realizing a tree, such as [GJP15].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
