Yixin Cao
Dániel Marx
Skip Abstract Section
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 10k ⋅ nO(1) for this problem—that is, we show that the problem is fixed-parameter tractable.
- Isolde Adler, Martin Grohe, and Stephan Kreutzer. 2008. Computing excluded minors. In Proceedings of SODA 2008. 641--650. DOI:http://dx.doi.org/10.1145/1347082.1347153 Google Scholar
Digital Library
- 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. DOI:http://dx.doi.org/10.1145/502102.502107 Google ScholarDigital Library
- Seymour Benzer. 1959. On the topology of the genetic fine structure. Proceedings of the National Academy of Sciences 45, 11, 1607--1620.Google ScholarCross Ref
- 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. DOI:http://dx.doi.org/10.1093/bioinformatics/11.1.49Google Scholar
- 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. DOI:http://dx.doi.org/10.1016/S0022-0000(76)80045-1 A preliminary version appeared in STOC 1975. Google ScholarDigital Library
- Andreas Brandstädt, Van Bang Le, and Jeremy P. Spinrad. 1999. Graph Classes: A Survey. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Peter Buneman. 1974. A characterization of rigid circuit graphs. Discrete Mathematics 9, 4, 205--212. DOI:http://dx.doi.org/10.1016/j.dam.2008.07.004 Google ScholarDigital Library
- Leizhen Cai. 1996. Fixed-parameter tractability of graph modification problems for hereditary properties. Information Processing Letters 58, 4, 171--176. DOI:http://dx.doi.org/10.1016/0020-0190(96)00050-6 Google ScholarDigital Library
- 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. DOI:http://dx.doi.org/10.1007/978-3-642-13731-0_10 Google ScholarDigital Library
- 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. DOI:http://dx.doi.org/10.1145/1411509.1411511 Google ScholarDigital Library
- Gabriel A. Dirac. 1961. On rigid circuit graphs. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 25, 1, 71--76. DOI:http://dx.doi.org/10.1007/BF02992776Google Scholar
- Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer. DOI:http://dx.doi.org/10.1007/978-1-4471-5559-1 Google ScholarDigital Library
- 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. DOI:http://dx.doi.org/10.1109/FOCS.2012.62 Google ScholarDigital Library
- Delbert R. Fulkerson and Oliver A. Gross. 1965. Incidence matrices and interval graphs. Pacific Journal of Mathematics 15, 3, 835--855.Google ScholarCross Ref
- Tibor Gallai. 1967. Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungarica 18, 1--2, 25--66. DOI:http://dx.doi.org/10.1007/BF02020961. 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.Google ScholarCross Ref
- 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. DOI:http://dx.doi.org/10.1089/ cmb.1995.2.139Google ScholarCross Ref
- Martin C. Golumbic. 2004. Algorithmic Graph Theory and Perfect Graphs. Annals of Discrete Mathematics, Vol. 57. North-Holland Publishing, Amsterdam, The Netherlands. Google ScholarDigital Library
- György Hajós. 1957. (Problem 65) Über eine Art von Graphen. Internationale Mathematische Nachrichten 11.Google Scholar
- 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. DOI:http://dx.doi.org/10.1137/S0097539796303044 A preliminary version appeared in FOCS 1994. Google ScholarDigital Library
- 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. DOI:http://dx.doi.org/10.1145/167088.167170 Google ScholarDigital Library
- Ken-ichi Kawarabayashi. 2009. Planarity allowing few error vertices in linear time. In Proceedings of FOCS 2009. IEEE, Los Alamitos, CA, 639--648. DOI:http://dx.doi.org/10.1109/FOCS.2009.45 Google ScholarDigital Library
- Ken-ichi Kawarabayashi and Bruce A. Reed. 2010. An (almost) linear time algorithm for odd cyles transversal. In Proceedings of SODA 2010.365--378. Google ScholarDigital Library
- David George Kendall. 1969. Incidence matrices, interval graphs and seriation in archaeology. Pacific Journal of Mathematics 28, 565--570.Google ScholarCross Ref
- 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. DOI:http://dx.doi.org/10.1006/jagm.1998.0936 A preliminary version appeared in ICALP 1996. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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. DOI:http://dx.doi.org/10.1016/0022-0000(80)90060-4. Preliminary versions were independently presented in STOC 1978.Google ScholarCross Ref
- 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. DOI:http://dx.doi.org/10.1007/3-540-56939-1_60 Google ScholarDigital Library
- Dániel Marx. 2010. Chordal deletion is fixed-parameter tractable. Algorithmica 57, 4, 747--768. DOI:http://dx.doi.org/10.1007/s00453-008-9233-8 Google ScholarDigital Library
- Dániel Marx and Ildikó Schlotter. 2012. Obtaining a planar graph by vertex deletion. Algorithmica 62, 3--4, 807--822. DOI:http://dx.doi.org/10.1007/s00453-010-9484-z Google ScholarDigital Library
- 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. DOI:http://dx.doi.org/10.1007/978-3-319-03898-8_25Google Scholar
- Sheng-Lung Peng and Chi-Kang Chen. 2006. On the interval completion of chordal graphs. Discrete Applied Mathematics 154, 6, 1003--1010. DOI:http://dx.doi.org/10.1016/j.dam.2005.09.010 Google ScholarDigital Library
- Bruce A. Reed, Kaleigh Smith, and Adrian Vetta. 2004. Finding odd cycle transversals. Operations Research Letters 32, 4, 299--301. DOI:http://dx.doi.org/10.1016/j.orl.2003.10.009 Google ScholarDigital Library
- Pim Van't Hof and Yngve Villanger. 2013. Proper interval vertex deletion. Algorithmica 65, 4, 845--867. DOI:http://dx.doi.org/10.1007/s00453-012-9661-3Google ScholarDigital Library
- 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. DOI:http://dx.doi.org/10.1137/070710913. A preliminary version appeared in STOC 2007. Google ScholarDigital Library
Index Terms
- Interval Deletion Is Fixed-Parameter Tractable
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