Directed Minors III. Directed Linked Decompositions

This is a short post about the following paper in my directed minor series :

  • Shiva Kintali. “Directed Minors III. Directed Linked Decompositions“. Preprint available on my publications page.

Thomas [Tho'90] proved that every undirected graph admits a linked tree decomposition of width equal to its treewidth. This theorem is a key technical tool for proving that every set of bounded treewidth graphs is well-quasi-ordered. An analogous theorem for branch-width was proved by Geelen, Gerards and Whittle [GGW'02]. They used this result to prove that all matroids representable over a fixed finite field and with bounded branch-width are well-quasi-ordered under minors. Kim and Seymour [KS'12] proved that every semi-complete digraph admits a linked directed path decomposition of width equal to its directed pathwidth. They used this result to show that all semi-complete digraphs are well-quasi-ordered under “strong” minors.

In this paper, we generalize Thomas’s theorem to all digraphs.

Theorem : Every digraph G admits a linked directed path decomposition and a linked DAG decomposition of width equal to its directed pathwidth and DAG-width respectively.

The above theorem is crucial to prove well-quasi-ordering of some interesting classes of digraphs. I will release Directed Minors IV soon. Stay tuned !!

Directed Width Parameters and Circumference of Digraphs

This is a short post about the following paper :

  • Shiva Kintali. “Directed Width Parameters and Circumference of Digraphs“. Preprint available on my publications page.

We prove that the directed treewidth, DAG-width and Kelly-width of a digraph are bounded above by its circumference plus one. This generalizes a theorem of Birmele stating that the treewidth of an undirected graph is at most its circumference. 

Theorem : Let G be a digraph of circumference l. Then the directed treewidth, DAG-width and Kelly-width of G are at most l + 1.

The above theorem can be seen as a mini mini mini directed grid minor theorem. I will be using this theorem in future papers to make progress towards a directed grid minor theorem. Stay tuned !!

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 !!

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.

minors

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

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 :

If you know any interesting Erdos links, leave a comment.

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

paul_erdos_painting