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)?

  • $\begingroup$ 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. $\endgroup$ – chazisop Aug 4 '11 at 8:00
  • $\begingroup$ Not like that. node connectivity or edge connectivity does not grab the property of DAG as I think. $\endgroup$ – Peng Zhang Aug 4 '11 at 8:31
  • $\begingroup$ 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. $\endgroup$ – Vijay D Aug 5 '11 at 0:59

There are loads of measures of nodes in a DAG you could use. For example:

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

The question should not be if there is a measure, but rather which measure is most appropriate. That depends on the problem you're trying to solve.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.