Timeline for Counting subgraphs of bipartite graphs
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2014 at 2:16 | comment | added | Alessandro Cosentino | A fresh reference for the general case (non necessarely bipartite): arxiv.org/abs/1410.3375 @TsuyoshiIto Maybe from this paper #P-completeness is more clear than the one citeb by the OP | |
| Jan 16, 2011 at 8:34 | comment | added | Yaroslav Bulatov | You can count the number of subgraphs with $m$ edges and $n$ vertices in polynomial time on bounded tree width graphs. | |
| Oct 4, 2010 at 4:41 | comment | added | Harrison Brown | Note that this is equivalent to computing the sum, over all order-m subsets of $V(G)$, of (-1) to the size of the induced subgraph on that subset. Believe it or not, similar sums have arisen in my research, which are related to counting graph homomorphisms. I'll have to think on whether it's possible to get a reduction to #3-COL in this way. | |
| Oct 3, 2010 at 19:32 | answer | added | Fiktor | timeline score: 1 | |
| Aug 3, 2010 at 12:00 | comment | added | Tsuyoshi Ito | I cannot see how to apply the results by Creignou, Schnoor and Schnoor to prove the #P-completeness of the case of general graphs (not necessarily bipartite). Can you elaborate a little bit? | |
| Mar 10, 2010 at 6:18 | comment | added | Carter Tazio Schonwald | Question, are we picking m vertices and seeing if the set of induced edges that connect pairs of these vertices is of odd size, or are we picking an odd number of edges from the graph and checking if the set of vertices induced in this graph is of order m? as for your square lattice case, I want to guess than perhaps something involving the structure of the associated dual graphs would prove helpful (eg in the infinite case this lattice is selfdual). | |
| Feb 4, 2010 at 9:13 | answer | added | Gerhard Paseman | timeline score: 0 | |
| Jan 19, 2010 at 23:42 | comment | added | Emil | Similar problems are #P-complete, for example counting the number of induced subgraphs with m edges in a bipartite graph. (A reduction from 1-in-3 monotone 3-SAT springs to mind.) However, the result by Ehrenfeucht & Karpinksi suggests that there could be an efficient algorithm. | |
| Jan 19, 2010 at 18:57 | comment | added | Joseph Malkevitch | While probably not specialized enough to answer this particular question about bipartite graphs, there is a nice book which is "restricted" to the properties of bipartite graphs: Bipartite Graphs and Their Applications A. Asratian, T. Denley, R. Haggkvist, Cambridge U. Press., 1998. | |
| Jan 19, 2010 at 13:55 | history | asked | AlastairK | CC BY-SA 2.5 |