Forbidden Directed Minors and Directed Pathwidth

Today’s post is about the following paper, a joint work with Qiuyi Zhang, one of my advisees. Qiuyi Zhang is now a graduate student in the Mathematics department of Berkeley.

  • Shiva Kintali, Qiuyi Zhang. Forbidden Directed Minors and Directed Pathwidth. (Preprint is available on my publications page)

Undirected graphs of pathwidth at most one are characterized by two forbidden minors i.e., (i) K_3 the complete graph on three vertices and (ii) S_{2,2,2} the spider graph with three legs of length two each (see the following figure).

dpw_minors

Directed pathwidth is a natural generalization of pathwidth to digraphs. We proved that digraphs of directed pathwidth at most one are characterized by a finite number of forbidden directed minors. In particular, we proved that the number of vertices in any forbidden directed minor is at most 8*160000+7. Ahem !!

This paper falls in the “directed minors” part of my research interests. In an earlier theorem, proved in April 2013 (see this earlier post), we proved that partial 1-DAGs are characterized by three forbidden directed minors. In a similar vein, I conjectured that the digraphs with directed pathwidth at most 1 are characterized by a finite number of forbidden directed minors. I assumed that the number of forbidden directed minors is number is around 100. So we started this project in May 2013 and started making a list of carefully constructed forbidden directed minors and tried to extend our techniques from partial 1-DAGs. Here is an initial list of minors we found.

dpw_minors_list

All the forbidden minors we found, looked very cute and we assumed that a proof is nigh. Soon, we realized that the list is  growing quickly and none of our earlier techniques are applicable. After almost an year of patient efforts and roller coaster rides, we proved our finiteness theorem in May 2014, two weeks before Qiuyi Zhang’s thesis defense. It took us 10 more months to get the paper to its current status. So this is a two year long adventure.

I am hoping to prove more theorems in the “directed minors” area in the coming years. The current paper taught me that patience and focus are big factors to make consistent progress. There should be a nice balance between `proving new theorems’ and `writing up the existing results’.