We give a conjecture that we still have an optimal treedepth decomposition even we use only minimal separators no larger than the treewidth of input graphs. Then, we give some theoretical results for the conjecture. Treedepth decomposition has several practical applications and can be used to speed up many parameterized algorithms. There are several works aiming to give a scalable and exact method for the decomposition . Those include works based on a set of all minimal separators. In our experiments with several graphs, when we consider only minimal separators which are no larger than treewidth, we can significantly speed up the decomposition while still have an optimal treedepth decomposition. By the conjecture, we solve more instances than any algorithm submitted to PACE 2020. Theoretically, we prove that the conjecture for many classes of graphs. We also prove a relaxed version of the conjecture that the size of the separators should not be larger than 2 \cdot tw +  1 when tw is the treewidth\le  .
 Treedepth decomposition has several practical applications and can be used to speed up many parameterized algorithms. There are several works aiming to design a scalable algorithm to compute exact treedepth decompositions . Those include works based on a set of all minimal separators. In those algorithms, although a number of minimal separators are enumerated, the minimal separators that are used for an optimal solution are empirically very small. Therefore, analyzing the upper bound on the size of minimal separators is an important problem because it has the potential to significantly reduce the computation time. A minimal separator S is called an optimal top separator if td(G) = |S| + td(G \backslash S), where td(G) denotes the treedepth of G. Then, we have two theoretical results on the size of optimal top separators. ( 1 ) For any G, there is an optimal top separator S such that |S|\le 2tw(G), where tw(G) is the treewidth of G. (2) For any c < 2, there exists a graph G such that any optimal top separator S of G have |S| > c \cdot tw(G), i.e., the first result gives a tight bound on the size of an optimal top separator .
D
We give a conjecture that we still have an optimal treedepth decomposition even we use only minimal separators no larger than the treewidth of input graphs. Then, we give some theoretical results for the conjecture.
R
give a scalable and exact method for the decomposition
design a scalable algorithm to compute exact treedepth decompositions
R
our experiments with several graphs, when we consider only minimal separators which are no larger than treewidth, we can significantly speed up the decomposition while still have an optimal treedepth decomposition. By the conjecture, we solve more instances than any algorithm submitted to PACE 2020. Theoretically, we prove that the conjecture for many classes of graphs. We also prove a relaxed version of the conjecture that the size of the separators should not be larger than 2 \cdot tw
those algorithms, although a number of minimal separators are enumerated, the minimal separators that are used for an optimal solution are empirically very small. Therefore, analyzing the upper bound on the size of minimal separators is an important problem because it has the potential to significantly reduce the computation time. A minimal separator S is called an optimal top separator if td(G) = |S|
A
td(G \backslash S), where td(G) denotes the treedepth of G. Then, we have two theoretical results on the size of optimal top separators. (
R
when tw is the treewidth
) For any G, there is an optimal top separator S such that |S|
A
2tw(G), where tw(G) is the treewidth of G. (2) For any c < 2, there exists a graph G such that any optimal top separator S of G have |S| > c \cdot tw(G), i.e., the first result gives a tight bound on the size of an optimal top separator