Paper Info
Title
Reachability and Matching in Single Crossing Minor Free Graphs.
Abstract
We construct in Logspace non-zero circulations for H-minor free graphs where H is any fixed graph with a single crossing. This extends the list of planar, bounded genus and K_{3,3}-free, K_5-free graphs for which non-zero circulations are already known. This implies static bounds of UL and SPL, respectively, for the problems of reachability and maximum matching in this class of graphs. Further, we prove the following dynamic complexity bounds for classes of graphs where polynomially bounded, skew-symmetric non-zero circulations are in Logspace: (1) A DynFO[Parity] bound (under polylogarithmic changes per step) for constructing perfect matching and maximum matching. (2) A DynFO[Parity] bound (under polylogarithmic changes per step) for distance. (3) A DynFO bound (under slightly sublogarithmic changes per step) for maximum cardinality matching size. The main technical contributions include the construction of polynomially bounded non-zero circulation weights in single crossing minor free graphs based on existing results [AGGT16,DKMTVZ20]; using the approach from [FGT16] to construct dynamic isolating weights and generalizing the rank algorithm from [DKMSZ15,DKMSZ18] to handle slightly sublogarithmic many (O(log n/log log n)) changes.
Year
DOI
Venue
2021
10.4230/LIPIcs.FSTTCS.2021.16
FSTTCS
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
0
6
Name
Order
Citations
PageRank
Samir Datta101.69
Chetan Gupta231432.42
Rahul Jain3147.70
Anish Mukherjee4133.98
Vimal Raj Sharma501.01
Raghunath Tewari6839.82