I am looking for a simple example of a charging scheme. That is, one that will take 1-2 minutes to explain in a talk. I know of one such example, though it concerns a geometric question, while I hope to find something more graph-theoretic.

My geometric example is about upper bounding the complexity of an envelope of squares, (that is, how many vertices can appear in the union of $n$ squares, counting only vertices that are on the border / not contained in the interior of another square). We allow the squares to have different sizes. A vertex on the envelope is either a vertex of a square or an intersection point of two squares, and thus, we immediately obtain a quadratic upper bound. A very simple charging scheme yields a linear bound.

We wish to charge every vertex of the envelope to a vertex of a square, such that every square vertex will be charged at most twice. This will immediately imply that there are at most $8n$ vertices on the envelope. A vertex of the envelope that is also a vertex of a square will charge itself. Let $p$ be a vertex of the envelope that is formed by the intersection of the squares $A,B$ such that $A$ is larger or equal to $B$. We travel from $p$ along the edge of $B$ in the direction that enters the interior of $A$, and charge the vertex of $B$ that is at the end of this edge. By drawing this, it is easy to verify that every vertex is indeed charged at most twice.

I hope that you will agree that this charging scheme can be explained in a talk in 1-2 minutes. Are there any such simple graph-theoretic examples?

Many thanks, Adam

  • 5
    $\begingroup$ This might be too trivial, but the proof that the total degree of a graph is twice the number of edges is a really simple charging argument (imagine each vertex dropping a coin on an adjacent edge - that's how I explained it in class once). More generally, the proof that a planar graph has at most 3n-6 edges, or that a bipartite planar graph has 2n-4, is also via a charging argument applied to Euler's theorem $\endgroup$ – Suresh Venkat Jul 19 '12 at 17:35
  • $\begingroup$ another fairly trivial example: a connected tree on $n$ vertices has $n-1$ edges. order the vertices by levels, where the (arbitrary) root has level 0. charge an edge to the higher-level vertex. you need to verify that no edge is between vertices on the same level, no vertex is charged twice, and the root is not charged. the proof by induction is easier though..but maybe this gives more intuition $\endgroup$ – Sasho Nikolov Jul 20 '12 at 1:31
  • 2
    $\begingroup$ Another simple charging scheme is to show that the greedy algorithm for the maximum independent set problem outputs $n/\Delta$ nodes where $\Delta$ is the maximum degree. The bound can refined to show $n/(2\Delta)$ where $\Delta$ is the average degree. $\endgroup$ – Chandra Chekuri Jul 20 '12 at 2:50
  • $\begingroup$ A less trivial example might be the analysis of the greedy algorithm for set cover, showing the log n approximation ratio. $\endgroup$ – Suresh Venkat Jul 20 '12 at 22:08

Your Answer

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

Browse other questions tagged or ask your own question.