A leaf power graph is the graph formed from the leaves of a tree by making two leaves adjacent when their tree distance is at most k. We show that recognizing these graphs is fixed-parameter tractable in a combination of two parameters: k and the degeneracy of the graph.
(James Nastos has pointed out a minor error in our statement of known prior results: the figure depicting chordal graphs that are not 4-leaf powers is labeled as a complete set of forbidden subgraphs, but it is only the complete set among graphs without true twin vertices.)
Given a partially ordered set of activities, we find in polynomial time a directed acyclic graph and a mapping from activities to its edges, such that the sequences of activities along paths in the graph are exactly the totally ordered subsets of activities in the input.
We provide a partial classification of the complexity of parameterized graph problems of the form "find a \(k\)-vertex induced subgraph with property \(X\) in a larger subgraph with property \(Y\)", in terms of the existence of large cliques and large independent sets in the graphs with properties \(X\) and \(Y\).
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.