Reachability and Matching in Single Crossing Minor Free Graphs

Samir Datta; Chetan Gupta; Rahul Jain; Anish Mukherjee; Vimalraj Sharma; Raghunath Tewari

Reachability and Matching in Single Crossing Minor Free Graphs

Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimalraj Sharma, Raghunath Tewari

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

26 Downloads (Pure)

Abstract

We show that for each single crossing graph H, a polynomially bounded weight function for all H-minor free graphs G can be constructed in logspace such that it gives nonzero weights to all the cycles in G. This class of graphs subsumes almost all classes of graphs for which such a weight function is known to be constructed in logspace. As a consequence, we obtain that for the class of H-minor free graphs where H is a single crossing graph, reachability can be solved in UL, and bipartite maximum matching can be solved in SPL, which are small subclasses of the parallel complexity class NC. In the restrictive case of bipartite graphs, our maximum matching result improves upon the recent result of Eppstein and Vazirani (SIAM J. Computing 2021), where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.

Original language	English
Title of host publication	41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Subtitle of host publication	FSTTCS 2021, December 15–17, 2021, Virtual Conference
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages	1-16
Number of pages	16
ISBN (Electronic)	978-3-95977-215-0
Publication status	Published - 29 Nov 2021
MoE publication type	A4 Conference publication
Event	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science - Virtual, Online Duration: 15 Dec 2021 → 17 Dec 2021 Conference number: 41

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl –Leibniz Center for Informatics
Volume	213
ISSN (Electronic)	1868-8969

Conference

Conference	IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Abbreviated title	FSTTCS
City	Virtual, Online
Period	15/12/2021 → 17/12/2021

Access to Document

Reachability and Matching in Single Crossing Minor Free GraphsFinal published version, 753 KBLicence: CC BY

https://drops.dagstuhl.de/opus/volltexte/2021/15527/Licence: CC BY

-: Parallel and distributed computing for Bayesian graphical models
Suomela, J. (Principal investigator)
04/09/2019 → 30/04/2023
Project: Academy of Finland: Other research funding

Cite this

Datta, S., Gupta, C., Jain, R., Mukherjee, A., Sharma, V., & Tewari, R. (2021). Reachability and Matching in Single Crossing Minor Free Graphs. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2021, December 15–17, 2021, Virtual Conference (pp. 1-16). Article 16 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 213). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://drops.dagstuhl.de/opus/volltexte/2021/15527/

Datta, Samir ; Gupta, Chetan ; Jain, Rahul et al. / Reachability and Matching in Single Crossing Minor Free Graphs. 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2021, December 15–17, 2021, Virtual Conference. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. pp. 1-16 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{7c41a4ae81d644caaef3ec7a2e36968a,

title = "Reachability and Matching in Single Crossing Minor Free Graphs",

abstract = "We show that for each single crossing graph H, a polynomially bounded weight function for all H-minor free graphs G can be constructed in logspace such that it gives nonzero weights to all the cycles in G. This class of graphs subsumes almost all classes of graphs for which such a weight function is known to be constructed in logspace. As a consequence, we obtain that for the class of H-minor free graphs where H is a single crossing graph, reachability can be solved in UL, and bipartite maximum matching can be solved in SPL, which are small subclasses of the parallel complexity class NC. In the restrictive case of bipartite graphs, our maximum matching result improves upon the recent result of Eppstein and Vazirani (SIAM J. Computing 2021), where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.",

author = "Samir Datta and Chetan Gupta and Rahul Jain and Anish Mukherjee and Vimalraj Sharma and Raghunath Tewari",

year = "2021",

month = nov,

day = "29",

language = "English",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "1--16",

booktitle = "41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science",

address = "Germany",

note = "IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS ; Conference date: 15-12-2021 Through 17-12-2021",

}

Datta, S, Gupta, C, Jain, R, Mukherjee, A, Sharma, V & Tewari, R 2021, Reachability and Matching in Single Crossing Minor Free Graphs. in 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2021, December 15–17, 2021, Virtual Conference., 16, Leibniz International Proceedings in Informatics (LIPIcs), vol. 213, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-16, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Virtual, Online, 15/12/2021. <https://drops.dagstuhl.de/opus/volltexte/2021/15527/>

Reachability and Matching in Single Crossing Minor Free Graphs. / Datta, Samir; Gupta, Chetan; Jain, Rahul et al.
41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2021, December 15–17, 2021, Virtual Conference. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. p. 1-16 16 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 213).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Reachability and Matching in Single Crossing Minor Free Graphs

AU - Datta, Samir

AU - Gupta, Chetan

AU - Jain, Rahul

AU - Mukherjee, Anish

AU - Sharma, Vimalraj

AU - Tewari, Raghunath

N1 - Conference code: 41

PY - 2021/11/29

Y1 - 2021/11/29

N2 - We show that for each single crossing graph H, a polynomially bounded weight function for all H-minor free graphs G can be constructed in logspace such that it gives nonzero weights to all the cycles in G. This class of graphs subsumes almost all classes of graphs for which such a weight function is known to be constructed in logspace. As a consequence, we obtain that for the class of H-minor free graphs where H is a single crossing graph, reachability can be solved in UL, and bipartite maximum matching can be solved in SPL, which are small subclasses of the parallel complexity class NC. In the restrictive case of bipartite graphs, our maximum matching result improves upon the recent result of Eppstein and Vazirani (SIAM J. Computing 2021), where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.

AB - We show that for each single crossing graph H, a polynomially bounded weight function for all H-minor free graphs G can be constructed in logspace such that it gives nonzero weights to all the cycles in G. This class of graphs subsumes almost all classes of graphs for which such a weight function is known to be constructed in logspace. As a consequence, we obtain that for the class of H-minor free graphs where H is a single crossing graph, reachability can be solved in UL, and bipartite maximum matching can be solved in SPL, which are small subclasses of the parallel complexity class NC. In the restrictive case of bipartite graphs, our maximum matching result improves upon the recent result of Eppstein and Vazirani (SIAM J. Computing 2021), where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.

M3 - Conference article in proceedings

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 1

EP - 16

BT - 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Y2 - 15 December 2021 through 17 December 2021

ER -

Datta S, Gupta C, Jain R, Mukherjee A, Sharma V, Tewari R. Reachability and Matching in Single Crossing Minor Free Graphs. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science: FSTTCS 2021, December 15–17, 2021, Virtual Conference. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2021. p. 1-16. 16. (Leibniz International Proceedings in Informatics (LIPIcs)).

Reachability and Matching in Single Crossing Minor Free Graphs

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

-: Parallel and distributed computing for Bayesian graphical models

Cite this