Skip to main content
deleted 205 characters in body
Source Link
Vor
  • 12.7k
  • 1
  • 30
  • 62

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way: for each node $v_i$ add a tail of $k$ new nodes.

  • check trivial case $|V| < 3$
  • recursively remove degree 1 nodes from $G$ (existing tails)
  • for each remaining degree >1 node $v_i$ add a tail of $k$ new nodes

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Removed nodes cannot be part of a clique in G, so $G'$ contains all cliques of $G$; addedAdded nodes cannot introduce new cliques on G′, so $G$ contains allexactly the same cliques of $G'$.

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way:

  • check trivial case $|V| < 3$
  • recursively remove degree 1 nodes from $G$ (existing tails)
  • for each remaining degree >1 node $v_i$ add a tail of $k$ new nodes

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Removed nodes cannot be part of a clique in G, so $G'$ contains all cliques of $G$; added nodes cannot introduce new cliques on G′, so $G$ contains all cliques of $G'$.

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way: for each node $v_i$ add a tail of $k$ new nodes.

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Added nodes cannot introduce new cliques on G′, so $G$ contains exactly the same cliques of $G'$.

added 52 characters in body
Source Link
Vor
  • 12.7k
  • 1
  • 30
  • 62

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way:

  • check trivial case $|V| < 3$
  • recursively remove degree 1 nodes from $G$ (existing tails)
  • for each remaining degree >1 node $v_i$ add a tail of $k$ new nodes

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Removed nodes cannot be part of a clique in G, so $G'$ contains all cliques of $G$; added nodes cannot introduce new cliques on G′, so $G$ contains all cliques of $G'$.

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way:

  • remove degree 1 nodes from $G$
  • for each degree >1 node $v_i$ add a tail of $k$ new nodes

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Removed nodes cannot be part of a clique in G, so $G'$ contains all cliques of $G$; added nodes cannot introduce new cliques on G′, so $G$ contains all cliques of $G'$.

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way:

  • check trivial case $|V| < 3$
  • recursively remove degree 1 nodes from $G$ (existing tails)
  • for each remaining degree >1 node $v_i$ add a tail of $k$ new nodes

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Removed nodes cannot be part of a clique in G, so $G'$ contains all cliques of $G$; added nodes cannot introduce new cliques on G′, so $G$ contains all cliques of $G'$.

Source Link
Vor
  • 12.7k
  • 1
  • 30
  • 62

You can reduce CLIQUE ($G$ has a clique of size $k$) to KITE: given $G=(V,E)$ and $k$, just build in polynomial time a new graph $G'$ in this way:

  • remove degree 1 nodes from $G$
  • for each degree >1 node $v_i$ add a tail of $k$ new nodes

If $G'$ has a kite of size $2k$ then the $G$ has a clique of size $k$ (the kite without the tail). Removed nodes cannot be part of a clique in G, so $G'$ contains all cliques of $G$; added nodes cannot introduce new cliques on G′, so $G$ contains all cliques of $G'$.