BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
A graph separator is a subset of vertices of a graph whose removal divides the graph into small components. Computing small graph separators for various classes of graphs is an important computational task. In this paper, we present a polynomial time algorithm that uses O(g1/2n1/2logn)-space to find an O(g1/2n1/2)-sized separator of a graph having n vertices and embedded on a surface of genus g.
The authors have withdrawn this paper due to an error in the proof of Lemma 3.4. -------------------------------------------------------------------------------------------- The authors have withdrawn this paper due to an error in the proof of Lemma 3.4z(Assadi, Chen, and Khanna, 2019) define a 4-player hidden-pointer-chasing (HPC4), and using it, give strong multi-pass lower bounds for graph problems in the streaming model of computation and a lower bound on the query complexity of sub-modular minimization. We present a two-player version (HPC2) of HPC4 that has matching communication complexity to HPC4. Our formulation allows us to lower bound its communication complexity with a simple direct-sum argument. Using this lower bound on the communication complexity of HPC2, we retain the streaming and query complexity lower bounds by (Assadi, Chen, and Khanna, 2019). Further, by giving reductions from HPC2, we prove new multi-pass space lower bounds for graph problems in turnstile streams. In particular, we show that any algorithm which computes the exact weight of the maximum weighted matching in an n-vertex graph requires O~(n2) space unless it makes ω(logn) passes over the turnstile stream, and that any algorithm which computes the minimum s-t distance in an n-vertex graph requires n2−o(1) space unless it makes nΩ(1) passes over the turnstile stream. Our reductions can be modified to use HPC4 as well.
Savitch showed in 1970 that nondeterministic logspace (NL) is contained in deterministic O(log2n) space but his algorithm requires quasipolynomial time. The question whether we can have a deterministic algorithm for every problem in NL that requires polylogarithmic space and simultaneously runs in polynomial time was left open. In this paper we give a partial solution to this problem and show that for every language in NL there exists an unambiguous nondeterministic algorithm that requires O(log2n) space and simultaneously runs in polynomial time.
Given a graph G and two vertices s and t in it, {\em graph reachability} is the problem of checking whether there exists a path from s to t in G. We show that reachability in directed layered planar graphs can be decided in polynomial time and O(nε) space, for any ε>0. The previous best known space bound for this problem with polynomial time was approximately O(n) space \cite{INPVW13}. Deciding graph reachability in {\SC} is an important open question in complexity theory and in this paper we make progress towards resolving this question.
In this paper, we show that given a weighted, directed planar graph G, and any ε>0, there exists a polynomial time and O(n21+ε) space algorithm that computes the shortest path between two fixed vertices in G. We also consider the {\RB} problem, which states that given a graph G whose edges are colored either red or blue and two fixed vertices s and t in G, is there a path from s to t in G that alternates between red and blue edges. The {\RB} problem in planar DAGs is {\NL}-complete. We exhibit a polynomial time and O(n21+ε) space algorithm (for any ε>0) for the {\RB} problem in planar DAG. In the last part of this paper, we consider the problem of deciding and constructing the perfect matching present in a planar bipartite graph and also a similar problem which is to find a Hall-obstacle in a planar bipartite graph. We show the time-space bound of these two problems are same as the bound of shortest path problem in a directed planar graph.
The perfect matching problem has a randomized NC algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We derandomize this lemma for K3,3-free and K5-free bipartite graphs, i.e. we give a deterministic log-space construction of such a weight assignment for these graphs. Such a construction was known previously for planar bipartite graphs. Our result implies that the perfect matching problem for K3,3-free and K5-free bipartite graphs is in SPL. It also gives an alternate proof for an already known result -- reachability for K3,3-free and K5-free graphs is in UL.
We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$. [-] We investigate the complexity of min-uniqueness - a central notion in studying the \NL vs \UL problem. We show that min-uniqueness is necessary and sufficient for showing $\NL =\UL$. We revisit the class $\OptL[\log n]$ and show that {\sc ShortestPathLength} - computing the length of the shortest path in a DAG, is complete for $\OptL[\log n]$. We introduce $\UOptL[\log n]$, an unambiguous version of $\OptL[\log n]$, and show that (a) $\NL =\UL$ if and only if $\OptL[\log n] = \UOptL[\log n]$, (b) $\LogFew \leq \UOptL[\log n] \leq \SPL$. [-] We show that the reachability problem over graphs embedded on 3 pages is complete for \NL. This contrasts with the reachability problem over graphs embedded on 2 pages which is logspace equivalent to the reachability problem in planar graphs and hence is in \UL.
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 ⊕Ł (in fact in \modk\ for all k≥2), \CeqL, 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.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.