# Forbidden Directed Minors and Kelly-width

Today’s post is about the following paper, a joint work with Qiuyi Zhang, one of my advisees. Qiuyi Zhang is an undergraduate (rising senior) in our mathematics department.

• Shiva Kintali, Qiuyi Zhang. Forbidden Directed Minors and Kelly-width. (Preprint available on my publications page)

It is well-known that an undirected graph is a partial 1-tree (i.e., a forest) if and only if it has no $K_3$ minor. We generalized this characterization to partial 1-DAGs. We proved that partial 1-DAGs are characterized by three forbidden directed minors, $K_3, N_4$ and $M_5$, shown in the following figure. We named the last two graphs as $N_4$ and $M_5$ because their bidirected edges resemble the letters N and M.

Partial k-trees characterize bounded treewidth graphs. Similarly, partial k-DAGs characterize bounded Kelly-width digraphs. Kelly-width is the best known generalization of treewidth to digraphs.

As mentioned in the paper, I have a series of upcoming papers (called Directed Minors) making progress towards a directed graph minor theorem (i.e., all digraphs are well-quasi-ordered by the directed minor relation). For more details of the directed minor relation, read the current paper. I will post about the upcoming results as and when the preprints are ready.

# 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
• 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.
• 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.

# Graceful Diameter-6 Trees

Graceful Tree Conjecture is one of my favorite open problems (See this earlier post). Trees with diameter 4 and 5 are known to be graceful a decade ago.

One of my advisees, Matt Superdock, made progress towards proving that all diameter 6 trees are graceful. Matt is an undergraduate senior in our Mathematics Department. He proved that an interesting class of diameter 6 trees are graceful. His thesis is available here.

I hope his work motivates more researchers to make progress towards resolving Graceful Tree Conjecture, particularly for diameter 6 trees. Matt’s work really tests the limit of current techniques. Perhaps we need new techniques/insights to prove that all diameter 6 trees are graceful.

# Happy Birthday Paul Erdos

Today (March 26 2013) is the 100th Birthday of Paul Erdos. The title of my Blog is inspired by one of his famous sayings “My Brain is Open”. In one of my earlier posts I mentioned a book titled “The Man Who Loved Only Numbers” about his biography.

Paul Erdos published more than 1500 papers. Most of them left a legacy of open problems and conjectures. What is your favorite open problem from Erdos’s papers ? Leave a comment. Hope we can solve some of his open problems during this special year.

Here are some interesting links :

Here is a painting of Paul Erdos, I made couple years back.

# Open Problems from Lovasz and Plummer’s Matching Theory Book

I always have exactly one bed-time mathematical book to read (for an hour) before going to sleep. It helps me learn new concepts and hopefully stumble upon interesting open problems. Matching Theory by Laszlo Lovasz and Michael D. Plummer has been my bed-time book for the last six months. I bought this book 3 years back (during my PhD days) but never got a chance to read it. This book often disappears from Amazon’s stock. I guess they are printing it on-demand.

If you are interested in learning the algorithmic and combinatorial foundations of Matching Theory (with a historic perspective), then this book is a must read. Today’s post is about the open problems mentioned in Matching Theory book. If you know the status (or progress) of these problems, please leave a comment.

—————————————————————————-

1 . Consistent Labeling and Maximum Flow

Conjecture (Fulkerson) : Any consistent labelling procedure results in a maximum flow in polynomial number of steps.

—————————————————————————-

2. Toughness and Hamiltonicity

The toughness of a graph $G$, $t(G)$ is defined to be $+\infty$, if $G = K_n$ and to be $min(|S|/c(G-S))$, if $G \neq K_n$. Here $c(G-S)$ is the number of components of $G-S$.

Conjecture (Chvatal 1973) : There exists a positive real number $t_0$ such that for every graph $G$, $t(G) \geq t_0$ implies $G$ is Hamiltonian.

—————————————————————————-

3. Perfect Matchings and Bipartite Graphs

Theorem : Let $X$ be a set, $X_1, \dots, X_t \subseteq X$ and suppose that $|X_i| \leq r$ for $i = 1, \dots, t$. Let $G$ be a bipartite graph such that

a) $X \subseteq V(G)$,

b) $G - X_i$ has a perfect matching , and

c) if any edge of $G$ is deleted, property (b) fails to hold in the resulting graph.

Then, the number of vertices in $G$ with degree $\geq 3$ is at most $r^3 {t \choose 3}$.

Conjecture : The conclusion of the above theorem holds for non-bipartite graphs as well.

—————————————————————————-

4. Number of Perfect Matchings

Conjecture (Schrijver and W.G.Valiant 1980) : Let $\Phi(n,k)$ denote the minimum number of perfect matchings a k-regular bipartite graph on 2n points can have. Then, $\lim_{n \to \infty} (\Phi(n,k))^{\frac{1}{n}} = \frac{(k-1)^{k-1}}{k^{k-2}}$.

—————————————————————————-

5. Elementary Graphs

Conjecture : For $k \geq 3$ there exist constants $c_1(k) > 1$ and $c_2(k) > 0$ such that every k-regular elementary graph on 2n vertices, without forbidden edges , contains at least $c_2(k){\cdot}c_1(k)^n$ perfect matchings. Furthermore $c_1(k) \to \infty$ as $k \to \infty$.

—————————————————————————-

6. Number of colorations

Conjecture (Schrijver’83) : Let G be a k-regular bipartite graph on 2n vertices. Then the number of colorings of the edges of G with k given colors is at least $(\frac{(k!)^2}{k^k})^n$.

—————————————————————————-

Theorem : A graph is perfect if and only if it does not contain, as an induced subgraph, an odd hole or an odd antihole.

—————————————————————————-

# 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 ?

# Complexity of Tessel

One of my hobbies (I developed during my PhD) is designing boardgames. I designed three boardgames so far, one of which is Tessel, a word-building game based on graph theory. I am glad that Tessel is getting good feedback especially from schools and families. One of the most time-consuming part of Tessel’s design is deciding what values to assign to the letters and deciding which pairs of letters to use in the tiles. The pairs of letters are carefully chosen based on computer simulations of frequency of letters in english words and their “relative” importance. The pairs are chosen so as to give fair share to both vocabulary skills and optimization skills.

Today’s post is about a nice theoretical problem arising from this game.

Before you read further, please read the rules of Tessel. Henceforth I will assume that you understood the rules and goal of this game.

I guess you observed that the tiles are being placed on the edges of a planar graph. Tessel uses a special planar graph that has cycles of length 3,4,5 and 6. In general, this game can be played on any planar graph. I am planning to design another board using Cairo tessellation. Anyways, here is a theoretical problem :

Let S be a set of finite alphabets. You are given two different words (using alphabets from S) of length l1 and l2. Construct a planar graph G and label each edge with two alphabets, such that there are two walks in G that correspond to the given two words. (Read the rules of tessel  and look at these examples to understand this correspondence). Your goal is to construct G with minimum number of vertices (or minimum number of edges).

In general you can ask the above question given k different words. What is the complexity of this problem ? I don’t know. I haven’t given it a deep thought. These days whatever I do for fun (to take my mind off open problems), ends up in another open problem

# 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.