<p><span class="math-container">$K_{1,4}$</span>-free graph is the graph with no induced subgraph of the form <span class="math-container">$K_{1,4}$</span>
<a href="https://i.sstatic.net/zwLpp.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/zwLpp.png" alt="enter image description here" /></a></p>
<p>An augmenting graph <span class="math-container">$H$</span> for <span class="math-container">$S$</span> (which is an independent set) is an induced bipartite subgraph of <span class="math-container">$G$</span>, where <span class="math-container">$H = (B, W, E)$</span> and the following properties hold:</p>
<ol>
<li><span class="math-container">$B\subseteq V(G)\setminus S$</span> and <span class="math-container">$W\subseteq S$</span>.</li>
<li><span class="math-container">$|B|&gt;|W|$</span>.</li>
<li><span class="math-container">$N(B)\cap S\subseteq W$</span>.</li>
</ol>
<p>An independent set <span class="math-container">$S$</span> in a graph <span class="math-container">$G$</span> is maximum if and only if
there are no augmenting graphs for <span class="math-container">$S$</span>.</p>

CC BY-SA 4.0
2024-03-21T10:48:40.723Z
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: https://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.
TheHolyJoker
CC BY-SA 4.0
2024-03-21T14:39:19.253Z
What exactly do you mean by "augmenting graph algorithm"? Do you demand that such an algorithm should run in polynomial time?
Christian Komusiewicz
CC BY-SA 4.0
2024-03-21T23:48:20.263Z
@TheHolyJoker In this case NP-hardness simply follows from NP-hardness on cubic graphs.
Laakeri
CC BY-SA 4.0
2024-03-22T08:43:38.297Z
@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?
user72110
CC BY-SA 4.0
2024-03-22T08:50:01.203Z
@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.
user72110
CC BY-SA 4.0
2024-03-22T14:29:17.750Z
Ok, then I suggest that you add this fact (polynomial running time) to the question? Btw, W[1]-hardness for $K_{1,4}$ free graphs suggests that not only that there is no polynomial-time augmenting graph algorithm but also that there is no such algorithm with FPT running time for the parameter $|H|$. Finally, what you call an augmenting graph is also called an improving swap $B\cup W$ in the local search literature.
Christian Komusiewicz
CC BY-SA 4.0
2024-03-23T06:30:34.943Z
@ChristianKomusiewicz thanks for the suggestions
user72110
<graph-theory><graph-algorithms><independent-set><graph-classes>
Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time
user72110
# Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time

(Asked by: username_0 on 2024-03-21)

$K\_{1,4}$-free graph is the graph with no induced subgraph of the form $K\_{1,4}$
[![enter image description here](https://i.sstatic.net/zwLpp.png)](https://i.sstatic.net/zwLpp.png)

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$.

**Tags:** graph-theory, graph-algorithms, independent-set, graph-classes

> **Comments:**
> **username_1**: 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: https://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.  
> **username_2**: What exactly do you mean by "augmenting graph algorithm"? Do you demand that such an algorithm should run in polynomial time?  
> **username_3**: @username_1 In this case NP-hardness simply follows from NP-hardness on cubic graphs.  
> **username_0**: @username_1 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?  
> **username_0**: @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.  
> **username_2**: Ok, then I suggest that you add this fact (polynomial running time) to the question? Btw, W[1]-hardness for $K_{1,4}$ free graphs suggests that not only that there is no polynomial-time augmenting graph algorithm but also that there is no such algorithm with FPT running time for the parameter $|H|$. Finally, what you call an augmenting graph is also called an improving swap $B\cup W$ in the local search literature.  
> **username_0**: @ChristianKomusiewicz thanks for the suggestions  

---

## 0 answers

