Timeline for Algorithm to evaluate "connectedness" of a binary matrix

10 events

when toggle format	what		by	license	comment
Jun 29 at 13:19	vote	accept	Fabius Wiesner
Jun 28 at 21:37	history	became hot network question
Jun 28 at 20:28	history	edited	RobPratt		edited tags
Jun 28 at 20:20	answer	added	RobPratt		timeline score: 4
Jun 28 at 19:27	history	edited	RobPratt	CC BY-SA 4.0	added 2 characters in body
Jun 28 at 17:07	answer	added	Max Alekseyev		timeline score: 4
Jun 28 at 15:19	history	edited	Fabius Wiesner	CC BY-SA 4.0	Added generalization of the problem.
Jun 28 at 14:02	comment	added	Daniel Weber		We can define a graph over the columns, where two columns are connected if their union isn't $[m]$. The condition is exactly that there aren't two connected nodes with one in $C_1$ and one in $C_2$. This condition can be realized as a 2-SAT instance, but I'm not sure how you can optimize $(1 + \|C_1\|)(1 + \|C_2\|)$ over it.
Jun 28 at 13:45	history	edited	Fabius Wiesner	CC BY-SA 4.0	added 13 characters in body
Jun 28 at 13:34	history	asked	Fabius Wiesner	CC BY-SA 4.0