Search

This work is devoted to the study of the Balanced Connected Subgraph Problem (BCS) from a complexity, inapproximability and approximation point of view. The input is a graph G = ( V , E ) , with each vertex having been colored, “red” or “blue”; the goal is to find a maximum connected subgraph G ′ = ( V ′ , E ′ ) from G that is color-balanced (having exactly | V ′ | / 2 red vertices and | V ′ | / 2 blue vertices). This problem is known to be NP -complete in general but polynomial in paths and trees. We propose a polynomial-time algorithm for block graph. We propose some complexity results for bounded-degree or bounded-diameter graphs, and also for bipartite graphs. We also propose inapproximability results for some graph classes, including chordal, planar, or subcubic graphs.

A subset $D \subseteq V$ is an \emph{independent} (or \emph{stable}) \emph{dominating set} of a graph $G = (V,E)$ if $D$ is an independent set (no edges between vertices of $D$) and dominates all the vertices of $G$ (each vertex of $V-D$ has a neighbour in $D$). In this paper we study a generalisation of this classical notion. Namely, an instance of our problem is a graph $G=(V, E)$ and $\Pi=(V_1, \dots, V_k)$ a partition of $V$. Each subset $V_i$ of $\Pi$ is called an \emph{obligation}. An \emph{Independent Dominating set with Obligation} (\IDO) $D$ in an instance $(G, \Pi)$ is an independent dominating set of $G$ with the additional property that if a vertex $u$ of obligation $V_i$ is in $D$, then \emph{all} the others vertices of $V_i$ must also be in $D$; i.e., for all $i=1,\dots,k$, either $V_i\cap D=\emptyset$ or $V_i \subseteq D$ (we say that $D$ \emph{respects} the obligations). Note that when each obligation of $\Pi$ is a singleton, an \IDO is just an independent dominating set of $G$ that can be constructed with a greedy algorithm. Among other things, we show that determining if an instance $(G=(V,E),\Pi)$ has an \IDO is $NP$-complete, even if $G$ is a path (each vertex of $G$ exactly has two neighbours, except two extremities that have one), all the obligations are independent sets of $G$ and they all have the same constant size $\lambda > 1$. We also show that the problem is also $NP$-complete, even if $\Pi$ is composed of $\sqrt{|V|}$ independent obligations each of size $\sqrt{|V|}$ or if the diameter of $G$ is three. Our results clearly show that this problem is very difficult, even in extremely restricted instances. Hence, in a second part of the paper, we relax the condition to dominate all the vertices of $G$. However, we show that determining if $(G=(V, E), \Pi)$ contains an independent set $D$ respecting the obligations and dominating at least $3\sqrt{|V|} -2$ vertices of $G$ is $NP$-complete, even if $G$ is a collection of disjoint paths and obligations are all independent sets of $G$. On the positive side, we propose a greedy algorithm constructing a solution dominating at least $2\sqrt{|V|} - 1$ vertices in any instance $(G=(V, E), \Pi)$ if all obligations of $\Pi$ are independent sets of $G$.