Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTesting isomorphism of circulant objects in polynomial time
82
0
0.0
(
0
)
Added by
Ilia Ponomarenko
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let ${frak K}$ be a class of combinatorial objects invariant with respect to a given regular cyclic group. It is proved that the isomorphism of any two objects $X,Yin{frak K}$ can be tested in polynomial time in sizes of $X$ and $Y$.
rate research
Read More
A Cayley graph over a group G is said to be central if its connection set is a normal subset of G. It is proved that for any two central Cayley graphs over explicitly given almost simple groups of order n, the set of all isomorphisms from the first graph onto the second can be found in time poly(n).
We construct a polynomial-time algorithm that given a graph $X$ with $4p$ vertices ($p$ is prime), finds (if any) a Cayley representation of $X$ over the group $C_2times C_2times C_p$. This result, together with the known similar result for circulant graphs, shows that recognising and testing isomorphism of Cayley graphs over an abelian group of order $4p$ can be done in polynomial time.
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is proved that the isomorphism of circular-arc graphs can be tested by the Weisfeiler-Leman algorithm after individualization of two vertices.
Let $mathcal{F}$ and $mathcal{G}$ be two $t$-uniform families of subsets over $[k] = {1,2,...,k}$, where $|mathcal{F}| = |mathcal{G}|$, and let $C$ be the adjacency matrix of the bipartite graph whose vertices are the subsets in $mathcal{F}$ and $mathcal{G}$, and there is an edge between $Ain mathcal{F}$ and $B in mathcal{G}$ if and only if $A cap B eq emptyset$. The pair $(mathcal{F},mathcal{G})$ is $q$-almost cross intersecting if every row and column of $C$ has exactly $q$ zeros. We consider $q$-almost cross intersecting pairs that have a circulant intersection matrix $C_{p,q}$, determined by a column vector with $p > 0$ ones followed by $q > 0$ zeros. This family of matrices includes the identity matrix in one extreme, and the adjacency matrix of the bipartite crown graph in the other extreme. We give constructions of pairs $(mathcal{F},mathcal{G})$ whose intersection matrix is $C_{p,q}$, for a wide range of values of the parameters $p$ and $q$, and in some cases also prove matching upper bounds. Specifically, we prove results for the following values of the parameters: (1) $1 leq p leq 2t-1$ and $1 leq q leq k-2t+1$. (2) $2t leq p leq t^2$ and any $q> 0$, where $k geq p+q$. (3) $p$ that is exponential in $t$, for large enough $k$. Using the first result we show that if $k geq 4t-3$ then $C_{2t-1,k-2t+1}$ is a maximal isolation submatrix of size $ktimes k$ in the $0,1$-matrix $A_{k,t}$, whose rows and columns are labeled by all subsets of size $t$ of $[k]$, and there is a one in the entry on row $x$ and column $y$ if and only if subsets $x,y$ intersect.
It is known that testing isomorphism of chordal graphs is as hard as the general graph isomorphism problem. Every chordal graph can be represented as the intersection graph of some subtrees of a tree. The leafage of a chordal graph, is defined to be the minimum number of leaves in the representing tree. We construct a fixed-parameter tractable algorithm testing isomorphism of chordal graphs with bounded leafage. The key point is a fixed-parameter tractable algorithm finding the automorphism group of a colored order-3 hypergraph with bounded sizes of color classes of vertices.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
