Graph editing problems with extended regularity constraints

DOI10.1016/J.TCS.2017.03.019zbMATH Open1370.68137arXiv1510.03482OpenAlexW2242403838MaRDI QIDQ526874FDOQ526874

Luke Mathieson

Publication date: 15 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: Graph editing problems offer an interesting perspective on sub- and supergraph identification problems for a large variety of target properties. They have also attracted significant attention in recent years, particularly in the area of parameterized complexity as the problems have rich parameter ecologies. In this paper we examine generalisations of the notion of editing a graph to obtain a regular subgraph. In particular we extend the notion of regularity to include two variants of edge-regularity along with the unifying constraint of strong regularity. We present a number of results, with the central observation that these problems retain the general complexity profile of their regularity-based inspiration: when the number of edits $k$ and the maximum degree $r$ are taken together as a combined parameter, the problems are tractable (i.e. in FPT{}), but are otherwise intractable. We also examine variants of the basic editing to obtain a regular subgraph problem from the perspective of parameterizing by the treewidth of the input graph. In this case the treewidth of the input graph essentially becomes a limiting parameter on the natural $k+r$ parameterization.

Full work available at URL: https://arxiv.org/abs/1510.03482

zbMATH Keywords

computational complexitygraph algorithmsparameterized complexitygraph editing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fundamentals of parameterized complexity
• Paths, Trees, and Flowers
• Parameterized complexity of finding regular induced subgraphs
• On problems without polynomial kernels
• Maximum \(k\)-regular induced subgraphs
• Tractable cases of the extended global cardinality constraint
• Parametrized complexity theory.
• On the completeness of a generalized matching problem
• Maximum matching and a polyhedron with 0,1-vertices
• Combinatorial optimization. Theory and algorithms.
• Looking at the stars
• The polynomial-time hierarchy
• General factors of graphs
• Editing to a graph of given degrees
• Editing to a Connected Graph of Given Degrees
• Editing graphs to satisfy degree constraints: a parameterized approach
• A Short Proof of the Factor Theorem for Finite Graphs
• Graph isomorphism parameterized by elimination distance to bounded degree
• Deciding first-order properties of locally tree-decomposable structures
• Deciding whether a planar graph has a cubic subgraph is NP-complete
• On locating cubic subgraphs in bounded-degree connected bipartite graphs
• Finding regular subgraphs in both arbitrary and planar graphs
• The complexity of regular subgraph recognition
• A note on the complexity of finding regular subgraphs
• Finding a \(\Delta\)-regular supergraph of minimum order
• Spanning subgraphs with specified valencies
• The factorization of graphs. II
• Parameterized complexity of three edge contraction problems with degree constraints
• The parameterized complexity of editing graphs for bounded degeneracy
• Win-Win Kernelization for Degree Sequence Completion Problems
• Editing to a planar graph of given degrees

Cited In (4)

• Fixed-parameter tractable distances to sparse graph classes
• A survey of parameterized algorithms and the complexity of edge modification
• Editing to a planar graph of given degrees
• Graph editing to a given neighbourhood degree list is fixed-parameter tractable

This page was built for publication: Graph editing problems with extended regularity constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q526874)