Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

Iyad A. Kanj; Christian Komusiewicz; Manuel Sorge; E.J. van Leeuwen

doi:10.1016/j.jcss.2017.08.002

Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

Iyad A. Kanj, Christian Komusiewicz, Manuel Sorge, E.J. van Leeuwen

Sub Algorithms and Complexity

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

A graph G is a (A, B )-graph if V (G) can be bipartitioned into A and B such that
G[A] satisfies property A and G[B] satisfies property B . The (A, B )-Recognition
problem is to recognize whether a given graph is a (A, B )-graph. There are many
(A, B )-Recognition problems, including the recognition problems for bipartite, split,and unipolar graphs. We present efficient algorithms for many cases of (A, B )-Recognitionbased on a technique which we dub inductive recognition. In particular, we givefixed-parameter algorithms for two NP-hard (A, B )-Recognition problems, Monopolar Recognition and 2-Subcoloring, parameterized by the number of maximal cliques in G[A]. We complement our algorithmic results with several hardness results for (A, B )-Recognition.

Original language	English
Pages (from-to)	22-47
Number of pages	26
Journal	Journal of Computer and System Sciences
Volume	92
DOIs	https://doi.org/10.1016/j.jcss.2017.08.002
Publication status	Published - Mar 2018

Keywords

Vertex-partition problems
Graph classes
Monopolar graphs
Subcolorings
Split graphs
Unipolar graphs
Fixed-parameter algorithms

Access to Document

10.1016/j.jcss.2017.08.002

kanjFinal published version, 813 KBLicence: Taverne

Cite this

@article{087211cc42864a4a823daddbb4707735,

title = "Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs",

abstract = "A graph G is a (A, B )-graph if V (G) can be bipartitioned into A and B such thatG[A] satisfies property A and G[B] satisfies property B . The (A, B )-Recognitionproblem is to recognize whether a given graph is a (A, B )-graph. There are many(A, B )-Recognition problems, including the recognition problems for bipartite, split,and unipolar graphs. We present efficient algorithms for many cases of (A, B )-Recognitionbased on a technique which we dub inductive recognition. In particular, we givefixed-parameter algorithms for two NP-hard (A, B )-Recognition problems, Monopolar Recognition and 2-Subcoloring, parameterized by the number of maximal cliques in G[A]. We complement our algorithmic results with several hardness results for (A, B )-Recognition.",

keywords = "Vertex-partition problems, Graph classes, Monopolar graphs, Subcolorings, Split graphs, Unipolar graphs, Fixed-parameter algorithms",

author = "Kanj, {Iyad A.} and Christian Komusiewicz and Manuel Sorge and {van Leeuwen}, E.J.",

year = "2018",

month = mar,

doi = "10.1016/j.jcss.2017.08.002",

language = "English",

volume = "92",

pages = "22--47",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

AU - Kanj, Iyad A.

AU - Komusiewicz, Christian

AU - Sorge, Manuel

AU - van Leeuwen, E.J.

PY - 2018/3

Y1 - 2018/3

N2 - A graph G is a (A, B )-graph if V (G) can be bipartitioned into A and B such thatG[A] satisfies property A and G[B] satisfies property B . The (A, B )-Recognitionproblem is to recognize whether a given graph is a (A, B )-graph. There are many(A, B )-Recognition problems, including the recognition problems for bipartite, split,and unipolar graphs. We present efficient algorithms for many cases of (A, B )-Recognitionbased on a technique which we dub inductive recognition. In particular, we givefixed-parameter algorithms for two NP-hard (A, B )-Recognition problems, Monopolar Recognition and 2-Subcoloring, parameterized by the number of maximal cliques in G[A]. We complement our algorithmic results with several hardness results for (A, B )-Recognition.

AB - A graph G is a (A, B )-graph if V (G) can be bipartitioned into A and B such thatG[A] satisfies property A and G[B] satisfies property B . The (A, B )-Recognitionproblem is to recognize whether a given graph is a (A, B )-graph. There are many(A, B )-Recognition problems, including the recognition problems for bipartite, split,and unipolar graphs. We present efficient algorithms for many cases of (A, B )-Recognitionbased on a technique which we dub inductive recognition. In particular, we givefixed-parameter algorithms for two NP-hard (A, B )-Recognition problems, Monopolar Recognition and 2-Subcoloring, parameterized by the number of maximal cliques in G[A]. We complement our algorithmic results with several hardness results for (A, B )-Recognition.

KW - Vertex-partition problems

KW - Graph classes

KW - Monopolar graphs

KW - Subcolorings

KW - Split graphs

KW - Unipolar graphs

KW - Fixed-parameter algorithms

U2 - 10.1016/j.jcss.2017.08.002

DO - 10.1016/j.jcss.2017.08.002

M3 - Article

SN - 0022-0000

VL - 92

SP - 22

EP - 47

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -

Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this