Advertisement

IWOCA 2011: Combinatorial Algorithms pp 135-143

# Complexity of Cycle Transverse Matching Problems

• Ross Churchley
• Jing Huang
• Xuding Zhu
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 7056)

## Abstract

The stable transversal problem for a fixed graph H asks whether a graph contains a stable set that meets every induced copy of H in the graph. Stable transversal problems generalize several vertex partition problems and have been studied for various classes of graphs. Following a result of Farrugia, the stable transversal problem for each C with ℓ ≥ 3 is NP-complete. In this paper, we study an ‘edge version’ of these problems. Specifically, we investigate the problem of determining whether a graph contains a matching that meets every copy of H. We show that the problem for C 3 is polynomial and for each C with ℓ ≥ 4 is NP-complete. Our results imply that the stable transversal problem for each C with ℓ ≥ 4 remains NP-complete when it is restricted to line graphs. We show by contrast that the stable transversal problem for C 3, when restricted to line graphs, is polynomial.

## Keywords

Stable transversal problem transverse matching problem algorithm complexity

## Preview

Unable to display preview. Download preview PDF.

## References

1. 1.
Brandstädt, A.: Partitions of graphs into one or two independent sets and cliques. Discrete Math. 152, 47–54 (1986)
2. 2.
Edmonds, J.: Paths, trees, and flowers. Canad. J. Math. 17, 449–467 (1965)
3. 3.
Farrugia, A.: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Combin. 11 (2004)Google Scholar
4. 4.
Foldes, S., Hammer, P.L.: Split graphs. In: Proc. 8th South-Eastern Conf. on Combinatorics, Graph Theory and Computing, pp. 311–315 (1977)Google Scholar
5. 5.
Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Company, San Francisco (1979)
6. 6.
Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5, 704–714 (1976)
7. 7.
Hoáng, C.T., Le, V.C.: On P 4-transversals of perfect graphs. Discrete Math. 216, 195–210 (2000)
8. 8.
Micali, S., Vazirani, V.: An $$O(\sqrt{|V|}\cdot|E|)$$ algorithm for finding maximum matching in general graphs. In: Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17–27 (1980)Google Scholar
9. 9.
Stacho, J.: On P 4-transversals of chordal graphs. Discrete Math. 308, 5548–5554 (2008)

## Copyright information

© Springer-Verlag Berlin Heidelberg 2011

## Authors and Affiliations

• Ross Churchley
• 1
• Jing Huang
• 1
• Xuding Zhu
• 2
1. 1.Department of Mathematics and StatisticsUniversity of VictoriaVictoriaCanada
2. 2.Department of mathematicsZhejiang Normal UniversityJinhuaPeople’s Republic of China

## Personalised recommendations

### Citepaper
{"ft_lang_label":"__label__en","ft_lang_prob":0.7378806,"math_prob":0.6391513,"size":2456,"snap":"2019-35-2019-39","text_gpt3_token_len":682,"char_repetition_ratio":0.1411093,"word_repetition_ratio":0.06896552,"special_character_ratio":0.26099348,"punctuation_ratio":0.23320158,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.958348,"pos_list":[0,1,2],"im_url_duplicate_count":[null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-08-23T11:47:15Z\",\"WARC-Record-ID\":\"<urn:uuid:dc4172d7-6e21-4197-a429-228b6de5abe4>\",\"Content-Length\":\"75087\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:dbd761df-01a2-4b24-900f-39c8f3791f89>\",\"WARC-Concurrent-To\":\"<urn:uuid:761903e8-87a9-4018-8eef-f438db7d65e1>\",\"WARC-IP-Address\":\"151.101.200.95\",\"WARC-Target-URI\":\"https://rd.springer.com/chapter/10.1007/978-3-642-25011-8_11\",\"WARC-Payload-Digest\":\"sha1:KXQPSAEN3BUS7RSIIJ5ILJZWGI6QPVKS\",\"WARC-Block-Digest\":\"sha1:IBB6FEO2IES65SYJ5DEVRANX5WC5MZYS\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-35/CC-MAIN-2019-35_segments_1566027318375.80_warc_CC-MAIN-20190823104239-20190823130239-00159.warc.gz\"}"}