QP-2019-04

An efficient algorithm for testing $(k,\ell)$-sparsity when $\ell<0$

Csaba Király

For two integers $k>0$ and $\ell$, a graph $G=(V,E)$ is called $(k,\ell)$-tight if $|E|=k|V|-\ell$ and $|E(X)|\leq k|X|-\ell$ for all $X\sbse V$ for which $k|X|-\ell\geq 0$. Lee and Streinu provided an algorithm for testing $(k,\ell)$-sparsity when $\ell\geq 0$. We show how to modify this algorithm for instances where $\ell<0$.

Bibtex entry:

@techreport{egresqp-19-04,

AUTHOR	=	{Kir{\'a}ly, Csaba},
TITLE	=	{An efficient algorithm for testing $(k,\ell)$-sparsity when $\ell<0$},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2019},
NUMBER	=	{QP-2019-04}

}