Sesión Matemática Discreta

Diciembre 14, 11:20 ~ 11:40

Una Base $\{-1,0,1\}$ y Máximamente Rala del Espacio Nulo de un Bosque en Tiempo Óptimo

Safe, Martín

Dada una matriz, el \textsc{Problema del Espacio Nulo} consiste en encontrar una base de su espacio nulo que sea \emph{máximamente rala} (es decir, con mínimo número posible de entradas no nulas). Este problema es NP-completo~\cite{MR857589} e incluso difícil de aproximar~\cite{MR3537025}. Algunas heurísticas para resolverlo fueron propuestas en~\cite{MR812616,MR918058,MR897742,MR3537025}. El \emph{espacio nulo} de un bosque es el espacio nulo de su matriz de adyacencia. Sander and Sander~\cite{MR2154182} y Akbari et al.~\cite{MR2214403} probaron, independientemente, que el espacio nulo de cada bosque admite una base $\{-1,0,1\}$ (es decir, con entradas $-1$, $0$ y $1$). En \cite{MR2214403} y \cite{MR2154182} se propusieron también algoritmos para producir una base $\{-1,0,1\}$ del espacio nulo de cualquier bosque dado, pero las bases producidas por estos algoritmos no son necesariamente máximamente ralas. En este trabajo hallamos un algoritmo para producir una base $\{-1,0,1\}$ y máximamente rala del espacio nulo de cualquier bosque dado. La complejidad temporal de nuesto algoritmo es óptima en el sentido que su ejecución requiere tiempo proporcional a la cantidad de entradas no nulas en cualquier base máximamente rala del bosque de entrada. Más aún, probamos que, dado un bosque $F$ de $n$ vértices, el conjunto de vértices $x$ de $F$ para los cuales existe un vector en el espacio nulo de $F$ que no se anula en $x$ y el mínimo número de entradas no nulas de una base del espacio nulo de $F$ pueden hallarse en tiempo $O(n)$. \begin{thebibliography}{1} \bibitem{MR2214403} S.~Akbari, A.~Alipour, E.~Ghorbani y G.~B. Khosrovshahi. \newblock {$\{-1,0,1\}$}-basis for the null space of a forest. \newblock {\em Linear Algebra Appl.}, 414(2-3):506--511, 2006. \bibitem{MR812616} M.~W. Berry, M.~T. Heath, I.~Kaneko, M.~Lawo, R.~J. Plemmons y R.~C. Ward. \newblock An algorithm to compute a sparse basis of the null space. \newblock {\em Numer. Math.}, 47(4):483--504, 1985. \bibitem{MR857589} T.~F. Coleman y A.~Pothen. \newblock The null space problem. {I}. {C}omplexity. \newblock {\em SIAM J. Algebraic Discrete Methods}, 7(4):527--537, 1986. \bibitem{MR918058} T.~F. Coleman y A.~Pothen. \newblock The null space problem. {II}. {A}lgorithms. \newblock {\em SIAM J. Algebraic Discrete Methods}, 8(4):544--563, 1987. \bibitem{MR897742} J.~R. Gilbert y M.~T. Heath. \newblock Computing a sparse basis for the null space. \newblock {\em SIAM J. Algebraic Discrete Methods}, 8(3):446--459, 1987. \bibitem{MR3537025} L.-A. Gottlieb y T.~Neylon. \newblock Matrix sparsification and the sparse null space problem. \newblock {\em Algorithmica}, 76(2):426--444, 2016. \bibitem{MR2154182} J.~W. Sander y T.~Sander. \newblock On simply structured bases of tree kernels. \newblock {\em AKCE Int. J. Graphs Comb.}, 2(1):45--56, 2005. \end{thebibliography}

Autores: Jaume, Daniel A. / MOLINA MUNAFÓ, Luis Gonzalo / Pastine, Adrián / Safe, Martín.