<p>In exact exponential algorithmics, the <em>subset convolution</em> 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. <em>Exact Exponential Algorithms</em> by Fomin and Kratsch or <a href="http://arxiv.org/abs/cs/0611101" rel="nofollow">this paper</a> by Björklund et al.</p>

<p>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 <a href="http://www.springerlink.com/content/x8m81u423t1r0063/" rel="nofollow">this paper</a> for the so-called 'counting in halves' approach to packing problems.</p>

<p>My intuition is that since the subset convolution -type methods <em>count</em> 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.</p>

CC BY-SA 3.0
2012-02-07T20:12:29.593Z
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.
Nikhil
CC BY-SA 3.0
2012-02-07T12:24:51.833Z
2012-02-07T12:24:51.833Z
Janne H. Korhonen
<p>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.</p>

<p>Here is an excerpt of the abstract of <a href="http://www.math.ucdavis.edu/~deloera/RECENT_WORK/nulla_issac_10.pdf">Hilbert’s Nullstellensatz and an Algorithm
for Proving Combinatorial Infeasibility</a>:</p>

<blockquote>
  <p>"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."</p>
</blockquote>

CC BY-SA 3.0
2012-02-05T20:19:18.537Z
2012-02-05T20:19:18.537Z
Mohammad Al-Turkistany
<p>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:</p>

<p><a href="http://arxiv.org/abs/0807.3026v3">http://arxiv.org/abs/0807.3026v3</a></p>

<p>and some other related papers:</p>

<p><a href="http://www.cs.cmu.edu/~jkoutis/papers/MultilinearDetection.pdf">http://www.cs.cmu.edu/~jkoutis/papers/MultilinearDetection.pdf</a></p>

<p><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.24">http://doi.ieeecomputersociety.org/10.1109/FOCS.2010.24</a></p>

<p><a href="http://arxiv.org/abs/0912.2371">http://arxiv.org/abs/0912.2371</a></p>

<p>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.</p>

CC BY-SA 3.0
2012-02-05T21:28:05.643Z
Thanks for the references and for clarifying on my doubt related to the algebraic-combinatorial approaches. This answer was really helpful.
Nikhil
CC BY-SA 3.0
2012-02-06T17:26:14.280Z
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)
vzn
CC BY-SA 3.0
2012-02-06T20:39:03.507Z
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.
Daniel Marx
CC BY-SA 3.0
2012-02-05T20:52:32.907Z
2012-02-06T20:35:15.370Z
2012-02-06T20:35:15.370Z
Daniel Marx
<p>My question is regarding the algebraic formulation for packing problems in graphs. </p>

<p>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?</p>

<p>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? </p>

<p>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.</p>

CC BY-SA 3.0
2012-02-04T00:32:53.917Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-02-04T01:35:48.037Z
Probably, it'd be helpful if you gave us an example of algebraic methods and combinatorial methods in the context of graph theory.
Yoshio Okamoto
CC BY-SA 3.0
2012-02-04T02:04:50.807Z
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.
Nikhil
CC BY-SA 3.0
2012-02-04T02:06:09.747Z
(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?
Nikhil
<ds.algorithms><graph-theory><graph-algorithms><approximation-algorithms><fixed-parameter-tractable>
Algebraic formulation for packing problem
Nikhil
# Algebraic formulation for packing problem

(Asked by: username_0 on 2012-02-03)

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.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, approximation-algorithms, fixed-parameter-tractable
> **Comments:**
> **username_1**: 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.  
> **username_2**: Probably, it'd be helpful if you gave us an example of algebraic methods and combinatorial methods in the context of graph theory.  
> **username_0**: 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.  
> **username_0**: (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?  

---

## 3 answers

### Answer by username_5 on 2012-02-05. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks for the references and for clarifying on my doubt related to the algebraic-combinatorial approaches. This answer was really helpful.  
> **username_6**: 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)  
> **username_5**: 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.  

---

### Answer by username_4 on 2012-02-05. Score: 5

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](http://www.math.ucdavis.edu/~deloera/RECENT_WORK/nulla_issac_10.pdf):

> "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 by username_3 on 2012-02-07. Score: 4

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](http://arxiv.org/abs/cs/0611101) 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](http://www.springerlink.com/content/x8m81u423t1r0063/) 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.

> **Comments:**
> **username_0**: 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.  

---

