A Note on Irreversible 2-Conversion Sets in Subcubic Graphs

Asahi TAKAOKA  Shuichi UENO  

IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.8   pp.1589-1591
Publication Date: 2015/08/01
Publicized: 2015/05/14
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015EDL8021
Type of Manuscript: LETTER
Category: Fundamentals of Information Systems
feedback vertex set,  graphic matroid parity problem,  irreversible threshold process,  subcubic graphs,  

Full Text: PDF>>
Buy this Article

Irreversible k-conversion set is introduced in connection with the mathematical modeling of the spread of diseases or opinions. We show that the problem to find a minimum irreversible 2-conversion set can be solved in O(n2log 6n) time for graphs with maximum degree at most 3 (subcubic graphs) by reducing it to the graphic matroid parity problem, where n is the number of vertices in a graph. This affirmatively settles an open question posed by Kyncl et al. (2014).