Open problems for 2014

Wish you all a Very Happy New Year. Here is a list of my 10 favorite open problems for 2014. They belong to several research areas inside discrete mathematics and theoretical computer science. Some of them are baby steps towards resolving much bigger open problems. May this new year shed new light on these open problems.

  • 2. Optimization : Improve the approximation factor for the undirected graphic TSP. The best known bound is 7/5 by Sebo and Vygen.
  • 3. Algorithms : Prove that the tree-width of a planar graph can be computed in polynomial time (or) is NP-complete.
  • 4. Fixed-parameter tractability : Treewidth and Pathwidth are known to be fixed-parameter tractable. Are directed treewidth/DAG-width/Kelly-width (generalizations  of  treewidth) and directed pathwidth (a generalization of pathwidth) fixed-parameter tractable ? This is a very important problem to understand the algorithmic and structural differences between undirected and directed width parameters.
  • 5. Space complexity : Is Planar ST-connectvity in logspace ? This is perhaps the most natural special case of the NL vs L problem. Planar ST-connectivity is known to be in UL \cap coUL. Recently, Imai, Nakagawa, Pavan, Vinodchandran and Watanabe proved that it can be solved simultaneously in polynomial time and approximately O(√n) space.
  • 6. Metric embedding : Is the minor-free embedding conjecture true for partial 3-trees (graphs of treewidth 3) ? Minor-free conjecture states that “every minor-free graph can be embedded in l_1 with constant distortion. The special case of planar graphs also seems very difficult. I think the special case of partial 3-trees is a very interesting baby step.
  • 7. Structural graph theory : Characterize pfaffians of tree-width at most 3 (i.e., partial 3-trees). It is a long-standing open problem to give a nice characterization of pfaffians and design a polynomial time algorithm to decide if an input graph is a pfaffian. The special of partial 3-trees is an interesting baby step.
  • 8. Structural graph theory : Prove that every minimal brick has at least four vertices of degree three. Bricks and braces are defined to better understand pfaffians. The characterization of pfaffian braces is known (more generally characterization of bipartite pfaffians is known). To understand pfaffians, it is important to understand the structure of bricks. Norine,Thomas proved that every minimal brick has at least three vertices of degree three and conjectured that every minimal brick has at least cn vertices of degree three.
  • 9. Communication Complexity : Improve bounds for the log-rank conjecture. The best known bound is O(\sqrt{rank})
  • 10. Approximation algorithms : Improve the approximation factor for the uniform sparsest cut problem. The best known factor is O(\sqrt{logn}).

Here are my conjectures for 2014 :)

  • Weak Conjecture : at least one of the above 10 problems will be resolved in 2014.
  • Conjecture : at least five of the above 10 problems will be resolved in 2014.
  • Strong Conjecture : All of the above 10 problems will be resolved in 2014.

Have fun !!

TrueShelf 1.0

One year back (on 6/6/12) I announced a beta version of TrueShelf, a social-network for sharing exercises and puzzles especially in mathematics and computer science. After an year of testing and adding new features, now I can say that TrueShelf is out of beta.

TrueShelf turned out to be a very useful website. When students ask me for practice problems (or books) on a particular topic, I simply point them to trueshelf and tell them the tags related to that topic. When I am advising students on research projects, I first tell them to solve all related problems (in the first couple of weeks) to prepare them to read research papers.

Here are the features in TrueShelf 1.0.

  • Post an exercise (or) multiple-choice question (or) video (or) notes.
  • Solve any multiple-choice question directly on the website.
  • Add topic and tags to any post
  • Add source or level (high-school/undergraduate/graduate/research).
  • Show text-books related to a post
  • Show related posts for every post.
  • View printable version (or) LaTex version of any post.
  • Email / Tweet / share on facebook (or) Google+ any post directly from the post.
  • Add any post to your Favorites
  • Like (a.k.a upvote) any post.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebooktwitter and google+. Here is a screenshot highlighting the important features.

trueshelf

Book Review of “Elements of Automata Theory”

During summer 2010 I started reading a book titled Elements of Automata Theory by Jacques Sakarovitch. It took me one year to read the book and submit my review to Bill Gasarch during summer 2011. It will be appearing in SIGACT book review column soon. I am posting my review here for the benefit of everybody.


———————————————————————————————————————————

Book : Elements of Automata Theory by Jacques Sakarovitch
Reviewer : Shiva Kintali

Introduction

During my undergrad I often found myself captivated by the beauty and depth of automata theory. I wanted to read one book on automata theory and say that I “know” automata theory. Couple of years later I realized that it is silly to expect such a book. The depth and breadth of automata theory cannot be covered by a single book.

My PhD thesis is heavily inspired by automata theory. I had to read several (fifty year old) papers and books related to automata theory to understand several fundamental theorems. Unfortunately, the concepts I wanted to learn are scattered in multiple books and old research papers, most of which are hard to find. When I noticed that Prof. Bill Gasarch is looking for a review of Elements of Automata Theory, I was very excited and volunteered to review it, mainly because I wanted to increase my knowledge about automata theory. Given my background in parsing technologies and research interests in space-bounded computation I wanted to read this book carefully. This book is around 750 pages long and it took me around one year to (approximately) read it. It is very close to my expectations of the one book on automata theory.

First impressions : Most of the books on automata theory start with the properties of regular languages, finite automata, pushdown automata, context-free languages, pumping lemmas, Chomsky hierarchy, decidability and conclude with NP-completeness and the P vs NP problem. This book is about “elements” of automata theory. It focuses only on finite automata over different mathematical structures. It studies pushdown automata only in the context of rational subsets in the free group. Yes, there is 750 pages worth literature studying only finite automata.

This book is aimed at people enthusiastic to know the subject rigorously and not intended as a textbook for automata theory course. It can also be used by advanced researchers as a desk reference. There is no prerequisite to follow this book, except for a reasonable mathematical maturity. It can be used as a self-study text. This book is a direct translation of its french original.

 
Summary

This book is divided into five major chapters. The first three chapters deal with the notions of rationality and recognizability. A family of languages are rationally closed if it is closed under rational operations (union, product and star). A language is reconizable if there exists a finite automata that recognizes it. The fourth and fifth chapters discuss rationality in relations. Chapter 0 acts as an appendix of several definitions of structures such as relations, monoids, semirings, matrices, graphs and concepts such as decidability. Following is a short summary of the five major chapters. There are several deep theorems (for example, Higman’s Theorem) studied in this book. I cannot list all of them here. The chapter summaries in the book have more details.

Chapter 1 essentially deals with the basic definitions and theorems required for any study of automata theory. It starts with the definitions of states, transitions, (deterministic and nondeterministic) automaton, transpose, ambiguity and basic operations such as union, cartesian product, star, quotient of a language. Rational operators, rational languages and rational expressions are defined and the relation between rationality and recognizability is established leading to the proof of Kleene’s theorem. String matching (i.e., finding a word in a text) is studied in detail as an illustrative example. Several theorems related to star height of languages are proved. A fundamental theorem stating that `the language accepted by a two-way automaton is rational’ is proved. The distinction between Moore and Mealy machines is introduced.

Chapter 2 deals with automata over the elements of an arbitrary monoid and the distinction between rational set and recognizable set in this context. This leads to a better understanding of Kleene’s theorem. The notion of morphism of automata is introduced and several properties of morphisms and factorisations are presented. Conway’s construction of universally minimal automaton is explained and the importance of well quasi-orderings is explained in detail. Based on these established concepts, McNaughton’s theorem (which states that the star height of a rational group language is computable) is studied with a new perspective.

Chapter 3 formalizes the notion of “weighted” automata that count the number of computations that make an element be accepted by an automaton, thus generalizing the previously introduced concepts in a new dimension. Languages are generalized to formal series and actions are generalized to representations. The concepts and theorems in this chapter makes the reader appreciate the deep connections of automata theory with several branches of mathematics. I personally enjoyed reading this chapter more than any other chapter in this book.

Chapter 4 builds an understanding of the relations realized by different finite automata in the order they are presented in chapters 1, 2 and 3. The Evaluation Theorem and the Composition Theorem play a central role in understanding this study. The decidability of the equivalence of transducers (with and without weigths) is studied. This chapter concludes with the study of deterministic and synchronous relations.

Chapter 5 studies the functions realized by finite automata. Deciding functionality, sequential functions, uniformisation of rational relations by rational functions, semi-monomial matrix representation, translations of a function and uniformly bounded functions are studied.

There are exercises (with solutions) at the end of every section of every chapter. These exercises are very carefully designed and aid towards better understanding of the corresponding concepts. First time readers are highly encouraged to solve (or at least glance through) these exercises. Every section ends with Notes and References mentioning the corresponding references and a brief historical summary of the chapter.

 
Opinion

Overall I found the book very enlightening. It has provided me new perspectives on several theorems that I assumed I understood completely. Most of the concepts in this book are new to me and I had no problems following the concepts and the corresponding theorems. The related exercises made these topics even more fun to learn. It was a joy for me to read this book and I recommend this book for anyone who is interested in automata theory (or more generally complexity theory) and wants to know the fundamental theorems of theory of computing. If you are a complexity theorist, it is worthwhile to look back at the foundations of theory of computing to better appreciate its beauty and history. This book is definitely unique in its approach and the topics chosen. Most of the topics covered are either available in very old papers or not accesible at all. I applaud the author for compiling these topics into a wonderful free-flowing text.

This book is nicely balanced between discussions of concepts and formal proofs. The writing is clear and the topics are organized very well from the most specific to the most general, making it a free-flowing text. On the other hand, it is very dense and requires lots of motivation and patience to read and understand the theorems. The author chose a rigorous way of explaining rationality and recognizability. Sometimes you might end up spending couple of hours to read just two pages. Such is the depth of the topics covered. Beginners might find this book too much to handle. I encourage beginners to read this book after taking an introductory automata theory course. This is definitely a very good reference text for researchers in the field of automata theory.

In terms of being used in a course, I can say that a graduate level course can be designed from a carefully chosen subset of the topics covered in this book. The exercises in the book can be readily used for such a course.

This is an expensive book, which is understandable based on the author’s efforts to cover several fundamental topics (along with exercises) in such a depth. If you think it is expensive, I would definitely suggest that you get one for your library.

———————————————————————————————————————————

TrueShelf

I have been teaching (courses related to algorithms and complexity) for the past six years (five years as a PhD student at GeorgiaTech, and the past one year at Princeton). One of the most challenging and interesting part of teaching is creating new exercises to help teach the important concepts in an efficient way. We often need lots of problems to include in homeworks, midterms, final exams and also to create practice problem sets.

We do not get enough time to teach all the concepts in class because the number of hours/week is bounded. I personally like to teach only the main concepts in class and design good problem sets so that students can learn the generalizations or extensions of the concepts by solving problems hands-on. This helps them develop their own intuitions about the concepts.

Whenever I need a new exercise I hardly open a physical textbook. I usually search on internet and find exercises from a course website (or) “extract” an exercise from a research paper. There are hundreds of exercises “hidden” in pdf files across several course homepages. Instructors often spend lots of time designing them. If these exercises can reach all the instructors and students across the world in an efficiently-indexed form, that will help everybody. Instructors will be happy that the exercises they designed are not confined to just one course. Students will have an excellent supply of exercises to hone their problem-solving skills.

During 2008, half-way through my PhD, I started collected the exercises I like in a private blog. At the same time I registered the domain trueshelf.com to make these exercises public. In 2011, towards the end of my PhD, I started using the trueshelf.com domain and made a public blog so that anybody can post an exercise. [ Notice that I did not use the trueshelf.com domain for three years. During these three years I got several offers ranging upto $5000 to sell the domain. So I knew I got the right name :) ] Soon, I realized that wordpress is somewhat “static” in nature and does not have enough “social” features I wanted. A screenshot of the old website is shown below.

The new version of TrueShelf is a social website enabling “crowd-sourcing” of exercises in any area. Here is the new logo, I am excited about :)

The goal of TrueShelf is to aid both the instructors and students by presenting quality exercises with tag-based indexing. Read the TrueShelf FAQ for more details. Note that we DO NOT allow users to post solutions. Each user may add his own “private” solution and notes to any exercise. I am planning to add more features soon.

In the long-run, I see TrueShelf becoming a “Youtube for exercises”. Users will be able to create their own playlists of exercises (a.k.a problem sets) and will be recommended relevant exercises. Test-preparation agencies will be able to create their own channels to create sample tests.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebook, twitter and google+.

Let’s see how TrueShelf evolves.

Computing Bounded Path Decompositions in Logspace

Today’s post is a continuation of earlier posts (here, here, here, here) on graph isomorphism, treewidth and pathwidth. As mentioned earlier, the best known upper bound for Graph Isomorphism of partial k-trees is LogCFL.

Theorem ([Das, Toran and Wagner'10]) : Graph isomorphism of bounded treewidth graphs is in LogCFL.

One of the bottlenecks of the algorithm of [DTW'10] is computing bounded tree decompositions in logspace. This is recently resolved by an amazing result of Elberfeld, Jakoby and Tantau [EJT'10]. The results in this paper are very powerful. Unfortunately, it is still not clear how to improve the LogCFL upper bound.

Can we improve the upper bound for special cases of partial k-trees ? How about bounded pathwidth graphs ? Again, one bottleneck here is to compute bounded path decompositions in logspace. [EJT'10]‘s paper does not address this bottleneck and it is not clear how to extend their algorithm to compute path decompositions.

In joint work with Sinziana Munteanu, we resolved this bottleneck and proved the following theorem. Sinziana is a senior undergraduate student in our department. She is working with me on her senior thesis.

Theorem (Kintali, Munteanu’12) : For all constants k, l \geq 1, there exists a logspace algorithm that, when given a graph G of treewidth \leq l, decides whether the pathwidth of G is at most k, and if so, finds a path decomposition of G of width \leq k in logspace.

A draft of our results is available here. The above theorem is a logspace counterpart of the corresponding polynomial-time algorithm of [Bodlaender, Kloks'96]. Converting it into a logspace algorithm turned out to be a tedious task with some interesting tricks. Our work motivates the following open problem :

Open problem : What is the complexity of Graph Isomorphism of bounded pathwidth graphs ? Is there a logspace algorithm ?

Stay tuned for more papers related to graph isomorphism, treewidth and pathwidth. I am going through a phase of life, where I have more results than I can type. Is there an app that converts voice to latex ? Is there a journal that accepts hand-written proofs ? :)

Graph Isomorphism, Tree Width, Path Width and LogSpace

Every once in a while, I can’t help thinking about “the complexity of graph isomorphism for bounded treewidth graphs“. Today has been one of those days again. See my earlier post to get the context.

Theorem ([Das, Toran and Wagner'10]) : Graph isomorphism of bounded treewidth graphs is in LogCFL.

The proof of the above theorem is as follows

  1. Graph isomorphism of bounded tree-distance width graphs is in L.
  2. Given two graphs and their tree decompositions, computing the isomorphism respecting these tree decompositions is reducible to (1).
  3. Given tree decomposition of only one graph, we can guess the tree decomposition of the other and guess the isomorphism (respecting the tree bags) and verify them using a non-deterministic auxiliary pushdown automata (a.k.a LogCFL).
  4. Since tree decomposition of a graph can be computed in LogCFL, the above theorem follows.
One of the bottlenecks, finding a tree decomposition of bounded treewidth graphs in logspace, is resolved by [Elberfeld, Jakoby and Tantau'10]. The following seems to be another major bottleneck.
Given a graph G and a decomposition D, how fast can we verify that D is a valid tree decomposition of G ? The upper bound of LogDCFL (the deterministic version of LogCFL) is clear from the above mentioned results. Can this verification be done in logspace ?
The answer is frustratingly unknown. An even more frustrating realization I had today is that “it is not clear how to beat the LogDCFL upper bound for the more restricted path decomposition“. Even though the underlying tree in a path decomposition is just a path, verifying the connectivity conditions of a path decomposition does seem to require recursion. It is not clear how to avoid recursion.
I thought that logspace upper bound is possible. Now I am much less confident about logspace upper bound. I cannot waste more time on this.
The truth is “this is a cute problem“. I need to do something to take my mind off this problem and move on. Easy enough, except I need an idea.
Update (Oct 12 2011) : Noticed that verification of path decompositions is easy.

Graph Isomorphism and Bounded Tree Width

If you read my earlier post, you known that I am fan of treewidth. Who isn’t !! The complexity of Graph Isomorphism (earlier post) is one of the long-standing open problem. Intersecting these two with one of my research interests (space-bounded computation) we get the following open problem :

Open Problem : What is the complexity of graph isomorphism for graphs with bounded treewidth ?

Graphs with treewidth at most k are also called partial k-trees. In 1992 Lindell proved that trees (graphs with treewidth=1) can be canonized in logspace [Lindel'92]. What about canonization for k=2 ? Recently Datta et. al [DLNTW'09] proved that the canonization of planar graph is logspace-complete. The following simple exercise shows that partial 2-trees are planar graphs. Hence the result of [DLNTW'09] implies that partial 2-trees can be canonized in logspace.

Exercise : Every partial 2-tree is planar.

In fact, canonization of partial 2-trees is settled earlier by [ADK'08]. What about k=3 ? Partial 3-trees may not be planar. An example is K_{3,3} itself. The tree width of K_{3,3} is three. I wanted to work on the case of k=3 and realized the following simple fact.

Exercise : Partial 3-trees are K_{5}-free.

In a follow-up paper to [DLNTW'09], Datta et al [DNTW'10] proved that canonization of K_{3,3}-free and K_{5}-free graphs is in Log-space. Hence we get the following corollary :

Corollary : Partial 3-trees can be canonized in log-space.

Since the above result is not explicitly mentioned in any papers, I wanted to make it clear in this post. Hence the open problem is for k \geq 4. LogCFL is the best known upper bound for graph isomorphism of partial k-trees [DTW'10]. One of the bottleneck, finding a tree decomposition of partial k-tree in logspace, is resolved recently [EJT'10]. The above mentioned papers make use of a decomposition of the input graph into two- or three-connected subgraphs, constructing an appropriate tree of these subgraphs, using the known structural properties of two- and three-connected graphs to canonize these subgraphs and using Lindell’s result to canonize the entire graph. Unfortunately no clean characterization exists for graphs with connectivity at least four. Many long-standing open problems in graph theory are trivial for 2- and 3- connected graphs and open for higher connectivity. A clean characterization of 4-connected graphs seems to be a major bottleneck in improving the space complexity of canonization of partial 4-trees. I am lost :(

Open Problems

  • Is graph isomorphism of partial k-trees (for k \geq 4) in logspace ?
  • Is canonization of partial k-trees in LogCFL ? The paper of [DTW'10] solves isomorphism only.

References :

  • [Lindell'92] Steven Lindell: A Logspace Algorithm for Tree Canonization STOC 1992: pages 400-404
  • [DLNTW'09] Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Planar Graph Isomorphism is in Log-Space. IEEE Conference on Computational Complexity 2009: 203-214
  • [DNTW'10] Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Graph Isomorphism for K{3, 3}-free and K5-free graphs is in Log-space. Electronic Colloquium on Computational Complexity (ECCC) 17: 50 (2010)
  • [ADK'08] Vikraman Arvind, Bireswar Das, Johannes Köbler: A Logspace Algorithm for Partial 2-Tree Canonization. CSR 2008: 40-51
  • [DTW'10] Bireswar Das, Jacobo Torán, Fabian Wagner: Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. STACS 2010: 227-238
  • [EJT'10] Michael Elberfeld, Andreas Jakoby, Till Tantau: Logspace Versions of the Theorems of Bodlaender and Courcelle. FOCS 2010: 143-152

Type Sensitive Depth and Karchmer Wigderson Games

Throughout this post, we will be considering circuits over the basis \{\vee,\wedge,\neg\} where \{\vee,\wedge\}-gates have fanin 2 and \neg-gates are only applied to input variables. Let f : \{0,1\}^n \rightarrow \{0,1\} be a boolean function on n variables and G_n be a circuit computing f. For an output gate g, let g_l and g_r be the sub-circuits, whose outputs are inputs to g. Let d(G_n) be the depth of circuit G_n and d(f) be the minimum depth of a circuit computing f.

Karchmer and Wigderson [KW'90] showed an equivalence between circuit depth and a related problem in communication complexity. It is a simple observation that we can designate the two players as an “and-player” and an “or-player”. Let S_0, S_1 \subseteq \{0,1\}^n such that S_0 \cap S_1 = \emptyset. Consider the communication game between two players (P_{\wedge} and P_{\vee}), where P_{\wedge} gets x \in S_1 and P_{\vee} gets y \in S_0. The goal of the players to find a coordinate i such that x_i \neq y_i. Let C(S_1,S_0) represent the minimum number of bits they have to communicate in order for both to agree on such coordinate.

Karchmer-Wigderson Theorem : For every function f : \{0,1\}^n \rightarrow \{0,1\} we have d(f) = C(f^{-1}(1),f^{-1}(0)).

Karchmer and Wigderson used the above theorem to prove that ‘monotone circuits for connectivity require super-logarithmic depth’. Let C_{\wedge}(S_1,S_0) (resp. C_{\vee}(S_1,S_0)) represent the minimum number of bits that P_{\wedge} (resp P_{\vee}) has to communicate. We can define type-sensitive depths of a circuit as follows. Let d_{\wedge}(G_n) (resp. d_{\vee}(G_n)) represent the AND-depth (resp. OR-depth) of G_n.

AND-depth : AND-depth of an input gate is defined to be zero. AND-depth of an AND gate g is max(d_{\wedge}(g_l), d_{\wedge}(g_r)) + 1. AND-depth of an OR gate g is max(d_{\wedge}(g_l), d_{\wedge}(g_l)). AND-depth of a circuit G_n is the AND-depth of its output gate.

OR-depth is defined analogously. Let d_{\wedge}(f) (resp. d_{\vee}(f)) be the minimum AND-depth (resp. OR-depth) of a circuit computing f.

Observation : For every function f : \{0,1\}^n \rightarrow \{0,1\} we have that C_{\wedge}(f^{-1}(1),f^{-1}(0)) corresponds to the AND-depth and C_{\vee}(f^{-1}(1),f^{-1}(0)) corresponds to the OR-depth of the circuit constructed by Karchmer-Wigderson.

 

Open Problems :

  • Can we prove explicit non-trivial lower bounds of d_{\wedge}(f) (or d_{\vee}(f)) of a given function f ? This sort of “asymmetric” communication complexity is partially addressed in [MNSW'98].
  • A suitable notion of uniformity in communication games is to be defined to address such lower bounds. More on this in future posts.

 

References :

  • [KW'90] Mauricio Karchmer and Avi Wigderson : Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255–265, 1990.
  • [MNSW'98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998)

 

Balanced ST-Connectivity

Today’s post is about a new open problem arising from my recent paper  (available on ECCC). The problem is as follows :

Let G(V,E) be a directed graph. Let G'(V,E') be the underlying undirected graph of G. Let P be a path in G'. Let e = (u,v) be an edge along the path P. Edge e is called neutral edge if both (u,v) and (v,u) are in E. Edge e is called forward edge if (u,v) \in E and (v,u) \notin E. Edge e is called backward edge if (u,v) \notin E and (v,u) \in E.

A path (say P) from s \in V to t \in V in G'(V,E') is called balanced if the number of forward edges along P is equal to the number of backward edges along P. A balanced path might have any number of neutral edges. By definition, if there is a balanced path from s to t then there is a balanced path from t to s. The path P may not be a simple path. We are concerned with balanced paths of length at most n.

Balanced ST-Connectivity : Given a directed graph G(V,E) and two distinguished nodes s and t, decide if there is balanced path (of length at most n) between s and t.

In my paper, I proved that SGSLOGCFL, a generalization of Balanced ST-Connectivity, is contained in DSPACE(lognloglogn). Details about SGSLOGCFL are in my paper.

Theorem 1 : SGSLOGCFL is in DSPACE(lognloglogn).

Open Problem : Is SGSLOGCFL \in L ?

Cash Prize : I will offer $100 for a proof of SGSLOGCFL \in L. I have spent enough sleepless nights trying to prove it. In fact, an alternate proof of Theorem 1 (or even any upper bound better than O({\log}^2n)) using zig-zag graph product seems to be a challenging task.

Usually people offer cash prizes for a mathematical problem when they are convinced that :

  • it is a hard problem.
  • it is an important problem worth advertising.
  • the solution would be beautiful, requires new techniques and sheds new light on our understanding of related problems.

My reason is “All the above”. Have Fun solving it !!

A cute puzzle : In Balanced ST-Connectivity we are only looking for paths of length at most n. There are directed graphs where the only balanced st-path is super-linear. The example in the following figure shows an instance of Balanced ST-Connectivity where the only balanced path between s and t is of length \Theta(n^2). The directed simple path from s to t is of length n/2. There is a cycle of length n/2 at the vertex v. All the edges (except (v,u)) on this cycle are undirected. The balanced path from s to t is obtained by traversing from s to v, traversing the cycle clockwise for n/2 times and then traversing from v to t.

Puzzle : Are there directed graphs where every balanced st-path is of super-polynomial size ?

Update : The above puzzle is now solved.

Open Problems

  • Is SGSLOGCFL \in L ?
  • Are there directed graphs where every balanced st-path is of super-polynomial size ? (solved)
  • More open problems are mentioned in my paper.

Hardness of Graph Isomorphism

The complexity of Graph Isomorphism (GI) is one of the major open problems. It is easy to see that GI \in NP. It is known that GI \in NP \cap coAM. The following theorem states that it is unlikely that GI is NP-complete.

Theorem [Schöning'87, BHZ'87] : If GI is NP-complete then the polynomial hierarchy collapses to its second level.

The counting version of GI is known to be reducible to its decisional version. A polynomial time algorithm solving GI would be a major breakthrough. The best known algorithm runs in 2^{O(\sqrt{n{\log}n})} for graphs with n vertices. Several special cases are shown to be in P. Several problems are known to be GI-hard. See this wikipedia article for details. GI is widely believed to be an NP-intermediate problem.

Conjecture : If P \neq NP, then GI is neither NP-complete nor in P.

Note that if the above conjecture is true then GI is P-hard. Is GI known to be P-hard ? What is the best known hardness of GI ? Well… we know very little about the hardness of GI. The following exercises show that GI is L-hard.

Exercise : Consider the following restricted automorphism problem: Given a graph G = (V,E) and two lists of nodes (x_1, \dots, x_k),(y_1,\dots, y_k), is there an automorphism in G mapping x_i to y_i for 1 ≤ i ≤ k ? Show that this problem is reducible to GI.

Exercise : Show that Undirected ST-connectivity is reducible to the above mentioned automorphism problem.

Torán [Torán'00] proved the following hardness theorem. Informally speaking, GI is hard for all complexity classes defined in terms of the number of accepting computations of a nondeterministic logarithmic space machine. These are the best known hardness results for GI.

Theorem [Torán'00] : GI is hard for NL, PL, Mod_k{L} and DET.

All these hardness results are under DLOGTIME uniform AC^0 many-one reductions. DET is the class of problems NC^1 Turing reducible to the determinant [Cook'85]. It is known that Mod_k{L} \subseteq DET and NL \subseteq C_{=}L \subseteq PL \subseteq DET. Hence the best known hardness of GI is DET-hardness. However, we do not know the exact complexity of DET i.e., we don’t know where DET lies in terms of the known complexity classes between NL and NC^2. In particular, what is the relation between LogCFL = SAC^1 and DET ?

Torán also showed a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. More details about the complexity of perfect matching in a future blog post.

Open Problems:

  • Is GI LogCFL-hard ?
  • Is DET LogCFL-hard ? What is the relation between LogCFL and DET ? This is an independent long-standing open problem. It deserves a separate blog post.
  • Is GI \in coNP ? A proof of this would imply that “if GI is NP-complete then NP = coNP“, improving the above mentioned theorem.
  • Is GI in P for strongly regular graphs ? The best known algorithm for strongly regular graphs, given by Spielman [Spielman'96], runs in time n^{O({n^{1/3}}{{\log}n})}.

References :

  • [BHZ'87] R. Boppana, J. Håstad, and S. Zachos , “Does co-NP have short interactive proofs?”, Information Processing Letters 25(2), pages 127-132, (1987).
  • [Schöning'87] Uwe Schöning, Graph isomorphism is in the low hierarchy, Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312–323
  • [Cook'85] Stephen A. Cook, A Taxonomy of Problems with Fast Parallel Algorithms Information and Control 64(1-3): 2-21 (1985)
  • [Spielman'96] Daniel A. Spielman, Faster isomorphism testing of strongly regular graphsSTOC ’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM, pp. 576–584
  • [Torán'00] Jacobo Torán, On the Hardness of Graph Isomorphism. FOCS’2000, also: SIAM J. Comput. 33(5): 1093-1108 (2004)