TY - GEN

T1 - Results on independent sets in categorical products of graphs, the ultimate categorical independence ratio and the ultimate categorical independent domination ratio

AU - Hon, Wing Kai

AU - Kloks, Ton

AU - Liu, Ching Hao

AU - Liu, Hsiang Hsuan

AU - Poon, Sheung Hung

AU - Wang, Yue Li

N1 - Funding Information:
Supported in part by grants 100-2628-E-007-020-MY3 and 101-2218-E-007-001 of the National Science Council (NSC), Taiwan, R.O.C.

PY - 2014

Y1 - 2014

N2 - We first present polynomial algorithms to compute maximum independent sets in the categorical products of two cographs or two splitgraphs, respectively. Then we prove that computing the independent set of the categorical product of a planar graph of maximal degree three and K 4 is NP-complete. The ultimate categorical independence ratio of a graph G is defined as lim k → ∞ α(G k )/n k . The ultimate categorical independence ratio can be computed in polynomial time for cographs, permutation graphs, interval graphs, graphs of bounded treewidth and splitgraphs. Also, we present an O â̂- (3 n/3) exact, exponential algorithm for the ultimate categorical independence ratio of general graphs. We further present a PTAS for the ultimate categorical independence ratio of planar graphs. Lastly, we show that the ultimate categorical independent domination ratio for complete multipartite graphs is zero, except when the graph is complete bipartite with color classes of equal size (in which case it is 1/2).

AB - We first present polynomial algorithms to compute maximum independent sets in the categorical products of two cographs or two splitgraphs, respectively. Then we prove that computing the independent set of the categorical product of a planar graph of maximal degree three and K 4 is NP-complete. The ultimate categorical independence ratio of a graph G is defined as lim k → ∞ α(G k )/n k . The ultimate categorical independence ratio can be computed in polynomial time for cographs, permutation graphs, interval graphs, graphs of bounded treewidth and splitgraphs. Also, we present an O â̂- (3 n/3) exact, exponential algorithm for the ultimate categorical independence ratio of general graphs. We further present a PTAS for the ultimate categorical independence ratio of planar graphs. Lastly, we show that the ultimate categorical independent domination ratio for complete multipartite graphs is zero, except when the graph is complete bipartite with color classes of equal size (in which case it is 1/2).

UR - http://www.scopus.com/inward/record.url?scp=84958554420&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-04657-0_23

DO - 10.1007/978-3-319-04657-0_23

M3 - Conference contribution

AN - SCOPUS:84958554420

SN - 9783319046563

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 237

EP - 248

BT - Algorithms and Computation - 8th International Workshop, WALCOM 2014, Proceedings

PB - Springer Verlag

T2 - 8th International Workshop on Algorithms and Computation, WALCOM 2014

Y2 - 13 February 2014 through 15 February 2014

ER -