Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Improving Vertex Cov ...
Article

Improving Vertex Cover as a Graph Parameter

Robert Ganian ORCID (1) (2) (3)
(1) Vienna University of Technology
(2) Vienna University of Technology = Technische Universität Wien
(3) Vienna University of Technology = Technischen Universität Wien
Download article
Open on HAL
Imported on
June 30, 2013
Published on
September 13, 2015
Last modified on
March 31, 2025
Volume 17
vol. 17:2
Discrete Algorithms
DOI
10.46298/dmtcs.2136
License
https://about.hal.science/hal-authorisation-v1
P 26696
Indicators
1841
Views
2346
Downloads

Improving Vertex Cover as a Graph Parameter

Robert Ganian ORCID (1) (2) (3)
(1) Vienna University of Technology
(2) Vienna University of Technology = Technische Universität Wien
(3) Vienna University of Technology = Technischen Universität Wien
Abstract
Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width; however, the drawback of vertex cover is that bounding it severely restricts admissible graph classes. We introduce a generalization of vertex cover called twin-cover and show that FPT algorithms exist for a wide range of difficult problems when parameterized by twin-cover. The advantage of twin-cover over vertex cover is that it imposes a lesser restriction on the graph structure and attains low values even on dense graphs. Apart from introducing the parameter itself, this article provides a number of new FPT algorithms parameterized by twin-cover with a special emphasis on solving problems which are not in FPT even when parameterized by tree-width. It also shows that MS1 model checking can be done in elementary FPT time parameterized by twin-cover and discusses the field of kernelization.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • Vertex cover
  • Twin-cover
  • Parameterized Complexity
Cited by

Source: OpenCitations

  • Structural Parameterization of Cluster Deletion

    Algorithmica

    Authors : Giuseppe F. Italiano ORCID, Athanasios L. Konstantinidis, Charis Papadopoulos ORCID

    Journal reference : Volume 87, 2025, pp. 961-981

    DOI : 10.1007/s00453-025-01303-1

  • First Order Logic on Pathwidth Revisited Again

    Authors : Lampis

    Journal reference : Volume , 2023, pp.

    DOI : 10.4230/lipics.icalp.2023.132

  • The Parameterized Complexity of Maximum Betweenness Centrality

    Lecture notes in computer science

    Authors : Šimon Schierreich ORCID, José Gaspar Smutný ORCID

    Journal reference : Volume , 2024, pp. 221-233

    DOI : 10.1007/978-981-97-2340-9_19

  • On Structural Parameterizations of the Harmless Set Problem

    Algorithmica

    Authors : Ajinkya Gaikwad ORCID, Soumen Maity

    Journal reference : Volume 86, 2024, pp. 1475-1511

    DOI : 10.1007/s00453-023-01199-9

  • Parameterized Complexity of Coupon Coloring of Graphs

    Lecture notes in computer science

    Authors : Pradeesha Ashok ORCID, Pradyun Devarakonda, Shiven Phogat, Swaroop A. Ram Rayala, J. A. Sherin

    Journal reference : Volume , 2025, pp. 25-37

    DOI : 10.1007/978-3-031-83438-7_3

  • Parameterized Spanning Tree Congestion

    DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Authors : Lampis, Mitsou, Nemery, Otachi, Vasilakis, Vaz

    Journal reference : Volume , 2025, pp.

    DOI : 10.4230/lipics.mfcs.2025.65

  • Finding a Maximum Common (Induced) Subgraph: Structural Parameters Revisited

    Lecture notes in computer science

    Authors : Tesshu Hanaka ORCID, Yuto Okada ORCID, Yota Otachi ORCID, Lena Volk

    Journal reference : Volume , 2026, pp. 172-186

    DOI : 10.1007/978-981-95-7127-7_12

  • Grouped domination parameterized by vertex cover, twin cover, and beyond

    Theoretical Computer Science

    Authors : Tesshu Hanaka ORCID, Hirotaka Ono ORCID, Yota Otachi ORCID, Saeki Uda

    Journal reference : Volume 996, 2024, pp. 114507

    DOI : 10.1016/j.tcs.2024.114507

  • Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts

    Lecture notes in computer science

    Authors : Cornelius Brand ORCID, Esra Ceylan ORCID, Robert Ganian ORCID, Christian Hatschka ORCID, Viktoriia Korchemna ORCID

    Journal reference : Volume , 2022, pp. 98-113

    DOI : 10.1007/978-3-031-15914-5_8

  • Dominator Coloring and CD Coloring in Almost Cluster Graphs

    Lecture notes in computer science

    Authors : Aritra Banik ORCID, Prahlad Narasimhan Kasthurirangan ORCID, Venkatesh Raman ORCID

    Journal reference : Volume , 2023, pp. 106-119

    DOI : 10.1007/978-3-031-38906-1_8

  • Bandwidth Parameterized by Cluster Vertex Deletion Number

    Algorithmica

    Authors : Tatsuya Gima ORCID, Eun Jung Kim ORCID, Noleen Köhler ORCID, Nikolaos Melissinos ORCID, Manolis Vasilakis ORCID

    Journal reference : Volume 87, 2025, pp. 1146-1177

    DOI : 10.1007/s00453-025-01315-x

  • Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials

    Algorithmica

    Authors : Bart M. P. Jansen ORCID, Astrid Pieterse ORCID

    Journal reference : Volume 81, 2019, pp. 3865-3889

    DOI : 10.1007/s00453-019-00578-5

  • The parameterized complexity of Strong Conflict-Free Vertex-Connection Colorability

    Discrete Applied Mathematics

    Authors : Carl Feghali ORCID, Hoang-Oanh Le, Van Bang Le ORCID

    Journal reference : Volume 383, 2025, pp. 85-93

    DOI : 10.1016/j.dam.2025.12.025

  • Coloring a Dominating Set Without Conflicts: q-Subset Square Coloring

    arXiv (Cornell University)

    Authors : V. P. Abidha, Pradeesha Ashok ORCID, Avi Tomar, Dolly Yadav ORCID

    Journal reference : Volume , 2022, pp. 17-34

    DOI : 10.1007/978-3-031-09574-0_2

  • Computing the Largest Bond and the Maximum Connected Cut of a Graph

    arXiv (Cornell University)

    Authors : Gabriel L. Duarte, Hiroshi Eto ORCID, Tesshu Hanaka ORCID, Yasuaki Kobayashi ORCID, Yusuke Kobayashi ORCID, Daniel Lokshtanov ORCID, Lehilton L. C. Pedrosa ORCID, Rafael C. S. Schouery ORCID, Uéverton S. Souza ORCID

    Journal reference : Volume 83, 2021, pp. 1421-1458

    DOI : 10.1007/s00453-020-00789-1

  • Fine-grained Meta-Theorems for Vertex Integrity

    Logical Methods in Computer Science

    Authors : Michael Lampis ORCID, Valia Mitsou

    Journal reference : Volume Volume 20, Issue 4, 2024, pp.

    DOI : 10.46298/lmcs-20(4:18)2024

  • Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond

    Lecture notes in computer science

    Authors : Tesshu Hanaka ORCID, Hirotaka Ono ORCID, Yota Otachi ORCID, Saeki Uda

    Journal reference : Volume , 2023, pp. 263-277

    DOI : 10.1007/978-3-031-30448-4_19

  • Computing L(p,1)-Labeling with Combined Parameters

    Journal of Graph Algorithms and Applications

    Authors : Tesshu Hanaka ORCID, Kazuma Kawai, Hirotaka Ono ORCID

    Journal reference : Volume 26, 2022, pp. 241-255

    DOI : 10.7155/jgaa.00592

  • Structural Parameterizations for Equitable Coloring: Complexity, FPT Algorithms, and Kernelization

    Algorithmica

    Authors : Guilherme C. M. Gomes ORCID, Matheus R. Guedes ORCID, Vinicius F. dos Santos ORCID

    Journal reference : Volume 85, 2022, pp. 1912-1947

    DOI : 10.1007/s00453-022-01085-w
Preview
Loading PDF preview...