Parameter: distance to outerplanar

Definition:

The distance to outerplanar of a graph $G = (V,E)$ is the minumum size of a vertex subset $X \subseteq V,ドル such that $G[V \backslash X]$ is a outerplanar graph.

Relations

Minimal/maximal is with respect to the contents of ISGCI. Only references for direct bounds are given. Where no reference is given, check equivalent parameters.

Minimal upper bounds for this parameter

This parameter is a minimal upper bound for

Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current parameter.

3-Colourability
[?]
Input: A graph G in this class.
Output: True iff each vertex of G can be assigned one colour out of 3 such that whenever two vertices are adjacent, they have different colours.
FPT
FPT from FPT-Linear on cliquewidth
FPT from FPT-Linear on treewidth
Clique
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise adjacent vertices, with |S| >= k.
FPT
FPT on cliquewidth
XP on maximum clique [by definition]
Clique cover
[?]
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into k sets Si, such that whenever two vertices are in the same set Si, they are adjacent.
XP
XP on cliquewidth
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)

Colourability
[?]
Input: A graph G in this class and an integer k.
Output: True iff each vertex of G can be assigned one colour out of k such that whenever two vertices are adjacent, they have different colours.
FPT
FPT on cliquewidth
Domination
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every vertex in G is either in S or adjacent to a vertex in S.
FPT
FPT from FPT-Linear on cliquewidth
FPT from FPT-Linear on treewidth
FPT on booleanwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

FPT on branchwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Feedback vertex set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of vertices, with |S| <= k, such that every cycle in G contains a vertex from S.
FPT
FPT on cliquewidth
FPT on treewidth
[1582]
B. Courcelle, S. Oum
Vertex-minors, monadic second-order logic and a conjecture by Seese
J. Comb. Theory (B) 97 91-126 (2007)

Graph isomorphism
[?]
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.
FPT
FPT on treewidth
[1737]
D. Lokshktanov, M. Pilipczuk, M. Pilipczuk, S. Saurabh
Fixed-Parameter-Tractable canonization and isomorphism test for graphs of bounded treewidth
55th IEEE Annual Symposium on Foundations of Computer Science FOCS-2014 186-195 (2014)

XP on rankwidth
[1763]
M. Grohe, P. Schweitzer
Isomorphism Testing for Graphs of Bounded Rank Width
Proc. of 55th Annual IEEE Symposium on Foundations of Computer Science FOCS (2015)

XP on treewidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Hamiltonian cycle
[?]
Input: A graph G in this class.
Output: True iff G has a simple cycle that goes through every vertex of the graph.
FPT
FPT from FPT-Linear on treewidth
XP on cliquewidth
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)
[1715]
R. Ganian, P. Hlineny, J. Obdrzalek
Clique-width: When hard does not mean impossible
Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl 404-415 (2011)

Hamiltonian path
[?]
Input: A graph G in this class.
Output: True iff G has a simple path that goes through every vertex of the graph.
FPT
FPT on treewidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

XP on cliquewidth
[1714]
W. Espelage, F. Gurski, E. Wanke
How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time
Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001)
[1715]
R. Ganian, P. Hlineny, J. Obdrzalek
Clique-width: When hard does not mean impossible
Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl 404-415 (2011)

XP on rankwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Independent set
[?]
Input: A graph G in this class and an integer k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that |S| >= k.
FPT
FPT on cliquewidth
[1716]
F. Gurski
A comparison of two approaches for polynomial time algorithms computing basic graph parameters
Manuscript 2008

Maximum cut
[?]
(decision variant)
Input: A graph G in this class and an integer k.
Output: True iff the vertices of G can be partitioned into two sets A,B such that there are at least k edges in G with one endpoint in A and the other endpoint in B.
FPT
FPT from FPT-Linear on treewidth
XP on cliquewidth
[1735]
E. Wanke
k-NLC graphs and polynomial algorithsm
Discrete Appl. Math. 54 No.2 251-266 (1994)

Monopolarity
[?]
Input: A graph G in this class.
Output: True iff G is monopolar.
Unknown to ISGCI
Polarity
[?]
Input: A graph G in this class.
Output: True iff G is polar.
XP
XP on cliquewidth
[1764]
V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

XP on treewidth
[1764]
V.B. Le, R. Nevries
Complexity and algorithms for recognizing polar and monopolar graphs
Theoretical Computer Science 528 1-11 (2014)

Weighted clique
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
FPT
FPT from FPT-Linear on treewidth
FPT on cliquewidth
FPT on degeneracy
[1849]
(no preview available)

XP on maximum clique [by definition]
Weighted feedback vertex set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of vertices, such that the sum of the weights of the vertices in S is at most k and every cycle in G contains a vertex from S.
FPT
FPT from FPT-Linear on cliquewidth
FPT on rankwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

FPT on treewidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Weighted independent dominating set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, with the sum of the weights of the vertices in S at most k, such that every vertex in G is either in S or adjacent to a vertex in S.
FPT
FPT from FPT-Linear on cliquewidth
Weighted independent set
[?]
Input: A graph G in this class with weight function on the vertices and a real k.
Output: True iff G contains a set S of pairwise non-adjacent vertices, such that the sum of the weights of the vertices in S is at least k.
FPT
FPT from FPT-Linear on cliquewidth
FPT from FPT-Linear on treewidth
FPT on booleanwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

FPT on branchwidth
[1701]
M. Vatshelle
New Width Parameters of Graphs
PhD Thesis, Dept. of Informatics, University of Bergen 2012

Graph classes

Bounded

back to top

Unbounded

back to top

Open

back to top

Unknown to ISGCI

back to top

AltStyle によって変換されたページ (->オリジナル) /