# measures for a DAG (directed acyclic graph)?

Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential. Well, is there a measure for the importance of a node (like the cut vertex in undirected graph)? or how separated the DAG is? May be after small amount of edge deletion (or node deletion) the DAG was decomposed into separated components (Better if the components have similar cardinality)?

• What you describe sounds to me like graph connectivity ( en.wikipedia.org/wiki/Connectivity_%28graph_theory%29 ). However I know only of connectivities that are label-agnostic, i.e. it doesn't matter which edges or nodes participate in the cut. – chazisop Aug 4 '11 at 8:00
• Not like that. node connectivity or edge connectivity does not grab the property of DAG as I think. – Peng Zhang Aug 4 '11 at 8:31
• Dominator analysis: not a measure but one view of what important nodes are. Look up tree-width, which is how far a graph is from being a tree. – Vijay D Aug 5 '11 at 0:59

• How much the removal of node $v$ reduces the max flow from sources to sinks
• the betweenness centrality of $v$
• the in-degree of $v$ times the out-degree of $v$