Tractability of König edge deletion problems. (English) Zbl 1435.68125
Summary: A graph is said to be a König graph if the size of its maximum matching is equal to the size of its minimum vertex cover. The König Edge Deletion problem asks if in a given graph there exists a set of at most \(k\) edges whose deletion results in a König graph. While the vertex version of the problem (König Vertex Deletion) has been shown to be fixed-parameter tractable more than a decade ago, the fixed-parameter-tractability of the König Edge Deletion problem has been open since then, and has been conjectured to be W[1]-hard in several papers. In this paper, we settle the conjecture by proving it W[1]-hard. We prove that a variant of this problem, where we are given a graph \(G\) and a maximum matching \(M\) and we want a \(k\)-sized König edge deletion set that is disjoint from \(M\), is fixed-parameter-tractable.
MSC:
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Alon, Noga; Lokshtanov, Daniel; Saurabh, Saket, Fast FAST, (Proceedings of the 36th International Colloquium Automata, Languages and Programming, Part I. Proceedings of the 36th International Colloquium Automata, Languages and Programming, Part I, ICALP 2009, Rhodes, Greece, July 5-12, 2009 (2009)), 49-58 · Zbl 1248.68547 |
| [2] | Balas, Egon, Integer and Fractional Matchings, North-Holland Mathematics Studies, vol. 59, 1-13 (1981), Elsevier · Zbl 0481.05055 |
| [3] | Bock, Adrian; Chandrasekaran, Karthekeyan; Könemann, Jochen; Peis, Britta; Sanità, Laura, Finding small stabilizers for unstable graphs, Math. Program., 154, 1-2, 173-196 (2015) · Zbl 1337.05085 |
| [4] | Cai, Leizhen, Fixed-parameter tractability of graph modification problems for hereditary properties, Inf. Process. Lett., 58, 4, 171-176 (1996) · Zbl 0875.68702 |
| [5] | Cygan, Marek; Fomin, Fedor V.; Jansen, Bart M. P.; Kowalik, Lukasz; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket, Open problems for FPT school (2014) |
| [6] | Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket, Parameterized Algorithms, vol. 3 (2015), Springer · Zbl 1334.90001 |
| [7] | Deming, Robert W., Independence numbers of graphs-an extension of the König-Egerváry theorem, Discrete Math., 27, 1, 23-33 (1979) · Zbl 0404.05034 |
| [8] | Dom, Michael; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf; Truß, Anke, Fixed-parameter tractability results for feedback set problems in tournaments, J. Discret. Algorithms, 8, 1, 76-86 (2010) · Zbl 1191.68349 |
| [9] | Feng, Qilong; Tan, Guanlan; Zhu, Senmin; Fu, Bin; Wang, Jianxin, New algorithms for edge induced König-Egerváry subgraph based on Gallai-Edmonds decomposition, (29th International Symposium on Algorithms and Computation. 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan (2018)), 31:1-31:12 · Zbl 1535.05247 |
| [10] | Garey, Michael R.; Johnson, David S., Computers and Intractability, vol. 29 (2002), Freeman: Freeman New York |
| [11] | Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis, Which problems have strongly exponential complexity?, J. Comput. Syst. Sci., 63, 4, 512-530 (2001) · Zbl 1006.68052 |
| [12] | Khot, Subhash; Raman, Venkatesh, Parameterized complexity of finding subgraphs with hereditary properties, Theor. Comput. Sci., 289, 2, 997-1008 (2002) · Zbl 1061.68061 |
| [13] | Kratsch, Stefan; Pilipczuk, Marcin; Rai, Ashutosh; Raman, Venkatesh, Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs, TOCT, 7, 1, Article 4 pp. (2014), 1-18 · Zbl 1347.68171 |
| [14] | Kumar, Mithilesh; Lokshtanov, Daniel, Faster exact and parameterized algorithm for feedback vertex set in tournaments, (33rd Symposium on Theoretical Aspects of Computer Science. 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France (2016)), Article 49 pp., 1-13 · Zbl 1388.68324 |
| [15] | Lewis, John M.; Yannakakis, Mihalis, The node-deletion problem for hereditary properties is np-complete, J. Comput. Syst. Sci., 20, 2, 219-230 (1980) · Zbl 0436.68029 |
| [16] | Lokshtanov, Daniel, Wheel-free deletion is w[2]-hard, (International Workshop on Parameterized and Exact Computation (2008), Springer), 141-147 · Zbl 1142.68366 |
| [17] | Lokshtanov, Daniel; Narayanaswamy, N. S.; Raman, Venkatesh; Ramanujan, M. S.; Saurabh, Saket, Faster parameterized algorithms using linear programming, ACM Trans. Algorithms, 11, 2, Article 15 pp. (2014), 1-31 · Zbl 1398.68254 |
| [18] | Lovász, László; Plummer, Michael D., Matching Theory, vol. 367 (2009), American Mathematical Soc. · Zbl 1175.05002 |
| [19] | Mishra, Sounaka; Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath; Subramanian, C. R., The complexity of König subgraph problems and above-guarantee vertex cover, Algorithmica, 61, 4, 857-881 (2011) · Zbl 1243.05203 |
| [20] | Nemhauser, George L.; Trotter, Leslie E., Vertex packings: structural properties and algorithms, Math. Program., 8, 1, 232-248 (1975) · Zbl 0314.90059 |
| [21] | Nemhauser, George L.; Trotter, Leslie E., Properties of vertex packing and independence system polyhedra, Math. Program., 6, 1, 48-61 (1974) · Zbl 0281.90072 |
| [22] | Picard, Jean-Claude; Queyranne, Maurice, On the integer-valued variables in the linear vertex packing problem, Math. Program., 12, 1, 97-101 (1977) · Zbl 0362.90065 |
| [23] | Pilipczuk, Marcin; Pilipczuk, Michal; Wrochna, Marcin, Edge bipartization faster than \(2^k\), Algorithmica, 1-50 (2017) · Zbl 1398.68406 |
| [24] | Pulleyblank, William R., Fractional matchings and the Edmonds-Gallai theorem, Discrete Appl. Math., 16, 1, 51-58 (1987) · Zbl 0637.05019 |
| [25] | Razgon, Igor; O’Sullivan, Barry, Almost 2-SAT is fixed-parameter tractable, J. Comput. Syst. Sci., 75, 8, 435-450 (2009) · Zbl 1184.68477 |
| [26] | Stersoul, F., A characterization of the graphs in which the transversal number equals the matching number, J. Comb. Theory, Ser. B, 27, 228-229 (1979) · Zbl 0415.05032 |
| [27] | Earl Trotter, Leslie, Solution Characteristics and Algorithms for the Vertex Packing Problem (1973), PhD Thesis, Ithaca, NY, USA |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
