7
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ I do not know what you mean by algebraic methods, but linear programming is used very, very often (approximation, branch and bound, branch and cut, …) to solve various combinatorial optimization problems, and I would be surprised if it is not used for the particular problem you mentioned. $\endgroup$ – Tsuyoshi Ito Feb 4 '12 at 0:32
  • $\begingroup$ Probably, it'd be helpful if you gave us an example of algebraic methods and combinatorial methods in the context of graph theory. $\endgroup$ – Yoshio Okamoto Feb 4 '12 at 1:35
  • $\begingroup$ Consider the kernelization of vertex cover problem (FPT version). Using a Linear programming approach, we can obtain a linear kernel of size 2k. At the same time, a technique like Crown Decomposition of Graphs can be used to get a kernel of 3k. I think I used the term "algebraic" to refer to the former techniques (LP, ILP) and the term "combinatorial" for techniques like Crown Decompositions. That was my notion of algebraic and combinatorial techniques which might be very loose and not precise. $\endgroup$ – Nikhil Feb 4 '12 at 2:04
  • $\begingroup$ (Continued from previous comment): Apart from the packing problem formulation, I am interested in knowing if there is some intuition governing that why would I want to use one approach over another. Or does it depend mainly on the properties/structure of the concerned problem? $\endgroup$ – Nikhil Feb 4 '12 at 2:06
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the references and for clarifying on my doubt related to the algebraic-combinatorial approaches. This answer was really helpful. $\endgroup$ – Nikhil Feb 5 '12 at 21:28
  • $\begingroup$ I looked at the RW paper & it seems to have nothing specifically on k disjoint triangles. is there some connection thats not outlined in the paper? do any of the others talk about k disjoint triangles in particular? (they dont in abstracts) $\endgroup$ – vzn Feb 6 '12 at 17:26
  • $\begingroup$ The link for the last paper was wrong, sorry (fixed now). The RW paper deals with finding paths, which was generalized to finding trees and then to finding bounded-treewidth subgraphs in the last paper. The graph formed by the union of k disjoint triangles has treewidth 2, thus in particular finding k disjoint triangles is covered by the last paper. $\endgroup$ – Daniel Marx Feb 6 '12 at 20:39
5
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Though I have not much idea about the "subset convolution" technique but thanks for mentioning it and the paper references. I will give it a look. $\endgroup$ – Nikhil Feb 7 '12 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.