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

# Kriesell’s Conjecture

Today’s short post is about Kriesell’s conjecture. In my first year of PhD I enjoyed reading several papers related to this cute conjecture.

Nash-Williams [N'61] and Tutte [Tutte'61] independently proved that a graph $G(V,E)$ has $k$ edge-disjoint spanning trees if and only if $E(P) \geq k(|P|-1)$ for every partition $P$ of $V$ into non-empty classes, where $E(P)$ denotes the number of edges connecting distinct classes of $P$. One interesting corollary of this result is the following :

Theorem : Every $2k$-edge-connected graph has $k$ edge-disjoint spanning trees.

Let $G(V,E)$ be an undirected multigraph and $S \subseteq V$. An $S-tree$ is a tree of $G$ that contains every vertex in $S$. An $S-cut$ is a subset of edges whose removal disconnects some vertices in $S$. A graph is $k-S-connected$ if every $S-cut$ has at least $k$ edges. Kriesell conjectured the following generalization of the above theorem.

Kriesell’s conjecture : If $G$ is $2k-S-connected$, then $G$ has $k$ edge-disjoint $S-trees$.

The first breakthrough towards proving Kriesell’s conjecture was by Lau. He proved that if G is $24k$-edge-connected in $T$ then it has $k$ edge-disjoint Steiner trees. Recently, West and Wu [pdf] proved that it suﬃces for $S$ to be $6.5k$-edge-connected in $G$.

Open Problems

1. Obvious open problem is to prove or disprove Kriesell’s conjecture.
2. There a several related open problems about S-connectors in West-Wu’s paper.

References :

• [Tutte'61] W.T.Tutte : On the problem of decomposing a graph into n connected factorsJ. London Math. Soc. 36 (1961), 221–230.
• [N'61] C.St.J.A.Nash-Williams : Edge disjoint spanning trees of ﬁnite graphs, J. London Math. Soc. 36 (1961), 445–450.
• [Lau'07] L. C. Lau : An approximate max-Steiner-tree-packing min-Steiner-cut theorem. Combinatorica 27 (2007), 71–90

# 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