NDLI: Testing Graph Isomorphism

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Fischer, Eldar Matsliah, Arie
Copyright Year	2008
Abstract	Two graphs G and H on n vertices are $\epsilon$-far from being isomorphic if at least $\epsilon\binom{n}{2}$ edges must be added or removed from $E(G)$ in order to make G and H isomorphic. In this paper we deal with the question of how many queries are required to distinguish between the case that two graphs are isomorphic and the case that they are $\epsilon$-far from being isomorphic. A query is defined as probing the adjacency matrix of any one of the two graphs, i.e., asking if a pair of vertices forms an edge of the graph or not. We investigate both one-sided and two-sided error testers under two possible settings: The first setting is where both graphs need to be queried, and the second setting is where one of the graphs is fully known to the algorithm in advance. We prove that the query complexity of the best one-sided error testing algorithm is $\widetilde{\Theta}(n^{3/2})$ if both graphs need to be queried, and that it is $\widetilde{\Theta}(n)$ if one of the graphs is known in advance (where the $\widetilde{\Theta}$ notation hides polylogarithmic factors in the upper bounds). For two-sided error testers, we prove that the query complexity of the best tester is $\widetilde{\Theta}(\sqrt{n})$ when one of the graphs is known in advance, and we show that the query complexity lies between $\Omega(n)$ and $\widetilde{O}(n^{5/4})$ if both G and H need to be queried. All of our algorithms are additionally nonadaptive, while all of our lower bounds apply for adaptive testers as well as nonadaptive ones.
Starting Page	207
Ending Page	225
Page Count	19
File Format	PDF
ISSN	00975397
DOI	10.1137/070680795
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	1
Volume Number	38
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2008-03-28
Access Restriction	Subscribed
Subject Keyword	approximation Analysis of algorithms and problem complexity graph isomorphism Randomized algorithms property testing
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance

Abstract Combinatorial Programs and Efficient Property Testers

On Proximity-Oblivious Testing

Testing of Clustering

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs

Testing of Clustering

Algorithmic Aspects of Property Testing in the Dense Graphs Model

Sublinear Time Algorithms

Testing Basic Boolean Formulae

Testing Graph Isomorphism

Similar Documents

The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance

Abstract Combinatorial Programs and Efficient Property Testers

On Proximity-Oblivious Testing

Testing of Clustering

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs

Testing of Clustering

Algorithmic Aspects of Property Testing in the Dense Graphs Model

Sublinear Time Algorithms

Testing Basic Boolean Formulae

Testing Graph Isomorphism