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

11 Citations (Scopus)

32 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: Elsevier licence

11 Citations
1 Conference article

Contracting chordal graphs and bipartite graphs to paths and trees
Heggernes, P., van 't Hof, P., Lévêque, B. & Paul, C., 2011, In: Electronic notes in discrete mathematics. 37, p. 87-92 6 p.
Research output: Contribution to journal › Conference article › Academic › peer-review
10 Link opens in a new tab Citations (Scopus)

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

Research output

Contracting chordal graphs and bipartite graphs to paths and trees

Cite this