Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Split Contraction

Split Contraction The edit operation that contracts edges, which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of Parameterized Complexity. In this article, we examine an important family of graphs, namely, the family of split graphs, which in the context of edge contractions is proven to be significantly less obedient than one might expect. Formally, given a graph G and an integer k, SPLIT CONTRACTION asks whether there exists X E(G) such that G/X is a split graph and |X| k. Here, G/X is the graph obtained from G by contracting edges in X. Guo and Cai [Theoretical Computer Science, 2015] claimed that SPLIT CONTRACTION is fixed-parameter tractable. However, our findings are different. We show that SPLIT CONTRACTION, despite its deceptive simplicity, is W[1]-hard. Our main result establishes the following conditional lower bound: Under the Exponential Time Hypothesis, SPLIT CONTRACTION cannot be solved in time 2o(2) nO(1), where is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the first tight lower bound of the form 2o(2) nO(1) for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Computation Theory (TOCT) Association for Computing Machinery

Split Contraction

Download PDF
22 pages

Loading next page...
 
/lp/association-for-computing-machinery/split-contraction-mFzl90oUer
Publisher
Association for Computing Machinery
Copyright
Copyright © 2019 ACM
ISSN
1942-3454
eISSN
1942-3462
DOI
10.1145/3319909
Publisher site
See Article on Publisher Site

Abstract

The edit operation that contracts edges, which is a fundamental operation in the theory of graph minors, has recently gained substantial scientific attention from the viewpoint of Parameterized Complexity. In this article, we examine an important family of graphs, namely, the family of split graphs, which in the context of edge contractions is proven to be significantly less obedient than one might expect. Formally, given a graph G and an integer k, SPLIT CONTRACTION asks whether there exists X E(G) such that G/X is a split graph and |X| k. Here, G/X is the graph obtained from G by contracting edges in X. Guo and Cai [Theoretical Computer Science, 2015] claimed that SPLIT CONTRACTION is fixed-parameter tractable. However, our findings are different. We show that SPLIT CONTRACTION, despite its deceptive simplicity, is W[1]-hard. Our main result establishes the following conditional lower bound: Under the Exponential Time Hypothesis, SPLIT CONTRACTION cannot be solved in time 2o(2) nO(1), where is the vertex cover number of the input graph. We also verify that this lower bound is essentially tight. To the best of our knowledge, this is the first tight lower bound of the form 2o(2) nO(1) for problems parameterized by the vertex cover number of the input graph. In particular, our approach to obtain this lower bound borrows the notion of harmonious coloring from Graph Theory, and might be of independent interest.

Journal

ACM Transactions on Computation Theory (TOCT) – Association for Computing Machinery

Published: May 31, 2019

Keywords: Split contraction

References

  • Edge-contraction problems
    Asano, Takao; Hirata, Tomio
  • Lower bounds for the parameterized complexity of minimum fill-in and other completion problems
    Bliznets, Ivan; Cygan, Marek; Komosa, Pawel; Mach, Lukás; Pilipczuk, Michal
  • A subexponential parameterized algorithm for proper interval completion
    Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michal
  • Subexponential parameterized algorithm for interval completion
    Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michal
  • Fixed-parameter tractability of graph modification problems for hereditary properties
    Cai, Leizhen
  • Contracting few edges to remove forbidden induced subgraphs
    Cai, Leizhen; Guo, Chengwei
  • Linear recognition of almost interval graphs
    Cao, Yixin
  • Unit interval editing is fixed-parameter tractable
    Cao, Yixin
  • Interval deletion is fixed-parameter tractable
    Cao, Yixin; Marx, Dániel
  • Chordal editing is fixed-parameter tractable
    Cao, Yixin; Marx, Dániel
  • Improved upper bounds for vertex cover
    Chen, Jianer; Kanj, Iyad A; Xia, Ge
  • Tight lower bounds on graph embedding problems
    Cygan, Marek; Fomin, Fedor V.; Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan; Pachocki, Jakub; Socala, Arkadiusz
  • Parameterized Algorithms
    Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket
  • Known algorithms for edge clique cover are probably optimal
    Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michal
  • Graph Theory, 4th ed
    Diestel, Reinhard
  • Fixed-parameter tractability and completeness II: On completeness for W{1}
    Downey, Rodney G.; Fellows, Michael R.
  • Fundamentals of Parameterized Complexity
    Downey, Rod G.; Fellows, Michael R.
  • On the threshold of intractability
    Drange, Pål Grønås; Dregi, Markus Sortland; Lokshtanov, Daniel; Sullivan, Blair D.
  • Exploring the subexponential complexity of completion problems
    Drange, Pål Grønås; Fomin, Fedor V.; Pilipczuk, Michal; Villanger, Yngve
  • A polynomial kernel for trivially perfect editing
    Drange, Pål Grønås; Pilipczuk, Michal
  • The harmonious chromatic number and the achromatic number
    Edwards, Keith
  • On the parameterized complexity of multiple-interval graph problems
    Fellows, Michael R.; Hermelin, Danny; Rosamond, Frances A.; Vialette, Stéphane
  • Parameterized Complexity Theory
    Flum, Jörg; Grohe, Martin
  • Tight bounds for parameterized complexity of cluster editing with a small number of clusters
    Fomin, Fedor V.; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michał; Villanger, Yngve
  • Subexponential parameterized algorithm for minimum fill-in
    Fomin, Fedor V.; Villanger, Yngve
  • Faster parameterized algorithms for deletion to split graphs
    Ghosh, Esha; Kolay, Sudeshna; Kumar, Mrinal; Misra, Pranabendu; Panolan, Fahad; Rai, Ashutosh; Ramanujan, M. S.
  • Obtaining planarity by contracting few edges
    Golovach, Petr A.; van ’t Hof, Pim; Paulusma, Daniel
  • Algorithmic Graph Theory and Perfect Graphs
    Golumbic, Martin Charles
  • A faster FPT algorithm for bipartite contraction
    Guillemot, Sylvain; Marx, Dániel
  • Obtaining split graphs by edge contraction
    Guo, Chengwei; Cai, Leizhen
  • Contracting graphs to paths and trees
    Heggernes, Pinar; van ’t Hof, Pim; Lévêque, Benjamin; Lokshtanov, Daniel; Paul, Christophe
  • Obtaining a bipartite graph by contracting few edges
    Heggernes, Pinar; van ’t Hof, Pim; Lokshtanov, Daniel; Paul, Christophe
  • Which problems have strongly exponential complexity?J
    Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis
  • Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs
    Kaplan, Haim; Shamir, Ron; Tarjan, Robert Endre
  • Tight running time lower bounds for vertex deletion problems
    Komusiewicz, Christian
  • An upper bound for the harmonious chromatic number
    Lee, Sin-Min; Mitchem, John
  • Slightly superexponential parameterized problems
    Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket
  • On the hardness of eliminating small induced subgraphs by contracting edges
    Lokshtanov, Daniel; Misra, Neeldhara; Saurabh, Saket
  • Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth
    Marx, Dániel; Mitsou, Valia
  • Upper bounds for harmonious coloring
    McDiarmid, Colin; Xinhua, Luo
  • Invitation to Fixed-parameter Algorithms
    Niedermeier, Rolf
  • Depth-first search and the vertex cover problem
    Savage, Carla D.
  • On the removal of forbidden graphs by edge-deletion or by edge-contraction
    Watanabe, Toshimasa; Ae, Tadashi; Nakamura, Akira
  • On the NP-hardness of edge-deletion and-contraction problems
    Watanabe, Toshimasa; Ae, Tadashi; Nakamura, Akira