6
$\begingroup$

This is a problem came from social network analysis. In a vertex colored (need not be proper) graph, an edge is monochromatic, if both endpoints of the edge are colored with the same color. Given a partially colored network, my goal is to extend it to total coloring such that the number of monochromatic edges in the network is maximum.

If the network (graph) is complete graph then the problem is easy (just see which color is appearing more and assign it all uncolored vertices). Suppose if my graph is a threshold graph, then I don't have any idea how to solve it in polynomial time. Can someone help me?

Improve this question
$\endgroup$
3
  • $\begingroup$ Re "to total coloring": I think you unintentionally 'hit' an already taken technical term: you evidently do not intend to in the end have a total coloring of your graph. Again, the meaning is clear, yet it might get even clearer if you edited your question to the mathematically precise "Given a graph $G=(V,E)$, some $S\subset V$ and a function $c\colon S\to \mathcal{C}$, my goal is to extend $c$ to [...] $\endgroup$
    – Peter Heinig
    Commented Sep 20, 2017 at 10:04
  • $\begingroup$ a function $\overline{c}\colon V\to\mathcal{C}$ such that $\overline{c}$ is a maximizer of the number of monochromatic edges among all such extensions. (Note that I recommend that you replace "high" with the usual 'monochromatic'.) And is there a reason for you to expect a polynomial time algorithm for threshold graphs? (The mentioning of which currently seems surprising.) $\endgroup$
    – Peter Heinig
    Commented Sep 20, 2017 at 10:05
  • $\begingroup$ @Peter Heining Since threshold graphs have nice structure, I expect a polynomial time algorithm to this problem. Moreover, I have not seen any hard graph problem on threshold graphs. Because of these two things I believe the problem is polytime solvable. $\endgroup$
    – user1659936
    Commented Sep 20, 2017 at 10:21

1 Answer 1

Reset to default
6
+50
$\begingroup$

Update 2017.09.26: As I've just learnt from Tamas Kiraly, this notion is well-studied and has several names, such as k-way cut, k-terminal cut, multiway cut. For at least three colors, the problem becomes $NP$-complete for general graphs, see E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis: The complexity of multiterminal cuts.

Earlier stuff: For two colors this can be solved in polynomial time for any graph, as it can be converted to a MinCut problem. Just connect all red vertices into a single vertex $s$, and all blue vertices into another single vertex $t$, obtaining a multigraph (or if you prefer, a graph with edge weights). The Minimum cut in this new graph between $s$ and $t$ gives the partition that gives the coloring maximizing the number of the monochromatic edges.

Improve this answer
$\endgroup$
4
  • $\begingroup$ It is polynomially solvable on any graph if the number of colors is at most two. What happens when the number of colors is more than two? $\endgroup$
    – user1659936
    Commented Sep 23, 2017 at 11:24
  • $\begingroup$ @user1659936 I've updated my answer. $\endgroup$
    – domotorp
    Commented Sep 26, 2017 at 11:47
  • $\begingroup$ thanks for the update, but again my question is for restricted classes of graphs, specifically threshold graphs. $\endgroup$
    – user1659936
    Commented Sep 26, 2017 at 18:00
  • $\begingroup$ @user1659936 Well now that you know the nomenclature and the relevant papers, you can start looking through the literature in the hope of finding related results. $\endgroup$
    – domotorp
    Commented Sep 27, 2017 at 4:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .