We introduce a generic approach for counting subgraphs in a graph. The main idea is to relate counting subgraphs to counting graph homomorphisms. This approach provides new algorithms and unifies several well-known results in algorithms and combinatorics, including the recent algorithm of Björklund, Husfeldt, and Koivisto for computing the chromatic polynomial, the classical algorithm of Kohn et al. for counting Hamiltonian cycles, Ryser's formula for counting perfect matchings of a bipartite graph, and color-coding-based algorithms of Alon, Yuster, and Zwick. By combining our method with known combinatorial bounds, ideas from succinct data structures, partition functions, and the color coding technique, we obtain the following new results. The number of optimal bandwidth permutations of a graph on n vertices excluding a fixed graph as a minor can be computed in time $ 2^{n+o(n)} $, in particular, in time $\mathcal{O}(2^{n}n^3)$ for trees and in time $2^{n+\mathcal{O}(\sqrt{n})}$ for planar graphs. Counting all maximum planar subgraphs, subgraphs of bounded genus, or more generally subgraphs excluding a fixed graph M as a minor can be done in $2^{\mathcal{O}(n)}$ time. Counting all subtrees with a given maximum degree (a generalization of counting Hamiltonian paths) of a given graph can be done in time $2^{\mathcal{O}(n)}$. A generalization of Ryser's formula is, Let G be a graph with an independent set of size $\ell$. Then the number of perfect matchings in G can be found in time $\mathcal{O}(2^{n-\ell} n^3)$. Let ${\cal H}$ be a graph class excluding a fixed graph M as a minor. Then the maximum number of vertex disjoint subgraphs from ${\cal H}$ in a graph G on n vertices can be found in time $2^{\mathcal{O}(n)}$. In order to show this, we prove that there exists a constant $c_M$ depending only on M such that the number of nonisomorphic n-vertex graphs in ${\cal H}$ is at most $c_M^n$. Let F be a k-vertex graph of treewidth t and let G be an n-vertex graph. A subgraph of G isomorphic to F (if one exists) can be found in $\mathcal{O}(4.32^k \cdot k \cdot t \cdot n^{t+1})$ expected time using $\mathcal{O}(\log{k} \cdot n^{t+1})$ space.

It is an intriguing question to see what kind of information on the structure of an oriented graph D one can obtain if D does not contain a fixed oriented graph H as a subgraph. The related question in the unoriented case has been an active area of research and is relatively well understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs and provide some results on the global behavior of the orientation of D. For the case where H is an oriented four-cycle we prove the following: in every H-free oriented graph D, there is a pair $A,B\subseteq V(D)$ such that $e(A,B)\geq e(D)^{2}/32|D|^{2}$ and $e(B,A)\leq e(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case where H is an oriented six-cycle and a more precise result in the case where D is dense and H is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph D, and we provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.

We consider the problem of reconstructing a compact 3-manifold (with boundary) embedded in ℜ3 from its crosssections with a given set of cutting planes having arbitrary orientations. Under appropriate sampling conditions that are satisfied when the set of cutting planes is dense enough, we prove that the algorithm presented by Liu et al. in [LBD+08] preserves the homotopy type of the original object. Using the homotopy equivalence, we also show that the reconstructed object is homeomorphic (and isotopic) to the original object. This is the first time that shape reconstruction from cross-sections comes with such theoretical guarantees.

In this article, we study a combinatorial optimization problem arising from on-board networks in satellites. In these kinds of networks, the entering signals (inputs) should be routed to amplifiers (outputs). The connections are made via expensive switches with four available links. The paths connecting inputs to outputs should be link-disjoint. More formally, we call a (p, λ, k)-network an undirected graph with p + λ inputs, p + k outputs, and internal vertices of degree four. A (p, λ, k)-network is valid if it is tolerant to a restricted number of faults in the network, i.e., if, for any choice of at most λ faulty inputs and k faulty outputs, there exist p edge-disjoint paths from the remaining inputs to the remaining outputs. Our optimization problem consists of determining N(p, λ, k), the minimum number of vertices in a valid (p, λ, k)-network. We present validity certificates and a quasi-partitioning technique from which we derive lower bounds for N(p, λ, k). We also provide constructions, and hence upper bounds, based on expanders. The problem is shown to be sensitive to the order of λ and k. For instance, when λ and k are small compared with p, the question reduces to the avoidance of some forbidden local configurations. For larger values of λ and k, the problem is to find graphs with a good expansion property for small sets. This leads us to introduce a new parameter called α-robustness. We use α-robustness to generalize our constructions for larger values of k and λ. In many cases, we provide asymptotically tight bounds for N(p, λ, k). © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We introduce the notion of (A, B)-colouring of a graph: For given vertex sets A, B, this is a colouring of the vertices in B so that both adjacent vertices and vertices with a common neighbour in A receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of plane graphs. We prove a general result which implies asymptotic versions of Wegner's and Borodin's Conjecture on these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs and then use Kahn's result that the list chromatic index is close from the fractional chromatic index. Our results are based on a strong structural lemma for planar graphs which also implies that the size of a clique in the square of a planar graph of maximum degree Δ is at most Δ plus a constant.

We present a result concerning the relation between the path-width of a plane graph and the path-width of its dual. We prove that for a 3-connected planar graph G, ${\rm pw}(G)\leq3{\rm pw}(G^*)+2$. For 4-connected planar graphs, and more generally for Hamiltonian planar graphs, we prove a stronger bound ${\rm pw}(G^*)\leq2~{\rm pw}(G)+c$. The best previously known bound was obtained by Fomin and Thilikos who proved that ${\rm pw}(G^*)\leq6~{\rm pw}(G)+c$. Our proof is based on a transformation which, given a fixed spanning tree of G, sends any given decomposition of G into one of $G^*$. The ratio of the corresponding parameters is bounded by the maximum degree of the spanning tree.

Covering problems are fundamental classical problems in optimization, computer science and complexity theory. Typically an input to these problems is a family of sets over a finite universe and the goal is to cover the elements of the universe with as few sets of the family as possible. The variations of covering problems include well known problems like Set Cover, Vertex Cover, Dominating Set and Facility Location to name a few. Recently there has been a lot of study on partial covering problems, a natural generalization of covering problems. Here, the goal is not to cover all the elements but to cover the specified number of elements with the minimum number of sets.