My question is regarding the algebraic formulation for packing problems in graphs. Taking an example, suppose I am interested in the problem of finding if there is a packing of k edge disjoint triangles in a given input (undirected) graph. I am aware of techniques that approach this problem combinatorially. Is there a way to frame this problem algebraically?Also, in context of graph theory, are algebraic methods less powerful when compared to combinatorial methods? Or is there any particular intuition that governs which approach is more effective in certain problems? I apologize if my question sounds too general. The purpose of this question is to try and form an understanding of algebraic vs combinatorial methods in the context of graph theory.
Algebraic formulation for packing problem
ds.algorithms;graph theory;graph algorithms;approximation algorithms;fixed parameter tractable
It is possible to prove the fixed-parameter tractability of various graph-theoretical problems (e.g., finding a path of length k or finding k disjoint triangles) using algebraic techniques by reducing the problem to questions about certain polynomials. See for example the following very readable paper by Ryan Williams:http://arxiv.org/abs/0807.3026v3and some other related papers:http://www.cs.cmu.edu/~jkoutis/papers/MultilinearDetection.pdfhttp://doi.ieeecomputersociety.org/10.1109/FOCS.2010.24http://arxiv.org/abs/0912.2371About your meta question: as the formulation of graph-theoretical problems is usually combinatorial, it is not surprising to me that most of the natural approaches are combinatorial rather than algebraic. The algebraic approaches work only if the problem has some unexpected connection with algebra, which is probably quite rare for natural combinatorial problems. In the above-mentioned papers, such a connection is discovered, allowing us to solve the problem using algebraic techniques. Interestingly, for these problems the algebraic algorithms are faster (have better bounds) than the combinatorial ones.