I am working on a decomposition of trees based on the null space of the adjacency matrix of the tree. Most algorithm on trees are really fast. The decomposition could give some algorithms to find independence sets and maximum matchings, but depends on as fast you can find a base of the null space of the adjacent matrix.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ At first glance, it's not even clear to me if the output has always at most linear size. $\endgroup$– Federico PoloniCommented Nov 3, 2016 at 14:53
-
1$\begingroup$ Indeed, a star graph has nullity (n - 2), so (at least a naive) encoding of the output has ~ $n^2$ numbers. $\endgroup$– aelguindyCommented Nov 3, 2016 at 15:09
-
$\begingroup$ First: lineal on |V(T)|, the number of vertices of the tree. $\endgroup$– Daniel Alejandro JaumeCommented Nov 3, 2016 at 15:30
-
$\begingroup$ Complexity is not my thing. Are you telling my that any algorithm must be at least quadratic? $\endgroup$– Daniel Alejandro JaumeCommented Nov 3, 2016 at 15:38
-
1$\begingroup$ Not necessarily -- aelguindy showed an example in which the basis is composed of $\approx n$ vectors, but in that specific case they can be encoded as a set of sparse vectors using linear space. So we don't have a counterexample for now, but we are considering the possibility that there might be one. $\endgroup$– Federico PoloniCommented Nov 3, 2016 at 16:01
Add a comment
|