2024/10/08 by Geevarghese Philip, Philip, Geevarghese, Shrinidhi Teganahally Sridhara +1
Computer Science · #Advanced Graph Neural Networks #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2410.06337
openalex publication_date 2024/10/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G = (V,E) is monopolar if its vertex set admits a partition V = (C \uplus I) where G[C] is a cluster graph and I is an independent set in G; this is a monopolar partition of G. The MONOPOLAR RECOGNITION problem -- deciding whether an input graph is monopolar -- is known to be NP-Hard in very restricted graph classes such as sub-cubic planar graphs. We derive a polynomial-time algorithm that takes (i) a graph G=(V,E) and (ii) a vertex modulator S of G to chair-free graphs as inputs, and checks whether G has a monopolar partition V=(C\uplusI) where set S is contained in the cluster part. We build on this algorithm to develop fast exact exponential-time and parameterized algorithms for MONOPOLAR RECOGNITION. Our exact algorithm solves MONOPOLAR RECOGNITION in O⋆(1.3734n) time on input graphs with n vertices, where the O⋆() notation hides polynomial factors. In fact, we solve the more general problems MONOPOLAR EXTENSTION and LIST-MONOPOLAR PARTITION in O⋆(1.3734n) time. These are the first improvements over the trivial O⋆(2n)-time algorithms for all these problems. It is known that -- assuming ETH -- these problems cannot be solved in O⋆(2o(n)) time. Our FPT algorithms solve MONOPOLAR RECOGNITION in O⋆(3.076^kv) and O⋆(2.253^ke) time where kv and ke are, respectively, the sizes of the smallest vertex and edge modulators of the input graph to claw-free graphs. These results are a significant addition to the small number of FPT algorithms currently known for MONOPOLAR RECOGNITION.