Search Results

Documents authored by Datta, Samir

Document
DOI: 10.4230/LIPIcs.MFCS.2024.43
The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs

Authors: Archit Chauhan, Samir Datta, Chetan Gupta, and Vimal Raj Sharma

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Finding a simple path of even length between two designated vertices in a directed graph is a fundamental NP-complete problem [Andrea S. LaPaugh and Christos H. Papadimitriou, 1984] known as the EP problem. Nedev [Zhivko Prodanov Nedev, 1999] proved in 1999, that for directed planar graphs, the problem can be solved in polynomial time. More than two decades since then, we make the first progress in extending the tractable classes of graphs for this problem. We give a polynomial time algorithm to solve the EP problem for classes of H-minor-free directed graphs, where H is a single-crossing graph. We make two new technical contributions along the way, that might be of independent interest. The first, and perhaps our main, contribution is the construction of small, planar, parity-mimicking networks. These are graphs that mimic parities of all possible paths between a designated set of terminals of the original graph. Finding vertex disjoint paths between given source-destination pairs of vertices is another fundamental problem, known to be NP-complete in directed graphs [Steven Fortune et al., 1980], though known to be tractable in planar directed graphs [Alexander Schrijver, 1994]. We encounter a natural variant of this problem, that of finding disjoint paths between given pairs of vertices, but with constraints on parity of the total length of paths. The other significant contribution of our paper is to give a polynomial time algorithm for the 3-disjoint paths with total parity problem, in directed planar graphs with some restrictions (and also in directed graphs of bounded treewidth).
Cite as

Archit Chauhan, Samir Datta, Chetan Gupta, and Vimal Raj Sharma. The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chauhan_et_al:LIPIcs.MFCS.2024.43,
  author =	{Chauhan, Archit and Datta, Samir and Gupta, Chetan and Sharma, Vimal Raj},
  title =	{{The Even-Path Problem in Directed Single-Crossing-Minor-Free Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.43},
  URN =		{urn:nbn:de:0030-drops-205992},
  doi =		{10.4230/LIPIcs.MFCS.2024.43},
  annote =	{Keywords: Graph Algorithms, EvenPath, Polynomial-time Algorithms, Reachability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.46
Query Maintenance Under Batch Changes with Small-Depth Circuits

Authors: Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Which dynamic queries can be maintained efficiently? For constant-size changes, it is known that constant-depth circuits or, equivalently, first-order updates suffice for maintaining many important queries, among them reachability, tree isomorphism, and the word problem for context-free languages. In other words, these queries are in the dynamic complexity class DynFO. We show that most of the existing results for constant-size changes can be recovered for batch changes of polylogarithmic size if one allows circuits of depth 𝒪(log log n) or, equivalently, first-order updates that are iterated 𝒪(log log n) times.
Cite as

Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Query Maintenance Under Batch Changes with Small-Depth Circuits. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.MFCS.2024.46,
  author =	{Datta, Samir and Khan, Asif and Mukherjee, Anish and Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Query Maintenance Under Batch Changes with Small-Depth Circuits}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.46},
  URN =		{urn:nbn:de:0030-drops-206027},
  doi =		{10.4230/LIPIcs.MFCS.2024.46},
  annote =	{Keywords: Dynamic complexity theory, parallel computation, dynamic algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.39
Dynamic Planar Embedding Is in DynFO

Authors: Samir Datta, Asif Khan, and Anish Mukherjee

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Planar Embedding is a drawing of a graph on the plane such that the edges do not intersect each other except at the vertices. We know that testing the planarity of a graph and computing its embedding (if it exists), can efficiently be computed, both sequentially [John E. Hopcroft and Robert Endre Tarjan, 1974] and in parallel [Vijaya Ramachandran and John H. Reif, 1994], when the entire graph is presented as input. In the dynamic setting, the input graph changes one edge at a time through insertion and deletions and planarity testing/embedding has to be updated after every change. By storing auxilliary information we can improve the complexity of dynamic planarity testing/embedding over the obvious recomputation from scratch. In the sequential dynamic setting, there has been a series of works [David Eppstein et al., 1996; Giuseppe F. Italiano et al., 1993; Jacob Holm et al., 2018; Jacob Holm and Eva Rotenberg, 2020], culminating in the breakthrough result of polylog(n) sequential time (amortized) planarity testing algorithm of Holm and Rotenberg [Jacob Holm and Eva Rotenberg, 2020]. In this paper we study planar embedding through the lens of DynFO, a parallel dynamic complexity class introduced by Patnaik et al [Sushant Patnaik and Neil Immerman, 1997] (also [Guozhu Dong et al., 1995]). We show that it is possible to dynamically maintain whether an edge can be inserted to a planar graph without causing non-planarity in DynFO. We extend this to show how to maintain an embedding of a planar graph under both edge insertions and deletions, while rejecting edge insertions that violate planarity. Our main idea is to maintain embeddings of only the triconnected components and a special two-colouring of separating pairs that enables us to side-step cascading flips when embedding of a biconnected planar graph changes, a major issue for sequential dynamic algorithms [Jacob Holm and Eva Rotenberg, 2020; Jacob Holm and Eva Rotenberg, 2020].
Cite as

Samir Datta, Asif Khan, and Anish Mukherjee. Dynamic Planar Embedding Is in DynFO. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.MFCS.2023.39,
  author =	{Datta, Samir and Khan, Asif and Mukherjee, Anish},
  title =	{{Dynamic Planar Embedding Is in DynFO}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.39},
  URN =		{urn:nbn:de:0030-drops-185736},
  doi =		{10.4230/LIPIcs.MFCS.2023.39},
  annote =	{Keywords: Dynamic Complexity, Planar graphs, Planar embedding}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.118
Dynamic Meta-Theorems for Distance and Matching

Authors: Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Reachability, distance, and matching are some of the most fundamental graph problems that have been of particular interest in dynamic complexity theory in recent years [Samir Datta et al., 2018; Samir Datta et al., 2018; Samir Datta et al., 2020]. Reachability can be maintained with first-order update formulas, or equivalently in DynFO in general graphs with n nodes [Samir Datta et al., 2018], even under O(log(n)/log log(n)) changes per step [Samir Datta et al., 2018]. In the context of how large the number of changes can be handled, it has recently been shown [Samir Datta et al., 2020] that under a polylogarithmic number of changes, reachability is in DynFOpar in planar, bounded treewidth, and related graph classes - in fact in any graph where small non-zero circulation weights can be computed in NC. We continue this line of investigation and extend the meta-theorem for reachability to distance and bipartite maximum matching with the same bounds. These are amongst the most general classes of graphs known where we can maintain these problems deterministically without using a majority quantifier and even maintain witnesses. For the bipartite matching result, modifying the approach from [Stephen A. Fenner et al., 2016], we convert the static non-zero circulation weights to dynamic matching-isolating weights. While reachability is in DynFOar under O(log(n)/log log(n)) changes, no such bound is known for either distance or matching in any non-trivial class of graphs under non-constant changes. We show that, in the same classes of graphs as before, bipartite maximum matching is in DynFOar under O(log(n)/log log(n)) changes per step. En route to showing this we prove that the rank of a matrix can be maintained in DynFOar, also under O(log(n)/log log(n)) entry changes, improving upon the previous O(1) bound [Samir Datta et al., 2018]. This implies a similar extension for the non-uniform DynFO bound for maximum matching in general graphs and an alternate algorithm for maintaining reachability under O(log(n)/log log(n)) changes [Samir Datta et al., 2018].
Cite as

Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari. Dynamic Meta-Theorems for Distance and Matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 118:1-118:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ICALP.2022.118,
  author =	{Datta, Samir and Gupta, Chetan and Jain, Rahul and Mukherjee, Anish and Sharma, Vimal Raj and Tewari, Raghunath},
  title =	{{Dynamic Meta-Theorems for Distance and Matching}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{118:1--118:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.118},
  URN =		{urn:nbn:de:0030-drops-164598},
  doi =		{10.4230/LIPIcs.ICALP.2022.118},
  annote =	{Keywords: Dynamic Complexity, Distance, Matching, Derandomization, Isolation, Matrix Rank}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.16
Reachability and Matching in Single Crossing Minor Free Graphs

Authors: Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

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 [David Eppstein and Vijay V. Vazirani, 2021], where they show an NC bound for constructing perfect matching in general single crossing minor free graphs.
Cite as

Samir Datta, Chetan Gupta, Rahul Jain, Anish Mukherjee, Vimal Raj Sharma, and Raghunath Tewari. 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2021.16,
  author =	{Datta, Samir and Gupta, Chetan and Jain, Rahul and Mukherjee, Anish and Sharma, Vimal Raj and Tewari, Raghunath},
  title =	{{Reachability and Matching in Single Crossing Minor Free Graphs}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{16:1--16:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.16},
  URN =		{urn:nbn:de:0030-drops-155277},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.16},
  annote =	{Keywords: Reachability, Matching, Logspace, Single-crossing minor free graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.7
Depth-First Search in Directed Planar Graphs, Revisited

Authors: Eric Allender, Archit Chauhan, and Samir Datta

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL∩co-UL), which is contained in AC². Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^{10}n) (corresponding to the complexity class AC^{10} ⊆ NC^{11}). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds.
Cite as

Eric Allender, Archit Chauhan, and Samir Datta. Depth-First Search in Directed Planar Graphs, Revisited. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.MFCS.2021.7,
  author =	{Allender, Eric and Chauhan, Archit and Datta, Samir},
  title =	{{Depth-First Search in Directed Planar Graphs, Revisited}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.7},
  URN =		{urn:nbn:de:0030-drops-144478},
  doi =		{10.4230/LIPIcs.MFCS.2021.7},
  annote =	{Keywords: Depth-First Search, Planar Digraphs, Parallel Algorithms, Space-Bounded Complexity Classes}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.36
Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles

Authors: Samir Datta and Kishlaya Jaiswal

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We present a parallel algorithm for permanent mod 2^k of a matrix of univariate integer polynomials. It places the problem in ⨁L ⊆ NC². This extends the techniques of Valiant [Leslie G. Valiant, 1979], Braverman, Kulkarni and Roy [Mark Braverman et al., 2009] and Björklund and Husfeldt [Andreas Björklund and Thore Husfeldt, 2019] and yields a (randomized) parallel algorithm for shortest two disjoint paths improving upon the recent (randomized) polynomial time algorithm [Andreas Björklund and Thore Husfeldt, 2019]. We also recognize the disjoint paths problem as a special case of finding disjoint cycles, and present (randomized) parallel algorithms for finding a shortest cycle and shortest two disjoint cycles passing through any given fixed number of vertices or edges.
Cite as

Samir Datta and Kishlaya Jaiswal. Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.MFCS.2021.36,
  author =	{Datta, Samir and Jaiswal, Kishlaya},
  title =	{{Parallel Polynomial Permanent Mod Powers of 2 and Shortest Disjoint Cycles}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{36:1--36:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.36},
  URN =		{urn:nbn:de:0030-drops-144763},
  doi =		{10.4230/LIPIcs.MFCS.2021.36},
  annote =	{Keywords: permanent mod powers of 2, parallel computation, graphs, shortest disjoint paths, shortest disjoint cycles}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.122
Dynamic Complexity of Reachability: How Many Changes Can We Handle?

Authors: Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was extended for changes of size (log n)/(log log n), where n is the size of the graph. Changes of polylogarithmic size can be handled when also majority quantifiers may be used. In this paper we extend these results by showing that, for changes of polylogarithmic size, first-order update formulas suffice for maintaining (1) undirected reachability, and (2) directed reachability under insertions. For classes of directed graphs for which efficient parallel algorithms can compute non-zero circulation weights, reachability can be maintained with update formulas that may use "modulo 2" quantifiers under changes of polylogarithmic size. Examples for these classes include the class of planar graphs and graphs with bounded treewidth. The latter is shown here. As the logics we consider cannot maintain reachability under changes of larger sizes, our results are optimal with respect to the size of the changes.
Cite as

Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity of Reachability: How Many Changes Can We Handle?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 122:1-122:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ICALP.2020.122,
  author =	{Datta, Samir and Kumar, Pankaj and Mukherjee, Anish and Tawari, Anuj and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Dynamic Complexity of Reachability: How Many Changes Can We Handle?}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{122:1--122:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.122},
  URN =		{urn:nbn:de:0030-drops-125291},
  doi =		{10.4230/LIPIcs.ICALP.2020.122},
  annote =	{Keywords: Dynamic complexity, reachability, complex changes}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.21
Planar Maximum Matching: Towards a Parallel Algorithm

Authors: Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
Perfect matchings in planar graphs have been extensively studied and understood in the context of parallel complexity [P W Kastelyn, 1967; Vijay Vazirani, 1988; Meena Mahajan and Kasturi R. Varadarajan, 2000; Datta et al., 2010; Nima Anari and Vijay V. Vazirani, 2017]. However, corresponding results for maximum matchings have been elusive. We partly bridge this gap by proving: 1) An SPL upper bound for planar bipartite maximum matching search. 2) Planar maximum matching search reduces to planar maximum matching decision. 3) Planar maximum matching count reduces to planar bipartite maximum matching count and planar maximum matching decision. The first bound improves on the known [Thanh Minh Hoang, 2010] bound of L^{C_=L} and is adaptable to any special bipartite graph class with non-zero circulation such as bounded genus graphs, K_{3,3}-free graphs and K_5-free graphs. Our bounds and reductions non-trivially combine techniques like the Gallai-Edmonds decomposition [L. Lovász and M.D. Plummer, 1986], deterministic isolation [Datta et al., 2010; Samir Datta et al., 2012; Rahul Arora et al., 2016], and the recent breakthroughs in the parallel search for planar perfect matchings [Nima Anari and Vijay V. Vazirani, 2017; Piotr Sankowski, 2018].
Cite as

Samir Datta, Raghav Kulkarni, Ashish Kumar, and Anish Mukherjee. Planar Maximum Matching: Towards a Parallel Algorithm. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ISAAC.2018.21,
  author =	{Datta, Samir and Kulkarni, Raghav and Kumar, Ashish and Mukherjee, Anish},
  title =	{{Planar Maximum Matching: Towards a Parallel Algorithm}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{21:1--21:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.21},
  URN =		{urn:nbn:de:0030-drops-99695},
  doi =		{10.4230/LIPIcs.ISAAC.2018.21},
  annote =	{Keywords: maximum matching, planar graphs, parallel complexity, reductions}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.19
Shortest k-Disjoint Paths via Determinants

Authors: Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
The well-known k-disjoint path problem (k-DPP) asks for pairwise vertex-disjoint paths between k specified pairs of vertices (s_i, t_i) in a given graph, if they exist. The decision version of the shortest k-DPP asks for the length of the shortest (in terms of total length) such paths. Similarly, the search and counting versions ask for one such and the number of such shortest set of paths, respectively. We restrict attention to the shortest k-DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdière and Schrijver [Éric Colin de Verdière and Alexander Schrijver, 2011] for the general one-face problem. We do so by providing a randomised NC^2 algorithm along with an O(n^{omega/2}) time randomised sequential algorithm, for any fixed k. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals. The algorithms are based on a bijection between a shortest k-tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "pure" cycle covers.
Cite as

Samir Datta, Siddharth Iyer, Raghav Kulkarni, and Anish Mukherjee. Shortest k-Disjoint Paths via Determinants. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2018.19,
  author =	{Datta, Samir and Iyer, Siddharth and Kulkarni, Raghav and Mukherjee, Anish},
  title =	{{Shortest k-Disjoint Paths via Determinants}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.19},
  URN =		{urn:nbn:de:0030-drops-99183},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.19},
  annote =	{Keywords: disjoint paths, planar graph, parallel algorithm, cycle cover, determinant, inclusion-exclusion}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.120
Reachability and Distances under Multiple Changes

Authors: Samir Datta, Anish Mukherjee, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Recently it was shown that the transitive closure of a directed graph can be updated using first-order formulas after insertions and deletions of single edges in the dynamic descriptive complexity framework by Dong, Su, and Topor, and Patnaik and Immerman. In other words, Reachability is in DynFO. In this article we extend the framework to changes of multiple edges at a time, and study the Reachability and Distance queries under these changes. We show that the former problem can be maintained in DynFO(+, x) under changes affecting O({log n}/{log log n}) nodes, for graphs with n nodes. If the update formulas may use a majority quantifier then both Reachability and Distance can be maintained under changes that affect O(log^c n) nodes, for fixed c in N. Some preliminary results towards showing that distances are in DynFO are discussed.
Cite as

Samir Datta, Anish Mukherjee, Nils Vortmeier, and Thomas Zeume. Reachability and Distances under Multiple Changes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 120:1-120:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ICALP.2018.120,
  author =	{Datta, Samir and Mukherjee, Anish and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Reachability and Distances under Multiple Changes}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{120:1--120:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.120},
  URN =		{urn:nbn:de:0030-drops-91245},
  doi =		{10.4230/LIPIcs.ICALP.2018.120},
  annote =	{Keywords: dynamic complexity, reachability, distances, complex changes}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.98
A Strategy for Dynamic Programs: Start over and Muddle Through

Authors: Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
A strategy for constructing dynamic programs is introduced that utilises periodic computation of auxiliary data from scratch and the ability to maintain a query for a limited number of change steps. It is established that if some program can maintain a query for log n change steps after an AC^1-computable initialisation, it can be maintained by a first-order dynamic program as well, i.e., in DynFO. As an application, it is shown that decision and optimisation problems defined by monadic second-order (MSO) and guarded second-order logic (GSO) formulas are in DynFO, if only change sequences that produce graphs of bounded treewidth are allowed. To establish this result, Feferman-Vaught-type composition theorems for MSO and GSO are established that might be useful in their own right.
Cite as

Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A Strategy for Dynamic Programs: Start over and Muddle Through. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 98:1-98:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ICALP.2017.98,
  author =	{Datta, Samir and Mukherjee, Anish and Schwentick, Thomas and Vortmeier, Nils and Zeume, Thomas},
  title =	{{A Strategy for Dynamic Programs: Start over and Muddle Through}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{98:1--98:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.98},
  URN =		{urn:nbn:de:0030-drops-74470},
  doi =		{10.4230/LIPIcs.ICALP.2017.98},
  annote =	{Keywords: dynamic complexity, treewidth, monadic second order logic}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.17
Graph Properties in Node-Query Setting: Effect of Breaking Symmetry

Authors: Nikhil Balaji, Samir Datta, Raghav Kulkarni, and Supartha Podder

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The query complexity of graph properties is well-studied when queries are on the edges. We investigate the same when queries are on the nodes. In this setting a graph G = (V,E) on n vertices and a property P are given. A black-box access to an unknown subset S of V is provided via queries of the form "Does i belong to S?". We are interested in the minimum number of queries needed in the worst case in order to determine whether G[S] - the subgraph of G induced on S - satisfies P. Our primary motivation to study this model comes from the fact that it allows us to initiate a systematic study of breaking symmetry in the context of query complexity of graph properties. In particular, we focus on the hereditary graph properties - properties that are closed under deletion of vertices as well as edges. The famous Evasiveness Conjecture asserts that even with a minimal symmetry assumption on G, namely that of vertex-transitivity, the query complexity for any hereditary graph property in our setting is the worst possible, i.e., n. We show that in the absence of any symmetry on G it can fall as low as O(n^{1/(d + 1)}) where d denotes the minimum possible degree of a minimal forbidden sub-graph for P. In particular, every hereditary property benefits at least quadratically. The main question left open is: Can it go exponentially low for some hereditary property? We show that the answer is no for any hereditary property with finitely many forbidden subgraphs by exhibiting a bound of Omega(n^{1/k}) for a constant k depending only on the property. For general ones we rule out the possibility of the query complexity falling down to constant by showing Omega(log(n)*log(log(n))) bound. Interestingly, our lower bound proofs rely on the famous Sunflower Lemma due to Erdos and Rado.
Cite as

Nikhil Balaji, Samir Datta, Raghav Kulkarni, and Supartha Podder. Graph Properties in Node-Query Setting: Effect of Breaking Symmetry. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{balaji_et_al:LIPIcs.MFCS.2016.17,
  author =	{Balaji, Nikhil and Datta, Samir and Kulkarni, Raghav and Podder, Supartha},
  title =	{{Graph Properties in Node-Query Setting: Effect of Breaking Symmetry}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.17},
  URN =		{urn:nbn:de:0030-drops-64329},
  doi =		{10.4230/LIPIcs.MFCS.2016.17},
  annote =	{Keywords: query complexity, graph properties, symmetry and computation, forbidden subgraph}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.28
Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs

Authors: Samir Datta, Raghav Kulkarni, and Anish Mukherjee

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We present a Logspace Approximation Scheme (LSAS), i.e. an approximation algorithm for maximum matching in planar graphs (not necessarily bipartite) that achieves an approximation ratio arbitrarily close to one, using only logarithmic space. This deviates from the well known Baker's approach for approximation in planar graphs by avoiding the use of distance computation - which is not known to be in Logspace. Our algorithm actually works for any "recursively sparse" graph class which contains a linear size matching and also for certain other classes like bounded genus graphs. The scheme is based on an LSAS in bounded degree graphs which are not known to be amenable to Baker's method. We solve the bounded degree case by parallel augmentation of short augmenting paths. Finding a large number of such disjoint paths can, in turn, be reduced to finding a large independent set in a bounded degree graph. The bounded degree assumption allows us to obtain a Logspace algorithm.
Cite as

Samir Datta, Raghav Kulkarni, and Anish Mukherjee. Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.MFCS.2016.28,
  author =	{Datta, Samir and Kulkarni, Raghav and Mukherjee, Anish},
  title =	{{Space-Efficient Approximation Scheme for Maximum Matching in Sparse Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.28},
  URN =		{urn:nbn:de:0030-drops-64436},
  doi =		{10.4230/LIPIcs.MFCS.2016.28},
  annote =	{Keywords: maximum matching, approximation scheme, logspace, planar graphs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.246
Counting Euler Tours in Undirected Bounded Treewidth Graphs

Authors: Nikhil Balaji, Samir Datta, and Venkatesh Ganesan

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
We show that counting Euler tours in undirected bounded tree-width graphs is tractable even in parallel - by proving a GapL upper bound. This is in stark contrast to #P-completeness of the same problem in general graphs. Our main technical contribution is to show how (an instance of) dynamic programming on bounded clique-width graphs can be performed efficiently in parallel. Thus we show that the sequential result of Espelage, Gurski and Wanke for efficiently computing Hamiltonian paths in bounded clique-width graphs can be adapted in the parallel setting to count the number of Hamiltonian paths which in turn is a tool for counting the number of Euler tours in bounded tree-width graphs. Our technique also yields parallel algorithms for counting longest paths and bipartite perfect matchings in bounded-clique width graphs. While establishing that counting Euler tours in bounded tree-width graphs can be computed by non-uniform monotone arithmetic circuits of polynomial degree (which characterize #SAC^1) is relatively easy, establishing a uniform #SAC^1 bound needs a careful use of polynomial interpolation.
Cite as

Nikhil Balaji, Samir Datta, and Venkatesh Ganesan. Counting Euler Tours in Undirected Bounded Treewidth Graphs. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 246-260, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{balaji_et_al:LIPIcs.FSTTCS.2015.246,
  author =	{Balaji, Nikhil and Datta, Samir and Ganesan, Venkatesh},
  title =	{{Counting Euler Tours in Undirected Bounded Treewidth Graphs}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{246--260},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.246},
  URN =		{urn:nbn:de:0030-drops-56493},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.246},
  annote =	{Keywords: Euler Tours, Bounded Treewidth, Bounded clique-width, Hamiltonian cycles, Parallel algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.254
Improved Bounds for Bipartite Matching on Surfaces

Authors: Samir Datta, Arjun Gopalan, Raghav Kulkarni, and Raghunath Tewari

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We exhibit the following new upper bounds on the space complexity and the parallel complexity of the Bipartite Perfect Matching (BPM) problem for graphs of small genus: (1) BPM in planar graphs is in UL (improves upon the SPL bound from Datta, Kulkarni, and Roy; (2) BPM in constant genus graphs is in NL (orthogonal to the SPL bound from Datta, Kulkarni, Tewari, and Vinodchandran.; (3) BPM in poly-logarithmic genus graphs is in NC; (extends the NC bound for O(log n) genus graphs from Mahajan and Varadarajan, and Kulkarni, Mahajan, and Varadarajan. For Part (1) we combine the flow technique of Miller and Naor with the double counting technique of Reinhardt and Allender . For Part (2) and (3) we extend Miller and Naor's result to higher genus surfaces in the spirit of Chambers, Erickson and Nayyeri.
Cite as

Samir Datta, Arjun Gopalan, Raghav Kulkarni, and Raghunath Tewari. Improved Bounds for Bipartite Matching on Surfaces. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 254-265, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2012.254,
  author =	{Datta, Samir and Gopalan, Arjun and Kulkarni, Raghav and Tewari, Raghunath},
  title =	{{Improved Bounds for Bipartite Matching on Surfaces}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{254--265},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.254},
  URN =		{urn:nbn:de:0030-drops-34141},
  doi =		{10.4230/LIPIcs.STACS.2012.254},
  annote =	{Keywords: Perfect Matching, Graphs on Surfaces, Space Complexity, NC, UL}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.579
Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs

Authors: Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N. Variyam Vinodchandran

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We investigate the space complexity of certain perfect matching problems over bipartite graphs embedded on surfaces of constant genus (orientable or non-orientable). We show that the problems of deciding whether such graphs have (1) a perfect matching or not and (2) a unique perfect matching or not, are in the logspace complexity class SPL. Since SPL is contained in the logspace counting classes oplus L (in fact in mod_k for all k >= 2), C=L, and PL, our upper bound places the above-mentioned matching problems in these counting classes as well. We also show that the search version, computing a perfect matching, for this class of graphs is in FL^SPL. Our results extend the same upper bounds for these problems over bipartite planar graphs known earlier. As our main technical result, we design a logspace computable and polynomially bounded weight function which isolates a minimum weight perfect matching in bipartite graphs embedded on surfaces of constant genus. We use results from algebraic topology for proving the correctness of the weight function.
Cite as

Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N. Variyam Vinodchandran. Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 579-590, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2011.579,
  author =	{Datta, Samir and Kulkarni, Raghav and Tewari, Raghunath and Vinodchandran, N. Variyam},
  title =	{{Space Complexity of Perfect Matching in Bounded Genus Bipartite Graphs}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{579--590},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.579},
  URN =		{urn:nbn:de:0030-drops-30450},
  doi =		{10.4230/LIPIcs.STACS.2011.579},
  annote =	{Keywords: perfect matching, bounded genus graphs, isolation problem}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2456
Log-space Algorithms for Paths and Matchings in k-trees

Authors: Bireswar Das, Samir Datta, and Prajakta Nimbhorkar

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Reachability and shortest path problems are \NLC\ for general graphs. They are known to be in \Log\ for graphs of tree-width $2$ \cite{JT07}. However, for graphs of tree-width larger than $2$, no bound better than \NL\ is known. In this paper, we improve these bounds for $k$-trees, where $k$ is a constant. In particular, the main results of our paper are log-space algorithms for reachability in directed $k$-trees, and for computation of shortest and longest paths in directed acyclic $k$-trees. Besides the path problems mentioned above, we consider the problem of deciding whether a $k$-tree has a perfect macthing (decision version), and if so, finding a perfect matching (search version), and prove that these problems are \Log-complete. These problems are known to be in \Ptime\ and in \RNC\ for general graphs, and in \SPL\ for planar bipartite graphs \cite{DKR08}. Our results settle the complexity of these problems for the class of $k$-trees. The results are also applicable for bounded tree-width graphs, when a tree-decomposition is given as input. The technique central to our algorithms is a careful implementation of divide-and-conquer approach in log-space, along with some ideas from \cite{JT07} and \cite{LMR07}.
Cite as

Bireswar Das, Samir Datta, and Prajakta Nimbhorkar. Log-space Algorithms for Paths and Matchings in k-trees. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 215-226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.STACS.2010.2456,
  author =	{Das, Bireswar and Datta, Samir and Nimbhorkar, Prajakta},
  title =	{{Log-space Algorithms for Paths and Matchings in k-trees}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{215--226},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2456},
  URN =		{urn:nbn:de:0030-drops-24563},
  doi =		{10.4230/LIPIcs.STACS.2010.2456},
  annote =	{Keywords: k-trees, reachability, matching, log-space}
}
Document
DOI: 10.4230/DagSemProc.09421.6
Planar Graph Isomorphism is in Log-Space

Authors: Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner

Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

Abstract
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important special case by presenting an upper bound that matches the known log-space hardness [JKMT03]. In fact, we show the formally stronger result that planar graph canonization is in log-space. This improves the previously known upper bound of AC1 [MR91]. Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to log-space reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in log-space by [DLN08]. This is achieved by using the above decomposition, and by making significant modifications to Lindell’s algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas including a non-trivial case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph.
Cite as

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar Graph Isomorphism is in Log-Space. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:DagSemProc.09421.6,
  author =	{Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian},
  title =	{{Planar Graph Isomorphism is in Log-Space}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--32},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.6},
  URN =		{urn:nbn:de:0030-drops-24169},
  doi =		{10.4230/DagSemProc.09421.6},
  annote =	{Keywords: Planar Graphs, Graph Isomorphism, Logspace}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2314
Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space

Authors: Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
Graph isomorphism is an important and widely studied computational problem with a yet unsettled complexity. However, the exact complexity is known for isomorphism of various classes of graphs. Recently, \cite{DLNTW09} proved that planar isomorphism is complete for log-space. We extend this result %of \cite{DLNTW09} further to the classes of graphs which exclude $K_{3,3}$ or $K_5$ as a minor, and give a log-space algorithm. Our algorithm decomposes $K_{3,3}$ minor-free graphs into biconnected and those further into triconnected components, which are known to be either planar or $K_5$ components \cite{Vaz89}. This gives a triconnected component tree similar to that for planar graphs. An extension of the log-space algorithm of \cite{DLNTW09} can then be used to decide the isomorphism problem. For $K_5$ minor-free graphs, we consider $3$-connected components. These are either planar or isomorphic to the four-rung mobius ladder on $8$ vertices or, with a further decomposition, one obtains planar $4$-connected components \cite{Khu88}. We give an algorithm to get a unique decomposition of $K_5$ minor-free graphs into bi-, tri- and $4$-connected components, and construct trees, accordingly. Since the algorithm of \cite{DLNTW09} does not deal with four-connected component trees, it needs to be modified in a quite non-trivial way.
Cite as

Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Graph Isomorphism for K_{3,3}-free and K_5-free graphs is in Log-space. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 145-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2009.2314,
  author =	{Datta, Samir and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian},
  title =	{{Graph Isomorphism for K\underline\{3,3\}-free and K\underline5-free graphs is in Log-space}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{145--156},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2314},
  URN =		{urn:nbn:de:0030-drops-23144},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2314},
  annote =	{Keywords: Graph isomorphism, K\underline\{3,3\}-free graphs, K\underline5-free graphs, log-space}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1749
3-connected Planar Graph Isomorphism is in Log-space

Authors: Samir Datta, Nutan Limaye, and Prajakta Nimbhorkar

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
We consider the isomorphism and canonization problem for $3$-connected planar graphs. The problem was known to be \Log-hard and in \ULcoUL\ \cite{TW07}. In this paper, we give a deterministic log-space algorithm for $3$-connected planar graph isomorphism and canonization. This gives an \Log-completeness result, thereby settling its complexity. \par The algorithm uses the notion of universal exploration sequences from \cite{koucky01} and \cite{Rei05}. To our knowledge, this is a completely new approach to graph canonization.
Cite as

Samir Datta, Nutan Limaye, and Prajakta Nimbhorkar. 3-connected Planar Graph Isomorphism is in Log-space. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 155-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.FSTTCS.2008.1749,
  author =	{Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta},
  title =	{{3-connected Planar Graph Isomorphism is in Log-space}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{155--162},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1749},
  URN =		{urn:nbn:de:0030-drops-17491},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1749},
  annote =	{Keywords: Planar graph isomorphism, three connected graphs, logspace, universal exploration sequence}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1346
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

Authors: Samir Datta, Raghav Kulkarni, and Sambuddha Roy

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as described in (Mulmuley et al. 1987) achieves the same for general graphs using a randomized weighting scheme, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the matching problem to testing whether a matrix is singular, under the promise that its determinant is $0$ or $1$, thus obtaining a highly parallel SPL algorithm for bipartite planar graphs. This improves the earlier known bounds of non-uniform SPL by (Allender et al. 1999) and $NC^2$ by (Miller and Naor 1995, Mahajan and Varadarajan 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Our techniques are elementary and simple.
Cite as

Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 229-240, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2008.1346,
  author =	{Datta, Samir and Kulkarni, Raghav and Roy, Sambuddha},
  title =	{{Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{229--240},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1346},
  URN =		{urn:nbn:de:0030-drops-13465},
  doi =		{10.4230/LIPIcs.STACS.2008.1346},
  annote =	{Keywords: }
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact