14 Search Results for "Pandya, Paritosh K."

Document
DOI: 10.4230/LIPIcs.CONCUR.2023.23
Satisfiability Checking of Multi-Variable TPTL with Unilateral Intervals Is PSPACE-Complete

Authors: Shankara Narayanan Krishna, Khushraj Nanik Madnani, Rupak Majumdar, and Paritosh Pandya

Published in: LIPIcs, Volume 279, 34th International Conference on Concurrency Theory (CONCUR 2023)

Abstract
We investigate the decidability of the {0,∞} fragment of Timed Propositional Temporal Logic (TPTL). We show that the satisfiability checking of TPTL^{0,∞} is PSPACE-complete. Moreover, even its 1-variable fragment (1-TPTL^{0,∞}) is strictly more expressive than Metric Interval Temporal Logic (MITL) for which satisfiability checking is EXPSPACE complete. Hence, we have a strictly more expressive logic with computationally easier satisfiability checking. To the best of our knowledge, TPTL^{0,∞} is the first multi-variable fragment of TPTL for which satisfiability checking is decidable without imposing any bounds/restrictions on the timed words (e.g. bounded variability, bounded time, etc.). The membership in PSPACE is obtained by a reduction to the emptiness checking problem for a new "non-punctual’’ subclass of Alternating Timed Automata with multiple clocks called Unilateral Very Weak Alternating Timed Automata (VWATA^{0,∞}) which we prove to be in PSPACE. We show this by constructing a simulation equivalent non-deterministic timed automata whose number of clocks is polynomial in the size of the given VWATA^{0,∞}.
Cite as

Shankara Narayanan Krishna, Khushraj Nanik Madnani, Rupak Majumdar, and Paritosh Pandya. Satisfiability Checking of Multi-Variable TPTL with Unilateral Intervals Is PSPACE-Complete. In 34th International Conference on Concurrency Theory (CONCUR 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 279, pp. 23:1-23:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{krishna_et_al:LIPIcs.CONCUR.2023.23,
  author =	{Krishna, Shankara Narayanan and Madnani, Khushraj Nanik and Majumdar, Rupak and Pandya, Paritosh},
  title =	{{Satisfiability Checking of Multi-Variable TPTL with Unilateral Intervals Is PSPACE-Complete}},
  booktitle =	{34th International Conference on Concurrency Theory (CONCUR 2023)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-299-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{279},
  editor =	{P\'{e}rez, Guillermo A. and Raskin, Jean-Fran\c{c}ois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2023.23},
  URN =		{urn:nbn:de:0030-drops-190171},
  doi =		{10.4230/LIPIcs.CONCUR.2023.23},
  annote =	{Keywords: TPTL, Satisfiability, Non-Punctuality, Decidability, Expressiveness, ATA}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.FSTTCS.2018.1
Random Testing for Distributed Systems with Theoretical Guarantees (Invited Paper)

Authors: Rupak Majumdar

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

Abstract
Random testing has proven to be an effective way to catch bugs in concurrent and distributed systems. This is surprising, as the space of executions is enormous and conventional formal methods intuition would suggest that bad behaviors would only be found by extremely unlikely coincidences. Empirically, many bugs in distributed systems can be explained by interactions among only a small number of features. Thus, one can attempt to explain the effectiveness of random testing under various "small depth" hypotheses. In particular, it may be possible to test all interactions of k features for a small constant k by executing a family of tests that is exponentially or even doubly-exponentially smaller than the family of all tests. Moreover, under certain conditions, a randomly chosen small set of tests is sufficient to cover all k-wise interactions with high probability. I will describe two concrete scenarios. First, I will describe bugs in distributed systems caused by network partition faults. In many practical instances, these bugs occur due to two or three key nodes, such as leaders or replicas, not being able to communicate, or because the leading node finds itself in a block of the partition without quorum. In this case, I will show using the probabilistic method that a small set of randomly chosen tests will cover all "small partition" scenarios with high probability. Second, I will consider bugs that arise due to unexpected schedules (interleavings) of concurrent events. Again, many bugs depend only on the relative ordering of a small number of events (the "bug depth" of the bug). In this case, I will show a testing algorithm that prioritizes low depth interleavings and a randomized testing algorithm that bounds the probability of sampling any behavior of bug depth k for a fixed k. The testing algorithm is based on combinatorial insights from the theory of partial orders, such as the notion of dimension and its generalization to d-hitting families as well as results on online chain partitioning. Beyond the potential for designing or explaining random testing procedures, the technical arguments show the potential of combining "Theory A" and "Theory B" results to the important domain of software testing. This is joint work primarily with Filip Niksic [Filip Niksic, 2018], and with Dmitry Chistikov, Simin Oraee, Burcu Kulahcioglu Özkan, Mitra Tabaei Befrouei, and Georg Weissenbacher. This work was partially funded by an ERC Synergy Award (ImPACT).
Cite as

Rupak Majumdar. Random Testing for Distributed Systems with Theoretical Guarantees (Invited Paper). In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{majumdar:LIPIcs.FSTTCS.2018.1,
  author =	{Majumdar, Rupak},
  title =	{{Random Testing for Distributed Systems with Theoretical Guarantees}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{1:1--1:1},
  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.1},
  URN =		{urn:nbn:de:0030-drops-99000},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.1},
  annote =	{Keywords: Random testing, Hitting families}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.7
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators

Authors: V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay

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

Abstract
Let F[X] be the polynomial ring over the variables X={x_1,x_2, ..., x_n}. An ideal I= <p_1(x_1), ..., p_n(x_n)> generated by univariate polynomials {p_i(x_i)}_{i=1}^n is a univariate ideal. We study the ideal membership problem for the univariate ideals and show the following results. - Let f(X) in F[l_1, ..., l_r] be a (low rank) polynomial given by an arithmetic circuit where l_i : 1 <= i <= r are linear forms, and I=<p_1(x_1), ..., p_n(x_n)> be a univariate ideal. Given alpha in F^n, the (unique) remainder f(X) mod I can be evaluated at alpha in deterministic time d^{O(r)} * poly(n), where d=max {deg(f),deg(p_1)...,deg(p_n)}. This yields a randomized n^{O(r)} algorithm for minimum vertex cover in graphs with rank-r adjacency matrices. It also yields an n^{O(r)} algorithm for evaluating the permanent of a n x n matrix of rank r, over any field F. Over Q, an algorithm of similar run time for low rank permanent is due to Barvinok [Barvinok, 1996] via a different technique. - Let f(X)in F[X] be given by an arithmetic circuit of degree k (k treated as fixed parameter) and I=<p_1(x_1), ..., p_n(x_n)>. We show that in the special case when I=<x_1^{e_1}, ..., x_n^{e_n}>, we obtain a randomized O^*(4.08^k) algorithm that uses poly(n,k) space. - Given f(X)in F[X] by an arithmetic circuit and I=<p_1(x_1), ..., p_k(x_k)>, membership testing is W[1]-hard, parameterized by k. The problem is MINI[1]-hard in the special case when I=<x_1^{e_1}, ..., x_k^{e_k}>.
Cite as

V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators. 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. 7:1-7:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2018.7,
  author =	{Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha},
  title =	{{Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{7:1--7:18},
  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.7},
  URN =		{urn:nbn:de:0030-drops-99068},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.7},
  annote =	{Keywords: Combinatorial Nullstellensatz, Ideal Membership, Parametric Hardness, Low Rank Permanent}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.9
The Cayley-Graph of the Queue Monoid: Logic and Decidability

Authors: Faried Abu Zaid and Chris Köcher

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

Abstract
We investigate the decidability of logical aspects of graphs that arise as Cayley-graphs of the so-called queue monoids. These monoids model the behavior of the classical (reliable) fifo-queues. We answer a question raised by Huschenbett, Kuske, and Zetzsche and prove the decidability of the first-order theory of these graphs with the help of an - at least for the authors - new combination of the well-known method from Ferrante and Rackoff and an automata-based approach. On the other hand, we prove that the monadic second-order of the queue monoid's Cayley-graph is undecidable.
Cite as

Faried Abu Zaid and Chris Köcher. The Cayley-Graph of the Queue Monoid: Logic and Decidability. 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. 9:1-9:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{abuzaid_et_al:LIPIcs.FSTTCS.2018.9,
  author =	{Abu Zaid, Faried and K\"{o}cher, Chris},
  title =	{{The Cayley-Graph of the Queue Monoid: Logic and Decidability}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{9:1--9:17},
  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.9},
  URN =		{urn:nbn:de:0030-drops-99088},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.9},
  annote =	{Keywords: Queues, Transformation Monoid, Cayley-Graph, Logic, First-Order Theory, MSO Theory, Model Checking}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.11
Towards a General Direct Product Testing Theorem

Authors: Elazar Goldenberg and Karthik C. S.

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

Abstract
The Direct Product encoding of a string a in {0,1}^n on an underlying domain V subseteq ([n] choose k), is a function DP_V(a) which gets as input a set S in V and outputs a restricted to S. In the Direct Product Testing Problem, we are given a function F:V -> {0,1}^k, and our goal is to test whether F is close to a direct product encoding, i.e., whether there exists some a in {0,1}^n such that on most sets S, we have F(S)=DP_V(a)(S). A natural test is as follows: select a pair (S,S')in V according to some underlying distribution over V x V, query F on this pair, and check for consistency on their intersection. Note that the above distribution may be viewed as a weighted graph over the vertex set V and is referred to as a test graph. The testability of direct products was studied over various domains and test graphs: Dinur and Steurer (CCC '14) analyzed it when V equals the k-th slice of the Boolean hypercube and the test graph is a member of the Johnson graph family. Dinur and Kaufman (FOCS '17) analyzed it for the case where V is the set of faces of a Ramanujan complex, where in this case V=O_k(n). In this paper, we study the testability of direct products in a general setting, addressing the question: what properties of the domain and the test graph allow one to prove a direct product testing theorem? Towards this goal we introduce the notion of coordinate expansion of a test graph. Roughly speaking a test graph is a coordinate expander if it has global and local expansion, and has certain nice intersection properties on sampling. We show that whenever the test graph has coordinate expansion then it admits a direct product testing theorem. Additionally, for every k and n we provide a direct product domain V subseteq (n choose k) of size n, called the Sliding Window domain for which we prove direct product testability.
Cite as

Elazar Goldenberg and Karthik C. S.. Towards a General Direct Product Testing Theorem. 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. 11:1-11:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{goldenberg_et_al:LIPIcs.FSTTCS.2018.11,
  author =	{Goldenberg, Elazar and C. S., Karthik},
  title =	{{Towards a General Direct Product Testing Theorem}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{11:1--11:17},
  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.11},
  URN =		{urn:nbn:de:0030-drops-99105},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.11},
  annote =	{Keywords: Property Testing, Direct Product, PCP, Johnson graph, Ramanujan Complex, Derandomization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.18
Graph Pattern Polynomials

Authors: Markus Bläser, Balagopal Komarath, and Karteek Sreenivasaiah

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

Abstract
Given a host graph G and a pattern graph H, the induced subgraph isomorphism problem is to decide whether G contains an induced subgraph that is isomorphic to H. We study the time complexity of induced subgraph isomorphism problems when the pattern graph is fixed. Nesetril and Poljak gave an O(n^{k omega}) time algorithm that decides the induced subgraph isomorphism problem for any 3k vertex pattern graph (the universal algorithm), where omega is the matrix multiplication exponent. Improvements are not known for any infinite pattern family. Algorithms faster than the universal algorithm are known only for a finite number of pattern graphs. In this paper, we show that there exists infinitely many pattern graphs for which the induced subgraph isomorphism problem has algorithms faster than the universal algorithm. Our algorithm works by reducing the pattern detection problem into a multilinear term detection problem on special classes of polynomials called graph pattern polynomials. We show that many of the existing algorithms including the universal algorithm can also be described in terms of such a reduction. We formalize this class of algorithms by defining graph pattern polynomial families and defining a notion of reduction between these polynomial families. The reduction also allows us to argue about relative hardness of various graph pattern detection problems within this framework. We show that solving the induced subgraph isomorphism for any pattern graph that contains a k-clique is at least as hard detecting k-cliques. An equivalent theorem is not known in the general case. In the full version of this paper, we obtain new algorithms for P_5 and C_5 that are optimal under reasonable hardness assumptions. We also use this method to derive new combinatorial algorithms - algorithms that do not use fast matrix multiplication - for paths and cycles. We also show why graph homomorphisms play a major role in algorithms for subgraph isomorphism problems. Using this, we show that the arithmetic circuit complexity of the graph homomorphism polynomial for K_k - e (The k-clique with an edge removed) is related to the complexity of many subgraph isomorphism problems. This generalizes and unifies many existing results.
Cite as

Markus Bläser, Balagopal Komarath, and Karteek Sreenivasaiah. Graph Pattern Polynomials. 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. 18:1-18:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.FSTTCS.2018.18,
  author =	{Bl\"{a}ser, Markus and Komarath, Balagopal and Sreenivasaiah, Karteek},
  title =	{{Graph Pattern Polynomials}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{18:1--18:13},
  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.18},
  URN =		{urn:nbn:de:0030-drops-99172},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.18},
  annote =	{Keywords: algorithms, induced subgraph detection, algebraic framework}
}
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.FSTTCS.2018.23
Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem

Authors: Sapna Grover, Neelima Gupta, Samir Khuller, and Aditya Pancholi

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

Abstract
In this paper, we give the first constant factor approximation algorithm for capacitated knapsack median problem (CKnM) for hard uniform capacities, violating the budget by a factor of 1+epsilon and capacities by a 2+epsilon factor. To the best of our knowledge, no constant factor approximation is known for the problem even with capacity/budget/both violations. Even for the uncapacitated variant of the problem, the natural LP is known to have an unbounded integrality gap even after adding the covering inequalities to strengthen the LP. Our techniques for CKnM provide two types of results for the capacitated k-facility location problem. We present an O(1/epsilon^2) factor approximation for the problem, violating capacities by (2+epsilon). Another result is an O(1/epsilon) factor approximation, violating the capacities by a factor of at most (1 + epsilon) using at most 2k facilities for a fixed epsilon>0. As a by-product, a constant factor approximation algorithm for capacitated facility location problem with uniform capacities is presented, violating the capacities by (1 + epsilon) factor. Though constant factor results are known for the problem without violating the capacities, the result is interesting as it is obtained by rounding the solution to the natural LP, which is known to have an unbounded integrality gap without violating the capacities. Thus, we achieve the best possible from the natural LP for the problem. The result shows that the natural LP is not too bad.
Cite as

Sapna Grover, Neelima Gupta, Samir Khuller, and Aditya Pancholi. Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem. 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. 23:1-23:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{grover_et_al:LIPIcs.FSTTCS.2018.23,
  author =	{Grover, Sapna and Gupta, Neelima and Khuller, Samir and Pancholi, Aditya},
  title =	{{Constant Factor Approximation Algorithm for Uniform Hard Capacitated Knapsack Median Problem}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{23:1--23:22},
  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.23},
  URN =		{urn:nbn:de:0030-drops-99224},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.23},
  annote =	{Keywords: Capacitated Knapsack Median, Capacitated k -Facility Location}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.34
On the Parameterized Complexity of [1,j]-Domination Problems

Authors: Mohsen Alambardar Meybodi, Fedor Fomin, Amer E. Mouawad, and Fahad Panolan

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

Abstract
For a graph G, a set D subseteq V(G) is called a [1,j]-dominating set if every vertex in V(G) setminus D has at least one and at most j neighbors in D. A set D subseteq V(G) is called a [1,j]-total dominating set if every vertex in V(G) has at least one and at most j neighbors in D. In the [1,j]-(Total) Dominating Set problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [1,j]-(total) dominating set of size at most k. The [1,j]-Dominating Set problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [1,2]-Total Dominating Set problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the Dominating Set problem, both are W[1]-hard when parameterized by solution size. In this work, we study [1,j]-Dominating Set on sparse graph classes from the perspective of parameterized complexity and prove the following results when the problem is parameterized by solution size: - [1,j]-Dominating Set is W[1]-hard on d-degenerate graphs for d = j + 1; - [1,j]-Dominating Set is FPT on nowhere dense graphs. We also prove that the known algorithm for [1,j]-Dominating Set on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). Finally, assuming SETH, we provide a lower bound for the running time of any algorithm solving the [1,2]-Total Dominating Set problem parameterized by pathwidth.
Cite as

Mohsen Alambardar Meybodi, Fedor Fomin, Amer E. Mouawad, and Fahad Panolan. On the Parameterized Complexity of [1,j]-Domination Problems. 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. 34:1-34:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{alambardarmeybodi_et_al:LIPIcs.FSTTCS.2018.34,
  author =	{Alambardar Meybodi, Mohsen and Fomin, Fedor and Mouawad, Amer E. and Panolan, Fahad},
  title =	{{On the Parameterized Complexity of \lbrack1,j\rbrack-Domination Problems}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{34:1--34:14},
  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.34},
  URN =		{urn:nbn:de:0030-drops-99330},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.34},
  annote =	{Keywords: \lbrack1, j\rbrack-dominating set, parameterized complexity, sparse graphs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.35
Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number

Authors: Pranabendu Misra, Saket Saurabh, Roohani Sharma, and Meirav Zehavi

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

Abstract
Fradkin and Seymour [Journal of Combinatorial Graph Theory, Series B, 2015] defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk [ESA, 2013], where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is that the yes-instances of the problems above have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, an inductive argument and structural properties of the digraphs.
Cite as

Pranabendu Misra, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number. 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. 35:1-35:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{misra_et_al:LIPIcs.FSTTCS.2018.35,
  author =	{Misra, Pranabendu and Saurabh, Saket and Sharma, Roohani and Zehavi, Meirav},
  title =	{{Sub-Exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{35:1--35:19},
  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.35},
  URN =		{urn:nbn:de:0030-drops-99341},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.35},
  annote =	{Keywords: sub-exponential fixed-parameter tractable algorithms, directed feedback arc set, directed cutwidth, optimal linear arrangement, bounded independence number digraph}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.39
Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model

Authors: Sumedh Tirodkar

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

Abstract
We present an improved deterministic algorithm for Maximum Cardinality Matching on general graphs in the Semi-Streaming Model. In the Semi-Streaming Model, a graph is presented as a sequence of edges, and an algorithm must access the edges in the given sequence. It can only use O(n polylog n) space to perform computations, where n is the number of vertices of the graph. If the algorithm goes over the stream k times, it is called a k-pass algorithm. In this model, McGregor [McGregor, 2005] gave the currently best known randomized (1+epsilon)-approximation algorithm for maximum cardinality matching on general graphs, that uses (1/epsilon)^{O(1/epsilon)} passes. Ahn and Guha [Ahn and Guha, 2013] later gave the currently best known deterministic (1+epsilon)-approximation algorithms for maximum cardinality matching: one on bipartite graphs that uses O(log log(1/epsilon)/epsilon^2) passes, and the other on general graphs that uses O(log n *poly(1/epsilon)) passes (note that, for general graphs, the number of passes is dependent on the size of the input). We present the first deterministic algorithm that achieves a (1+epsilon)-approximation on general graphs in only a constant number ((1/epsilon)^{O(1/epsilon)}) of passes.
Cite as

Sumedh Tirodkar. Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model. 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. 39:1-39:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{tirodkar:LIPIcs.FSTTCS.2018.39,
  author =	{Tirodkar, Sumedh},
  title =	{{Deterministic Algorithms for Maximum Matching on General Graphs in the Semi-Streaming Model}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{39:1--39:16},
  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.39},
  URN =		{urn:nbn:de:0030-drops-99383},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.39},
  annote =	{Keywords: Semi Streaming, Maximum Matching}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2018.39
Logics Meet 1-Clock Alternating Timed Automata

Authors: Shankara Narayanan Krishna, Khushraj Madnani, and Paritosh K. Pandya

Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)

Abstract
This paper investigates a decidable and highly expressive real time logic QkMSO which is obtained by extending MSO[<] with guarded quantification using block of less than k metric quantifiers. The resulting logic is shown to be expressively equivalent to 1-clock ATA where loops are without clock resets, as well as, RatMTL, a powerful extension of MTL[U_I] with regular expressions. We also establish 4-variable property for QkMSO and characterize the expressive power of its 2-variable fragment. Thus, the paper presents progress towards expressively complete logics for 1-clock ATA.
Cite as

Shankara Narayanan Krishna, Khushraj Madnani, and Paritosh K. Pandya. Logics Meet 1-Clock Alternating Timed Automata. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 39:1-39:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{krishna_et_al:LIPIcs.CONCUR.2018.39,
  author =	{Krishna, Shankara Narayanan and Madnani, Khushraj and Pandya, Paritosh K.},
  title =	{{Logics Meet 1-Clock Alternating Timed Automata}},
  booktitle =	{29th International Conference on Concurrency Theory (CONCUR 2018)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Schewe, Sven and Zhang, Lijun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.39},
  URN =		{urn:nbn:de:0030-drops-95779},
  doi =		{10.4230/LIPIcs.CONCUR.2018.39},
  annote =	{Keywords: Metric Temporal Logic, Alternating Timed Automata, MSO, Regular Expressions, Expressive Completeness}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.28
An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation

Authors: Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, and Howard Straubing

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
In earlier work (LICS 2016), the authors introduced two-variable first-order logic supplemented by a binary relation that allows one to say that a letter appears between two positions. We found an effective algebraic criterion that is a necessary condition for definability in this logic, and conjectured that the criterion is also sufficient, although we proved this only in the case of two-letter alphabets. Here we prove the general conjecture. The proof is quite different from the arguments in the earlier work, and required the development of novel techniques concerning factorizations of words. We extend the results to binary relations specifying that a factor appears between two positions.
Cite as

Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, and Howard Straubing. An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 28:1-28:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{krebs_et_al:LIPIcs.CSL.2018.28,
  author =	{Krebs, Andreas and Lodaya, Kamal and Pandya, Paritosh K. and Straubing, Howard},
  title =	{{An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.28},
  URN =		{urn:nbn:de:0030-drops-96953},
  doi =		{10.4230/LIPIcs.CSL.2018.28},
  annote =	{Keywords: two-variable logic, finite model theory, algebraic automata theory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.77
Making Metric Temporal Logic Rational

Authors: Shankara Narayanan Krishna, Khushraj Madnani, and Paritosh K. Pandya

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We study an extension of MTL in pointwise time with regular expression guarded modality Reg_I(re) where re is a rational expression over subformulae. We study the decidability and expressiveness of this extension (MTL+Ureg+Reg), called RegMTL, as well as its fragment SfrMTL where only star-free rational expressions are allowed. Using the technique of temporal projections, we show that RegMTL has decidable satisfiability by giving an equisatisfiable reduction to MTL. We also identify a subclass MITL+UReg of RegMTL for which our equisatisfiable reduction gives rise to formulae of MITL, yielding elementary decidability. As our second main result, we show a tight automaton-logic connection between SfrMTL and partially ordered (or very weak) 1-clock alternating timed automata.
Cite as

Shankara Narayanan Krishna, Khushraj Madnani, and Paritosh K. Pandya. Making Metric Temporal Logic Rational. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 77:1-77:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{krishna_et_al:LIPIcs.MFCS.2017.77,
  author =	{Krishna, Shankara Narayanan and Madnani, Khushraj and Pandya, Paritosh K.},
  title =	{{Making Metric Temporal Logic Rational}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{77:1--77:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.77},
  URN =		{urn:nbn:de:0030-drops-81112},
  doi =		{10.4230/LIPIcs.MFCS.2017.77},
  annote =	{Keywords: Metric Temporal Logic, Timed Automata, Regular Expression, Equisatisfiability, Expressiveness}
}
  • Refine by Author
  • 3 Krishna, Shankara Narayanan
  • 3 Pandya, Paritosh K.
  • 2 Madnani, Khushraj
  • 2 Majumdar, Rupak
  • 1 Abu Zaid, Faried
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Logic
  • 2 Theory of computation → Probabilistic computation
  • 1 Information systems → Data structures
  • 1 Mathematics of computing → Combinatorial algorithms
  • Show More...

  • Refine by Keyword
  • 2 Expressiveness
  • 2 Metric Temporal Logic
  • 1 ATA
  • 1 Alternating Timed Automata
  • 1 Capacitated Knapsack Median
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 12 2018
  • 1 2017
  • 1 2023

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact