Timeline for A question on linear extensions of partial orders

9 events

when toggle format	what		by	license	comment
Jul 2, 2012 at 7:44	history	edited	Kaveh		edited tags
Jun 29, 2012 at 22:35	history	tweeted			twitter.com/#!/StackCSTheory/status/218835003998609408
Jun 29, 2012 at 20:41	comment	added	Suresh Venkat		In my variation each subsequence has length exactly 4, so Yury's answer kicks in. My only hope at this point is that the subsequences have very special structure and are related to each other, so maybe something specific to the problem would help. But there's no general hammer.
Jun 29, 2012 at 20:40	vote	accept	Suresh Venkat
Jun 29, 2012 at 19:56	comment	added	Chandra Chekuri		You are right of course, me not thinking straight.
Jun 29, 2012 at 19:52	comment	added	David Eppstein		Er, every undirected graph can be oriented to be a DAG. Just choose an ordering of the vertices and use that ordering to orient the edges.
Jun 29, 2012 at 19:51	answer	added	Yury		timeline score: 14
Jun 29, 2012 at 19:32	comment	added	Chandra Chekuri		If each of the sequences are of length $2$ then one can think of each sequence as an undirected edge and we are asking whether an undirected graph can be oriented to be a DAG - iff if there is no cycle. But a greedy algorithm also works. Start with an edge and orient it arbitrarily and keep going as long as you can and if you get stuck you know it is not possible. Did you try that for your variation? Seems like it may work.
Jun 29, 2012 at 19:16	history	asked	Suresh Venkat	CC BY-SA 3.0