1
$\begingroup$

I'm interested to know whether there has been any work done on the problem in the title. For the problem to be meaningful, we would naturally need that the hyperedges must have large ($\omega(1)$) size, otherwise there would be zero-degree vertices.

Any references to algorithmic results that would be helpful in such a scenario would also be appreciated, as are results to other generalizations of colouring such as rainbow colouring and list colouring.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ There is a poly-time reduction from graph coloring to graph coloring with $o(n)$ edges. (Given a graph with $\hat n$ nodes, just add $\hat n^2$ zero-degree nodes.) As you point out, this is not very meaningful, so presumably you want to add the restriction that there are no zero-degree nodes. But even with that restriction, surely the problem remains NP-hard by a similar reduction. What kind of works are you interested in? Approximation algorithms / hardness of approximation? $\endgroup$
    – Neal Young
    May 8, 2020 at 13:56
  • $\begingroup$ Thank you. I guess such a reduction would work as long as the number of edges is restricted to be $O(n^c)$ for some $c>0$. But as I understand it, your reduction would not work for $O(\log n)$ edges, because we would need to add exponentially many new variables. Do you have any idea about what to do for this case? I considered trying to come up with an ILP formulation, but the ones I came up with had too many variables to solve in poly-time. $\endgroup$
    – gov
    May 9, 2020 at 6:31
  • $\begingroup$ Since the problem I am interested in can be reduced from similar instances, I am primarily interested in a hardness of approximation. But approximation algorithms are also useful to me, as I could try to see what restriction I would need on my problem so as to reduce to colouring. $\endgroup$
    – gov
    May 9, 2020 at 6:31
  • $\begingroup$ If you're interested in the case with $O(\log n)$ edges, it might help to edit the post and title to reflect that. It could make it more likely that someone who knows something about it will take a look. $\endgroup$
    – Neal Young
    May 9, 2020 at 12:05
  • $\begingroup$ Yes, I've modified it. I was unaware that the hardness for $O(n)$ edges would translate to the hardness for $O(n^c)$ edges, for any constant $c$, thank you for your comment. $\endgroup$
    – gov
    May 9, 2020 at 12:18

0

Reset to default

Your Answer

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