28th – 29th November 2024
The Algorithms and Formal Methods research group (ALFOM) of the Computer Science and Engineering department at NIT Calicut is organizing a National Workshop on Advances in Graph Algorithms: Theory and Applications (AGATHA), with registration now open!
The workshop focuses on advanced topics in graph algorithms, including parameterized and randomized methods, approximation techniques, subgraph detection, graph decomposition, and their applications in fields like probabilistic reasoning, statistical physics, and system verification.
Professor, CSA, IISc Bangalore
Associate Professor, CSE, IIT Palakkad
Associate Professor, CSE, IIT Palakkad
Associate Professor, CSE, IIT Palakkad
Assistant Professor, CSE, IIT Palakkad
Day 1 - November 28, 2024
Keynote abstract: Ideals (also known as downsets or monotone decreasing families or abstract simplicial complexes) are fundamental objects which are central to the study of set systems and have been very well studied. Let the smallest antichain, which generates an ideal of size $n$ be $\alpha(n)$. While a $\log{n}$ upper bound is easy, no non-trivial improvement for this bound is known in spite of its importance in computer science. In this work, we give a constructive proof that,
a) for every $n\geq 3$, $\alpha(n)\leq 20\sqrt{\log{n}}\log\log{n}$,
b) there exists infinitely many $n\in \mathbb{N}$ for which $ \alpha(n)\geq \log_{2}(\lceil 0.5\log_{2}n \rceil))$.
Our results have surprising and immediate implications to the area of model counting. More specifically, our constructions improve the state-of-the-art techniques for weighted model counting, which have applications in probabilistic reasoning, network reliability estimation, statistical physics, program synthesis and system verification.
TBA
TBA
TBA
Day 2 - November 29, 2024
TBA
Separation Dimension of a graph G is the smallest natural number d for which the vertices of G can be embedded in R^d such that any two disjoint edges of G can be separated by an axis-normal hyperplane. It's easily seen to be a monotone parameter, starting at 0 for the empty graph and growing to Θ(lg n) for the complete graphs. In 2017 [1], we asked whether graphs with bounded separation dimension have at most O(n) edges, where n is the number of vertices.
In this talk, we will build some familiarity with this parameter and then see how a construction designed to study the Zarankiewicz's problem on a restricted class of hypergraphs in 2021 [2] led to answering the above question in the negative [3].
[1] Alon, N., Basavaraju, M., Chandran, L. S., Mathew, R., & Rajendraprasad, D. (2018). Separation dimension and sparsity. Journal of Graph Theory, 89(1), 14-25.
[2] Basit, A., Chernikov, A., Starchenko, S., Tao, T., & Tran, C. M. (2021, January). Zarankiewicz’s problem for semilinear hypergraphs. In Forum of Mathematics, Sigma (Vol. 9, p. e59). Cambridge University Press.
[3] Tomon, I., & Zakharov, D. (2021). Turán-type results for intersection graphs of boxes. Combinatorics, Probability and Computing, 30(6), 982-987.
In this talk, we will revisit some of the classical problems in graph theory of finding a specific type of subgraph (spanning tree, spanning out-tree single-source shortest path tree, perfect matching, k-path,...) of a given edge-colored graph with constraints on the number of edges of each color. Some of these problems have efficient solutions (color-constrained spanning tree [1,2]), some of them are long standing open questions (color-constrained perfect matching [2]) and some of them are NP-hard (color-constrained long path and large tree [3]). In this talk, we will present some of the results from our recent work on color-constrained shortest path trees [4]. En route, we will see nice connections to colored matroids and color-constrained independent sets.
[1] Christos H. Papadimitriou and Mihalis Yannakakis. The complexity of restricted spanning tree problems. Journal of the ACM, 29(2), 1982.
[2] Harold N. Gabow and Robert Endre Tarjan. Efficient Algorithms for a Family of Matroid Intersection Problems. J. Algorithms, 5(1), 1984.
[3] P. S. Ardra, R. Krithika, Saket Saurabh, Roohani Sharma: Balanced Substructures in Bicolored Graphs. SOFSEM 2023.
[4] P. S. Ardra, Jasine Babu, Kritika Kashyap, R. Krithika, Sreejith K. Pallathumadam, Deepak Rajendraprasad: Arborescences and Shortest Path Trees when Colors Matter. CoRR abs/2403.06580, 2024.
In this talk, we will revisit some of the classical problems in graph theory of finding a specific type of subgraph (spanning tree, spanning out-tree single-source shortest path tree, perfect matching, k-path,...) of a given edge-colored graph with constraints on the number of edges of each color. Some of these problems have efficient solutions (color-constrained spanning tree [1,2]), some of them are long standing open questions (color-constrained perfect matching [2]) and some of them are NP-hard (color-constrained long path and large tree [3]). In this talk, we will present some of the results from our recent work on color-constrained shortest path trees [4]. En route, we will see nice connections to colored matroids and color-constrained independent sets.
[1] Christos H. Papadimitriou and Mihalis Yannakakis. The complexity of restricted spanning tree problems. Journal of the ACM, 29(2), 1982.
[2] Harold N. Gabow and Robert Endre Tarjan. Efficient Algorithms for a Family of Matroid Intersection Problems. J. Algorithms, 5(1), 1984.
[3] P. S. Ardra, R. Krithika, Saket Saurabh, Roohani Sharma: Balanced Substructures in Bicolored Graphs. SOFSEM 2023.
[4] P. S. Ardra, Jasine Babu, Kritika Kashyap, R. Krithika, Sreejith K. Pallathumadam, Deepak Rajendraprasad: Arborescences and Shortest Path Trees when Colors Matter. CoRR abs/2403.06580, 2024.
TBA