Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable\n Graphs

2017/02/14 by Iyad Kanj, Christian Komusiewicz, Kanj, Iyad +5 · 1 citation
Computer Science · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1702.04322

openalex publication_date 2017/02/14 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

A graph G is a (\Π_A,\Π_B)-graph if V(G) can be bipartitioned into\nA and B such that G[A] satisfies property \Π_A and G[B] satisfies\nproperty \Π_B. The (\Π_A,\Π_B)-Recognition problem is to recognize\nwhether a given graph is a (\Π_A,\Π_B)-graph. There are many\n(\Π_A,\Π_B)-Recognition problems, including the recognition problems\nfor bipartite, split, and unipolar graphs. We present efficient algorithms for\nmany cases of (\Π_A,\Π_B)-Recognition based on a technique which we dub\ninductive recognition. In particular, we give fixed-parameter algorithms for\ntwo NP-hard (\Π_A,\Π_B)-Recognition problems, Monopolar Recognition and\n2-Subcoloring. We complement our algorithmic results with several hardness\nresults for (\Π_A,\Π_B)-Recognition.\n

Cited by

• Subcoloring of (Unit) Disk Graphs

Related

• Faster Algorithms for Graph Monopolarity
• Efficient recognition algorithms for (1,2)-, (2,1)- and (2,2)-graphs
• Recognition of unipolar and generalised split graphs
• Beyond circular-arc graphs -- recognizing lollipop graphs and medusa graphs
• 2-subcoloring is NP-complete for planar comparability graphs