In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NPhard and hard to approximate within a factor of n1−ε for any ε > 0. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In Hfree graphs, that is, graphs not containing a fixed graph H as an induced subgraph, the problem is known to remain NPhardmore »
Complexity of CkColoring in Hereditary Classes of Graphs
For a graph F, a graph G is Ffree if it does not contain an induced subgraph isomorphic to F. For two graphs G and H, an Hcoloring of G is a mapping f : V (G) → V (H) such that for every edge uv ∈ E(G) it holds that f(u)f(v) ∈ E(H). We are interested in the complexity of the problem HColoring, which asks for the existence of an Hcoloring of an input graph G. In particular, we consider HColoring of Ffree graphs, where F is a fixed graph and H is an odd cycle of length at least 5. This problem is closely related to the well known open problem of determining the complexity of 3Coloring of Ptfree graphs.
We show that for every odd k ≥ 5 the CkColoring problem, even in the precoloringextension variant, can be solved in polynomial time in P9free graphs. On the other hand, we prove that the extension version of CkColoring is NPcomplete for Ffree graphs whenever some component of F is not a subgraph of a subdivided claw.
 Award ID(s):
 1763817
 Publication Date:
 NSFPAR ID:
 10164201
 Journal Name:
 European Symposium on Algorithms
 Page Range or eLocationID:
 31:1  31:15
 Sponsoring Org:
 National Science Foundation
More Like this


We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $ \Sigma $ of genus $ g$ and let $ L=(L(v):v\in V(G))$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is trianglefree, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$coloring of $ G$ is a mapping $more »

Given two (di)graphs G, H and a cost function c:V(G) x V(H) > Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)> V(H) (a.k.a Hcoloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximablemore »

Given two (di)graphs G, H and a cost function c:V(G) x V(H) > Q_{>= 0} cup {+infty}, in the minimum cost homomorphism problem, MinHOM(H), we are interested in finding a homomorphism f:V(G)> V(H) (a.k.a Hcoloring) that minimizes sum limits_{v in V(G)}c(v,f(v)). The complexity of exact minimization of this problem is well understood [Pavol Hell and Arash Rafiey, 2012], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. In terms of digraphs, MinHOM(H) is not approximablemore »

The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $E(S)/S$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are wellstudied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a nonnegative supermodular function $f:more »