2006/04/24 by Gregory Gutin, Stefan Szeider, Gutin, Gregory +3 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0604095
arxiv created 2006/04/24 · openalex publication_date 2006/04/24 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a graph. An ordering of G is a bijection α: V\dom \1,2,..., |V|\. For a vertex v in G, its closed neighborhood is N[v]=\u∈ V: uv∈ E\∪ \v\. The profile of an ordering α of G is \prfα(G)=∑v∈ V(α(v)-min\α(u): u∈ N[v]\). The profile \prf(G) of G is the minimum of \prfα(G) over all orderings α of G. It is well-known that \prf(G) is the minimum number of edges in an interval graph H that contains G is a subgraph. Since |V|-1 is a tight lower bound for the profile of connected graphs G=(V,E), the parametrization above the guaranteed value |V|-1 is of particular interest. We show that deciding whether the profile of a connected graph G=(V,E) is at most |V|-1+k is fixed-parameter tractable with respect to the parameter k. We achieve this result by reduction to a problem kernel of linear size.