Contracting chordal graphs and bipartite graphs to paths and trees

Pinar Heggernes; Pim van 't Hof; Benjamin Lévêque; Christophe Paul

doi:10.1016/j.dam.2013.02.025

Contracting chordal graphs and bipartite graphs to paths and trees

Pinar Heggernes, Pim van 't Hof, Benjamin Lévêque, Christophe Paul

Research output: Contribution to journal › Article › Academic › peer-review

9 Citations (Scopus)

29 Downloads (Pure)

Abstract

We study the following two graph modification problems: given a graph and an integer , decide whether can be transformed into a tree or into a path, respectively, using at most edge contractions. These problems, which we call Tree Contraction and Path Contraction, respectively, are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in and time, respectively. As a contrast, both problems remain NP-complete when restricted to bipartite input graphs.

Original language	English
Pages (from-to)	444-449
Number of pages	6
Journal	Discrete applied mathematics
Volume	164
Issue number	2
DOIs	https://doi.org/10.1016/j.dam.2013.02.025
Publication status	Published - 19 Feb 2014
Externally published	Yes

Access to Document

10.1016/j.dam.2013.02.025Licence: Other

1-s2.0-S0166218X13001121-mainFinal published version, 384 KBLicence: Other

Cite this

@article{06dbd915ce8c4d1cbca675d932543bf9,

title = "Contracting chordal graphs and bipartite graphs to paths and trees",

abstract = "We study the following two graph modification problems: given a graph and an integer , decide whether can be transformed into a tree or into a path, respectively, using at most edge contractions. These problems, which we call Tree Contraction and Path Contraction, respectively, are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in and time, respectively. As a contrast, both problems remain NP-complete when restricted to bipartite input graphs.",

author = "Pinar Heggernes and {van 't Hof}, Pim and Benjamin L{\'e}v{\^e}que and Christophe Paul",

year = "2014",

month = feb,

day = "19",

doi = "10.1016/j.dam.2013.02.025",

language = "English",

volume = "164",

pages = "444--449",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "2",

}

TY - JOUR

T1 - Contracting chordal graphs and bipartite graphs to paths and trees

AU - Heggernes, Pinar

AU - van 't Hof, Pim

AU - Lévêque, Benjamin

AU - Paul, Christophe

PY - 2014/2/19

Y1 - 2014/2/19

N2 - We study the following two graph modification problems: given a graph and an integer , decide whether can be transformed into a tree or into a path, respectively, using at most edge contractions. These problems, which we call Tree Contraction and Path Contraction, respectively, are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in and time, respectively. As a contrast, both problems remain NP-complete when restricted to bipartite input graphs.

AB - We study the following two graph modification problems: given a graph and an integer , decide whether can be transformed into a tree or into a path, respectively, using at most edge contractions. These problems, which we call Tree Contraction and Path Contraction, respectively, are known to be NP-complete in general. We show that on chordal graphs these problems can be solved in and time, respectively. As a contrast, both problems remain NP-complete when restricted to bipartite input graphs.

U2 - 10.1016/j.dam.2013.02.025

DO - 10.1016/j.dam.2013.02.025

M3 - Article

SN - 0166-218X

VL - 164

SP - 444

EP - 449

JO - Discrete applied mathematics

JF - Discrete applied mathematics

IS - 2

ER -

Contracting chordal graphs and bipartite graphs to paths and trees

Abstract

Access to Document

Fingerprint

Cite this