Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

DOI10.1016/J.JCSS.2017.08.002zbMATH Open1380.68227arXiv1702.04322OpenAlexW2963464338MaRDI QIDQ1678166FDOQ1678166

Authors: Christian Komusiewicz, Manuel Sorge, Erik Jan van Leeuwen, Iyad Kanj 

Publication date: 14 November 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: A graph $G$ is a $(P{i}_A,P{i}_B)$-graph if $V(G)$ can be bipartitioned into $A$ and $B$ such that $G[A]$ satisfies property $P{i}_A$ and $G[B]$ satisfies property $P{i}_B$. The $(P{i}_A,P{i}_B)$-Recognition problem is to recognize whether a given graph is a $(P{i}_A,P{i}_B)$-graph. There are many $(P{i}_A,P{i}_B)$-Recognition problems, including the recognition problems for bipartite, split, and unipolar graphs. We present efficient algorithms for many cases of $(P{i}_A,P{i}_B)$-Recognition based on a technique which we dub inductive recognition. In particular, we give fixed-parameter algorithms for two NP-hard $(P{i}_A,P{i}_B)$-Recognition problems, Monopolar Recognition and 2-Subcoloring. We complement our algorithmic results with several hardness results for $(P{i}_A,P{i}_B)$-Recognition.

Full work available at URL: https://arxiv.org/abs/1702.04322

Recommendations

• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Complexity and algorithms for recognizing polar and monopolar graphs
• Recognizing polar planar graphs using new results for monopolarity
• Solving partition problems with colour-bipartitions
• Monopolar graphs: complexity of computing classical graph parameters

zbMATH Keywords

fixed-parameter algorithmsgraph classessplit graphsmonopolar graphsunipolar graphssubcoloringsvertex-partition problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Fundamentals of parameterized complexity
• Title not available (Why is that?)
• Finding odd cycle transversals.
• Which problems have strongly exponential complexity?
• Parameterized algorithms
• Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
• The splittance of a graph
• The complexity of some problems related to GRAPH 3-COLORABILITY
• Recognition of unipolar and generalised split graphs
• More about subcolorings
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• List monopolar partitions of claw-free graphs
• On the Polarity and Monopolarity of Graphs
• Polarity of chordal graphs
• On the computational complexity of (O,P)-partition problems
• Subcolorings and the subchromatic number of a graph
• The complexity of \(G\)-free colourability
• Graph Subcolorings: Complexity and Algorithms
• Parameterized algorithms for deletion to \((r,\ell)\)-graphs
• Title not available (Why is that?)
• Algorithms for unipolar and generalized split graphs
• Solving partition problems with colour-bipartitions
• Wheel-Free Deletion Is W[2]-Hard
• Complexity and algorithms for recognizing polar and monopolar graphs
• On 2-Subcolourings of Chordal Graphs

Cited In (6)

• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Solving partition problems almost always requires pushing many vertices around
• Title not available (Why is that?)
• Solving partition problems with colour-bipartitions
• Minimization and parameterized variants of vertex partition problems on graphs
• Monopolar graphs: complexity of computing classical graph parameters

This page was built for publication: Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1678166)