Show simple item record

dc.contributor.authorFomin, Fedor
dc.contributor.authorGolovach, Petr
dc.contributor.authorMisra, Pranabendu
dc.contributor.authorRamanujan, M.S.
dc.PublishedLeibniz International Proceedings in Informatics. 2020, 173 50:1-50:13.
dc.description.abstractThe incidence matrix of a graph is a fundamental object naturally appearing in many applications, involving graphs such as social networks, communication networks, or transportation networks. Often, the data collected about the incidence relations can have some slight noise. In this paper, we initiate the study of the computational complexity of recovering incidence matrices of graphs from a binary matrix: given a binary matrix M which can be written as the superposition of two binary matrices L and S, where S is the incidence matrix of a graph from a specified graph class, and L is a matrix (i) of small rank or, (ii) of small (Hamming) weight. Further, identify all those graphs whose incidence matrices form part of such a superposition. Here, L represents the noise in the input matrix M. Another motivation for this problem comes from the Matroid Minors project of Geelen, Gerards and Whittle, where perturbed graphic and co-graphic matroids play a prominent role. There, it is expected that a perturbed binary matroid (or its dual) is presented as L+S where L is a low rank matrix and S is the incidence matrix of a graph. Here, we address the complexity of constructing such a decomposition. When L is of small rank, we show that the problem is NP-complete, but it can be decided in time (mn)^O(r), where m,n are dimensions of M and r is an upper-bound on the rank of L. When L is of small weight, then the problem is solvable in polynomial time (mn)^O(1). Furthermore, in many applications it is desirable to have the list of all possible solutions for further analysis. We show that our algorithms naturally extend to enumeration algorithms for the above two problems with delay (mn)^O(r) and (mn)^O(1), respectively, between consecutive outputs.en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsNavngivelse 4.0 Internasjonal*
dc.rightsNavngivelse 4.0 Internasjonal*
dc.titleOn the Complexity of Recovering Incidence Matricesen_US
dc.typeJournal articleen_US
dc.typePeer revieweden_US
dc.rights.holderCopyright 2020 The Authorsen_US
dc.source.journalLeibniz International Proceedings in Informaticsen_US
dc.relation.projectNorges forskningsråd: 263317en_US
dc.identifier.citationLeibniz International Proceedings in Informatics. 2020, 173, 50:1-50:13en_US

Files in this item


This item appears in the following Collection(s)

Show simple item record

Navngivelse 4.0 Internasjonal
Except where otherwise noted, this item's license is described as Navngivelse 4.0 Internasjonal