Exact arborescences, matchings and cycles (Q1095157): Difference between revisions

Given a graph in which each edge has an integral weight, an exact problem is to determine whether a desired structure exists for which the sum of the edge weights is exactly k for some specified k. Given a directed graph with a specified vertex r, an arborescence rooted at r is a set of arcs which induce a connected directed subgraph such that r has indegree zero and all other vertices have indegree one. The existence of polynomial algorithms is shown for exact arborescence, exact spanning tree, exact perfect matching in planar graphs, and exact cycle sum for a class of planar directed graphs.