Apakah pewarnaan vertex - dalam arti tertentu?

Kita tahu bahwa pewarna tepi grafik $G$ adalah pewarna simpul dari graph khusus, yaitu dari grafik garis $L(G)$ dari $G$ .

Apakah ada operator grafik $\Phi$ sehingga pewarnaan simpul pada grafik $G$ adalah pewarnaan tepi dari grafik $\Phi(G)$ ? Saya tertarik pada operator grafik yang dapat dibangun dalam waktu polinomial, yaitu grafik $\Phi(G)$ dapat diperoleh dari $G$ dalam waktu polinomial.

Catatan : Pertanyaan serupa dapat ditanyakan untuk set dan pertandingan yang stabil. Pencocokan dalam adalah set yang stabil di . Apakah ada operator grafik sehingga set stabil di cocok dengan ? Sejak STABIL SET adalah -Lengkap dan MATCHING milik , seperti operator grafik (jika ada) tidak dapat dibangun dalam waktu polinomial, dengan asumsi . $G$ $L(G)$ $\Psi$ $G$ $\Psi(G)$ $\mathsf{ NP}$ $\mathsf{P}$ $\Psi$ $\mathsf{NP}\not=\mathsf{P}$

EDIT: Terinspirasi oleh jawaban @ usul dan komentar @ Okamoto dan @ King, saya menemukan bentuk yang lebih lemah untuk masalah saya: Pewarnaan vertex pada grafik adalah pewarnaan tepi dari hypergraph didefinisikan sebagai berikut. Vertex set adalah himpunan simpul yang sama . Untuk setiap simpul dari , lingkungan tertutup adalah tepi dari hypergraph $G$ $\Phi(G)$ $\Phi(G)$ $G$ $v$ $G$ $N_G[v]= N_G(v) \cup\{v\}$ . Maka adalah grafik garis dari hypergraph dan oleh karena itu pewarnaan simpul dari adalah pewarnaan tepi dari . $\Phi(G)$ $G$ $\Phi(G)$ $G$ $\Phi(G)$

Sekali lagi, saya berterima kasih atas semua jawaban dan komentar yang menunjukkan bahwa, dengan atau tanpa asumsi , operator yang saya cari tidak ada. Alangkah baiknya jika saya bisa menerima semua jawaban! $\mathsf{NP}\not=\mathsf{P}$

graph-theory graph-algorithms pengguna13136
sumber

Terima kasih atas komentar baik (dan kesabaran!) Dan jawaban yang bermanfaat. Saya perlu waktu untuk membaca, berpikir dan mungkin kembali dengan mata segar.

user13136

Saya menemukan masalah yang cukup menarik yang diajukan oleh Nishizeki dan Zhou pada tahun 1998 yang entah bagaimana terkait dengan pertanyaan Anda dan komentar kedua Anda ke @TsuyoshiIto: Dapatkah masalah pewarnaan simpul "hanya" dikurangi menjadi masalah pewarnaan tepi? (...) Karena kedua masalah adalah NP-lengkap, baik dapat direduksi ke yang lain secara masuk akal melalui 3-SAT, karena teori kelengkapan NP. Demikianlah masalah yang terbuka bertanya, ... (lihat di sini )

vb le

@ vble: terima kasih! Saya akui bahwa saya ingin "terlalu banyak". Operator seperti itu akan menyelesaikan masalah Nishizeki dan Zhou.

user13136

Jawaban:

Dengan analogi dengan grafik garis , saya pikir Anda menanyakan yang berikut:

Untuk setiap graf tak berarah , tidak terdapat sebuah grafik diarahkan sehingga setiap simpul bersesuaian dengan tepi dan tepi sesuai dengan dan saham setidaknya satu titik akhir jika dan hanya jika $G = (V,E)$ $G' = (V',E')$ $v \in V$ $(v_1,v_2) \in E'$ $u \in V$ $v \in V$ ? $(u,v) \in E$

Jawabannya bisa dilihat tidak . Pertimbangkan pohon empat-simpul dengan root memiliki tiga anak . Dalam , kita harus memiliki empat sisi: . Lebih lanjut, harus demikian halnya $G$ $v$ $x,y,z$ $G'$ $(v_1,v_2),(x_1,x_2),(y_1,y_2),(z_1,z_2)$ atau adalah titik akhir dari masing-masing dari tiga sisi lainnya (yaitu, , dll). Tetapi ini berarti bahwa setidaknya dua dari tiga sisi lainnya harus memiliki titik akhir yang sama, yang melanggar persyaratan kami karena tidak ada dua dari yang berdekatan dalam grafik asli. $v_1$ $v_2$ $\left| \{v_1,v_2\} \cap \{x_1,x_2\} \right| \geq 1$ $x,y,z$

Saya pikir grafik yang sama akan memberi Anda contoh tandingan untuk pertanyaan yang cocok juga.

usul
sumber

Poin bagus! Sebenarnya saya memiliki pikiran yang sama. Tapi mungkin ada cara lain untuk mendefinisikan

? Atau bagaimana kita dapat membuktikan secara formal bahwa operator seperti itu

tidak ada?

G^{'}

$G'$

Φ

$\Phi$

user13136

@ user13136, hmm, mungkin ada beberapa cara kreatif untuk mengatasinya, tetapi Anda perlu mengulangi pertanyaan Anda (saya pikir counterexample saya adalah bukti formal untuk pertanyaan seperti yang diungkapkan dalam kotak yang dikutip). Secara intuitif, saya pikir masalahnya adalah bahwa ketika pergi ke arah garis-grafik, kita mengambil sisi (yang hanya dapat dihubungkan ke dua simpul) dan mengubahnya menjadi simpul (yang dapat dihubungkan ke sejumlah sisi) - mudah . Kebalikannya berlawanan dan lebih sulit.

usul

Just adding to usul's answer, the short answer is no, because matchings have structural properties not necessarily present in stable sets. For example, every line graph is also quasi-line and claw-free; this really limits the depth of edge colourings compared to vertex colourings.

Andrew D. King

The question contains some ambiguity in what you mean by “vertex colorings of a graph G are edge colorings of a graph H,” but it is NP-hard to construct a graph whose edge chromatic number is equal to the (vertex) chromatic number of a given graph. Formally, the following relation problem is NP-hard.

Mewakili bilangan kromatik sebagai ujung bilangan kromatik
Instance : Grafik G .
Solusi : Sebuah grafik H sehingga tepi bilangan kromatik χ '( H ) dari H adalah sama dengan jumlah kromatik χ ( G ) dari G .

Hal ini karena teorema Vizing memberikan algoritma yang efisien (sepele) yang mendekati angka kromatik tepi dalam kesalahan aditif 1 sedangkan angka kromatik sulit bahkan diperkirakan dalam berbagai pengertian. Sebagai contoh, Khanna, Linial, dan Safra [KLS00] menunjukkan bahwa masalah berikut ini adalah NP-complete (dan kemudian Guruswami dan Khanna [GK04] memberikan bukti yang jauh lebih sederhana):

3-yg berhasil versus non-4-yg berhasil
Instance : Grafik G .
Ya-janji : G adalah 3-warna.
Tanpa janji : G tidak dapat berwarna 4.

Hasil ini cukup untuk membuktikan kekerasan NP yang saya klaim di awal. Bukti dibiarkan sebagai latihan, tapi di sini ada petunjuk:

Latihan . Buktikan bahwa masalah yang disebutkan di atas "Mewakili angka kromatik sebagai angka tepi kromatik" adalah NP-hard di bawah reducibilitas fungsional waktu-polinomial dengan mengurangi "3-colorable versus non-4-colorable". Yaitu, membangun dua fungsi polinomial-waktu f (yang memetakan grafik ke grafik) dan g (yang memetakan grafik ke sedikit) sehingga

Jika G adalah grafik 3-warna dan H adalah grafik sedemikian rupa sehingga χ ( f ( G )) = χ '( H ), maka g ( H ) = 1.

Jika G adalah grafik yang tidak berwarna dan H adalah grafik sedemikian rupa sehingga χ ( f ( G )) = χ '( H ), maka g ( H ) = 0.

Referensi

[GK04] Venkatesan Guruswami dan Sanjeev Khanna. Pada kekerasan 4-warna, sebuah grafik 3-warna. Jurnal SIAM pada Matematika Diskrit , 18 (1): 30–40, 2004. DOI: 10.1137 / S0895480100376794 .

[KLS00] Sanjeev Khanna, Nathan Linial, dan Shmuel Safra. Pada kekerasan mendekati angka kromatik. Combinatorica , 20 (3): 393-415, Maret 2000. DOI: 10.1007 / s004930070013 .

Tsuyoshi Ito
sumber

Thank you for reply! I am a little bit imprecise by formulating “vertex colorings of a graph

G

$G$ are edge colorings of a graph

H

$H$ ”. What I mean is an operator

Φ

$\Phi$ like the line graph operator

L

$L$ , but from vertex colourings to edge colourings. This is somehow more than

χ (G) = χ^{'} (H)

$\chi(G) = \chi'(H)$ .

user13136

Since VERTEX COLOURING and EDGE COLOURING are both

N P

$\mathsf{NP}$ -complete, we can construct, by definition,

H

$H$ from

G

$G$ in polynomial time such that

χ (G) \leq k

$\chi(G) \le k$ iff

χ^{'} (H) \leq k^{'}

$\chi'(H) \le k'$ .But such a construction need not fulfill the property for an operator

Φ

$\Phi$ I am looking for. It only reduces vertex colourings to edge colourings.

user13136

@ user13136: Jika persyaratan yang lebih lemah tidak mungkin dipenuhi, persyaratan yang lebih kuat jelas juga tidak mungkin. Ini logika. Anda harus memahami bahwa contoh grafik planar Anda bukan contoh tandingan untuk ini. Memutuskan 3-colorability dari grafik planar yang diberikan bukan persyaratan yang lebih lemah daripada memutuskan 4-colorability dari grafik planar yang diberikan; mereka hanya persyaratan yang berbeda. Di sisi lain, saya sudah menunjukkan bahwa apa yang Anda inginkan tidak mungkin kecuali P = NP, titik. Tetapi jika Anda kesulitan memahami hal ini, saya tidak berpikir ada yang bisa saya lakukan untuk membantu Anda memahami.

Tsuyoshi Ito

Φ

$\Phi$

G = K_{1, 3}

$G=K_{1,3}$ and suppose such

Φ (G)

$\Phi(G)$ exists. Since

G

$G$ is 2-colorable,

Φ (G)

$\Phi(G)$ should be 2-edge-colorable. This means the maximum degree of

Φ (G)

$\Phi(G)$ is at most two. Since

Φ (G)

$\Phi(G)$ has four edges, we can go through all candidates for

Φ (G)

$\Phi(G)$ (seven candidates up to isomorphism), and we will find that the family of edge colorings of

Φ (G)

$\Phi(G)$ and the family of vertex colorings of

G

$G$ are different. A contradiction.

Yoshio Okamoto

@user13136: It occurred to me that you might have been confused because I wrote only a proof idea and I left out the actual proof. I revised the answer so that it would be clear that I left out the actual proof, and added some hints for proof. If this still does not work for you, then I will give up.

Tsuyoshi Ito

(This is an addition to usul's answer and YoshioOkamoto's comment, rather than an answer.) It can be seen that your operation $\Phi$ exists only for those graphs $G$ for which there is a graph $G'$ with $G = L(G')$ , i.e. $G$ is a line graph (checkable in polytime). In this case, $\Phi$ is the "inverse line graph operator" $L^{-1}$ , i.e. $\Phi(G)=G'$ , and vertex colorings of $G$ are edge colorings of $\Phi(G)$ .

In Theory
sumber