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.

• 1. Combinatorics : Prove that trees with diameter 6 are graceful. (see earlier posts graceful tree conjecture, graceful diameter-6 trees).

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

• 10. Approximation algorithms : Improve the approximation factor for the uniform sparsest cut problem. The best known factor is .

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