Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Tolerant bipartiteness testing in dense graphs

Tools
- Tools
+ Tools

Ghosh, Arijit, Mishra, Gopinath, Raychaudhury, Rahul and Sen, Sayantan (2022) Tolerant bipartiteness testing in dense graphs. In: The 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP), Paris, France, 4-8 Jul 2022. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 229 69:1-69:19. ISBN 9783959772358. ISSN 1868-8969. doi:10.4230/LIPIcs.ICALP.2022

[img]
Preview
PDF
WRAP-tolerant-bipartiteness-testing-dense-graphs-Mishra-2022.pdf - Published Version - Requires a PDF viewer.
Available under License Creative Commons Attribution 4.0.

Download (842Kb) | Preview
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2022

Request Changes to record.

Abstract

Bipartite testing has been a central problem in the area of property testing since its inception in the seminal work of Goldreich, Goldwasser, and Ron.
Though the non-tolerant version of bipartite testing has been extensively studied in the literature, the tolerant variant is not well understood. In this paper, we consider the following version of the tolerant bipartite testing problem:
Given two parameters $\varepsilon, \delta \in (0,1)$, with $\delta > \varepsilon$, and access to the adjacency matrix of a graph $G$, we have to decide whether $G$ can be made bipartite by editing at most $\varepsilon n^2$ entries of the adjacency matrix of $G$, or we have to edit at least $\delta n^2$ entries of the adjacency matrix to make $G$ bipartite. In this paper, we prove that for $\delta=(2+\Omega(1))\varepsilon$, tolerant bipartite testing can be decided by performing $\widetilde{\mathcal{O}}\left({1}/{\varepsilon ^3}\right)$ many adjacency queries and in $2^{\widetilde{\mathcal{O}}(1/\varepsilon)}$ time complexity. This improves upon the state-of-the-art query and time complexities of this problem of $\widetilde{\mathcal{O}}\left({1}/{\varepsilon ^6}\right)$ and $2^{\widetilde{\mathcal{O}}(1/\varepsilon^2)}$, respectively, due to
Alon, Fernandez de la Vega, Kannan and Karpinski,
where $\widetilde{\mathcal{O}}(\cdot)$ hides a factor polynomial in $\log \left({1}/{\varepsilon}\right)$.

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science)
Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Faculty of Science, Engineering and Medicine > Science > Mathematics
Library of Congress Subject Headings (LCSH): Bipartite graphs, Machine theory, Computational complexity, Linear systems
Journal or Publication Title: Leibniz International Proceedings in Informatics (LIPIcs)
Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
ISBN: 9783959772358
ISSN: 1868-8969
Official Date: 2022
Dates:
DateEvent
2022Published
11 April 2022Accepted
Volume: 229
Page Range: 69:1-69:19
Article Number: 69
DOI: 10.4230/LIPIcs.ICALP.2022
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Open Access
RIOXX Funder/Project Grant:
Project/Grant IDRIOXX Funder NameFunder ID
UNSPECIFIEDCentre for Discrete Mathematics and its Applications, University of WarwickUNSPECIFIED
EP/V01305X/1[EPSRC] Engineering and Physical Sciences Research Councilhttp://dx.doi.org/10.13039/501100000266
Conference Paper Type: Paper
Title of Event: The 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP)
Type of Event: Conference
Location of Event: Paris, France
Date(s) of Event: 4-8 Jul 2022
Open Access Version:
  • ArXiv
  • Publisher

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us