algorithms

by

Recreational Math Books – Part I

Most of us encounter math puzzles during high-school. If you are really obsessed with puzzles, actively searching and solving them, you will very soon run out of puzzles !! One day you will simply realize that you are not encountering any new puzzles. No more new puzzles. Poof. They are all gone. You feel like screaming “Give me a new puzzle“. This happened to me around the end of my undergrad days. During this phase of searching for puzzles, I encountered Graceful Tree Conjecture and realized that there are lots of long-standing open “puzzles”. I don’t scream anymore. Well… sometimes I do scream when my proofs collapse. But that’s a different kind of screaming.

Sometimes, I do try to create new puzzles. Most of the puzzles I create are either very trivial to solve (or) very hard and related to long-standing conjectures. Often it takes lots of effort and ingenuity to create a puzzle with right level of difficulty.

In today’s post, I want to point you to some of the basic puzzle books that everybody should read. So, the next time you see a kid screaming “Give me a new puzzle“, simply point him/her to these books. Hopefully they will stop screaming for sometime. If they comeback to you soon, point them to Graceful Tree Conjecture  🙂

1) Mathematical Puzzles: A Connoisseur’s Collection by Peter Winkler

2) Mathematical Mind-Benders by Peter Winkler

3) The Art of Mathematics: Coffee Time in Memphis by Bela Bollobás

4) Combinatorial Problems and Exercises by Laszlo Lovasz

5) Algorithmic Puzzles by Anany Levitin and Maria Levitin

I will mention more recreational math books in part 2 of this blog post.

by

How to teach Algorithms ?

Algorithms

Algorithms are everywhere. They help us travel efficiently, retrieve information from huge data sets, secure money transactions, recommend movies, books, videos, predict stock market etc. It is very tough to think about a daily task that does not benefit from efficient algorithms. Often the algorithms behind most of these tasks are very simple, yet their impact is tremendous. When I say “simple”, they are simple to people who know them. Most common people consider algorithms too mathematical. They assume that it is beyond their capability to understand algorithms. What they do not realize is that algorithms are often simple extensions of our daily rational thinking process.

For example, almost everybody considers it stupid to buy an item for $24 and pay $6 shipping, if there is free shipping for orders of more than $25. If you add one more item of cost $1, you saved $5. Also, when we pack our bags for travel, most of us try to do it as “efficiently” as possible, trying to carry as many “valuable” things as possible while trying to avoid paying for extra luggage on airlines. We consider these rational choices. Algorithms are simply “step-by-step procedures to achieve these rational objectives“.

If you are an instructor (like me), teaching Algorithms, you might have noticed that most students (around 70%) are intimidated when they take a basic algorithms course. Most of them DO end up doing well in the course, but they consider the process painful. If they reflect on the course, most often they say “that course was a nightmare, I don’t remember what I learnt in that course”. They do not seem to have enjoyed the course. Probably they might remember 30% of the material. This is definitely not acceptable for such a fundamental course.

Often, when I comeback to my office after teaching, I say to myself  “I should have given them one more example, to help them get better intuition”. You can always do better job if you are given more time. Alas, we have time-bounded classes and almost infinite details to cover. We expect students to learn some concepts on their own and develop their own intuitions. We want to give “good” reading material. So, their understanding depends on how well these readings are written.

Today’s post is about “How to teach Algorithms ?” Here is one of my experiences, while I was teaching an undergrad algorithms course at GeorgiaTech. I was teaching dynamic programming. I gave several examples to make sure that they understand the paradigm. At the end of the class, almost 50% of class had questions, because this is the first time they saw dynamic programming. I told them to see me in my office hours. I quickly implemented a java applet to show how the matrix entries are filled by the algorithm, step by step. When I showed them this applet and a pseudo-code side-by-side (highlighting every current line of code being executed), almost all of the students understood the main idea behind dynamic programming. Some of them also said “it is easy”. I was glad and wanted to add more algorithms in my code.

The Kintali Language

The goal is to have a very simple to understand “executable pseudo-code” along with an animation framework that “understands” this language. So I started designing a new language and called it Kintali language, for lack of a better word 🙂 . I borrowed syntax from several pseudo-codes. It took me almost two years to implement all the necessary features keeping in mind a broad range of algorithms. I developed an interpreter to translate this language into an intermediate representation with callbacks to an animation library. This summer, I finally implemented the animation library and the front-end in Objective-C. The result is the Algorithms App for iPad, released on Sep 20, 2012. This is my attempt to teach as many algorithms as possible by intuitive visualization and friendly exercises.

Features

Current version has Sorting algorithms (Insertion Sort, Bubble Sort, Quick Sort and MergeSort). The main advantage of my framework will be demonstrated once I add graph algorithms. I will add some “adaptive” exercises and games too. For example, one of the games is to predict what is the next matrix entry that will be filled next by an algorithm.

Also, I have the necessary framework to visually demonstrate recursion (by showing the recursion tree), dynamic programming (by showing the status (filled or waiting to be filled) of matrix entries), divide and conquer (by splitting the data) etc. Since the framework is ready, adding new algorithms will not take much time.

Here is a screenshot of Quick Sort in action.

quicksort

Platforms

After I developed the interpreter, I was wondering what platforms to support first. I went ahead with iPad because I developed the interpreter in C. Objective-C is a superset of C. The Mac desktop version should be available in couple of weeks. In the long run I will implement the Android, Linux and Windows 8 versions too.

Goal

The big goal here is to “almost” replace an algorithms textbook. I added a button to access relevant wikipedia articles (within the app) describing the corresponding algorithms. With simple pseudo-code, intuitive animations, adaptive exercises and easy access to online articles, I think this goal is definitely achievable.

Questions

I have some quick questions to all the instructors and students of Algorithms.

  • What algorithms do you want to see soon i.e., what algorithms did you have most difficulty learning/teaching ?
  • What are some current methods you use to overcome the limitations of “static” textbooks ?
  • Any more ideas to make algorithms more fun and cool to learn/teach ?

I wanted to write this post after achieving at least 100 downloads. I assumed this will take a month. To my surprise, there were 100 downloads from 15 countries, in the first 40 hours. I guess I have to add new features faster than I planned.

TrueShelf and Algorithms App are new additions to my hobbies. The others being Painting, BoardGames and Biking. Man’s got to have some hobbies. 🙂

Follow Algorithms App on Facebook, Twitter and Google+.

Download Algorithms App for iPad

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

by

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.

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

7. The Strong Perfect Graph Conjecture (resolved)

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

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

by

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.

by

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

by

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 😦

by

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

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
by

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 graphs, STOC ’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)
by

Approximating TreeWidth

Today’s post is about TreeWidth. When I first came across treewidth, I became an instant fan.

Definition : A tree-decomposition of a graph G(V,E) is a pair (\{X_i | i \in I \}, T=(I,F)) where \{X_i | i \in I \} is a family of subsets of V, one for each node of T, and T is a tree such that :

  • The union of the sets X_i is equal to V.
  • for all edges (v,w) \in E, there exists an i \in I with v \in X_i and w \in X_i.
  • for all i,j,k \in I : if j is on the path from i to k in T, then X_i \cap X_k \subseteq X_j.

The treewidth of a tree-decomposition is max_{i \in I}|X_i| - 1. The treewidth of a graph G is the minimum treewidth over all possible tree-decompositions of G.

Following are some interesting facts :

  • Exercise : TreeWidth of a tree is 1.
  • Exercise : TreeWidth of a clique on n vertices in n-1.
  • Determining whether treewidth of a given graph is at most k is NP-complete.
  • See [BGHK’95] for interesting applications of treewidth Eg : Choleski factorization on sparse symmetric matrices.
  • There is an analogous notion of pathwidth which is also NP-complete.

Approximating tree-width : Bodlaender et. al [BGHK’95] presented an O({\log}n) factor approximation algorithm for treewidth. This also gives an O({{\log}^2}n) factor approximation algorithm for pathwidth. Their algorithm works by repeatedly finding vertex separators and uses Leighton-Rao’s algorithm at its heart. The main insights from their paper are as follows :

  • If there is a factor \alpha approximation algorithm for vertex separator then there is an O(\alpha) approximation algorithm for treewidth.
  • if there is a factor \beta approximation algorithm for treewidth then there is an O(\beta{\log}n) approximation algorithm for pathwidth.

In 1995 the best known approximation factor for vertex separator was O({\log}n). Feige, Hajiaghayi and Lee [FHL’2008] improved this to O(\sqrt{{\log}n}). Hence we have O(\sqrt{{\log}n}) and O(\sqrt{{\log}n}{\cdot}{\log}n) factor approximation factors for treewidth and pathwidth respectively.

 

Special cases : What about computing treewidth of restricted classes of graphs ?

  • When k is any fixed constant, the graphs with treewidth k can be recognized, and a width k tree decomposition can be constructed for them, in linear time [Bodlaender’96].
  • Seymour and Thomas [ST’] showed that branchwidth of planar graphs can be computed in polynomial time. This implies a factor 3/2 approximation for treewdith of planar graphs.

Bounded TreeWidth : If the treewidth of a graph G is bounded by some fixed constant k, then several problems (that are NP-hard (even PSPACE-hard) for general graphs) can be solved in polynomial-time and often linear time !! Some of them include Maximum Independent set (hence maximum Clique), Hamiltonian cycle, Graph Isomorphism. Instead of listing all these problems, lets look at the following awesome theorem.

Courcelle’s Theorem : Any property of graphs definable in monadic second-order logic (MSO2) can be decided in linear time on any class of graphs of bounded tree-width. In other words, MSO2 is fixed-parameter tractable on any such class of graphs.

More information about Courcelle’s theorem can be found in this book. A recent paper (appeared today on arXiv) proved the following lower bound.
Theorem [KT’2010] : If C is any class of graphs which is closed under taking sub-graphs and whose tree-width is not bounded by a poly-logarithmic function then MSO2-model checking is intractable on C (under suitable assumptions from complexity theory)
There are several open problems related to treewidth, pathwidth, branchwidth and the related cops-robber games. Following are some that interest me :

Open Problems :

  • Perhaps the most interesting open question is to obtain a constant factor approximation for treewidth.
  • Bodlaender et. al ruled out absolute approximation algorithm, (unless P = NP) for treewidth and pathwidth. This is the best known hardness. Can we even rule out PTAS for treewidth ? Note that the hardness of treewidth implies the hardness of vertex separator (with constant factor blow-up).
  • How hard is computing treewidth of planar graphs ? NP-hardness is not known. Many researchers I talked to, believe that treewidth of planar graphs can be computed in polynomial-time.
  • Can the lower bound from [KT’2010] be improved ? In this context, it is interesting to note that Maximum Independent Set can be solved in polynomial time even when the treewidth is bounded by O({\log}n).
  • Datta et. al [DLNTW’2009] showed that planar graph isomorphism is in logspace. Is isomorphism for graphs with bounded treewidth in logspace ? I asked this question to some researchers, and this seems to be an open problem.

References :

    • [BGHK’95] Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree. J. Algorithms 18(2): 238-255 (1995)
    • [Bodlaender’96] Bodlaender, Hans L. : A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25 (6): 1305–1317 (1996)
    • [KT’2010] Stephan Kreutzer, Siamak Tazari Lower Bounds for the Complexity of Monadic Second-Order Logic arXiv:1001.5019

 

 

 

 

 

    • [FHL’2008] Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee: Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38(2): 629-657 (2008)
    • [ST’90] PaulD.Seymour and Robin Thomas : Call Routing and the Ratcacher. Combinatorica 14(2): 217-241 (1994)
    • [DLNTW’2009] 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