11
$\begingroup$

Given a complete graph $G$, an arbitrary graph $H$, and a positive integer $n$, are there subgraphs $A_1,\dots,A_n$ of $G$ (not necessarily disjoint) such that their union is $G$, and each of them are isomorphic to $H$?

This is a problem which I believe is NP-complete, but I am unsure if it is actually so. Any ideas of how to prove this?

Notes:

  • If $G$ is instead allowed to be an arbitrary graph, then this is clearly at least as hard as subgraph isomorphism, which is NP-complete.
  • If $G$ is allowed to be an arbitrary graph, and $A_1,\dots,A_n$ are required to be isomorphic to a subgraph of $H$, instead of the entire graph $H$, then the problem can be reduced from vertex cover (which is NP-complete) by setting $H$ to be a star graph with the number of spokes equal to the number of nodes in $G$.
  • The problem where $H$ must also be a complete graph is called "covering design", and has some discussion here, with closed forms for when $H$ has 3 or 4 nodes. Finding algorithm for this is apparently an open problem.
Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ If $G=K_m$, is $m$ given in binary or unary? $\endgroup$
    – Wei Zhan
    Mar 12, 2018 at 17:19
  • $\begingroup$ @WillardZhan I didn't think about it before. (I mainly thought about cases where $H$ is nearly as large as $G$.) Let's say I'm interested in answers of either variant. $\endgroup$
    – Theemathas Chirananthavat
    Mar 12, 2018 at 20:28
  • 2
    $\begingroup$ Another special case that looks hard (an open problem since 1967) is when $H$ is a collection of vertex-disjoint cycles: en.wikipedia.org/wiki/Oberwolfach_problem $\endgroup$
    – j_random_hacker
    Mar 13, 2018 at 14:51
  • 1
    $\begingroup$ Do you mean a subgraph by a subgraph induced by a subset of vertices of $G$ (which is the definition used in subgraph isomorphism problem)? How do you define the union of two subgraphs? $\endgroup$
    – xskxzr
    Oct 27, 2018 at 19:12

0

Reset to default

Your Answer

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