Algebraic formulation for packing problem

Question

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.

Answer 1

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.3026v3

and some other related papers:

http://www.cs.cmu.edu/~jkoutis/papers/MultilinearDetection.pdf

http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.24

http://arxiv.org/abs/0912.2371

About 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.

Answer 2

There are algebraic formalizations of combinatorial problems. Combinatorial problems can be transferred to a problem of solvability of a system of polynomials. For instance, Bayer was able to model 3-colorability using a system of polynomial equations.

Here is an excerpt of the abstract of Hilbert’s Nullstellensatz and an Algorithm for Proving Combinatorial Infeasibility:

"Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K."

Answer 3

In exact exponential algorithmics, the subset convolution is a particularly useful algebraic technique for solving covering, packing and partitioning problems. It generally works very well when the objects to be packed are 'hard', like dominating or independent sets. For example, the best known $k$-colouring (i.e. partition into independent sets) algorithm uses subset convolution. See e.g. Exact Exponential Algorithms by Fomin and Kratsch or this paper by Björklund et al.

The subset convolution is most often used in the context of exponential algorithms, but there are some useful applications in polynomial side of things. In particular, see this paper for the so-called 'counting in halves' approach to packing problems.

My intuition is that since the subset convolution -type methods count the number of solutions instead of finding just one, they usually cannot be used to obtain fixed parameter algorithms. Also, they are rather space-intensive; their space complexity often equals their time complexity.