tag:blogger.com,1999:blog-12932458.post114659010118716616..comments2023-09-29T09:03:36.236-05:00Comments on Logicomp: Game theoretic characterization of treewidthanthonywlinhttp://www.blogger.com/profile/07618509800342861247noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-12932458.post-13891367871744439302011-06-02T11:33:25.894-05:002011-06-02T11:33:25.894-05:00Rather amusing pieceRather amusing pieceHow To Play Slot Machineshttp://how-toplayslotmachines.com/noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1149123200429814602006-05-31T19:53:00.000-05:002006-05-31T19:53:00.000-05:00Sorry for not replying earlier. Lost of papers ta...Sorry for not replying earlier. Lost of papers talk about it...a reasonable reference is <A HREF="http://www.cs.berkeley.edu/~jordan/papers/hmm.ps.Z" REL="nofollow">here</A>.halhttps://www.blogger.com/profile/02162908373916390369noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1147278330939194352006-05-10T11:25:00.000-05:002006-05-10T11:25:00.000-05:00Hal, I've heard of this before, but I never unders...Hal, I've heard of this before, but I never understood it. Could you please give me a reference to back up your claim here? Thanks.<BR/><BR/>Anthonyanthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1147221860431611342006-05-09T19:44:00.000-05:002006-05-09T19:44:00.000-05:00Furthering the previous comment, many algorithms i...Furthering the previous comment, many algorithms in statistics (statistical physics, machine learning, etc.) scale naturally with the treewidth of the underlying Markov field (viewed as a graph). Many natural problems can be expressed as graphs with small treewidths.halhttps://www.blogger.com/profile/02162908373916390369noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1147206565309978062006-05-09T15:29:00.000-05:002006-05-09T15:29:00.000-05:00There are many equivalent formulations of cops and...There are many equivalent formulations of cops and robber games. For example, the one that Seymour and Thomas use in their paper requires the robber to choose a connected component instead of a vertex. It will be great if you can specify the version of this game that you looked at.<BR/><BR/>Why is the notion of treewidth is important in CS? If you've done a bit of algorithms and complexity, you notice that proving your problem is NP-complete does not make the problem go away. Many NP-complete problems are very practical, and it's extremely important to come up with "good" algorithms for them. One approach is to restrict the problem instances under consideration (e.g. rather than consider the class of all graphs, we consider the class of all trees). As many algorithmists argue, most graphs that we look at in practice have small treewidths. Therefore, it suffices to come up with an algorithm for the problem with complexity f(k)n^c where f: N -> N is an increasing function that "does not go very fast", k is the treewidth of the input graph, n is the size of the graph, and c is a constant natural number independent of k and n. For example, f(k) = 2^k is tolerable. Many intractable graph problems become tractable when we restrict ourselves to graphs of bounded treewidth.<BR/><BR/>Another reason why treewidth is important in CS is Courcelle's theorem that says: if your graph problem is MSO-definable, then it can be solved in time f(k)n, where k and n are defined as above.<BR/><BR/>I hope this convinces you of the importance of treewidth in CS.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1147203026362322922006-05-09T14:30:00.000-05:002006-05-09T14:30:00.000-05:00Second that. A while ago I looked at this type of...Second that. <BR/>A while ago I looked at this type of game, but with cops on the ground. It's interesting to think about computing k for simple structures like grids, and to wonder whether robber speed matters.<BR/><BR/>I wonder if you could try to summarize in your experience why treewidth is important for CS. <BR/>My exposure to the concept tells me that one can often take a self-reducible graph theory (or graph-theory-like) problem, exhaustively expand the self-reduction until it hits tree-cases of the problem, then solve these efficiently; if the treewidth is bounded the expansion won't be too huge.<BR/><BR/>Is this a superficial understanding of treewidth's importance?<BR/>Thanks!Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1146747034778220042006-05-04T07:50:00.000-05:002006-05-04T07:50:00.000-05:00This is a really interesting note. I never heard o...This is a really interesting note. I never heard of this characterization.<BR/><BR/>Thank you!<BR/><BR/>Maverick WooAnonymousnoreply@blogger.com