Top

Journal of Combinatorial Optimization

Published in:

17-05-2021

Complete-Subgraph-Transversal-Sets problem on bounded treewidth graphs

Authors: Ke Liu, Mei Lu

Published in: Journal of Combinatorial Optimization | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Let \(G=(V,E)\) be a graph. A complete subgraph of G is a subgraph of pairwise adjacent vertices of V of size at least 2. Let \(\Phi _C(G)\) be the set of all complete subgraphs of G and \(\Phi \subseteq {\Phi }_C(G)\). In this paper, we consider the Complete-Subgraph-Transversal-Set on \(\Phi \) problem and the L-Max Complete-Subgraph-Transversal-Set on \(\Phi \) problem. We give polynomial time algorithms to these two problems on graphs of bounded treewidth. At last, we show the connections between these two problems with some other NP-complete problems, for example Clique-Transversal-Set problem on graphs and Vertex-Cover problem on hypergraphs.

previous article A continuous generalization of domination-like invariants

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Alber J, Bodlaender HL, Fernau H, Kloks T, Niedermeier R (2002) Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33:461–493MathSciNetCrossRef

Arnborg S, Corneil DG, Proskurowski A (1987) Complexity of finding embeddings in a \(k\)-tree. SIAM J Alg Discrete Methods 8:277–284MathSciNetCrossRef

Balachandran V, Nagavamsi P, Rangan CP (1996) Clique transversal and clique independence on comparability graphs. Inf Process Lett 58:181–184MathSciNetCrossRef

Bertelé U, Brioschi F (1972) Nonserial dynamic programming. Academic Press, New YorkMATH

Bodlaender HL (1996) A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J Comput 25(6):1305–1317MathSciNetCrossRef

Bonomo F, Durn G, Lin MC, Szwarcfiter JL (2005) On balanced graphs. Math Program Ser B 105:233–250MathSciNetCrossRef

Chang GJ, Farber M, Tuza Zs (1993) Algorithmic aspects of neighbourhood numbers. SIAM J Discrete Math 6:24–29MathSciNetCrossRef

Chang MS, Chen YH, Chang GJ, Yan JH (1996) Algorithmic aspects of the generalized clique-transversal problem on chordal graphs. Discrete Appl Math 66:189–203MathSciNetCrossRef

Durán G, Lin MC, Szwarcfiter JL (2002) On clique-transversals and clique-independent sets. Ann Oper Res 116:71–77MathSciNetCrossRef

Erdős P, Gallai T, Tuza Z (1992) Covering the cliques of graph with vertices. Discrete Math 108:279–289MathSciNetCrossRef

Grohe M, Marx D (2009) On tree width, bramble size, and expansion. J Combin Theory Ser B 99(1):218–228MathSciNetCrossRef

Guruswami V, Rangan CP (2000) Algorithmic aspects of clique-transversal and clique-independent sets. Discrete Appl Math 100:183–202MathSciNetCrossRef

Halin R (1976) \(S\)-functions for graph. J Geom 8:171–186MathSciNetCrossRef

Hochbaum DS (1997) Approximation algorithms for NP-hard problems. PWS Publishing Company, BostonMATH

Korach E, Solel N (1993) Tree-width, path-width, and cutwidth. Discrete Appl Math 43(1):97–101MathSciNetCrossRef

Lee CM, Chang MS (2006) Distance-hereditary graphs are clique-perfect. Discrete Appl Math 154:525–536MathSciNetCrossRef

Liang ZS, Shan EF (2011) Approximation algorithms for clique-transversals and clique-independent sets in cubic graphs. Inf Process Lett 111:1104–1107MathSciNetCrossRef

Niedermeier R (2006) Invitation to fixed-parameter algorithms. Oxford University Press, OxfordCrossRef

Okun M (2005) On approximation of the vertex cover problem in hypergraphs. Discrete Optim 2:101–111MathSciNetCrossRef

Paschos VT (1997) A survey of approximately optimal solutions to some covering and packing problems. ACM Comput Surv 29(2):171–209CrossRef

Robertson N, Seymour PD (1984) Graph minors III: planar tree-width. J Comb Theory Ser B 36(1):49–64MathSciNetCrossRef

Tuza Zs (1990) Covering all cliques of a graph. Discrete Math 86(13):117–126MathSciNetCrossRef

Vazirani VV (2001) Approximation algorithms. Springer, BerlinMATH

Title: Complete-Subgraph-Transversal-Sets problem on bounded treewidth graphs
Authors: Ke Liu
Mei Lu
Publication date: 17-05-2021
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 4/2021
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-021-00703-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 4/2021

Capacitated inverse optimal value problem on minimum spanning tree under bottleneck Hamming distance

An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties

The m-Steiner Traveling Salesman Problem with online edge blockages

A continuous generalization of domination-like invariants

A metaheuristic for the delivery man problem with time windows

Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty

Premium Partner