Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

DOI10.1016/J.JCSS.2017.08.002MaRDI QIDQ1678166zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1702.04322, https://drops.dagstuhl.de/opus/volltexte/2016/6036/

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)

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.

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

Cites work

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

Cited in

(6)

• Solving partition problems with colour-bipartitions
• Solving partition problems almost always requires pushing many vertices around
• Monopolar graphs: complexity of computing classical graph parameters
• scientific article; zbMATH DE number 7378721 (Why is no real title available?)
• Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
• Minimization and parameterized variants of vertex partition problems on graphs

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)