Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIsomorphism of graph classes related to the circular-ones property
871
0
0.0
(
0
)
Added by
Francisco Soulignac
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We give a linear-time algorithm that checks for isomorphism between two 0-1 matrices that obey the circular-ones property. This algorithm leads to linear-time isomorphism algorithms for related graph classes, including Helly circular-arc graphs, Gamma-circular-arc graphs, proper circular-arc graphs and convex-round graphs.
rate research
Read More
153 -
Pavel Dvov{r}ak
, Duv{s}an Knop (Department ofn Applied Mathematics Charles University Prague
2016
We show that it is possible to use Bondy-Chvatal closure to design an FPT algorithm that decides whether or not it is possible to cover vertices of an input graph by at most k vertex disjoint paths in the complement of the input graph. More precisely, we show that if a graph has tree-width at most w and its complement is closed under Bondy-Chvatal closure, then it is possible to bound neighborhood diversity of the complement by a function of w only. A simpler proof where tree-depth is used instead of tree-width is also presented.
In a (parameterized) graph edge modification problem, we are given a graph $G$, an integer $k$ and a (usually well-structured) class of graphs $mathcal{G}$, and ask whether it is possible to transform $G$ into a graph $G in mathcal{G}$ by adding and/or removing at most $k$ edges. Parameterized graph edge modification problems received considerable attention in the last decades. In this paper, we focus on finding small kernels for edge modification problems. One of the most studied problems is the Cluster Editing problem, in which the goal is to partition the vertex set into a disjoint union of cliques. Even if this problem admits a $2k$ kernel [Cao, 2012], this kernel does not reduce the size of most instances. Therefore, we explore the question of whether linear kernels are a theoretical limit in edge modification problems, in particular when the target graphs are very structured (such as a partition into cliques for instance). We prove, as far as we know, the first sublinear kernel for an edge modification problem. Namely, we show that Clique + Independent Set Deletion, which is a restriction of Cluster Deletion, admits a kernel of size $O(k/log k)$. We also obtain small kernels for several other edge modification problems. We prove that Split Addition (and the equivalent Split Deletion) admits a linear kernel, improving the existing quadratic kernel of Ghosh et al. [Ghosh et al., 2015]. We complement this result by proving that Trivially Perfect Addition admits a quadratic kernel (improving the cubic kernel of Guo [Guo, 2007]), and finally prove that its triangle-free version (Starforest Deletion) admits a linear kernel, which is optimal under ETH.
We give a family of counter examples showing that the two sequences of polytopes $Phi_{n,n}$ and $Psi_{n,n}$ are different. These polytopes were defined recently by S. Friedland in an attempt at a polynomial time algorithm for graph isomorphism.
The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
