research-article

Interval Deletion Is Fixed-Parameter Tractable

Authors:

Dániel MarxAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 11, Issue 3

Article No.: 21, Pages 1 - 35

https://doi.org/10.1145/2629595

Published: 13 January 2015 Publication History

Abstract

We study the minimum interval deletion problem, which asks for the removal of a set of at most k vertices to make a graph of n vertices into an interval graph. We present a parameterized algorithm of runtime 10^k ⋅ n^O(1) for this problem—that is, we show that the problem is fixed-parameter tractable.

References

[1]

Isolde Adler, Martin Grohe, and Stephan Kreutzer. 2008. Computing excluded minors. In Proceedings of SODA 2008. 641--650.

Digital Library

[2]

Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, and Baruch Schieber. 2001. A unified approach to approximating resource allocation and scheduling. Journal of the ACM 48, 5, 1069--1090.

Digital Library

[3]

Seymour Benzer. 1959. On the topology of the genetic fine structure. Proceedings of the National Academy of Sciences 45, 11, 1607--1620.

[4]

Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Michael T. Hallett, and Harold T. Wareham. 1995. Parameterized complexity analysis in computational biology. Computer Applications in the Biosciences 11, 1, 49--57.

[5]

Kellogg S. Booth and George S. Lueker. 1976. Testing for the consecutive ones property, interval graphs, and graph planarity using P Q-tree algorithms. Journal of Computer and System Sciences 13, 3, 335--379. A preliminary version appeared in STOC 1975.

Digital Library

[6]

Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. 1999. Graph Classes: A Survey. SIAM, Philadelphia, PA.

Digital Library

[7]

Peter Buneman. 1974. A characterization of rigid circuit graphs. Discrete Mathematics 9, 4, 205--212.

Digital Library

[8]

Leizhen Cai. 1996. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters 58, 4, 171--176.

Digital Library

[9]

Yixin Cao, Jianer Chen, and Yang Liu. 2010. On feedback vertex set: New measure and new structures. In Algorithm Theory—SWAT 2010. Lecture Notes in Computer Science, Vol. 6139. Springer, 93--104.

Digital Library

[10]

Jianer Chen, Yang Liu, Songjian Lu, Barry O'Sullivan, and Igor Razgon. 2008. A fixed-parameter algorithm for the directed feedback vertex set problem. Journal of the ACM 55, 5, Article No. 21.

Digital Library

[11]

Gabriel A. Dirac. 1961. On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 25, 1, 71--76.

[12]

Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer.

Digital Library

[13]

Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, and Saket Saurabh. 2012. Planar F-deletion: Approximation and optimal FPT algorithms. In Proceedings of FOCS 2012. IEEE, Los Alamitos, CA, 470--479.

Digital Library

[14]

Delbert R. Fulkerson and Oliver A. Gross. 1965. Incidence matrices and interval graphs. Pacific Journal of Mathematics 15, 3, 835--855.

[15]

Tibor Gallai. 1967. Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungarica 18, 1--2, 25--66. Translated by Frédéric Maffray and Myriam Preissmann in Perfect Graphs, Jorge L. Ramírez-Alfonsín and Bruce A. Reed (Eds.). Wiley, 2001, 25--66.

[16]

Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, and Ron Shamir. 1995. Four strikes against physical mapping of DNA. Journal of Computational Biology 2, 1, 139--152. cmb.1995.2.139

[17]

Martin C. Golumbic. 2004. Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, Vol. 57. North-Holland Publishing, Amsterdam, The Netherlands.

Digital Library

[18]

György Hajós. 1957. (Problem 65) Über eine Art von Graphen. Internationale Mathematische Nachrichten 11.

[19]

Haim Kaplan, Ron Shamir, and Robert E. Tarjan. 1999. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs. SIAM Journal on Computing 28, 5, 1906--1922. A preliminary version appeared in FOCS 1994.

Digital Library

[20]

Richard M. Karp. 1993. Mapping the genome: Some combinatorial problems arising in molecular biology. In Proceedings of STOC 1993 ACM, New York, NY, 278--285.

Digital Library

[21]

Ken-ichi Kawarabayashi. 2009. Planarity allowing few error vertices in linear time. In Proceedings of FOCS 2009. IEEE, Los Alamitos, CA, 639--648.

Digital Library

[22]

Ken-ichi Kawarabayashi and Bruce A. Reed. 2010. An (almost) linear time algorithm for odd cyles transversal. In Proceedings of SODA 2010.365--378.

Digital Library

[23]

David George Kendall. 1969. Incidence matrices, interval graphs and seriation in archaeology. Pacific Journal of Mathematics 28, 565--570.

[24]

Ton Kloks, Dieter Kratsch, and C. K. Wong. 1998. Minimum fill-in on circle and circular-arc graphs. Journal of Algorithms 28, 2, 272--289. A preliminary version appeared in ICALP 1996.

Digital Library

[25]

C. G. Lekkerkerker and J. Ch. Boland. 1962. Representation of a finite graph by a set of intervals on the real line. Fundamenta Mathematicae 51, 45--64.

[26]

John M. Lewis and Mihalis Yannakakis. 1980. The node-deletion problem for hereditary properties is NP-complete. Journal of Computer and System Sciences 20, 2, 219--230. Preliminary versions were independently presented in STOC 1978.

[27]

Carsten Lund and Mihalis Yannakakis. 1993. The approximation of maximum subgraph problems. In Automata, Languages, and Programming. Lecture Notes in Computer Science, Vol. 700. Springer, 40--51.

Digital Library

[28]

Dániel Marx. 2010. Chordal deletion is fixed-parameter tractable. Algorithmica 57, 4, 747--768.

Digital Library

[29]

Dániel Marx and Ildikó Schlotter. 2012. Obtaining a planar graph by vertex deletion. Algorithmica 62, 3--4, 807--822.

Digital Library

[30]

N. S. Narayanaswamy and R. Subashini. 2013. FPT algorithms for consecutive ones submatrix problems. In Parameterized and Exact Computation. Lecture Notes in Computer Science, Vol. 8246. Springer, 295--307.

[31]

Sheng-Lung Peng and Chi-Kang Chen. 2006. On the interval completion of chordal graphs. Discrete Applied Mathematics 154, 6, 1003--1010.

Digital Library

[32]

Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. 2004. Finding odd cycle transversals. Operations Research Letters 32, 4, 299--301.

Digital Library

[33]

Pim Van't Hof and Yngve Villanger. 2013. Proper interval vertex deletion. Algorithmica 65, 4, 845--867.

Digital Library

[34]

Yngve Villanger, Pinar Heggernes, Christophe Paul, and Jan Arne Telle. 2009. Interval completion is fixed parameter tractable. SIAM Journal on Computing 38, 5, 2007--2020. A preliminary version appeared in STOC 2007.

Digital Library

Cited By

Cao YYuan HWang J(2024)Modification problems toward proper (Helly) circular-arc graphsInformation and Computation10.1016/j.ic.2024.105211301(105211)Online publication date: Dec-2024
https://doi.org/10.1016/j.ic.2024.105211
Agrawal ALokshtanov DMisra PSaurabh SZehavi M(2023)Polynomial Kernel for Interval Vertex DeletionACM Transactions on Algorithms10.1145/357107519:2(1-68)Online publication date: 15-Apr-2023
https://dl.acm.org/doi/10.1145/3571075
Agrawal ABhattacharjee SJana SSahu A(2023)Parameterized complexity of perfectly matched setsTheoretical Computer Science10.1016/j.tcs.2023.113861958:COnline publication date: 22-May-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113861
Show More Cited By

Index Terms

Interval Deletion Is Fixed-Parameter Tractable
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K"1","3, the complete bipartite graph on four vertices where the two parts have one and three vertices, ...
Chordal Deletion is Fixed-Parameter Tractable

It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of k vertices or by the deletion of k edges. Here we present a uniformly polynomial-time algorithm for both problems: the running time is f(k)źnź for some constant ź ...
Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable

Given a graph G and an integer k, the Feedback Vertex Set (FVS) problem asks if there is a vertex set T of size at most k that hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 11, Issue 3

January 2015

269 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2721890

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 January 2015

Accepted: 01 April 2014

Revised: 01 January 2014

Received: 01 May 2013

Published in TALG Volume 11, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

51
Total Citations
View Citations
315
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cao YYuan HWang J(2024)Modification problems toward proper (Helly) circular-arc graphsInformation and Computation10.1016/j.ic.2024.105211301(105211)Online publication date: Dec-2024
https://doi.org/10.1016/j.ic.2024.105211
Agrawal ALokshtanov DMisra PSaurabh SZehavi M(2023)Polynomial Kernel for Interval Vertex DeletionACM Transactions on Algorithms10.1145/357107519:2(1-68)Online publication date: 15-Apr-2023
https://dl.acm.org/doi/10.1145/3571075
Agrawal ABhattacharjee SJana SSahu A(2023)Parameterized complexity of perfectly matched setsTheoretical Computer Science10.1016/j.tcs.2023.113861958:COnline publication date: 22-May-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113861
Jacob Ade Kroon JMajumdar DRaman V(2023)Deletion to scattered graph classes I - Case of finite number of graph classesJournal of Computer and System Sciences10.1016/j.jcss.2023.05.005138(103460)Online publication date: Dec-2023
https://doi.org/10.1016/j.jcss.2023.05.005
Jacob AMajumdar DRaman V(2023)Deletion to scattered graph classes II - improved FPT algorithms for deletion to pairs of graph classesJournal of Computer and System Sciences10.1016/j.jcss.2023.03.004136(280-301)Online publication date: Sep-2023
https://doi.org/10.1016/j.jcss.2023.03.004
Crespelle CDrange PFomin FGolovach P(2023)A survey of parameterized algorithms and the complexity of edge modificationComputer Science Review10.1016/j.cosrev.2023.10055648(100556)Online publication date: May-2023
https://doi.org/10.1016/j.cosrev.2023.100556
Bishnu AGhosh AKolay SMishra GSaurabh S(2023)Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data StreamsTheory of Computing Systems10.1007/s00224-023-10136-w67:6(1241-1267)Online publication date: 20-Sep-2023
https://doi.org/10.1007/s00224-023-10136-w
Ahn JKim ELee E(2022)Towards Constant-Factor Approximation for Chordal/Distance-Hereditary Vertex DeletionAlgorithmica10.1007/s00453-022-00963-784:7(2106-2133)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00453-022-00963-7
Agrawal ARamanujan M(2022)Distance from Triviality 2.0: Hybrid ParameterizationsCombinatorial Algorithms10.1007/978-3-031-06678-8_1(3-20)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-06678-8_1
Agrawal ALokshtanov DMisra PSaurabh SZehavi M(2022)Erdős–Pósa property of obstructions to interval graphsJournal of Graph Theory10.1002/jgt.22895102:4(702-727)Online publication date: 29-Sep-2022
https://doi.org/10.1002/jgt.22895
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents