On the complete width and edge clique cover problems

Le Van Bang () and Sheng-Lung Peng ()
Additional contact information
Le Van Bang: Universität Rostock
Sheng-Lung Peng: National Dong Hwa University

Journal of Combinatorial Optimization, 2018, vol. 36, issue 2, No 12, 532-548

Abstract: Abstract A complete graph is the graph in which every two vertices are adjacent. For a graph $$G=(V,E)$$ G = ( V , E ) , the complete width of G is the minimum k such that there exist k independent sets $$\mathtt {N}_i\subseteq V$$ N i ⊆ V , $$1\le i\le k$$ 1 ≤ i ≤ k , such that the graph $$G'$$ G ′ obtained from G by adding some new edges between certain vertices inside the sets $$\mathtt {N}_i$$ N i , $$1\le i\le k$$ 1 ≤ i ≤ k , is a complete graph. The complete width problem is to decide whether the complete width of a given graph is at most k or not. In this paper we study the complete width problem. We show that the complete width problem is NP-complete on $$3K_2$$ 3 K 2 -free bipartite graphs and polynomially solvable on $$2K_2$$ 2 K 2 -free bipartite graphs and on $$(2K_2,C_4)$$ ( 2 K 2 , C 4 ) -free graphs. As a by-product, we obtain the following new results: the edge clique cover problem is NP-complete on $$\overline{3K_2}$$ 3 K 2 ¯ -free co-bipartite graphs and polynomially solvable on $$C_4$$ C 4 -free co-bipartite graphs and on $$(2K_2, C_4)$$ ( 2 K 2 , C 4 ) -free graphs. We also give a characterization for k-probe complete graphs which implies that the complete width problem admits a kernel of at most $$2^k$$ 2 k vertices. This provides another proof for the known fact that the edge clique cover problem admits a kernel of at most $$2^k$$ 2 k vertices. Finally we determine all graphs of small complete width $$k\le 3$$ k ≤ 3 .

Keywords: Probe graphs; Complete width; Edge clique cover (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0106-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:2:d:10.1007_s10878-016-0106-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0106-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().