$K_{1,4}$-free graph is the graph with no induced subgraph of the form $K_{1,4}$ enter image description here

An augmenting graph $H$ for $S$ (which is an independent set) is an induced bipartite subgraph of $G$, where $H = (B, W, E)$ and the following properties hold:

  1. $B\subseteq V(G)\setminus S$ and $W\subseteq S$.
  2. $|B|>|W|$.
  3. $N(B)\cap S\subseteq W$.

An independent set $S$ in a graph $G$ is maximum if and only if there are no augmenting graphs for $S$.

  • $\begingroup$ No. "Let $H$ be a connected graph which is neither a path nor a subdivision of the claw. Then MIS is NP-hard in $H$-free graphs." This is stated as Theorem 1 in the following link: arxiv.org/pdf/1810.04620.pdf, which cite the paper: "The effect of local constraints on the complexity of determination of the graph independence number." by V. Alekseev. which is in Russian. $\endgroup$ Mar 21 at 10:48
  • $\begingroup$ What exactly do you mean by "augmenting graph algorithm"? Do you demand that such an algorithm should run in polynomial time? $\endgroup$ Mar 21 at 14:39
  • 2
    $\begingroup$ @TheHolyJoker In this case NP-hardness simply follows from NP-hardness on cubic graphs. $\endgroup$
    – Laakeri
    Mar 21 at 23:48
  • $\begingroup$ @TheHolyJoker thanks for mentioning this paper, this states that in theorem 2 that MIS on K1,4-free is W[1]-hard. Is it safe to say that no augmenting graph algorithm exists for this problem? $\endgroup$
    – user72110
    Mar 22 at 8:43
  • $\begingroup$ @ChristianKomusiewicz It means that after finding initial independent set, the graph should have some subgraph which we called augmenting graph. By finding such subgraph structures we can swap vertices in the independent set to them which are not. Identification of such augmenting graphs should be also done in polynomial time. $\endgroup$
    – user72110
    Mar 22 at 8:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.